Ataque cuántico en funciones hash

La línea de preguntas está inspirada en el truco elegido en la Sección 4 de la versión en PDF del documento Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding (Ambainis et al. , 2014) . Diapositivas disponibles aquí . No sigo completamente el argumento allí, así que tal vez me perdí algo importante, pero aquí está mi interpretación de su truco.

Considere una función hash clásica que es resistente a la colisión, es decir, es computacionalmente difícil de encontrar H (x) = H (x ') \ land x \ neq x' . Deseamos codificar un compromiso de un mensaje usando esta función hash. Es decir, tomo un mensaje my concateno algo de aleatoriedad u al final de modo que genere un compromiso c = H (m \ Vert u) . Cuando se me pide que demuestre mi compromiso, no puedo encontrar un par diferente (m ', u') tal que c = H (m '\ Vert u') debido a la naturaleza libre de colisiones de los hashes. Mi única opción es abrir el compromiso con (m, u) .$x \rightarrow H(x)$$H(x) = H(x') \land x\neq x'$$m$$u$$c = H(m\Vert u)$$(m',u')$$c = H(m'\Vert u')$$(m,u)$

Ahora, atacamos este protocolo con un circuito cuántico de la función hash.

1. Tome una superposición sobre todas las entradas posibles $x_i$ y consulte la función hash con este estado para obtener el estado $\vert\psi\rangle = \sum_{i}\vert x_i\rangle\vert H(x_i)\rangle$ .

2. Mida el segundo registro para obtener un compromiso aleatorio. La medición selecciona aleatoriamente $c = H(x_i)$ para algunos $i$ . El primer registro tiene entonces $\vert\phi\rangle = \sum_j \vert x_j\rangle$ tal que $\forall j, c = H(x_j)$ .

3. Me gustaría abrir el compromiso con algunos $m'$ que me da el oponente. Use la búsqueda de Grover en el primer registro para encontrar una $x_{\text{sol}}$ del estado $\vert\phi\rangle = \sum_j\vert x_j\rangle$ que satisfaga alguna propiedad especial. Específicamente, la propiedad especial es que la primera $|m'|$bits de $x_{\text{sol}}$ son $m'$ . Es decir, buscaré para encontrar $x_{\text{sol}} = m'\Vert u'$ .

El uso de las diapositivas publicado anteriormente (Diapositiva 8) y su terminología, es eficiente para encontrar un valor de la intersección de dos conjuntos y . Aquí es el conjunto de todas tal que y es el conjunto de todas donde la primeralos bits de son exactamente .$x$$S$$P$$S$$x$$H(x) = c$$P$$x$$|m'|$$x$$m'$

Mis preguntas sobre este ataque son las siguientes:

1. ¿Tengo la idea básica del ataque correcta? Si está equivocado, ¡ignora el resto de la publicación!

2. ¿Cuántos elementos hay en la superposición después de comprometernos con una cierta ? Para poder abrir el compromiso con cualquier mensaje, parece que debería tener elementos (el tamaño del rango de la función hash). Pero esto es demasiado grande.$\vert\phi\rangle$$c$$O(N)$

3. La velocidad de la búsqueda de Grover, esto está relacionado con el punto anterior, es la otra cosa. ¿No sería la complejidad computacional de buscar en una superposición tan grande como tratar de adivinar una preimagen para una salida dada de la función hash ya que uno tiene que buscar en todo el ? En este caso, ¿dónde está la ventaja?$\vert\phi\rangle$$u$

Estoy buscando la intuición más que las pruebas matemáticas, por lo que cualquier ayuda es muy apreciada.

¿Tengo la idea básica del ataque correcta? Si está equivocado, ¡ignora el resto de la publicación!

Principalmente. De la forma en que lo describe, obtendrá el estado , pero no podrá realizar la transformación unitaria . Pero en el paso 3, cuando ejecuta Grover en estado , en realidad necesita aplicar como parte del algoritmo de Grover. La razón es la siguiente: Por lo general, Grover se presenta como un algoritmo que las búsquedas de un valor que satisface un predicado . En este caso, el algoritmo de Grover primero inicializa el estado en$\lvert\phi\rangle$$I-\lvert\phi\rangle\langle\phi\rvert$$\lvert\phi\rangle$$I-\lvert\phi\rangle\langle\phi\rvert$$x\in\{0,1\}^n$$P$$\lvert\phi\rangle:=\sum_{x\in\{0,1\}^n}2^{-n/2}\lvert x\rangle$. Y, durante su ciclo principal, aplica el operador de volteo . Ese operador es bastante fácil de construir si , por lo que normalmente no es mencionado como un requisito del algoritmo. Sin embargo, en lugar de buscar , se podría buscar para algún conjunto . (Después de todo, no hay nada especial en las cadenas de bits de longitud .) Luego, debe cambiar la descripción de Grover: El estado inicial será , y necesitamos aplicar$I-\lvert\phi\rangle\langle\phi\rvert$$\lvert\phi\rangle=\sum_{x\in\{0,1\}^n}2^{-n/2}\lvert x\rangle$$x\in\{0,1\}^n$$x\in X$$X$$n$$\lvert\phi\rangle=\sum_{x \in X}2^{-\lvert X\rvert/2}\lvert x\rangle$$I-\lvert\phi\rangle\langle\phi\rvert$durante el ciclo principal. Para muchos conjuntos (por ejemplo, números módulo ) será bastante fácil construir e . Sin embargo, en el caso general, puede ser que sea difícil construir cualquiera de ellos. En su descripción del algoritmo, tenemos una situación similar. A saber, para algunos fijos . Pero para ese conjunto , no hay forma de construir o . Es por eso que su algoritmo no funciona (pero aún da la idea correcta). En cambio, en el documento que cita, ambos$X$$N$$\lvert\phi\rangle$$I-\lvert\phi\rangle\langle\phi\rvert$$X=\{x:H(x)=c\}$$c$$X$$\lvert\phi\rangle$$I-\lvert\phi\rangle\langle\phi\rvert$$\lvert\phi\rangle$y son proporcionados por oráculos especiales construidos solo para este propósito. Usando esos oráculo, puede ejecutar el algoritmo de Grovers en el estado .$I-\lvert\phi\rangle\langle\phi\rvert$$\lvert\phi\rangle$

¿Cuántos elementos hay en la superposición después de que nos comprometemos con una cierta ?$\lvert\phi\rangle$$c$

Esto dependerá de los parámetros que elija. Esperamos aproximadamente si es el tamaño del dominio y el tamaño de la gama de . Para que las cosas sean interesantes, debe elegir para que exista exponencialmente muchos elementos en la superposición (y al menos para que cada mensaje sea posible). Sin embargo, supongo que la razón por la que se está preguntando acerca de esto es porque cree que el número de elementos debería ser pequeño para que Grover funcione, lo cual no es el caso, vea a continuación:$M/N$$M$$N$$H$$M\gg N$$2^{\lvert m\rvert}$

La velocidad de la búsqueda de Grover: este es el problema principal y no estoy seguro de cómo funciona realmente su truco. ¿No sería la complejidad computacional lo mismo que tratar de adivinar una imagen previa para una salida dada de la función hash ya que uno tiene que buscar en todo el u? En este caso, ¿dónde está la ventaja?

Aquí parece mentir un error. Recuerda mis explicaciones sobre el algoritmo de Grover al comienzo de esta respuesta. Grover búsquedas algunos , satisfaciendo algún predicado . En nuestro caso, puede ser enorme ( elementos ) porque es el conjunto de todas las preimágenes de . Pero eso no importa. Recuerde que el Grover original funciona en que también es enorme, pero funciona rápido siempre que busquemos alguna que tenga alguna propiedad común . Por ejemplo, si buscamos usando Grover que satisfaga ese (el predicado$x\in X$$P$$X$$M/N$$c$$\{0,1\}^n$$x\in\{0,1\}^n$$P$$x\in\{0,1\}^n$$33\mid x$$P$), entonces tenemos que hay muchas que satisfacen , cada 33. ¡ satisface! Y el tiempo de ejecución será algo así como . Entonces, como regla general, si un predicado se satisface para cada -ésimo elemento de , entonces el algoritmo de Grover que busca que satisface toma aproximadamente pasos. ¡Aquí no importa qué conjunto sea ​​o qué tan grande sea! (Siempre que tengamos una manera de construir e para este conjunto$x$$P$$x$$\sqrt{33}$$P$$i$$X$$x\in X$$P$$\sqrt i$$X$$\lvert\phi\rangle$$I-\lvert\phi\rangle\langle\phi\rvert$$X$.) Ahora, en la configuración que describe, . Y es el predicado que dice que comienza con . Para analizar el tiempo de ejecución del algoritmo de Grover en este caso, que no se preocupan por , pero necesitamos saber con qué frecuencia un elemento satisface . Eso es fácil: cada elemento sí. Por lo tanto, el tiempo de ejecución de Grover será . Esto es un problema si es largo, pero si es, por ejemplo, solo un poco, entonces esto funciona bien. Por ejemplo, si usamos la función hash para enviar mensajes de un bit, podemos abrir el compromiso a cualquier valor de$X=\{x:H(x)=c\}$$P$$x$$m'$$X$$P$$2^{\lvert m'\rvert}$$O(\sqrt{2^{\lvert m'\rvert}})$$m'$$m'$$m'$.

Si desea un ejemplo donde es más largo, entonces necesita variar la construcción. Básicamente, usted se compromete en cada bit individualmente y concatena los compromisos. Luego, cada compromiso puede romperse utilizando el método descrito anteriormente, y debe ejecutar el algoritmo veces.$m'$$\lvert m'\rvert$