Strong Privacy for RFID Systems from Plaintext-Aware Encryption

he Vaudenay model for RFID privacy from Asiacrypt 2007 suffers from the impossibility to address strong privacy. It has however been shown by Ng et al. at ESORICS 2008 that the impossibility result leads to no practical threat, so that the definition from 2007 may be unnecessarily strong. This paper proposes a slight change in the definition of privacy from the Vaudenay model (Asiacrypt 2007). Then, we show that by adding a plaintext-aware assumption on the public-key cryptosystem, the proposed protocol always achieves strong privacy with our new definitions.