Existe um hash contínuo?

Questões:

Pode haver um hash (criptograficamente seguro) que preserva a topologia de informações de $\{0,1\}^{*}$?

Podemos adicionar um predicado de proximidade eficientemente computável que, dado $h_k(x)$ e $h_k(y)$ (ou $y$ próprio) nos diz se $y$está muito perto de$x$ (por exemplo, a distância de Levenshtein ou distância de Hamming de $x$ e $y$ é menor que uma constante fixa $c$)?

Fundo:

Por topologia de informações em $\Sigma^*$ em eu quero dizer o espaço de topologia com pontos $\Sigma^*$ e com a base $\{x\Sigma^* : x \in \Sigma^* \}$.

Uma boa maneira de pensar em topologia é considerar conjuntos abertos como propriedades de pontos que são afirmados / verificáveis (ou seja, se for verdade, pode-se verificar / observar que é verdade). Com isso em mente, conjuntos fechados são propriedades refutáveis .

Uma função $f:\Sigma^* \to \Sigma^*$é contínuo se a imagem inversa de conjuntos abertos estiver aberta. No nosso caso, isso significa que, para todos$y \in \Sigma^*$, Há sim $I \subseteq \Sigma^*$ de tal modo que

Uma boa maneira de pensar sobre a topologia da informação é vê-la como uma árvore de cadeias binárias. Cada subárvore é um conjunto aberto de base (e outro conjunto aberto pode ser obtido através da união de conjuntos abertos de base).

Às vezes, isso é chamado de topologia de informações de cadeias, porque cada ponto $\Sigma^*$ pode ser considerado como uma aproximação finita de uma sequência / sequência binária. $x$ aproxima $y$ iff $x$ é uma substring inicial de $y$ ($x \sqsubseteq y$) Por exemplo$0011\Sigma^*$ é uma aproximação para $00110^*$ Porque $0011 \subseteq 00110^*$.

E para continuidade, se dermos uma sequência $\{x_i\}_i$ que aproximam e convergem para sequência binária $y$ (Imagine $y$ como um galho infinito na árvore e $x_i$s como pontos nesse ramo) então $\{f(x_i)\}$ convergir para $f(y)$,

Para funções hash criptográficas modernas, não, não há predicado de proximidade computável com eficiência, assumindo a distribuição em $x$tem entropia suficiente. A intuição é que essas funções de hash são projetadas para "não ter estrutura", para que não admitam nada assim.

Em termos técnicos, as funções hash criptográficas modernas se comportam "como um oráculo aleatório". Para um oráculo aleatório, não existe esse predicado de proximidade: o melhor que você pode fazer é inverter a função hash e, em seguida, enumerar todas as strings próximas e as hash. Como resultado, não há como fazer isso para funções hash criptográficas modernas.

Heuristicamente, é possível projetar uma função de hash personalizada que admita um predicado de proximidade eficiente e que é (aproximadamente) o mais seguro possível, considerando esse fato. Vamos supor que as strings que vamos hash tenham comprimento fixo. Suponha que tenhamos um bom código de correção de erros e permita$D$ seja o algoritmo de decodificação (para mapear uma cadeia de bits para uma palavra de código próxima, se possível).

Para obter um esquema simples, mas imperfeito, imagine definir $h(x) = \text{SHA256}(D(x))$. E se$x,y$ são duas seqüências aleatórias suficientemente próximas, então há uma chance decente de $h(x)=h(y)$. E se$x,y$ não estão perto, então $h(x)$ não será nada parecido $h(y)$, e não obteremos informações além do fato de que $x,y$não estão perto. Isto é simples. No entanto, também é imperfeito. Existem muitos pares$x,y$ que estão próximos, mas onde não podemos detectar esse fato $h(x),h(y)$ (por exemplo, porque a função de decodificação $D$ falha).

Heuristicamente, parece possível melhorar essa construção. Em tempo de design, escolha seqüências de bits aleatórias$r_1,\dots,r_k$. Agora, defina a seguinte função de hash:

Agora se $x,y$ suficientemente perto, é provável que exista $i$ de tal modo que $D(x \oplus r_i) = D(y \oplus r_i)$e assim $h(x)_i = h(y)_i$. Isso sugere imediatamente um predicado de proximidade: se$h(x)$ fósforos $h(y)$ em qualquer um de seus $k$ componentes, então $x,y$são próximos; caso contrário, deduza que eles não estão próximos.

Se você deseja adicionalmente resistência à colisão, uma construção simples é a seguinte: deixe $h_1(\cdot)$ser uma função hash com um predicado de proximidade; então$h(x) = (h_1(x), \text{SHA256}(x))$ é resistente a colisões (qualquer colisão para isso também é uma colisão para o SHA256) e tem um predicado de proximidade (basta usar o predicado de proximidade para $h_1$) Você pode deixar$h_1(\cdot)$ seja a função hash definida acima.

Isso é tudo para a distância de Hamming. A distância de edição é provavelmente significativamente mais difícil.

Ao apresentar a construção acima, fui inspirado pelo seguinte artigo:

Ari Juels, Martin Wattenberg. Um Esquema de Compromisso Difuso .

Ari Juels, Madhi Sudhan. Um esquema de cofre difuso . Designs, Codes and Cryptography 38 (2): 237-257, 2006.

Aliás: na criptografia, as funções de hash não são codificadas. Se você deseja algo com chave, pode dar uma olhada nas funções pseudo-aleatórias.