Cryptographic techniques are provided having a complexity level which permits their implementation in inexpensive radio frequency identification (RFID) tags or other RFID devices. In an RFID system comprising one or more RFID devices and at least one reader that communicates with the devices, a plurality of pseudonyms is associated with a given one of the RFID devices. The RFID device transmits different ones of the pseudonyms in response to different reader queries, and an authorized verifier is able to determine that the different transmitted pseudonyms are associated with the same RFID device.