An Improved LPN Algorithm

Abstract : HB+ is a shared-key authentication protocol, proposed by Juels and Weis at Crypto 2005, using prior work of Hopper and Blum. Its very low computational cost makes it attractive for low-cost devices such as radio-frequency identification(RFID) tags. Juels and Weis gave a security proof, relying on the hardness of the “learning parity with noise” (LPN) problem. Here, we improve the previous best known algorithm proposed by Blum, Kalai, and Wasserman for solving the LPN problem. This new algorithm yields an attack for HB+ in the detection-based model with work factor 252.
Type de document :
Communication dans un congrès
Roberto De Prisco and Moti Yung. Security and Cryptography for Networks, 5th International Conference, SCN 2006, 2006, Maiori, Italy. Springer, 4116, pp.348-359, 2006, Lecture Notes in Computer Science. 〈10.1007/11832072_24〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00563959
Contributeur : Pierre-Alain Fouque <>
Soumis le : lundi 7 février 2011 - 16:28:56
Dernière modification le : jeudi 11 janvier 2018 - 06:19:17

Identifiants

Collections

PSL

Citation

Eric Levieil, Pierre-Alain Fouque. An Improved LPN Algorithm. Roberto De Prisco and Moti Yung. Security and Cryptography for Networks, 5th International Conference, SCN 2006, 2006, Maiori, Italy. Springer, 4116, pp.348-359, 2006, Lecture Notes in Computer Science. 〈10.1007/11832072_24〉. 〈inria-00563959〉

Partager

Métriques

Consultations de la notice

68