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 reducing its round complexity from super-logarithmic (in the security parameter) to 3.
Using a recent result by Regev (STOC 2005) regarding the LPN problem, we answer the aforementioned question in the affirmative and prove security of the HB and HB+ protocols under parallel/concurrent executions. Applying Regev's result also yields what we find to be substantially simpler security proofs for these protocols which are also more complete in that they explicitly address the dependence of the soundness error on the number of iterations.
Category / Keywords: secret-key cryptography / HB, RFID, authentication Publication Info: To appear at Eurocrypt 2006 Date: received 19 Dec 2005, last revised 10 Mar 2006 Contact author: jkatz at cs umd edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20060310:144919 (All versions of this report) Short URL: ia.cr/2005/461 Discussion forum: Show discussion | Start new discussion