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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Berlekamp, E.R., McEliece, R.J., Tilborg, V.: On the Inherent Intractability of Certain Coding Problem. IEEE Transactions on Information Theory 24, 384–386 (1978)
Blum, A., Furst, M., Kearns, M., Lipton, R.J.: Cryptographic Primitives Based on Hard Learning Problems. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 278–291. Springer, Heidelberg (1994)
Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant Learning, the Parity Problem, and the Statistical Query Problem. Journal of the ACM 50(4), 506–519 (2003)
Bringer, J., Chabanne, H., Dottax, E.: HB++: A Lightweight Authentication Protocol Secure againt Some Attacks. In: IEEE International Conference on Pervasive Services, Workshop on Security, Privacy and Trust in Pervasive and Ubiquitous Computing, SecPerU (2006), Available at: http://eprint.iacr.org/2005/440
Gilbert, H., Robshaw, M., Sibert, H.: An Active Attack Against HB+ - A Provably Secure Lightweight Authentication Protocol, Available at: http://eprint.iacr.org/2005/237
Goldreich, O., Levin, L.: A Hard Predicate for all one-way functions. In: STOC 1989, pp. 25–32. ACM, New York (1998)
Hastad, J.: Some Optimal Inapproximability Results. In: STOC 1997, pp. 1–10. ACM, New York (1997)
Hopper, N.J., Blum, M.: Secure Human Identification Protocols. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 52–66. Springer, Heidelberg (2001)
Juels, A., Weis, S.A.: Authenticating Pervasive Devices with Human Protocols. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 293–308. Springer, Heidelberg (2005), Updated version available at: http://www.rsasecurity.com/rsalabs/staff/bios/ajuels/publications/pdfs/lpn.pdf
Katz, J., Shin, J.S.: Parallel and Concurrent Security of the HB and HB + Protocols. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 73–87. Springer, Heidelberg (2006)
Kearns, M.: Efficient Noise-Tolerant Learning from Statistical Queries. J. ACM 45(6), 983–1006 (1998)
Mitzenmacher, M., Upfal, E.: Probability and computing. Cambridge University Press, Cambridge (2005)
Regev, O.: On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. In: STOC 2005, pp. 84–93. ACM, New York (2005)
Wagner, D.: A Generalized Birthday Problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288–303. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Levieil, É., Fouque, PA. (2006). An Improved LPN Algorithm. In: De Prisco, R., Yung, M. (eds) Security and Cryptography for Networks. SCN 2006. Lecture Notes in Computer Science, vol 4116. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11832072_24
Download citation
DOI: https://doi.org/10.1007/11832072_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-38080-1
Online ISBN: 978-3-540-38081-8
eBook Packages: Computer ScienceComputer Science (R0)