One embodiment of the present invention provides a system that facilitates protecting an item of private information in a database, wherein the item of private information is used as a key for retrieving data from the database. During operation, the system receives the item of private information and creates a hash of the item. The system then stores the hash in the database along with any associated information in a database record containing the hash.