# Secure distance calculation

I am working on securing a feature in a csv file. My goal is to encrypt, anonymize, mask.... etc the content of the records of the feature while preserving the distance between the characters. as example : record 1 : mtlcfg record 2 : mtlfff

The distance between them is 2 so I want to secure the actual values and preserve the distance on the secured value so the other party is able to retrieve the distance without retrieving the actual values.

I know that adding a noise vector will work and preserve the distance but it is not secure enough. All papers that I am reading now are focusing on multi-party secure distance computation such as additive homomorphic encryption. Yet this doesn't match with my case, all I want to do is to be able to calculate the distance on secured content. Can anyone suggest any papers to guidance I am really lost in a lot of papers

• By distance, I assume you mean geographical Euclidean distance (as opposed to, say, hamming distance). However, if you know the distance of point A to two points B and C of known location, you can deduce that point A is in one of two locations (and the distance to a third point would eliminate that ambiguity). That would appear to imply that the obvious geometric transformation may be about the best you can do... – poncho May 18 '18 at 18:24
• Thank you for your comment, I have edited my question my apologies for not being clear enough in the beginning at first – Fighter May 18 '18 at 18:39

You asked a How do I question. You probably asked a Should I question. As in "Should I release a data set that reveals the distance between two strings where everything else is anonymized?" The answer is No unless you're making a crossword puzzle. (XKCD beat me to the joke for something similar. Your scenario is much more crossword-like however.)

Even if you found a scheme that didn't directly reveal individual letters, just having the information you get from string edit distances reveals a lot of information. Example: You have two records in a medical trial program with similar demographic data. You suspect "Bob Example Sr." and "Bob Example Jr." participated. Your two similar rows of data have “ “ “anonymized” ” ” (this needs triple scare quotes to triple scare you out of becoming responsible for publicizing poorly anonymized data) name records which are both 15 characters long and differ in one character. Start making guesses.

One could also build a weighted graph of dictionary words. (Where every node is a word and every pair of nodes is connected by an edge with weight equal to their edit distance.) For your idea you are hiding the labels of each node but not the edges or weights. One could make an informed guess at the values of the encrypted data by looking for similar sub-graphs in both the encrypted and dictionary-based graphs. Once you find one answer it becomes easier to guess the rest.

It is very difficult to design a system that anonymizes complex data sets. Otherwise intelligent people think they're outwitting hackers when they do things like hash email address, credit card info, or social security numbers. And that's the most obviously de-anonymizable scheme one can think of.

The most powerful tool to deanonymize data is to exploit the relations between data. If the purpose of your encryption is anonymization while maintaining properties in the original data then you're trying to do two things that are at odds with each other. It's a lot like deliberately encrypting with the same key/nonce pair even if you could find the perfect scheme.

Now to answer the "How do I [best stick a fork in an electrical socket"] part. I can think of three methods.

1. Store a table that relates pairs of records to their edit distance. This requires $O(n^2)$ space but is the least bad option. Omit the original string data or substitute it with randomly assigned ID numbers. You can't add new data to an annoymized database with this method.
2. If you want the Hamming distance between two strings, then use one substitution cipher for the first character of each string, another for the second, and so on. Breaking a substitution cipher is easy enough that it requires no knowledge of modern cryptography. (Or much knowledge at all beyond literacy.)
3. If you want Levenshtein distance then you use only one substitution cipher. This choice is also horribly insecure.

There may be better privacy-preserving methods than 2 and 3, but not 1. There may be way more complicated ways involving "multi-party secure distance computation, oblivious transform such as secure modular hashing, additive homomorphic encryption" but if any scheme leaks the data you say you want to preserve to a person who holds a copy of the supposedly anonymized data then it's no better at preserving privacy than 1.