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).$$
Is there a continuous hash?
complexity theory;cryptography;hash;string metrics;topology