I have a theoretical problem inspired by a real world problem I have come across.
I am writing code for some spreadsheets, and part of the process is error correcting names with typos. One complication is that the names are encrypted before I see the sheet. This makes testing a bit fiddly, as one step of the process is to merge data for two entries where they are the same name but with a typo.
I was wondering whether there are secure encryptions with an edit distance where two strings which are similar before are similar afterwards. My intuition says this wouldn't be possible (e.g., if an edit distance looked at transpositions and swaps, then if these remained low then what the encryption was doing would presumably be similar to a reversible sequence of these actions), but I'm not sure how you would express this formally, especially as there might be more creative ways to measure string distance than what I have come across.
(Distance we use for working out if there's been a typo currently) https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
(encryption we used currently for the names) https://en.wikipedia.org/wiki/SHA-2