A method for obfuscating data, the method including: reading values occurring in one or more fields of multiple records from a data source; storing a key value; for each of multiple of the records, generating an obfuscated value to replace an original value in a given field of the record using the key value such that the obfuscated value depends on the key value and is deterministically related to the original value; storing the collection of obfuscated data (114, 416) including records that include obfuscated values in a data storage system; and further including: storing profile information including statistics characterizing values of at least one of the fields wherein the obfuscated value is generated using the key value and the stored profile information for the given field, wherein the obfuscated value occurs in the given field of the collection of obfuscated data at a frequency determined based on statistics in the stored profile information characterizing values of the given field, wherein the obfuscated value is generated by using the original value and the key as inputs to a function that generates an index value and using the index value to look up the obfuscated value in a predetermined set of obfuscated values, and wherein multiple index values within a range correspond to the same obfuscated value in the predetermined set of obfuscated values, wherein the size of the range is based on the statistics in the stored profile information characterizing values of the given field. reading values occurring in one or more fields of multiple records from a data source; storing a key value; for each of multiple of the records, generating an obfuscated value to replace an original value in a given field of the record using the key value such that the obfuscated value depends on the key value and is deterministically related to the original value; storing the collection of obfuscated data (114, 416) including records that include obfuscated values in a data storage system; and further including: storing profile information including statistics characterizing values of at least one of the fields wherein the obfuscated value is generated using the key value and the stored profile information for the given field, wherein the obfuscated value occurs in the given field of the collection of obfuscated data at a frequency determined based on statistics in the stored profile information characterizing values of the given field, wherein the obfuscated value is generated by using the original value and the key as inputs to a function that generates an index value and using the index value to look up the obfuscated value in a predetermined set of obfuscated values, and wherein multiple index values within a range correspond to the same obfuscated value in the predetermined set of obfuscated values, wherein the size of the range is based on the statistics in the stored profile information characterizing values of the given field. storing profile information including statistics characterizing values of at least one of the fields wherein the obfuscated value is generated using the key value and the stored profile information for the given field, wherein the obfuscated value occurs in the given field of the collection of obfuscated data at a frequency determined based on statistics in the stored profile information characterizing values of the given field, wherein the obfuscated value is generated by using the original value and the key as inputs to a function that generates an index value and using the index value to look up the obfuscated value in a predetermined set of obfuscated values, and wherein multiple index values within a range correspond to the same obfuscated value in the predetermined set of obfuscated values, wherein the size of the range is based on the statistics in the stored profile information characterizing values of the given field.