Is there a continuous hash?

Question

Questions:

Can there be a (cryptographically secure) hash that preserves the information topology of $\{0,1\}^{*}$?

Can we add an efficiently computable closeness predicate which given $h_k(x)$ and $h_k(y)$ (or $y$ itself) tells us if $y$ is very close to $x$ (e.g. the Levenshtein distance or Hamming distance of $x$ and $y$ is less than a fixed constant $c$)?

---

Background:

By information topology on $\Sigma^*$ on I mean the topology space with points $\Sigma^*$ and with the base $\{x\Sigma^* : x \in \Sigma^* \}$.

A nice way to think about topology is considering open sets as properties of points which are affirmable/verifiable (i.e. if it is true, it can be verify/observe that it is true). With this in mind, closed sets are refutable properties.

A function $f:\Sigma^* \to \Sigma^*$ is continuous if the inverse image of opens sets are open. In our case this means that for all $y \in \Sigma^*$, there is $I \subseteq \Sigma^*$ such that $$f^{-1}(y\Sigma^*) = \bigcup_{x\in I} x\Sigma^*. $$

A nice way to think about the information topology is looking at it as a tree of binary strings. Each subtree is a an base open set (and other open set can be obtained from taking a union of base open sets).

This is sometimes referred to as information topology of strings because each point in $\Sigma^*$ can be considered as a finite approximation to a binary string/sequence. $x$ approximates $y$ iff $x$ is an initial substring of $y$ ($x \sqsubseteq y$). E.g. $0011\Sigma^*$ is an approximation to $00110^*$ because $0011 \subseteq 00110^*$.

And for continuity, if we take a sequence $\{x_i\}_i$ which approximate and converge to binary sequence $y$ (think of $y$ as an infinite branch in the tree and $x_i$s as points on that branch) then $\{f(x_i)\}$ converge to $f(y)$, $$f(y) = \bigsqcup_i f(x_i).$$

Answer 1

For modern cryptographic hash functions, no, there is no efficiently computable closeness predicate, assuming the distribution on $x$ has sufficient entropy. The intuition is that these hash functions are designed to "have no structure", so they don't admit anything like this.

In technical terms, modern cryptographic hash functions behave "like a random oracle". For a random oracle, there is no such closeness predicate: the best you can do appears to be to invert the hash function and then enumerate all close strings and hash them. As a result, there's no way to do this for modern cryptographic hash functions.

Heuristically, it does possible to design a custom hash function which does admit an efficiently closeness predicate, and which is (roughly) "as secure as possible" given this fact. Let's assume the strings we are going to hash are of fixed length. Suppose we have a good error-correcting code, and let $D$ be the decoding algorithm (so it maps a bit-string to a nearby codeword, if it can).

To get a simple but imperfect scheme, imagine defining $h(x) = \text{SHA256}(D(x))$. If $x,y$ are two random strings that are sufficiently close, then there is a decent chance that $h(x)=h(y)$. If $x,y$ are not close, then $h(x)$ will look nothing like $h(y)$, and we'll get no information beyond the fact that $x,y$ are not close. This is simple. However, it is also imperfect. There are many pairs $x,y$ that are close but where we can't detect this fact from $h(x),h(y)$ (e.g., because the decoding function $D$ fails).

Heuristically, it looks possible to improve this construction. At design time, choose random bit-strings $r_1,\dots,r_k$. Now, define the following hash function:

$$h(x) = (\text{SHA256}(D(x \oplus r_1), \dots, \text{SHA256}(D(x \oplus r_k)).$$

Now if $x,y$ are sufficiently close, it is likely that there exists $i$ such that $D(x \oplus r_i) = D(y \oplus r_i)$, and thus $h(x)_i = h(y)_i$. This immediately suggests a closeness predicate: if $h(x)$ matches $h(y)$ in any of its $k$ components, then $x,y$ are close; otherwise, infer that they are not close.

If you additionally want collision resistance, a simple construction is the following: let $h_1(\cdot)$ be a hash function with a closeness predicate; then $h(x) = (h_1(x), \text{SHA256}(x))$ is collision-resistant (any collision for this is also a collision for SHA256) and has a closeness predicate (simply use the closeness predicate for $h_1$). You can let $h_1(\cdot)$ be the hash function defined above.

This is all for Hamming distance. Edit distance is probably significantly harder.

In coming up with the above construction, I was inspired by the following paper:

Ari Juels, Martin Wattenberg. A Fuzzy Commitment Scheme.

Ari Juels, Madhi Sudhan. A Fuzzy Vault Scheme. Designs, Codes, and Cryptography 38(2): 237-257, 2006.

Incidentally: in cryptography, hash functions are unkeyed. If you wanted a keyed thing, you might want to take a look at pseudorandom functions.