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.
