On Hardware-Oriented Message Authentication with Applications towards RFID

We consider ultra light-weight constructions of message authentication in hardware applications like RFID. We propose a new type of constructions that will be less costly to implement in hardware, compared to any previous construction. These constructions are based on the framework of universal hash functions, Toeplitz matrices and epsilon-biased sample spaces. Some new theoretical results in this area are derived. The hardware-attractive new constructions come at the price of not being able to prove the exact substitution probability. The expected probability is examined both through theoretical methods as well as through simulation.