REAL UNDERSTANDING OF LPN-PROBLEM-BASED LIGHTWEIGHT AUTHENTICATION PROTOCOLS
A family of lightweight authentication protocols, HB-family, has been proposed for low-computation-load-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.
rfid np-completeness the lpn problem wireless communications