Strong Privacy for RFID Systems from Plaintext-Aware Encryption

Modeling privacy for RFID protocols went through different milestones. One pretty complete model was proposed by Vaudenay at ASIACRYPT 2007. It provides a hierarchy of privacy levels, depending on whether corruption is addressed by the protocol and on whether the return channel from the reader is available. The strongest notion of privacy was proven to be impossible to achieve, but the counterexample which was given was not convincing. Somehow, it showed that the requirements for strong privacy were unnecessarily too high. Several amendments were considered until a slight change in the definition which was proposed at CANS 2012. There, the simulator (blinder) was given access to the adversary's random tape, making him able to read his mind. Thanks to plaintext-aware encryption, we can now prove that strong privacy is possible.