Protocolos de Conocimiento Cero

cryptography
Autor/a

Diego Pedraza López

Fecha de publicación

1 de enero de 2018

Introducción

Supongamos que Víctor (con V de Verifier) quiere resolver un Sudoku. El Sudoku demuestra ser todo un desafío y decide pedirle ayuda a Peggy (con P de Prover), que tiene acceso a un potente ordenador. Peggy corre un programa y obtiene una solución del Sudoku. Peggy contacta con Víctor y le ofrece la solución a cambio de 20€. Sin embargo, Víctor y Peggy desconfían el uno del otro. Víctor quiere asegurarse de que Peggy tiene realmente la solución antes de pagar y que no le va a dar gato por liebre. Peggy no quiere mostrarle la solución a Víctor antes de que él haya pagado. Peggy debe probar a Víctor que conoce la solución del Sudoku sin que Víctor gane ninguna información sobre la solución. Ésta es la idea esencial detrás de una prueba de conocimiento cero. Para hacer una definición más formal, necesitaremos algunas definiciones.

Los protocolos de conocimiento cero que trataremos son sistemas de pruebas interactivas, donde un probador y un verificador intercambian varios mensajes. Peggy y Víctor llevarán a cabo computaciones privadas, y cada uno tiene un generador de números aleatorios privados. Asumimos además que Peggy tiene acceso a infinito poder computacional. Se comunican a través de una canal de comunicación. Inicialmente, Peggy y Víctor poseen cierto dato \(x\) de un lenguaje \(L\).

El objetivo de la prueba interactiva es que el probador convenza al verificador de que \(x\) posee alguna propiedad específica. En particular, pediremos que \(x\) sea una sí-instancia de un problema de decisión \(Π\). En nuestro ejemplo, \(Π\) es el problema de decidir si un sudoku es solucionable. \(x\) sería un sudoku parcialmente relleno. \(x\) sería una sí-instancia si \(x\) es solucionable.

Definiciones

Debemos tener en cuenta que la noción tradicional de prueba matemática es alterada. En este contexto, las pruebas son probabilísticas en lugar de absolutas.

  • La totalidad de una prueba interactiva es la probabilidad de que un verificador rechace la prueba de una sí-instancia \(x\).

  • Una prueba interactiva es total si tiene totalidad \(1\).

  • El error de solvencia de una prueba es la probabilidad de que un un verificador acepte una prueba de una no-instancia \(x\).

  • Diremos que una prueba interactiva es solvente si el error de solvencia es bajo.

  • Llamaremos sistema de prueba de conocimiento a un protocolo de prueba interactiva solvente y total.

Ejemplo: Grafos no isomorfos

Consideremos el siguiente protocolo hecho para comprobar si dos grafos son isomorfos. Aquí \(Π\) será el problema de decidir si dos grafos no son isomorfos y \(x\) será un par de grafos \(G_1\) y \(G_2\).

Input: Dos grafos \(G_1\) y \(G_2\) con conjunto de vértices \(\{1,\dots,n\}\), número \(m\).

  • Repetir \(m\) veces:
    • Víctor elige aleatoriamente un \(i=1\) ó \(i=2\) y toma una permutación cualquiera \(π \in S_n\). Víctor computa \(H = π(G_i)\) y envía \(H\) a Peggy.
    • Peggy determina el valor de \(j\) tal que \(G_j\) es isomorfo a \(H\) y envía \(j\) a Víctor.
    • Víctor comprueba si \(i = j\).
  • Víctor acepta la prueba si \(i = j\) en cada una de las \(m\) rondas.

Si \(G_1\) no es isomorfo a \(G_2\), entonces \(i=j\) en cada una de las rondas, por lo que Víctor aceptará la prueba con probabilidad \(1\). Por lo tanto, el protocolo es total.

Por otro lado, supongamos que \(G_1\) es isomorfo a \(G_2\). Entonces tanto \(H\) será isomorfo a los dos grafos y Peggy enviará aleatoriamente \(j=1\) ó \(j=2\). Víctor sólo aceptará la prueba si \(i=j\) en cada una de las \(m\) rondas. Luego el error de solvencia es \(2^{-m}\).

Véase que las computaciones de Víctor son polinomiales, mientras que Peggy resuelve problemas de isomorfismo de grafo, que puede que no sea resoluble en tiempo polinomial. Aquí, Peggy está haciendo uso de su infinito poder computacional.

