A system and method for RFID privacy-preserving authentication is disclosed. The method first has a reader sending a request and a first random number to a tag. The tag then generates a second random number. A plurality of hash values are then computed at the tag. Each hash value uses the first random number, the second random number and at least one part of a key of the tag as inputs. The second random number and the computed hash values are then sent to the reader. Lastly, the reader identifies a validity of the tag from the received values. The hash values are all generated in parallel and are independent to each other.