¿Hay un hash continuo?

8

Preguntas:

¿Puede haber un hash (criptográficamente seguro) que conserva la topología de la información de {0,1}?

¿Podemos agregar un predicado de cercanía eficientemente computable que dado hk(x) y hk(y) (o y en sí) nos dice si yestá muy cerca dex (por ejemplo, la distancia de Levenshtein o la distancia de Hamming de x y y es menor que una constante fija c)?


Antecedentes:

Por topología de información en Σ Me refiero al espacio de topología con puntos Σ y con la base {xΣ:xΣ}.

Una buena manera de pensar sobre la topología es considerar los conjuntos abiertos como propiedades de puntos que son afirmables / verificables (es decir, si es cierto, se puede verificar / observar que es cierto). Con esto en mente, los conjuntos cerrados son propiedades refutables .

Una función f:ΣΣes continuo si la imagen inversa de los conjuntos abiertos está abierta. En nuestro caso esto significa que para todosyΣ, Ahi esta IΣ tal que

f1(yΣ)=xIxΣ.

Una buena manera de pensar sobre la topología de la información es mirarla como un árbol de cadenas binarias. Cada subárbol es un conjunto abierto de base (y se puede obtener otro conjunto abierto tomando una unión de conjuntos abiertos de base).

Esto a veces se denomina topología de información de cadenas porque cada punto en Σ puede considerarse como una aproximación finita a una secuencia / secuencia binaria. x aproximados y iff x es una subcadena inicial de y (xy) P.ej0011Σ es una aproximación a 00110 porque 001100110.

Y para la continuidad, si tomamos una secuencia {xi}i que se aproximan y convergen a la secuencia binaria y (pensar en y como una rama infinita en el árbol y xis como puntos en esa rama) entonces {f(xi)} converger a f(y),

f(y)=if(xi).
Kaveh
fuente
He olvidado todo lo que una vez supe sobre topología. ¿Sería posible desempacar lo que significa "preservar la topología de la información" en términos autónomos? Además, cuando dices criptográficamente seguro, ¿a qué versión de eso te refieres? ¿Te refieres a "se comporta como un oráculo al azar", o te refieres a "unidireccional y resistente a colisiones"?
DW
@DW Agregué alguna explicación, pero escribir eso me hizo notar que mi primera pregunta no está clara. Tengo que pensar un poco para aclararlo. La segunda pregunta parece estar bien.
Kaveh
1
El hash localmente sensible puede ser relevante. en.wikipedia.org/wiki/Locality-sensitive_hashing
zenna

Respuestas:

5

Para las funciones hash criptográficas modernas, no, no existe un predicado de cercanía computable de manera eficiente, suponiendo que la distribución en xTiene suficiente entropía. La intuición es que estas funciones hash están diseñadas para "no tener estructura", por lo que no admiten nada como esto.

En términos técnicos, las funciones hash criptográficas modernas se comportan "como un oráculo aleatorio". Para un oráculo aleatorio, no existe dicho predicado de cercanía: lo mejor que puede hacer es invertir la función hash y luego enumerar todas las cadenas cerradas y hacerlas hash. Como resultado, no hay forma de hacer esto para las funciones hash criptográficas modernas.

Heurísticamente, es posible diseñar una función hash personalizada que admite un predicado de cercanía eficiente y que es (aproximadamente) "lo más seguro posible" dado este hecho. Supongamos que las cadenas que vamos a hacer hash son de longitud fija. Supongamos que tenemos un buen código de corrección de errores, y dejemosD ser el algoritmo de decodificación (por lo que puede asignar una cadena de bits a una palabra de código cercana, si puede).

Para obtener un esquema simple pero imperfecto, imagine definir h(x)=SHA256(D(x)). Six,y son dos cadenas aleatorias que están lo suficientemente cerca, entonces hay una posibilidad decente de que h(x)=h(y). Six,y no están cerca, entonces h(x) no se parecerá en nada h(y), y no obtendremos información más allá del hecho de que x,yNo están cerca. Esto es simple. Sin embargo, también es imperfecto. Hay muchos paresx,y que están cerca pero donde no podemos detectar este hecho h(x),h(y) (por ejemplo, porque la función de decodificación D falla).

Heurísticamente, parece posible mejorar esta construcción. En tiempo de diseño, elija cadenas de bits aleatoriasr1,,rk. Ahora, defina la siguiente función hash:

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

Ahora si x,y están lo suficientemente cerca, es probable que exista i tal que D(xri)=D(yri), y por lo tanto h(x)i=h(y)i. Esto sugiere inmediatamente un predicado de cercanía: sih(x) partidos h(y) en cualquiera de sus k componentes, entonces x,yestán cerca; de lo contrario, infiera que no están cerca.

Si además desea resistencia a la colisión, una construcción simple es la siguiente: deje h1()ser una función hash con un predicado de cercanía; entoncesh(x)=(h1(x),SHA256(x)) es resistente a colisiones (cualquier colisión para esto también es una colisión para SHA256) y tiene un predicado de cercanía (simplemente use el predicado de cercanía para h1) Puedes dejarh1() ser la función hash definida anteriormente.

Esto es todo por la distancia de Hamming. Editar distancia es probablemente significativamente más difícil.

Al proponer la construcción anterior, me inspiré en el siguiente artículo:

Ari Juels, Martin Wattenberg. Un esquema de compromiso difuso .

Ari Juels, Madhi Sudhan. Un esquema de bóveda difusa . Diseños, códigos y criptografía 38 (2): 237-257, 2006.

Por cierto: en criptografía, las funciones hash no están tecleadas. Si quería algo con clave, es posible que desee echar un vistazo a las funciones pseudoaleatorias.

DW
fuente