<p>I'm not sure I fully grasp the question as posed, but it seems to me that the asker is looking for some kind of approximation of the Levenshtein distance metric. Perhaps the following reference might be of some use?</p>

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.78.6784" rel="nofollow">Bar-Yosef, Ziv et al., "Approximating Edit Distance Efficiently", FOCS 2004</a></p>

<blockquote>
  <p>In this section we describe our two sketching
  algorithms for solving gap edit distance problems. The underlying
  principle in both algorithms is the same: the two
  input strings have a small edit distance if and only if they
  share many sufficiently long substrings occurring at nearly
  the same position in both strings, and hence, the number
  of mismatching substrings provides an estimate of the edit
  distance. More formally, both algorithms map the inputs x
  and y into sets $T_x$ and $T_y$, respectively; these sets consist of pairs of the form ($\gamma$, i), where $\gamma$ is a sufficiently long substring
  and i is a special “encoding” of the position at which
  the substring begins. [...] </p>
  
  <p>This gives rise to a natural reduction from the task of estimating
  edit distance between x and y to that of estimating
  the Hamming distance between the characteristic vectors u
  and v of $T_x$ and $T_y$, respectively.</p>
</blockquote>

CC BY-SA 2.5
2010-12-07T22:38:38.013Z
This is a good answer.  I think the paper you've referenced is very applicable.  Especially in leading me full circle back to my selected answer of my original question.  I thought I was going in a different direction, but upon refinement, arrived at the same place.  I'll leave this open for the duration of the bounty in case there are additional perspectives.
Jason Kleban
CC BY-SA 2.5
2010-12-07T22:41:55.297Z
I'm especially keen on the language of the sketch algorithms, which I think is more accurate to describe the hash algorithm.
Jason Kleban
CC BY-SA 2.5
2010-12-07T01:21:37.533Z
2010-12-07T01:27:39.403Z
2010-12-07T01:27:39.403Z
mhum
<p>Related to <a href="https://cstheory.stackexchange.com/questions/2148/intermediate-coding-representation-for-levenshtein-distance">this question</a>, but asked in a different way.</p>

<p>For the purposes of a text-based implementation of a <a href="http://scholar.google.com/scholar?q=fuzzy+vault" rel="nofollow noreferrer">fuzzy vault</a>, what metrics can we take on Sequences that are isolated such that the set of measured values is resilient to "small changes"?  More changes would mean more members of the set would be different.</p>

<blockquote>
  <p>Specifically, is there a hash function
  with these properties as described
  below?  Next best thing to a working
  algorithm would be clarifying
  discussion about why such a function
  should be feasible or why such a
  function cannot exist.</p>
  
  <p>Below contains background, a
  description of such a hash function
  (not implemented), and an
  implementation of an algorithm that
  seems to have some, but not all of the
  desired properties.</p>
</blockquote>

<p>Fuzzy Vaults in biometrics work because the included measurements of, say, the face are independent.  The width of two faces could match even if their heights don't.  If we could collect a set of independent measurements about a string, a <em>pass phrase</em>, then we might implement a Fuzzy Vault that would allow similar phrases, within a tolerance, to reveal a secret.</p>

<p>From my reading, Fuzzy Vaults work with intersecting sets of exactly matching values, not sets of similar values.  Typos in a pass phrase would be some combination of omitted characters, additional characters, and replaced characters.  If we could restrict the errors made to only replaced characters, each character's index could be used - the character value of each index would be components of the Fuzzy Key.  A single typo would only affect a single key component.  Unfortunately, because of inserted and deleted characters affect the offsets of the remainder of the sequence, single typos can dramatically affect the key components of later in the sequence.</p>

