Preguntas:
¿Puede haber un hash (criptográficamente seguro) que conserva la topología de la información de ?
¿Podemos agregar un predicado de cercanía eficientemente computable que dado y (o en sí) nos dice si está muy cerca de (por ejemplo, la distancia de Levenshtein o la distancia de Hamming de y es menor que una constante fija )?
Antecedentes:
Por topología de información en Me refiero al espacio de topología con puntos y con la base .
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 es continuo si la imagen inversa de los conjuntos abiertos está abierta. En nuestro caso esto significa que para todos, Ahi esta tal que
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. aproximados iff es una subcadena inicial de () P.ej es una aproximación a porque .
Y para la continuidad, si tomamos una secuencia que se aproximan y convergen a la secuencia binaria (pensar en como una rama infinita en el árbol y s como puntos en esa rama) entonces converger a ,
Respuestas:
Para las funciones hash criptográficas modernas, no, no existe un predicado de cercanía computable de manera eficiente, suponiendo que la distribución enx Tiene 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 definirh(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,y No 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:
Ahora six,y están lo suficientemente cerca, es probable que exista i tal que D(x⊕ri)=D(y⊕ri) , 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,y está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: dejeh1(⋅) 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.
fuente