Abstract
Hopper and Blum (Asiacrypt 2001) and Juels and Weis (Crypto 2005) recently proposed two shared-key authentication protocols—HB and HB+, respectively—whose extremely low computational cost makes them attractive for low-cost devices such as radio-frequency identification (RFID) tags. The security of these protocols is based on the conjectured hardness of the “learning parity with noise” (LPN) problem, which is equivalent to the problem of decoding random binary linear codes. The HB protocol is proven secure against a passive (eavesdropping) adversary, while the HB+ protocol is proven secure against active attacks.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Bellare, R. Impagliazzo, M. Naor. Does parallel repetition lower the error in computationally sound protocols?, in 38th IEEE Symposium on Foundations of Computer Science (IEEE, New York, 1997), pp. 374–383
E.R. Berlekamp, R.J. McEliece, H.C.A. van Tilborg, On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24, 384–386 (1978)
A. Blum, M. Furst, M. Kearns, R. Lipton, Cryptographic primitives based on hard learning problems, in Adv. in Cryptology—Crypto’93. LNCS, vol. 773 (Springer, Berlin, 1994), pp. 278–291
A. Blum, A. Kalai, H. Wasserman, Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM 50(4), 506–519 (2003)
J. Bringer, H. Chabanne, E. Dottax, HB++: A lightweight authentication protocol secure against some attacks, in Proceedings of SecPerU 2006, ed. by P. Georgiadis, J. Lopez, S. Gritzalis, G. Marias (IEEE Computer Society Press, Los Alamitos, 2006), pp. 28–33
R. Canetti, J. Kilian, E. Petrank, A. Rosen, Black-box concurrent zero-knowledge requires (almost) logarithmically many rounds. SIAM J. Comput. 32(1), 1–47 (2002)
R. Canetti, S. Halevi, M. Steiner. Hardness amplification of weakly verifiable puzzles, in 2nd Theory of Cryptography Conference (TCC 2005). LNCS, vol. 3378 (Springer, Berlin, 2005), pp. 17–33
F. Chabaud, On the security of some cryptosystems based on error-correcting codes, in Adv. in Cryptology—Eurocrypt ’94. LNCS, vol. 950 (Springer, Berlin, 1995), pp. 131–139
D.N. Duc, K. Kim, HB+ Securing against GRS man-in-the-middle attack, in Institute of Electronics, Information and Communication Engineers, Symposium on Cryptography and Information Security, Jan. 23–26, 2007
U. Feige, A. Shamir, Witness indistinguishability and witness hiding protocols, in 22nd ACM Symposium on Theory of Computing (ACM, New York, 1990), pp. 416–426
M. Fossorier, M.J. Mihaljevic, H. Imai, Y. Cui, K. Matsuura, An algorithm for solving the LPN problem and its application to security evaluation of the HB protocols for RFID authentication, in Progress in Cryptology—INDOCRYPT 2006. LNCS, vol. 4329 (Springer, Berlin, 2006), pp. 48–62
H. Gilbert, M. Robshaw, H. Silbert, An active attack against HB+: A provably secure lightweight authentication protocol. IEE Electron. Lett. 41(21), 1169–1170 (2005)
H. Gilbert, M.J.B. Robshaw, Y. Seurin, Good variants of HB+ are hard to find, in Financial Cryptography and Data Security, FC 2008. LNCS, vol. 5143 (Springer, Berlin, 2008), pp. 156–170
H. Gilbert, M.J.B. Robshaw, Y. Seurin, HB#: Increasing the security and efficiency of HB+, in Adv. in Cryptology—EUROCRYPT 2008. LNCS, vol. 4965 (Springer, Berlin, 2008), pp. 361–378
O. Goldreich, Modern Cryptography, Probabilistic Proofs, and Pseudorandomness (Springer, Berlin, 1998)
O. Goldreich, H. Krawczyk, On the composition of zero-knowledge proof systems. SIAM J. Comput. 25(1), 169–192 (1996)
O. Goldreich, Y. Oren, Definitions and properties of zero-knowledge proof systems. J. Cryptol. 7(1), 1–32 (1994)
O. Goldreich, N. Nisan, A. Wigderson, On Yao’s XOR-lemma. Available at http://eccc.uni-trier.de/eccc-reports/1995/TR95-050/
V. Guruswami, List Decoding of Error-Correcting Codes (Springer, Berlin, 2004)
J. Håstad, Some optimal inapproximability results. J. ACM 48(4), 798–859 (2001)
N. Hopper, M. Blum, A secure human-computer authentication scheme. Technical Report CMU-CS-00-139, Carnegie Mellon University, 2000
N. Hopper, M. Blum, Secure human identification protocols, in Adv. in Cryptology—Asiacrypt 2001. LNCS, vol. 2248 (Springer, Berlin, 2001), pp. 52–66
S.M. Johnson, A new upper bound for error-correcting codes. IRE Trans. Inf. Theory 8(3), 203–207 (1962)
S.M. Johnson, Improved asymptotic bounds for error-correcting codes. IEEE Trans. Inf. Theory 9(3), 198–205 (1963)
A. Juels, S. Weis, Authenticating pervasive devices with human protocols, in Adv. in Cryptology—Crypto 2005. LNCS, vol. 3621 (Springer, Berlin, 2005), pp. 293–308. Updated version available at: http://www.rsasecurity.com/rsalabs/staff/bios/ajuels/publications/pdfs/lpn.pdf
J. Katz, J.-S. Shin, Parallel and concurrent security of the HB and HB+ protocols, in Adv. in Cryptology—Eurocrypt 2006. LNCS, vol. 4004 (Springer, Berlin, 2006), pp. 73–87
J. Katz, A. Smith, Analyzing the HB and HB+ protocols in the “large error” case. Available at http://eprint.iacr.org/2006/326
M. Kearns, Efficient noise-tolerant learning from statistical queries. J. ACM 45(6), 983–1006 (1998)
Z. Kfir, A. Wool, Picking virtual pockets using relay attacks on contactless smartcard systems. Available at http://eprint.iacr.org/2005/052
I. Kirschenbaum, A. Wool, How to build a low-cost, extended-range RFID skimmer. Available at http://eprint.iacr.org/2006/054
E. Levieil, P.-A. Fouque, An improved LPN algorithm, in Security and Cryptography for Networks (SCN 2006). LNCS, vol. 4116 (Springer, Berlin, 2006), pp. 348–359
V. Lyubashevsky, The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem, in 9th Intl. Workshop on Randomization and Computation (RANDOM 2005). LNCS, vol. 3624 (Springer, Berlin, 2005), pp. 378–389
J. Munilla, A. Peinado, HB-MP: A further step in the hb-family of lightweight authentication protocols. Comput. Netw. 51, 2262–2267 (2007)
R. Pass, M. Venkitasubramaniam, An efficient parallel repetition theorem for Arthur-Merlin games, in 39th ACM Symposium on Theory of Computing (ACM, New York, 2007), pp. 420–429
C. Peikert, Public-key cryptosystems from the worst-case shortest vector problem, in 41st ACM Symposium on Theory of Computing (ACM, New York, 2009), pp. 333–342
R. Raz, A parallel repetition theorem. SIAM J. Comput. 27(3), 763–803 (1998)
O. Regev, On lattices, learning with errors, random linear codes, and cryptography, in 37th ACM Symposium on Theory of Computing (ACM, New York, 2005), pp. 84–93
A.C.-C. Yao, Theory and applications of trapdoor functions, in 23rd IEEE Symposium on Foundations of Computer Science (IEEE, New York, 1982), pp. 80–91
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Rafail Ostrovsky
The results of this work appeared in preliminary form in [26] and [27]. Some of this research was performed while J.K. and A.S. were visiting the Institute for Pure and Applied Mathematics (IPAM) at UCLA.
Research of J. Katz supported by NSF CyberTrust grant #0627306 and NSF CAREER award #0447075.
Research of A. Smith supported in part by NSF CCF grant #0729171.
Rights and permissions
About this article
Cite this article
Katz, J., Shin, J.S. & Smith, A. Parallel and Concurrent Security of the HB and HB+ Protocols. J Cryptol 23, 402–421 (2010). https://doi.org/10.1007/s00145-010-9061-2
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00145-010-9061-2