SPEAKER:
Kristiyan Haralambiev
NYU

TITLE: 
HB and HB+: Authentication Protocols for Low-Cost Devices

ABSTRACT:
At Crypto 2005, Juels and Weis (building on prior work of Hopper and
Blum) proposed and analyzed 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.
Using a recent result by Regev (STOC 2005) regarding the LPN problem,
Katz and Shin answered the aforementioned question in the affirmative
and proved security of the HB and HB+ protocols under
parallel/concurrent executions.
Furthermore, Gilbert, Robshaw, and Sibert have proven that the
detection-based model in the papers above is vulnerable to a simple
active attack. So, it is interesting open problem whether there is an
efficient protocol based on the LPN problem that is resistant to
man-in-the-middle attacks.