Radio Frequency Identification (RFID) has received recently a great attention from large
organizations and researchers due to the dropping tag costs and vigorous RFID standardization.
They are becoming more common in daily use to identify, locate and track people, assets, and
animals. Number of protocols has been proposed in the literature for the security of RFID against
passive attacks. One of the well-known protocols is the HB family protocol which utilizes the
complexity of decoding linear codes for RFID security against passive attacks. The nonlinear HB
(NLHB) is one member of the HB family protocol which achieves high security by reducing the
provably hard problem of decoding a class of nonlinear codes to passive attacks. This paper
introduces Multi-Nonlinear Stages to the HB protocol to enhance its security against passive
attacks. More specifically, the paper presents two Multi-Nonlinear versions of the HB protocol;
Double-Nonlinear HB (DNLHB), and Triple-Nonlinear HB (TNLHB). The proposed protocols
increase significantly the security of RFID systems against passive attacks at a lower
implementation cost.