HB ♭ protocol for lightweight authentication; Its information theoretic indistinguishability against MITM attack watching reader's response

A lightweight authentication protocol, based on the hardness of the Learning Parity with Noise (LPN) problem, was first designed by Hopper and Blum (HB) in 2001. The protocol is practical for low-cost pervasive devices like RFID, and a lot of varieties were investigated for further improvements about communication complexity and about security. In this paper, on HB ♭ protocol recently proposed as an augmented version avoiding many practical drawbacks in the previously existing versions, we show that the information theoretic indistinguishability can be safely proven against MITM attack in which the attacker can utilize information obtained by watching response of the RFID reader to the communication signals intervened by the attacker. Through the proof, we find that the property holds for rather wide parameter range whereas very tiny range of parameter was indicated as an concrete example in the previous paper where the protocol was originally proposed.