RFID Mutual Authentication Protocols with Universally Composable Security

Universally Composable (UC) framework is the strongest security notion for designing fully trusted cryptographic protocols, and it is very challenging on applying UC security in the design of RFID mutual authentication protocols. In this paper, we formulate the necessary conditions for achieving UC secure RFID mutual authentication protocols in a fully trusted environment, and indicate the flaws of some existing schemes under UC framework. We define the ideal functionality for RFID mutual authentication and propose the first UC secure RFID mutual authentication protocol based on public key encryption and some trusted third parties which can be modeled as functionalities. We prove the security of our protocol under the strongest adversary model assuming both the tags' and readers' corruptions. Furthermore, we present two (public) key update protocols for the cases of multiple readers: one uses Message Authentication Code (MAC); the other uses trusted certificates in Public Key Infrastructure (PKI).