Untraceable RFID tag via insubvertible encryption

We introduce a new cryptographic primitive, called insubvertible encryption, that produces ciphertexts which can be randomized without the need of any key material. Unlike plain universal re-encryption schemes, insubvertible encryption prevents against adversarial exploitation of hidden channels, by including certificates proving that the cipher-text can only be decrypted by authorized parties. The scheme can be applied to RFID tags, providing strong protection against tracing. This enables post-sale applications of manufacturer-issued RFID tags while preserving the privacy of consumers. The functionality required of the RFID tags is minimal, namely that they be re-writable (many-writable). No cryptographic capabilities are required of the tags themselves, as the readers perform all necessary computations.