How can I transform names in a confidential data set to make it anonymous, but preserve some of the characteristics of the names?

Question

Motivation

I work with datasets that contain personally identifiable information (PII) and sometimes need to share part of a dataset with third parties, in a way that doesn't expose PII and subject my employer to liability. Our usual approach here is to withhold data entirely, or in some cases to reduce its resolution; e.g., replacing an exact street address with the corresponding county or census tract.

This means that certain types of analysis and processing must be done in-house, even when a third party has resources and expertise more suited to the task. Since the source data is not disclosed, the way we go about this analysis and processing lacks transparency. As a result, any third party's ability to perform QA/QC, adjust parameters or make refinements may be very limited.

Anonymizing Confidential Data

One task involves identifying individuals by their names, in user-submitted data, while taking into account errors and inconsistencies. A private individual might be recorded in one place as "Dave" and in another as "David," commercial entities can have many different abbreviations, and there are always some typos. I've developed scripts based on a number of criteria that determine when two records with non-identical names represent the same individual, and assign them a common ID.

At this point we can make the dataset anonymous by withholding the names and replacing them with this personal ID number. But this means the recipient has almost no information about e.g. the strength of the match. We would prefer to be able to pass along as much information as possible without divulging identity.

What Doesn't Work

For instance, it would be great to be able to encrypt strings while preserving edit distance. This way, third parties could do some of their own QA/QC, or choose to do further processing on their own, without ever accessing (or being able to potentially reverse-engineer) PII. Perhaps we match strings in-house with edit distance <= 2, and the recipient wants to look at the implications of tightening that tolerance to edit distance <= 1.

But the only method I am familiar with that does this is ROT13 (more generally, any shift cipher), which hardly even counts as encryption; it's like writing the names upside down and saying, "Promise you won't flip the paper over?"

Another bad solution would be to abbreviate everything. "Ellen Roberts" becomes "ER" and so forth. This is a poor solution because in some cases the initials, in association with public data, will reveal a person's identity, and in other cases it's too ambiguous; "Benjamin Othello Ames" and "Bank of America" will have the same initials, but their names are otherwise dissimilar. So it doesn't do either of the things we want.

An inelegant alternative is to introduce additional fields to track certain attributes of the name, e.g.:

+-----+----+-------------------+-----------+--------+
| Row | ID | Name              | WordChars | Origin |
+-----+----+-------------------+-----------+--------+
| 1   | 17 | "AMELIA BEDELIA"  | (6, 7)    | Eng    |
+-----+----+-------------------+-----------+--------+
| 2   | 18 | "CHRISTOPH BAUER" | (9, 5)    | Ger    |
+-----+----+-------------------+-----------+--------+
| 3   | 18 | "C J BAUER"       | (1, 1, 5) | Ger    |
+-----+----+-------------------+-----------+--------+
| 4   | 19 | "FRANZ HELLER"    | (5, 6)    | Ger    |
+-----+----+-------------------+-----------+--------+

I call this "inelegant" because it requires anticipating which qualities might be interesting and it's relatively coarse. If the names are removed, there's not much you can reasonably conclude about the strength of the match between rows 2 & 3, or about the distance between rows 2 & 4 (i.e., how close they are to matching).

Conclusion

The goal is to transform strings in such a way that as many useful qualities of the original string are preserved as possible while obscuring the original string. Decryption should be impossible, or so impractical as to be effectively impossible, no matter the size of the data set. In particular, a method that preserves the edit distance between arbitrary strings would be very useful.

I've found a couple papers that might be relevant, but they're a bit over my head:

• Privacy Preserving String Comparisons Based on Levenshtein Distance
• An Empirical Comparison of Approaches to Approximate String Matching in Private Record Linkage

Answer 1

One of the references I mentioned in the OP led me to a potential solution that seems quite powerful, described in "Privacy-preserving record linkage using Bloom filters":

A new protocol for privacy-preserving record linkage with encrypted identifiers allowing for errors in identifiers has been developed. The protocol is based on Bloom filters on q-grams of identifiers.

The article goes into detail about the method, which I will summarize here to the best of my ability.

A Bloom filter is a fixed-length series of bits storing the results of a fixed set of independent hash functions, each computed on the same input value. The output of each hash function should be an index value from among the possible indexes in the filter; i.e., if you have a 0-indexed series of 10 bits, hash functions should return (or be mapped to) values from 0 to 9.

The filter starts with each bit set to 0. After hashing the input value with each function from the set of hash functions, each bit corresponding to an index value returned by any hash function is set to 1. If the same index is returned by more than one hash function, the bit at that index is only set once. You could consider the Bloom filter to be a superposition of the set of hashes onto the fixed range of bits.

The protocol described in the above-linked article divides strings into n-grams, which are in this case sets of characters. As an example, "hello" might yield the following set of 2-grams:

["_h", "he", "el", "ll", "lo", "o_"]

Padding the front and back with spaces seems to be generally optional when constructing n-grams; the examples given in the paper that proposes this method use such padding.

Each n-gram can be hashed to produce a Bloom filter, and this set of Bloom filters can be superimposed on itself (bitwise OR operation) to produce the Bloom filter for the string.

If the filter contains many more bits than there are hash functions or n-grams, arbitrary strings are relatively unlikely to produce exactly the same filter. However, the more n-grams two strings have in common, the more bits their filters will ultimately share. You can then compare any two filters A, B by means of their Dice coefficient:

