International Association for Cryptologic Research
The need for light-weight cryptography is increasing rapidly due to the growing deployment of low-cost devices, such as smart cards and RFID tags, in the real world. The authors show how to construct, from any weak pseudorandom function, a 3-round symmetric-key authentication protocol that is secure against man-in-the-middle attacks. The construction is very efficient, requiring both the secret key and communication size to be only 3n bits long. Their techniques also extend to certain classes of randomized weak-PRFs, chiefly among which are those based on the classical LPN problem and its more efficient variants such as Toeplitz-LPN and ring-LPN.