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.

For example, 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.

In the past, what we have done is to completely remove PII if we need to transfer any data to a third party. But this means that the third party has really no idea of the relationships between entities. We would prefer to be able to pass along some information about those relationships, without divulging identity.

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) any PII. But the only method I am familiar with for doing this is ROT13, 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.

Are there accepted methods for obscuring data like this, or is it effectively impossible?

I have found at least one paper that looks relevant but it's a bit over my head.