<blockquote>
  <p>Here's an attempt at formulating the
  challenge:</p>
  
  <p>Define $f(s)$ as a hashing transform
  of any sequence $s$ into a set $K$ of
  values $k$.  For any two sequences
  $s1$ and $s2$, $s1 = s2 \Rightarrow f(s1) = f(s2)$, $s1 \ne s2 \simeq&gt; f(s1) \ne f(s2)$.  </p>
  
  <p>A commutative $g(f(s_1), f(s_2))$
  gives $|K1 = f(s_1) \cap K2 = f(s_2)|$
  which decreases linearly with each
  difference in $s_1$ from $s_2$. 
  Differences being additional,
  ommitted, or replaced elements. 
  Additions and omissions should
  conceptually score a unit $u$ of
  difference.  A replaced element having a
  difference score of somewhere between
  $u$ and $2u$ probably $\sqrt2u$.</p>
  
  <p>Length of $k$, $n$ is not specified
  and could be fixed or variable;
  however, a small $1/n$ is desirable.</p>
</blockquote>

<p>I've come up with an algorithm, illustrated below, which attempts to measure a string not by character position, but by the counts of distinct characters before and after each index in the string.  Each collection of character counts is a <code>table</code>.  (For single-byte encoded strings,) <code>tables</code> are considered coordinate points in a 256-dimensional space - points between which distances can be calculated.  <code>atoms</code> are pairs of these points - distances between which are the greater distance between their component pairs of points.  A string of length $n$ yields $n$ <code>atoms</code>.</p>

<p>In this way, a string's representation is transformed from an ordered sequence of characters into an unordered set of <code>atoms</code>.  The comparison of strings could be performed by mapping the <code>atoms</code> of one string to the <code>atoms</code> of another by minimum <code>atom</code>-distance.  The worst remaining distance becomes the similarity score for the strings, lower scores (to 0) indicate a better match.</p>

<p>This algorithm may be known or it may be flawed.  Exact matches return 0.  The smallest typo gives 1.  Worse typos, casually, give higher values.  This algorithm's performance degrades exponentially with longer strings, but that would be acceptable for short sequences like pass phrases.</p>

<p>But worst of all, it won't work for a Fuzzy Vault because though the atoms are free of relative ordering, their values are still very much intertwined.  Single typos can affect all atoms (even if only minimally).  And Fuzzy Vault keys require measurements to be independent such that the number of mismatched values are proportional to the number of errors.</p>

<p>But what could work?  It seems odd to me that measurements of body parts and voice could all be used for this purpose, but not something simple like pass phrases!</p>

<p>To the extent that it is possible in biometrics (are width and height of a face really independent?), I assume it would be an important property of a solution that each metric should be independent of other metrics and not constrain the practical atom-set-space to within crackable limits.  The is, any combination of "atoms" must be equally likely and not constrained by biases in the pass-phrase language.</p>

<pre><code>table : dict&lt;char, int&gt; // to store non-zero character counts
atom : (table, table) // a pair of tables per character in a string

getAtom(s : string, i : index) : atom =
{
  before = s.take(i).groupBy(c =&gt; c).select(g =&gt; (g.key, g.count())); // ex (a 3, B 1, n 2);
  after = s.skip(i).groupBy(c =&gt; c).select(g =&gt; (g.key, g.count())); // ex (a 1, b 1, o 1, t 1);

  return (before, after);
}

atomDistance(a : atom, b : atom) : int =
{
  beforeCoefficients = a.before.keys.concat(b.before.keys).distinct();
  afterCoefficients = a.after.keys.concat(b.after.keys).distinct();

  beforeDist = Sqrt(beforeCoefficients.sum(c =&gt; (a.before[c] - b.before[c]) ^ 2));
  afterDist = Sqrt(afterCoefficients .sum(c =&gt; (a.after[c] - b.after[c]) ^ 2));

  return Max(beforeDist, afterDist );
}

getAtoms(s : string) : set&lt;atom&gt;
{
  return [0 .. s.length()].select(i =&gt; i.getAtom(s, i));
}

compareSets(A : set&lt;atom&gt;, B : set&lt;atom&gt;)
{
  pairs = A.crossJoin(B).groupBy(ab =&gt; ab.a);
  bestMatchDistances = pairs.select(p =&gt; p.items.Min(m =&gt; atomDistance(p.key, m)));
  return bestMatchDistances.Max();
}
</code></pre>