Los problemas de decisión que tienen asociado un sistema de prueba de conocimiento de este tipo forman el espacio de complejidad \(IP\). Curiosamente, \(IP=PSPACE\), donde \(PSPACE\) es el conjunto de problemas de decisión resolubles por una máquina de Turing usando una cantidad polinómica de espacio. Este resultado se debe a Adi Shamir.

Pruebas de Conocimiento Cero

Pruebas de Conocimiento Cero Perfecto

Volviendo a la Prueba Interactiva de No-Isomorfismo de Grafos, podemos observar que Víctor puede manipular la información que envía a Peggy para obtener información que no tenía previamente. Supongamos que Víctor se hace con un grafo \(G_3\), del que sabe únicamente que es isomorfo a \(G_1\) ó a \(G_2\), pero no a cual. Si Víctor envía siempre una permutación de \(G_3\) a Peggy, que le devuelve en cada ronda el mismo valor de \(j\), Víctor deducirá que \(G_3 \simeq G_j\) y habrá adquirido un conocimiento que no poseía previamente.

Vamos a imponer a nuestros protocolos una propiedad más que nos asegure que Víctor no puede adquirir información durante el protocolo. Esto resulta ser complicado de definir formalmente. Empezaremos por representar lo que Víctor ve durante la prueba interactiva. A esto le llamamos transcripción, y consiste en:

  • El dato inicial \(x \in L\).
  • Los mensajes enviados por el canal de comunicación
  • Los números aleatorios generados por Víctor.

Si Víctor adquiere alguna información debe ser a través de la transcripción. La idea para la definición de prueba de conocimiento cero es ver si Víctor podría falsificar una transcripción, de manera que sea indistinguible de una transcripción real. Si es una falsificación perfecta, cualquier método que Víctor use para obtener información de transcripciones, dará información que puede información de transcripciones falsas, que él mismo ha creado. Luego Víctor no está adquiriendo realmente ninguna información.

Simulador

Para las siguientes definiciones denotaremos al probador como \(P\) y a Víctor como \(V\). Además los consideraremos máquinas probabilísticas. En particular, \(V\) es de tiempo polinómico. Recordemos que \(V\) no es necesariamente honesto.

Un algoritmo probabilístico \(S\) es un simulador de una prueba interactiva si para todo \(x \in L\), la salida de \(S(x)\) es una transcripción.

Queremos simuladores cuyas salidas sean indistinguibles de una transcripción real. Sea \(\mathcal{T}(V,x)\) el conjunto de todas las posibles transcripciones producidas en la prueba interactiva entre \(P\) y \(V\) con un dato inicial \(x \in L\). Sea \(\mathcal{F}(S,x)\) el conjunto de todas las posibles falsas transcripciones producidas por un simulador \(S\) con un dato inicial \(x\). Sea \(p_{\mathcal{T}}(T)\) la probabilidad de que \(T\) sea la transcripción generada por la prueba interactiva. Sea \(p_{\mathcal{F}}(T)\) la probabilida de que \(T\) sea la transcripción generada por \(S\).

Decimos que un sistema prueba de conocimiento es de conocimiento cero perfecto si para cada \(V\), existe un simulador de tiempo polinomial \(S=S(V)\) con:

  1. \(\mathcal{F}(S,x) = \mathcal{T}(V,x)\)
  2. \(\forall T \in \mathcal{T}(V,x)\), \(p_\mathcal{F}(T) = p_\mathcal{T}(T)\).

En resumen, cualquier transcripción válida podría haber sido simulada o realizada con igual probabilidad.

Para abreviar, nos referiremos a los sistemas de pruebas de conocimiento cero perfecto como ZKP (de Zero-Knowledge Proof, siempre suponemos que se trata de conocimiento cero perfecto). Obsérvese que para el simulador puede depender de \(V\). Esto será crucial, porque significa que podremos hacer uso del algoritmo de \(V\) para entender cómo podría estar haciendo trampa. A menudo, las demostraciones se basarán en reiniciar la máquina \(V\) varias veces (restableciendo sus variables internas a los valores iniciales). Esto se suele ilustrar con que tenemos una máquina del tiempo que nos permite ver qué hace Víctor en la \(k\)-ésima ronda todas las veces que queramos.

Ejemplo: Grafos isomorfos

Veamos un ejemplo de ZKP para Isomorfismo de Grafos. Aquí suponemos, como es habitual, que Peggy es capaz de computar el isomorfismo entre dos grafos isomorfos, que es una permutación \(σ\) de sus vértices.

