NLHB: A Light-Weight, Provably-Secure Variant of the HB Protocol Using Simple Non-Linear Functions
In this paper, the authors propose a light-weight provably secure authentication protocol called the NLHB protocol, which is a variant of the HB protocol. The HB protocol uses the complexity of decoding linear codes for security against passive attacks. In contrast, security for the NLHB protocol is proved by reducing the provably hard problem of decoding a class of nonlinear codes to passive attacks. They demonstrate that the existing passive attacks on the HB protocol family, which have contributed to considerable reduction in its effective key-size, do not work against the NLHB protocol.