<p><em>compareSets would not be used in the fuzzy vault implementation, but I feel that it helps complete the example.  I know there are flaws in this algorithm's consistency, I'm not trying to discover them.</em></p>

CC BY-SA 2.5
2010-12-02T19:18:38.490Z
please tag with fuzzy-vault
Jason Kleban
CC BY-SA 2.5
2010-12-02T20:12:00.607Z
maybe you could explain your algorithm in a little more detail ? it's a little cryptic
Suresh Venkat
CC BY-SA 2.5
2010-12-02T21:52:19.727Z
Ok, I added some more detail.  I fudged the syntax for brevity, but hopefully its clear (and accurate).
Jason Kleban
CC BY-SA 2.5
2010-12-03T07:11:30.657Z
actually I didn't mean code. I meant an algorithm.
Suresh Venkat
CC BY-SA 2.5
2010-12-03T17:49:14.153Z
Hi Suresh, I'm struggling here.  1) The algorithm is probably garbage.  It might be a useful starting point, somehow, but I don't have any questions about the algorithm.  2) I felt that the code, which isn't any real language, describes the algorithm well and succinctly.  ...  I appreciate the time you've taken on this question at all and you're obviously a well-respected member of this TCS community.  I'd like to make this question as accessible as possible, but I fear I'm just making it more confusing.  If you haven't lost interest, can you guide me more about what you need from me?  Thanks.
Jason Kleban
CC BY-SA 2.5
2010-12-03T22:38:59.423Z
I guess what I'd like is this: can you precisely define the input to the problem, and the desired output ? the way one might do for sorting "take n numbers and output them in nondecreasing order" etc. In your case, it sounds like the FV is a kind of hash function that's tolerant to small changes ? so you want a hash function so that all items that are within some distance of each other are hashed together ? and then the question is what distance is suitable ?
Suresh Venkat
CC BY-SA 2.5
2010-12-04T15:30:09.070Z
I tried again.  The final distance is not to be computed.  What this function does is convert a single big fact into many independent facts for use as a fuzzy key.  Fuzzy keys exhibit differences much like the original strings and can be compared.  The "suitable distance" would be some selectable fuzziness in increments of 1/n.
Jason Kleban
CC BY-SA 2.5
2010-12-05T14:15:23.217Z
@uosɐſ, I've read through what you've written, but I can't find the question. It's unclear what's being asked... As in, if someone posted an answer in response, it would be difficult for me to recognize whether it was correct (or not) or what you wanted (or not). Are you looking for hashing functions with certain properties as answers?
Daniel Apon
CC BY-SA 2.5
2010-12-05T16:13:22.810Z
@Daniel, thanks for taking the time.  I've reorganized, called out answer criteria.
Jason Kleban
CC BY-SA 2.5
2010-12-05T17:08:56.480Z
What does "s1=s2⇒>f(s1)=f(s2), s1≠s2≃>>f(s1)≠f(s2)." mean?
Jeffε
CC BY-SA 2.5
2010-12-05T17:58:08.857Z
@JeffE string 1 equaling string 2 implies that the hash of string 1 equals the hash of string 2.  string 1 not equaling string 2 (mostly) implies that the hash of string 1 does not equal the has of string 2.  "(mostly)" because there may be multiple strings that map to the same hash, but it shouldn't be by similar strings.  Is there a better way to write that?
Jason Kleban
CC BY-SA 2.5
2010-12-05T22:37:39.453Z
oh, and the formatting got screwed up!
Jason Kleban
CC BY-SA 2.5
2010-12-05T22:42:36.150Z
What is $|K1 = f(s_1) \cap K2 = f(s_2)|$ supposed to imply ? what does it even mean to intersect K1 and K2 ?
Suresh Venkat
CC BY-SA 2.5
2010-12-05T22:49:19.250Z
K1 and K2 are sets of values.  The count of the intersecting values of the set is what matters.  Fuzzy Vaults give up the secret if you know enough of the components of the key.
Jason Kleban
CC BY-SA 2.5
2010-12-05T22:55:42.847Z
but you're still not explaining what properties you want f to have if $s_1$ and $s_2$ are not the same. it sounds like you want the hash values to be VERY FAR apart if the two strings are similar, but they can be similar if the strings are far apart. Is that correct ?
Suresh Venkat
CC BY-SA 2.5
2010-12-05T23:13:42.497Z
No, if the strings are similar but not equal, then the count $|K1 = f(s1) \cap K2 = f(s2)|$ should be high, nearly $n$.  If the strings are very different, the count of the intersection should be near 0.  If $n$ is shorter than the string, it is possible for wildly different values to map to the same K, but let's ignore that.  $f()$ generates the key and is the goal.  $g()$ is just a test, a stand-in for the Fuzzy Vault algorithm.
Jason Kleban
CC BY-SA 2.5
2010-12-06T01:53:14.927Z
What does "(mostly) implies" mean?  Either A implies B or it doesn't.  Or you mean something else, like "If A, then the probability of B is high." (But then what distribution?)
Jeffε
<cr.crypto-security><formal-modeling><metrics>
Extracting Independent Information About Sequences
Jason Kleban
# Extracting Independent Information About Sequences

