An improved LPN algorithm. (English) Zbl 1152.94434

Levieil, Éric; Fouque, Pierre-Alain

De Prisco, Roberto (ed.) et al., Security and cryptography for networks. 5th international conference, SCN 2006, Maiori, Italy, September 6–8, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-38080-1/pbk). Lecture Notes in Computer Science 4116, 348-359 (2006).

Summary: 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 \(2^{52}\).
For the entire collection see [Zbl 1146.68007].

MSC:

94A60	Cryptography
94A62	Authentication, digital signatures and secret sharing