A protocol with constant-time complexity solves the problem of private identification of tags in low-cost, large-scale radio frequency identification (RFID) systems--assuming that an adversary has complete control over the communication channel. Each RFID tag has an internal counter, c, and is preloaded with a unique pseudonym, .psi., and a secret key, k. A RFID reader attempting to identify and authenticate a tag within its range generates and transmits a random nonce to the RFID tag, which returns a first hash of its current pseudonym and counter, and a second hash that is a function of the secret key. The reader uses the returned data to identify the RFID tag and its secret key by reference to a database and returns other hash values that authenticate the reader to the RFID tag. The most expensive operation that RFID tags are required to perform is a hash function.