Existe um hash contínuo?

8

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 hk(x) e hk(y) (ou y próprio) nos diz se yestá muito perto dex (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 Σ em eu quero dizer o espaço de topologia com pontos Σ e com a base {xΣ:xΣ}.

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:ΣΣé contínuo se a imagem inversa de conjuntos abertos estiver aberta. No nosso caso, isso significa que, para todosyΣ, Há sim IΣ de tal modo que

f1(yΣ)=xIxΣ.

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 Σ 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 (xy) Por exemplo0011Σ é uma aproximação para 00110 Porque 001100110.

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

f(y)=Euf(xEu).
Kaveh
fonte
Esqueci tudo o que eu sabia sobre topologia. Seria possível descompactar o que significa "preservar a topologia da informação" em termos independentes? Além disso, quando você diz que é criptograficamente seguro, qual versão você quer dizer? Você quer dizer "se comporta como um oráculo aleatório" ou quer dizer "unidirecional e resistente a colisões"?
DW
@DW eu adicionei alguma explicação, mas escrever isso me faz perceber que minha primeira pergunta não é clara. Eu tenho que pensar um pouco para esclarecer isso. Segunda pergunta parece bem.
Kaveh
1
O hash sensível a localidade pode ser relevante. en.wikipedia.org/wiki/Locality-sensitive_hashing
zenna

Respostas:

5

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 xtem 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 permitaD 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)=SHA256(D(x)). E sex,y são duas seqüências aleatórias suficientemente próximas, então há uma chance decente de h(x)=h(y). E sex,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,ynão estão perto. Isto é simples. No entanto, também é imperfeito. Existem muitos paresx,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óriasr1,,rk. Agora, defina a seguinte função de hash:

h(x)=(SHA256(D(xr1),,SHA256(D(xrk)).

Agora se x,y suficientemente perto, é provável que exista Eu de tal modo que D(xrEu)=D(yrEu)e assim h(x)Eu=h(y)Eu. Isso sugere imediatamente um predicado de proximidade: seh(x) fósforos h(y) em qualquer um de seus k componentes, então x,ysã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 h1()ser uma função hash com um predicado de proximidade; entãoh(x)=(h1(x),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 h1) Você pode deixarh1() 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.

DW
fonte