D_{A, B} = 2h / (a + b)

Where h is the number of bits that are set to 1 in both filters, a is the number of bits set to 1 in only filter A, and b is the number of bits set to 1 in only filter B. If the strings are exactly the same, the Dice coefficient will be 1; the more they differ, the closer the coefficient will be to 0.

Because the hash functions are mapping an indeterminate number of unique inputs to a small number of possible bit indexes, different inputs may produce the same filter, so the coefficient indicates only a probability that the strings are the same or similar. The number of different hash functions and the number of bits in the filter are important parameters for determining the likelihood of false positives - pairs of inputs that are much less similar than the Dice coefficient produced by this method predicts.

I found this tutorial to be very helpful for understanding the Bloom filter.

There is some flexibility in the implementation of this method; see also this 2010 paper (also linked at the end of the question) for some indications of how performant it is in relation to other methods, and with various parameters.

Answer 2

Halfway through reading your question, I realized Levenshtein Distance could be a nice solution to your problem. It's good to see that you have a link to a paper on the topic; let me see if I can shed some light into what a Levenshtein solution would look like.

Levenshtein distance is used across many industries for entity resolution. What makes it useful is that it is a measure of the difference between two sequences. In the case of string comparison, it is just sequences of characters.

This could help solve your problem by allowing you to provide one number that gives a measure of how similar the text of another field is.

Here is an example of a basic way of using Levenshtein with the data you gave:

This provides an ok solution, the distance of 8 provides some indication of a relationship, and it is very PII compliant. However, it is still not super useful. Let's see what happens if we do some text magic to take only the first initial of the first name, the full last name and dropping anything in the middle:

As you can see, the Levenshtein distance of 0 is pretty indicative of a relationship. Commonly data providers will combine a bunch of Levenshtein permutations of the first and last names with 1, 2, or all of the characters just to give some dimensionality as to how entities are related while still maintaining anonymity within the data.

Answer 3

If feasible, I would link related records (e.g., Dave, David, etc.) and replace them with a sequence number (1,2,3, etc.) or a salted hash of the string that is used to represent all related records (e.g., David instead of Dave).

I assume that third parties need not have any idea what the real name is, otherwise you might as well give it to them.

You need to define and justify what kind of operations the third party needs to be able to do. For example, what is wrong with using initials followed by a number (e.g., BOA-1, BOA-2, etc.) to disambiguate Bank of America from Benjamin Othello Ames? If that's too revealing, you could bin some of the letters or names; e.g., [A-E] -> 1, [F-J] -> 2, etc. so BOA would become 1OA, or ["Bank", "Barry", "Bruce", etc.] -> 1, so Bank of America is again 1OA.

For more information see k-anonymity.

Answer 4

One option (depending on your dataset size) is to just provide edit distances (or other measures of similarity you're using) as an additional dataset.

E.g.:

1. Generate a set of unique names in the dataset
2. For each name, calculate edit distance to each other name
3. Generate an ID or irreversable hash for each name
4. Replace names in the original dataset with this ID
5. Provide matrix of edit distances between ID numbers as new dataset

Though there's still a lot that could be done to deanonymise the data from these even.

E.g. if "Tim" is known to be the most popular name for a boy, frequency counting of IDs that closely match the known percentage of Tims across the population might give that away. From there you could then look for names with an edit distance of 1, and conclude that those IDs might refer to "Tom" or "Jim" (when combined with other info).

Answer 5

I'm not quite sure, but maybe locality-sensitive hashing is a good solution. It does hashing of input data (in your case - names), so original strings would be preserved. On the other side, the main idea of LSH is to maximize hashes likelihood for similar items. There are a lot of different LSH-implementations. I tried Nilsimsa-hash for comparing tweet texts, and it worked quite well. But I'm not sure, how well it will work in case of short strings (names) - this issue require testing. I tried your examples, and here is the result (name A, name B, "distance" - maximum is 120):

1. AMELIA BEDELIA  - CHRISTOPH BAUER - 107
2. AMELIA BEDELIA  - C J BAUER       - 82
3. AMELIA BEDELIA  - FRANZ HELLER    - 91
4. CHRISTOPH BAUER - C J BAUER       - 81
5. CHRISTOPH BAUER - FRANZ HELLER    - 98
6. C J BAUER       - FRANZ HELLER    - 83

As you see, CHRISTOPH BAUER and C J BAUER turned up to be the closest pair. But difference is not significant. And just for example - hash representation of these names:

AMELIA BEDELIA  6b208299602b5000c3005a048122a43a828020889042240005011c1880864502
CHRISTOPH BAUER 22226448000ab10102e2860b52062487ff0000928e0822ee106028016cc01237
C J BAUER       2282204100961060048050004400240006032400148000802000a80130402002
FRANZ HELLER    58002002400880080b49172044020008030002442631e004009195020ad01158

Answer 6

Here's an approach I didn't see mentioned: separate the process into two steps: the first step focused on encoding names so that alternative versions of the same name are encoded the same (or nearly the same), and the second step focused on making them anonymous.

For the first step, you could use one of the Phonetic Algorithms (Soundex and variants), applied to first name, last name, and initials in various orders. (See this article, also). It's in this step where you resolve similarities vs. differences in names to balance false positives from false negatives.

For the second step, you can pick any hashing or cryptographic method you like, without concern for how that method affects name matching. This gives you freedom to use a method that has the best characteristics for both performance, robustness, and anonymity.