REAL UNDERSTANDING OF LPN-PROBLEM-BASED LIGHTWEIGHT AUTHENTICATION PROTOCOLS
Keywords:RFID, the LPN problem, wireless communications, NP-completeness.
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.
Copyright terms are indicated in the Republic of Lithuania Law on Copyright and Related Rights, Articles 4-37.