REAL UNDERSTANDING OF LPN-PROBLEM-BASED LIGHTWEIGHT AUTHENTICATION PROTOCOLS

Abstract

A family of lightweight authentication protocols, HB-family, has been proposed for low-computationload- required applications such as radio frequency identification (RFID). Security of this family is based on the learning parity with noise (LPN) problem which has been proven to be an NP-complete problem. But, we find that security of these LPN-problem-based protocols is doubted. We will demonstrate how to cheat the verifier without solving the secret keys with high probability.