A Fully-Secure RFID Authentication Protocol from Exact LPN Assumption

In the recent years, several light-weight cryptographic solutions have been proposed for RFID system. HB-family is one of promising protocol series, based on the hardness of the Learning Parity with Noise (LPN) problem. Most protocols in HB-family are not suited for mobile/wireless reader applications due to secure channel assumptions. In this paper, we present a fully secure collaborative mutual authentication protocol for an RFID system where both channels tag-reader and reader-server are considered to be insecure. More precisely, we introduce a new variant of an HB-like protocol where the complete RFID system is authenticated under LPN-based commitment scheme by taking advantages of properties of perfect computational hiding commitment scheme, pseudo inverse matrix, and randomized Hill cipher. In addition, through detailed security and privacy analysis, we show that our scheme achieves required security and privacy properties, under not the random oracle model, but the standard model.