Abstract
Juels andWeis (building on prior work of Hopper and Blum) propose and analyze two shared-key authentication protocols - HB and HB + - whose extremely low computational cost makes them attractive for low-cost devices such as radio-frequency identification (RFID) tags. Security of these protocols is based on the conjectured hardness of the “learning parity with noise” (LPN) problem: the HB protocol is proven secure against a passive (eavesdropping) adversary, while the HB + protocol is proven secure against active attacks.
Juels and Weis prove security of these protocols only for the case of sequential executions, and explicitly leave open the question of whether security holds also in the case of parallel or concurrent executions. In addition to guaranteeing security against a stronger class of adversaries, a positive answer to this question would allow the HB + protocol to be parallelized, thereby substantially reducing its round complexity.
Adapting a recent result by Regev, we answer the aforementioned question in the affirmative and prove security of the HB and HB+ protocols under parallel/concurrent executions. We also give what we believe to be substantially simpler security proofs for these protocols which are more complete in that they explicitly address the dependence of the soundness error on the number of iterations.
The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI: 10.1007/978-3-540-34547-3_36
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Associated Press. Geeks Flex Hacker Muscles at Defcon. Article appeared on CNN.com, August 2 (2005)
Bellare, M., Fischlin, M., Goldwasser, S., Micali, S.: Identification Protocols Secure against Reset Attacks. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 495–511. Springer, Heidelberg (2001)
Bellare, M., Impagliazzo, R., Naor, M.: Does Parallel Repetition Lower the Error in Computationally-Sound Protocols? In: 38th IEEE Symposium on Foundations of Computer Science, pp. 374–383. IEEE, Los Alamitos (1997)
Berlekamp, E.R., McEliece, R.J., van Tilborg, H.C.A.: On the Inherent Intractability of Certain Coding Problems. IEEE Trans. Info. Theory 24, 384–386 (1978)
Blum, A., Furst, M., Kearns, M., Lipton, R.: 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 Model. J. ACM 50(4), 506–519 (2003)
Canetti, R., Halevi, S., Steiner, M.: Hardness Amplification of Weakly Verifiable Puzzles. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 17–33. Springer, Heidelberg (2005)
Canetti, R., Kilian, J., Petrank, E., Rosen, A.: Black-Box Concurrent Zero-Knowledge Requires (Almost) Logarithmically Many Rounds. SIAM J. Computing 32(1), 1–47 (2002)
Chabaud, F.: On the Security of Some Cryptosystems Based on Error-Correcting Codes. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 131–139. Springer, Heidelberg (1995)
Diffie, W., Hellman, M.: New Directions in Cryptography. IEEE Trans. Info. Theory 22(6), 644–654 (1976)
Feige, U., Shamir, A.: Witness Indistinguishability and Witness Hiding Protocols. In: 22nd ACM Symposium on Theory of Computing, pp. 416–426. ACM, New York (1990)
Gilbert, H., Robshaw, M., Silbert, H.: An Active Attack against HB + — a Provably Secure Lightweight Authentication Protocol (2005), available at: http://eprint.iacr.org/2005/237
Goldreich, O.: Modern Cryptography, Probabilistic Proofs, and Pseudorandomness. Springer, Heidelberg (1998)
Goldreich, O., Krawczyk, H.: On the Composition of Zero-Knowledge Proof Systems. SIAM J. Computing 25(1), 169–192 (1996)
Goldreich, O., Nisan, N., Wigderson, A.: On Yao’s XOR-Lemma (1995), available at: http://eccc.uni-trier.de/eccc-reports/1995/TR95-050/
Goldreich, O., Oren, Y.: Definitions and Properties of Zero-Knowledge Proof Systems. J. Cryptology 7(1), 1–32 (1994)
Håstad, J.: Some Optimal Inapproximability Results. J. ACM 48(4), 798–859 (2001)
Hopper, N., Blum, M.: A Secure Human-Computer Authentication Scheme. Technical Report CMU-CS-00-139, Carnegie Mellon University (2000)
Hopper, N., 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.: 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/
Kearns, M.: Efficient Noise-Tolerant Learning from Statistical Queries. J. ACM 45(6), 983–1006 (1998)
Kfir, Z., Wool, A.: Picking Virtual Pockets using Relay Attacks on Contactless Smartcard Systems (2005), available at: http://eprint.iacr.org/2005/052
Kirschenbaum, I., Wool, A.: How to Build a Low-Cost, Extended-Range RFID Skimmer (2006), available at: http://eprint.iacr.org/2006/054
Raz, R.: A Parallel Repetition Theorem. SIAM J. Computing 27(3), 763–803 (1998)
Regev, O.: On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. In: 37th ACM Symposium on Theory of Computing, pp. 84–93. ACM, New York (2005)
Yao, A.C.-C.: Theory and Applications of Trapdoor Functions. In: 23rd IEEE Symposium on Foundations of Computer Science, pp. 80–91. IEEE, Los Alamitos (1982)
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
Katz, J., Shin, J.S. (2006). Parallel and Concurrent Security of the HB and HB + Protocols. In: Vaudenay, S. (eds) Advances in Cryptology - EUROCRYPT 2006. EUROCRYPT 2006. Lecture Notes in Computer Science, vol 4004. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11761679_6
Download citation
DOI: https://doi.org/10.1007/11761679_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34546-6
Online ISBN: 978-3-540-34547-3
eBook Packages: Computer ScienceComputer Science (R0)