<p>I have a theoretical problem inspired by a real world problem I have come across.</p>
<p>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.</p>
<p>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.</p>
<p>(Distance we use for working out if there's been a typo currently) <a href="https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance</a></p>
<p>(encryption we used currently for the names)
<a href="https://en.wikipedia.org/wiki/SHA-2" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/SHA-2</a></p>

CC BY-SA 4.0
2021-09-10T03:37:35.883Z
"One complication is that the names are encrypted before I see the sheet." Priceless!
usul
CC BY-SA 4.0
2021-09-10T03:41:38.137Z
I think SHA-2 is hashing, not encryption?
usul
CC BY-SA 4.0
2021-09-10T14:02:40.470Z
apologies - you're right, it is hashing
riemann_lebesgue
CC BY-SA 4.0
2021-09-10T14:04:56.083Z
@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!!
riemann_lebesgue
CC BY-SA 4.0
2021-09-12T21:32:06.357Z
To answer the question in the title: yes, conditional Kolmogorov complexity.  But I think the question in post asks something somewhat different.
Neal Young
<string-matching>
Is there a measure of string distance which remains small between two strings after encryption?
riemann_lebesgue
# Is there a measure of string distance which remains small between two strings after encryption?

(Asked by: username_0 on 2021-09-09)

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>

**Tags:** string-matching

> **Comments:**
> **username_1**: "One complication is that the names are encrypted before I see the sheet." Priceless!  
> **username_1**: I think SHA-2 is hashing, not encryption?  
> **username_0**: apologies - you're right, it is hashing  
> **username_0**: @username_1 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!!  
> **username_2**: To answer the question in the title: yes, conditional Kolmogorov complexity.  But I think the question in post asks something somewhat different.  

---

## 0 answers

