Defining Strong Privacy for RFID

In this work, we consider privacy in Radio Frequency IDentification (RFID) systems. Our contribution is twofold: (i) We propose a simple, formal definition of strong privacy useful for basic analysis of RFID systems, as well as a different (weaker) definition applicable to multiverifier systems; (ii) We apply our definition to reveal vulnerabilities in several proposed privacy-enhancing RFID protocols; and (iii) We formally analyze and suggest improvements to hash-locks, one of the first privacy-enhancing RFID protocols in the literature.