(Asked by: username_0 on 2010-12-02)

Related to this question, but asked in a different way.
For the purposes of a text-based implementation of a fuzzy vault, what metrics can we take on Sequences that are isolated such that the set of measured values is resilient to "small changes"?  More changes would mean more members of the set would be different.

Specifically, is there a hash function
  with these properties as described
  below?  Next best thing to a working
  algorithm would be clarifying
  discussion about why such a function
  should be feasible or why such a
  function cannot exist.
Below contains background, a
  description of such a hash function
  (not implemented), and an
  implementation of an algorithm that
  seems to have some, but not all of the
  desired properties.

Fuzzy Vaults in biometrics work because the included measurements of, say, the face are independent.  The width of two faces could match even if their heights don't.  If we could collect a set of independent measurements about a string, a pass phrase, then we might implement a Fuzzy Vault that would allow similar phrases, within a tolerance, to reveal a secret.
From my reading, Fuzzy Vaults work with intersecting sets of exactly matching values, not sets of similar values.  Typos in a pass phrase would be some combination of omitted characters, additional characters, and replaced characters.  If we could restrict the errors made to only replaced characters, each character's index could be used - the character value of each index would be components of the Fuzzy Key.  A single typo would only affect a single key component.  Unfortunately, because of inserted and deleted characters affect the offsets of the remainder of the sequence, single typos can dramatically affect the key components of later in the sequence.

Here's an attempt at formulating the
  challenge:
Define $f(s)$ as a hashing transform
  of any sequence $s$ into a set $K$ of
  values $k$.  For any two sequences
  $s1$ and $s2$, $s1 = s2 \Rightarrow f(s1) = f(s2)$, $s1 \ne s2 \simeq> f(s1) \ne f(s2)$.  
A commutative $g(f(s_1), f(s_2))$
  gives $|K1 = f(s_1) \cap K2 = f(s_2)|$
  which decreases linearly with each
  difference in $s_1$ from $s_2$. 
  Differences being additional,
  ommitted, or replaced elements. 
  Additions and omissions should
  conceptually score a unit $u$ of
  difference.  A replaced element having a
  difference score of somewhere between
  $u$ and $2u$ probably $\sqrt2u$.
Length of $k$, $n$ is not specified
  and could be fixed or variable;
  however, a small $1/n$ is desirable.

