Privacy-Preserving RFID Systems: Model and Constructions
In this paper, we study systems where a reader wants to authenticate and identify legitimate RFID tags. Such system needs thus to be correct (legitimate tags are accepted) and sound (fake tags are rejected). Moreover, an RFID tag in a privacy-preserving system should be anonymous and untraceable, except for the legitimate reader. We here present the first security model for RFID authentication/identification privacy-preserving systems which is at the same time complete and easy to use. Our correctness property permits to take into account active adversaries. Our soundness property incorporates the case of adversaries realizing relay attacks. Finally, our privacy model includes adversaries with no restrictions on their interactions with the system and moreover takes into account the case of ``future correlations''. We next propose several constructions, based on the work from Vaudenay, proving that (i) our strongest property is at least as strong as those of Vaudenay and (ii) this property is reachable by efficient schemes.