# Extracting Independent Information About Sequences

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<char, int> // 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<atom>
{
return [0 .. s.length()].select(i => i.getAtom(s, i));
}

compareSets(A : set<atom>, B : set<atom>)
{
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.

• please tag with fuzzy-vault – Jason Kleban Dec 2 '10 at 19:18
• maybe you could explain your algorithm in a little more detail ? it's a little cryptic – Suresh Venkat Dec 2 '10 at 20:12
• Ok, I added some more detail. I fudged the syntax for brevity, but hopefully its clear (and accurate). – Jason Kleban Dec 2 '10 at 21:52
• actually I didn't mean code. I meant an algorithm. – Suresh Venkat Dec 3 '10 at 7:11
• 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 Dec 3 '10 at 22:38

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

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.

• 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 Dec 7 '10 at 22:38
• I'm especially keen on the language of the sketch algorithms, which I think is more accurate to describe the hash algorithm. – Jason Kleban Dec 7 '10 at 22:41