I've come up with an algorithm, illustrated below, which attempts to measure a string not by character position, but by the counts of distinct characters before and after each index in the string.  Each collection of character counts is a table.  (For single-byte encoded strings,) tables are considered coordinate points in a 256-dimensional space - points between which distances can be calculated.  atoms are pairs of these points - distances between which are the greater distance between their component pairs of points.  A string of length $n$ yields $n$ atoms.
In this way, a string's representation is transformed from an ordered sequence of characters into an unordered set of atoms.  The comparison of strings could be performed by mapping the atoms of one string to the atoms of another by minimum atom-distance.  The worst remaining distance becomes the similarity score for the strings, lower scores (to 0) indicate a better match.
This algorithm may be known or it may be flawed.  Exact matches return 0.  The smallest typo gives 1.  Worse typos, casually, give higher values.  This algorithm's performance degrades exponentially with longer strings, but that would be acceptable for short sequences like pass phrases.
But worst of all, it won't work for a Fuzzy Vault because though the atoms are free of relative ordering, their values are still very much intertwined.  Single typos can affect all atoms (even if only minimally).  And Fuzzy Vault keys require measurements to be independent such that the number of mismatched values are proportional to the number of errors.
But what could work?  It seems odd to me that measurements of body parts and voice could all be used for this purpose, but not something simple like pass phrases!
To the extent that it is possible in biometrics (are width and height of a face really independent?), I assume it would be an important property of a solution that each metric should be independent of other metrics and not constrain the practical atom-set-space to within crackable limits.  The is, any combination of "atoms" must be equally likely and not constrained by biases in the pass-phrase language.
table : dict // to store non-zero character counts
atom : (table, table) // a pair of tables per character in a string

getAtom(s : string, i : index) : atom =
{
  before = s.take(i).groupBy(c => c).select(g => (g.key, g.count())); // ex (a 3, B 1, n 2);
  after = s.skip(i).groupBy(c => c).select(g => (g.key, g.count())); // ex (a 1, b 1, o 1, t 1);

  return (before, after);
}

atomDistance(a : atom, b : atom) : int =
{
  beforeCoefficients = a.before.keys.concat(b.before.keys).distinct();
  afterCoefficients = a.after.keys.concat(b.after.keys).distinct();

  beforeDist = Sqrt(beforeCoefficients.sum(c => (a.before[c] - b.before[c]) ^ 2));
  afterDist = Sqrt(afterCoefficients .sum(c => (a.after[c] - b.after[c]) ^ 2));

  return Max(beforeDist, afterDist );
}

getAtoms(s : string) : set
{
  return [0 .. s.length()].select(i => i.getAtom(s, i));
}

compareSets(A : set, B : set)
{
  pairs = A.crossJoin(B).groupBy(ab => ab.a);
  bestMatchDistances = pairs.select(p => p.items.Min(m => atomDistance(p.key, m)));
  return bestMatchDistances.Max();
}

compareSets would not be used in the fuzzy vault implementation, but I feel that it helps complete the example.  I know there are flaws in this algorithm's consistency, I'm not trying to discover them.