Datos: Dos grafos \(G_1\) y \(G_2\) con conjunto de vértices \(\{1,\dots,n\}\), número \(m\).

  • Repetir \(m\) vececs:
    • Peggy elige una permutación aleatoria \(π\) de \(\{1,\dots,n\}\). Computa \(H=π(G_1)\) y envía \(H\) a Víctor.
      • Víctor elige un aleatoriamente \(i=1\) ó \(i=2\) y envía \(i\) a Peggy.
      • Si \(i=1\), Peggy envía \(π\) a Víctor. Si \(i=2\), Peggy envía \(π \circ σ\), donde \(σ\) es la permutación que lleva \(G_2\) a \(G_1\). En todo caso, Víctor recibe una permutación \(ρ\).
      • Víctor comprueba si \(ρ(G_i)=H\).
  • Víctor acepta la prueba si \(ρ(G_i)=H\) en cada una de las \(m\) rondas.

Claramente el protocolo es total. Si \(i=1\), \(ρ(G_1)=π(G_1)=H\). Por otro lado, si \(i=2\), \(ρ(G_2) = π(σ(G_2)) = π(G_1)=H\). Veamos el error de solvencia. Si \(G_1\) no es isomorfo a \(G_2\), Peggy sólo puede engañar a Víctor si acierta que \(i\) eligirá y enviar una \(H\) isomorfa a \(G_i\). Por lo tanto, la probabilidad que Peggy acierte en \(m\) rondas será \(2^{-m}\).

Ahora que hemos visto que el protocolo es un sistema de prueba de conocimiento, tenemos que cumple la propiedad de conocimiento cero perfecto. Veamos qué aspecto tendrá una transcripción \(T\) genérica. \[ T = \{(G_1,G_2), (H_1,i_1,ρ_1), (H_2,i_2,ρ_2), \dots, (H_m,i_m,ρ_m) \}\] donde \(H_k\), \(i_k\) y \(ρ_k\) es la elección en la \(k\)-ésima ronda. Toda transcripción debe empezar \((G_1,G_2)\), así que movemos nuestro interés en las \((H_k,i_k,ρ_k)\). ¿Cuántas tripletas son posibles? Tenemos 2 elecciones de \(i_k\) y \(n!\) elecciones de \(ρ_k\). \(H_k\) viene determinado por los valores de \(i_k\) y \(ρ_k\). Por lo que hay \(2 \cdot n!\) posibles tripletas. Sin embargo, no debemos olvidar que Víctor puede no ser honesto. Por ejemplo, puede que Víctor manipule su generador números aleatorios para que elija \(i=2\) en las rondas pares, lo que reduciría el conjunto de transcripciones posibles.

Consideramos qué pasa durante la ronda \(k\) de la prueba interactiva. Digamos que la probabilidad de que \(V\) elija \(i_k = 1\) es \(p_k\), donde \(p_k\) viene determinado por el estado de \(V\) al principio de la ronda \(k\). Como Peggy elige \(ρ_k\) con probabilidad uniforme y \(H\) viene determinado por \(i_k\) y \(ρ_k\), la probabilidad de que la \(k\)-ésima entrada de la transcripción sea \((H_k,i_k,ρ_k)\) es \(p_k/n!\) si \(i_k=1\) y \((1-p_k)/n!\) si \(i_k=2\).

Desarrollamos un simulador que cree las mismas transcripciones con la misma distribución que \(V\).

