The Hopper-Blum (HB) protocol, which uses noised linear parities of a shared key for authentication, has been proposed for light-weight applications such as RFID. Recently, algorithms for decoding linear codes have been specially designed for use in passive attacks on the HB protocol. These linear coding attacks have resulted in the need for long keys in the HB protocol, making the protocol too complex for RFID in some cases. In this work, we propose the NLHB protocol, which is a non-linear variant of the HB protocol. The non-linearity is such that passive attacks on the NLHB protocol continue to be provably hard by reduction. However, the linear coding attacks cannot be directly adapted to the proposed NLHB protocol because of the non-linearity. Hence, smaller key sizes appear to be sufficient in the NLHB protocol for the same level of security as the HB protocol. We construct specific instances of the NLHB protocol and show that they can be significantly less complex for implementation than the HB protocol, in spite of the non-linearity. Further, we propose an extension, called the NLHB+ protocol, that is provably secure against a class of active attack models. © 2010 IEEE.