Paper 2006/197

A Novel Algorithm for Solving the LPN Problem and its Application to Security Evaluation of the HB Protocol for RFID Authentication

Marc P. C. Fossorier, Miodrag J. Mihaljevic, Hideki Imai, Yang Cui, and Kanta Matsuura

Abstract

A novel algorithm for solving the LPN problem is proposed and analyzed. The algorithm originates from the recently proposed advanced fast correlation attacks, and it employs the concepts of decimation, linear combining, hypothesizing and minimum distance decoding. The proposed algorithm appears as more powerful than the best one previously reported known as the BKW algorithm. In fact the BKW algorithm is shown to be a special instance of the proposed algorithm, but without optimized parameters. An improved security evaluation of the HB protocol for RFID authentication is then developed. Employing the proposed algorithm, the security of the HB protocol is reevaluated, implying that the previously reported security margins appear as overestimated.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
cryptanalysisLPN problemfast correlation attacksHB protocolRFID authentication
Contact author(s)
miodragm @ turing mi sanu ac yu
History
2006-06-20: received
Short URL
https://ia.cr/2006/197
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/197,
      author = {Marc P. C.  Fossorier and Miodrag J.  Mihaljevic and Hideki Imai and Yang Cui and Kanta Matsuura},
      title = {A Novel Algorithm for Solving the LPN Problem and its Application to Security Evaluation of the HB Protocol for RFID Authentication},
      howpublished = {Cryptology ePrint Archive, Paper 2006/197},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/197}},
      url = {https://eprint.iacr.org/2006/197}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.