Authors: Fossorier, Marc P. C.
Mihaljević, Miodrag J. 
Imai, Hideki
Cui, Yang
Matsuura, Kanta
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: An algorithm for solving the LPN problem and its application to security evaluation of the HB protocols for RFID authentication
Journal: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume: 4329 LNCS
First page: 48
Last page: 62
Issue Date: 1-Jan-2006
Rank: M23
ISBN: 978-3-540-49767-7
ISSN: 0302-9743
DOI: 10.1007/11941378_5
An algorithm for solving the “learning parity with noise” (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. However, as opposed to fast correlation attacks, no preprocessing phase is allowed for the LPN problem. The proposed algorithm appears as more powerful than the best one previously reported known as the BKW algorithm proposed by Blum, Kalai and Wasserman. In fact the BKW algorithm is shown to be a special instance of the proposed algorithm, but without optimized parameters. An improved security evaluation, assuming the passive attacks, of Hopper and Blum HB and HB+ protocols for radio-frequency identification (RFID) authentication is then developed. Employing the proposed algorithm, the security of the HB protocols is reevaluated, implying that the previously reported security margins appear as overestimated.
Keywords: Cryptanalysis | Fast correlation attacks | HB protocols | LPN problem | RFID authentication
Publisher: Springer Link
Project: Advanced methods for cryptology and information processing 

Show full item record


checked on May 16, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.