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

  • 1
    $\begingroup$ "One complication is that the names are encrypted before I see the sheet." Priceless! $\endgroup$
    – usul
    Sep 10 at 3:37
  • 1
    $\begingroup$ I think SHA-2 is hashing, not encryption? $\endgroup$
    – usul
    Sep 10 at 3:41
  • $\begingroup$ apologies - you're right, it is hashing $\endgroup$ Sep 10 at 14:02
  • $\begingroup$ @usul there was an extremely painful debugging process with me making changes and someone with access to the proper spreadsheet telling me if they'd worked!! $\endgroup$ Sep 10 at 14:04
  • $\begingroup$ To answer the question in the title: yes, conditional Kolmogorov complexity. But I think the question in post asks something somewhat different. $\endgroup$
    – Neal Young
    Sep 12 at 21:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.