**Tags:** cr.crypto-security, formal-modeling, metrics
> **Comments:**
> **username_0**: please tag with fuzzy-vault  
> **username_1**: maybe you could explain your algorithm in a little more detail ? it's a little cryptic  
> **username_0**: Ok, I added some more detail.  I fudged the syntax for brevity, but hopefully its clear (and accurate).  
> **username_1**: actually I didn't mean code. I meant an algorithm.  
> **username_0**: Hi Suresh, I'm struggling here.  1) The algorithm is probably garbage.  It might be a useful starting point, somehow, but I don't have any questions about the algorithm.  2) I felt that the code, which isn't any real language, describes the algorithm well and succinctly.  ...  I appreciate the time you've taken on this question at all and you're obviously a well-respected member of this TCS community.  I'd like to make this question as accessible as possible, but I fear I'm just making it more confusing.  If you haven't lost interest, can you guide me more about what you need from me?  Thanks.  
> **username_1**: I guess what I'd like is this: can you precisely define the input to the problem, and the desired output ? the way one might do for sorting "take n numbers and output them in nondecreasing order" etc. In your case, it sounds like the FV is a kind of hash function that's tolerant to small changes ? so you want a hash function so that all items that are within some distance of each other are hashed together ? and then the question is what distance is suitable ?  
> **username_0**: I tried again.  The final distance is not to be computed.  What this function does is convert a single big fact into many independent facts for use as a fuzzy key.  Fuzzy keys exhibit differences much like the original strings and can be compared.  The "suitable distance" would be some selectable fuzziness in increments of 1/n.  
> **username_2**: @uosɐſ, I've read through what you've written, but I can't find the question. It's unclear what's being asked... As in, if someone posted an answer in response, it would be difficult for me to recognize whether it was correct (or not) or what you wanted (or not). Are you looking for hashing functions with certain properties as answers?  
> **username_0**: @Daniel, thanks for taking the time.  I've reorganized, called out answer criteria.  
> **username_3**: What does "s1=s2⇒>f(s1)=f(s2), s1≠s2≃>>f(s1)≠f(s2)." mean?  
> **username_0**: @JeffE string 1 equaling string 2 implies that the hash of string 1 equals the hash of string 2.  string 1 not equaling string 2 (mostly) implies that the hash of string 1 does not equal the has of string 2.  "(mostly)" because there may be multiple strings that map to the same hash, but it shouldn't be by similar strings.  Is there a better way to write that?  
> **username_0**: oh, and the formatting got screwed up!  
> **username_1**: What is $|K1 = f(s_1) \cap K2 = f(s_2)|$ supposed to imply ? what does it even mean to intersect K1 and K2 ?  
> **username_0**: K1 and K2 are sets of values.  The count of the intersecting values of the set is what matters.  Fuzzy Vaults give up the secret if you know enough of the components of the key.  
> **username_1**: but you're still not explaining what properties you want f to have if $s_1$ and $s_2$ are not the same. it sounds like you want the hash values to be VERY FAR apart if the two strings are similar, but they can be similar if the strings are far apart. Is that correct ?  
> **username_0**: No, if the strings are similar but not equal, then the count $|K1 = f(s1) \cap K2 = f(s2)|$ should be high, nearly $n$.  If the strings are very different, the count of the intersection should be near 0.  If $n$ is shorter than the string, it is possible for wildly different values to map to the same K, but let's ignore that.  $f()$ generates the key and is the goal.  $g()$ is just a test, a stand-in for the Fuzzy Vault algorithm.  
> **username_3**: What does "(mostly) implies" mean?  Either A implies B or it doesn't.  Or you mean something else, like "If A, then the probability of B is high." (But then what distribution?)  

---

## 1 answers

### Answer by username_4 on 2010-12-07. Score: 3 | Accepted answer

I'm not sure I fully grasp the question as posed, but it seems to me that the asker is looking for some kind of approximation of the Levenshtein distance metric. Perhaps the following reference might be of some use?

[Bar-Yosef, Ziv et al., "Approximating Edit Distance Efficiently", FOCS 2004](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.78.6784)

> In this section we describe our two sketching
> algorithms for solving gap edit distance problems. The underlying
> principle in both algorithms is the same: the two
> input strings have a small edit distance if and only if they
> share many sufficiently long substrings occurring at nearly
> the same position in both strings, and hence, the number
> of mismatching substrings provides an estimate of the edit
> distance. More formally, both algorithms map the inputs x
> and y into sets $T\_x$ and $T\_y$, respectively; these sets consist of pairs of the form ($\gamma$, i), where $\gamma$ is a sufficiently long substring
> and i is a special “encoding” of the position at which
> the substring begins. [...]
>
> This gives rise to a natural reduction from the task of estimating
> edit distance between x and y to that of estimating
> the Hamming distance between the characteristic vectors u
> and v of $T\_x$ and $T\_y$, respectively.

> **Comments:**
> **username_0**: This is a good answer.  I think the paper you've referenced is very applicable.  Especially in leading me full circle back to my selected answer of my original question.  I thought I was going in a different direction, but upon refinement, arrived at the same place.  I'll leave this open for the duration of the bounty in case there are additional perspectives.  
> **username_0**: I'm especially keen on the language of the sketch algorithms, which I think is more accurate to describe the hash algorithm.  

---

