Parallel and concurrent security of the HB and \(HB^{+}\) protocols (Q5962225)

\textit{N. Hopper} and \textit{M. Blum} [Secure human identification protocols. Advances in cryptology -- ASIACRYPT 2001. 7th international conference on the theory and application of cryptology and information security, Gold Coast, Australia. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2248, 52--66 (2001; Zbl 1062.94549)] and \textit{A. Juels} and \textit{S. A. Weis} [Authenticating pervasive devices with human protocols. Advances in cryptology -- CRYPTO 2005. 25th annual international cryptology conference, Santa Barbara, CA, USA 2005. Proceedings. Berlin: Springer. Lecture Notes in Computer Science 3621, 293--308 (2005; Zbl 1145.94470)] proposed the shared-key authentication protocols \(HB\) and \(HB^+\), respectively. Their extremely low computational cost make 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. In this paper, the \(HB\) protocol is proven secure against a passive (eavesdropping) adversary and the \(HB^+\) protocol is proven secure against active attacks.