Input: Dos grafos \(G_1\) y \(G_2\) con conjunto de vértices \(\{1,\dots,n\}\), número \(m\).

  • Asigna \(T = \{(G_1, G_2)\}\)
  • Para \(k=1\) hasta \(m\):
    • Asigna \(s = estado(V)\)
    • Asigna \(i_k = 1\). Asigna \(i_k' = 2\)
    • Mientras \(i_k \neq i_k'\):
      • Elige \(i_k \in \{1,2\}\) aleatoriamente
      • Elige \(ρ_k \in S_n\) aleatoriamente
      • Computa \(H_k = ρ_k(G_i)\)
      • Llama \(V\): enviando \(H_k\) a Víctor y obteniendo \(i_k'\)
      • Si \(i_k = i_k'\)
        • Añade \((H_k,i_k,ρ_k)\) al final de \(T\)
      • Si no:
        • Asigna \(estado(V) = s\). (reestablece estado de \(V\))

Consideramos qué ocurre en la ronda \(k\). En cualquiera de los ciclos, la probabilidad de que \(S\) elija un grafo \(H_k\) es \(1/n!\). La probabilidad que \(S\) y \(V\) elijan \(i_k=1\) es \(p_k/2\). Similarmente, la probabilidad que \(S\) y \(V\) elijan \(i_k=2\) es \((1-p_k)/2\). Con probabilidad \(1/2\) se produce \(i_k \neq i_k'\) y se vuelve al principio del ciclo. Entonces la probabilidad de que la \((H_k,1,ρ_k)\) sea escrito en el \(j\)-ésimo loop es \(p_k/(2^j\cdot n!)\). Por lo tanto la probabilidad de que \((H_k,1,ρ_k)\) es escriba en la \(k\)-ésima ronda es: \[ \sum_{j=1}^\infty \frac{p_k}{2^j \cdot n!} = \frac{p_k}{n!} \sum_{j=1}^\infty 2^{-j} = \frac{p_k}{n!} \]

Análogamente, obtenemos que la probabilidad de que \((H_k,2,ρ_k)\) se escriba es \((1-p_k)/n!\). Como en la ronda \(k\)-ésima coinciden las probabilidades y las posibles ternas \((H_k,i_k,ρ_k)\), concluimos en durante todo el protocolo el simulador actúa como queremos. Entonces \(p_\mathcal{T}(T) = p_\mathcal{F}(T)\) y \(\mathcal{T}(V,x) = \mathcal{F}(S,x)\). Por lo tanto, el protocolo es un ZKP.

A menudo, las pruebas interactivas incluirán alguna especie de desafío de Víctor a Peggy. Por ejemplo, en el ZKP de Isomorfismo de Grafos, Víctor desafía a Peggy enviando un \(i\) y esperando obtener un isomorfismo \(ρ : G_i \to H\). Para extender las posibilidades de desafíos que podemos usar cuando diseñeos pruebas interactivas, tenemos que introducir el concepto de esquema de compromiso.

Esquemas de compromiso

Supongamos que Peggy escribe un mensaje en un papel, que guarda en una caja fuerte cuya combinación sólo ella conoce. Si Peggy entrega esa caja a Víctor, Víctor no podrá leer ese mensaje, pero sabe que Peggy no puede modificar el mensaje que hay dentro de la caja fuerte. Supondremos siempre que el mensaje comprometido es una cadena de bits, para ello definiremos los esquemas de compromiso de un solo bit. Peggy usará dicho esquema en cada uno de los bits del mensaje.

Sean \(X\) e \(Y\) conjuntos finitos y \(b\) un bit. Un esquema de compromiso es una función \(f : \{0,1\} \times X \to Y\), tal que:

  • (Oculto) Para un bit \(b \in \{0,1\}\) y un \(x \in X\), Víctor no puede determinar el valor de \(b\) a partir de \(f(b,x)\).
  • (Vinculante) Aunque Peggy conozca \(x \in X\) y \(b \in \{0,1\}\), Peggy no puede encontrar un \(x' \in X\), tal que \(f(1-b,x') = f(b,x)\).

En nuestras pruebas interactivas, Peggy elegirá un valor de \(b \in \{0,1\}\) y una clave \(x \in X\). Enviará \(f(b,x)=y\) a Víctor. Víctor no puede obtener el valor de \(b\) (por ser oculto). Peggy puede convencer a Víctor que encriptó efectivamente \(b\), enviando \(x\) a Víctor, para que compruebe que efectivamente \(y=f(b,x)\). Peggy no será capaz de convencer a Víctor de que encriptó un \(b\) distinto (por ser vinculante).

Este concepto puede recordar bastante a las funciones hash. Efectivamente, un esquema de compromiso habitual es definir \(f(b,x) = h(b | x)\), donde \(h\) es una función hash y \(|\) es una concatenación.

Otra cosa a tener en cuenta es que la condición de esquema de compromiso oculto es equivalente a la condición de función one-way. La existencia de este tipo de funciones no está demostrada, pues depende del problema \(P \overset{?}{=} NP\). Volveremos a este tema en breve, tras definir las pruebas de conocimiento cero computacional.

Pruebas de Conocimiento Cero Computacional (CZKP)

Recordemos que en la definición prueba de conocimiento cero, exigíamos que:

  • \(\mathcal{F}(S,x) = \mathcal{T}(V,x)\).
  • \(\forall T \in \mathcal{T}(V,x), p_\mathcal{F}(T) = p_\mathcal{T}(T)\).

Decimos que una prueba de conocimiento es una prueba de conocimiento cero computacional (a partir de ahora CZKP) si Víctor no puede desmentir las anteriores condiciones usando tests probabilísticos en tiempo polinómico. En otras palabras, Víctor no puede distinguir transcripciones reales de transcripciones falsificadas en una cantidad de tiempo razonable. Esta es una útil relajación de las ZKP, que nos permitirá extender la clase de problemas sobre las que podemos diseñar pruebas de conocimiento cero. De hecho, si llamamos \(CZK\) a la clase de problemas que tienen una CZKP, entonces si existen las funciones one-way, entonces:

  • \(P \neq NP\)
  • \(NP \subseteq CZK\) (demostrado por Goldreich, Micali y Wigderson)
  • \(CZK = IP\) (demotrado por Ben-Or, Goldreich, Goldwasser, Hastad, Kilian, Micali y Rogaway)

Sobre todo nos interesa el segundo apartado, que significa que hay una CZKP para cada problema NP. Esto se puede demostrar, viendo que hay una CZKP para el problema NP-completo de la 3-coloración de grafos.

Input: Un grafo \(G\) con conjunto de vértices \(\{1,\dots,n\}\)

  • Peggy computa una 3-coloración \(C\) de \(G\).
  • Para \(k=1\) hasta \(m\):
    • Peggy elige una permutación \(π \in S_3\). Peggy compromete cada uno de los elementos de \(C\) tras usar la permutación \(π\).
    • Víctor elige aleatoriamente un \((i,j)\) arista de \(G\) y lo envía a Peggy.
    • Peggy descompromete a Víctor los valores de \(c_i = π(C(i))\), \(c_j = π(C(j))\).
    • Víctor comprueba si \(c_i \neq c_j\).
  • Víctor acepta la prueba si \(c_i \neq c_j\) en cada una de las \(m\) rondas.

No incluiremos demostración de que esta prueba interactiva es efectivamente una CZKP.

Aplicaciones y conclusiones

Al principio mencionamos la idea de que Peggy quería vender un sudoku resuelto a Víctor por cierta cantidad de dinero. Este ejemplo no ha sido elegido al azar, pues se basa en una transferencia real usando la red Bitcoin. Esta transacción, a través del protocolo Zero-Knowledge Contingent Payment, consistió en la compra de la solución de un sudoku \(16\times 16\) por \(0.10\) Bitcoin. Algunos de los que colaboraron en dicha transacción, también desarrollaron la criptomoneda Zcash, que busca dar total privacidad a las transacciones manteniendo la estructura de blockchain de Bitcoin. Para ello, hace uso de zk-SNARKs, que mezcla criptografía homomórfica con pruebas de conocimiento cero de forma computacionalmente eficiente.

Sin embargo, los protocolos de conocimiento cero no parecen haber obtenido gran popularidad práctica, por su alto coste computacional. Sin embargo, hay una gran cantidad de estudios teóricos sobre las ventajas que pueda traer su implementación en temas como el voto electrónico y certificados digitales.

Quizás el más importante protocolo de conocimiento cero usado hoy en día, es el Secure Remote Password (o SRP), desarrollado principalmente por la Universidad de Stanford, e implementado en librerías como OpenSSL y GNU Crypto. Estos protocolos de contraseña para SSL/TLS presentan ventajas como protección contra Phishing y autentificación mutua (de servidor a cliente y de cliente a servidor).

El reciente interés por la privacidad y seguridad, junto al desarrollo de procesadores suficientemente rápidos, ha aumentado el interés por la implementación de protocolos de conocimiento cero. El estudio teórico no se ha detenido, siendo un tema muy habitual en las revistas de criptografía y en las conferencias de la International Association for Cryptologic Research.

Bibliografía

  • Mohr, Austin. 2007. “A Survey of Zero-Knowledge Proofs with Applications to Cryptography.”
  • Raffo, Daniele, and François Morain. 2002. “Digital Certificates and the Feige-Fiat-Shamir Zero-Knowledge Protocol.”
  • Stinson, Douglas R. 2006. “Cryptography: Theory and Practice.” 3rd ed. The CRC Press Series on Discrete Mathematics and Its Applications. Boca Raton: Chapman & Hall/CRC.