Pruebas de conocimiento cero

Pruebas de conocimiento cero Doriana Hern´andez Fern´andez Trabajo de Fin de Grado Dirigido por Jos´e Ignacio Iglesias Curto Francisco Jos´e Plaza Mart´ın Grado en Matem´aticas Facultad de Ciencias Julio 2020 2 Pruebas de conocimiento cero Doriana Hern´andez Fern´andez Trabajo de Fin de Grado Dirigido por Jos´e Ignacio Iglesias Curto Francisco Jos´e Plaza Mart´ın Grado en Matem´aticas Facultad de Ciencias Julio 2020 2 ´ Indice general 1. Introducci´on 5 1.1. Ejemplo ..................................... 6 2. Pruebas de conocimiento cero 7 2.1. M´aquinasdeTuring............................... 7 2.2. Protocolos y sistemas de pruebas interactivas . . . . . . . . . . . . . . . . . 9 2.3. Conocimientocero ............................... 11 2.3.1. Indistinguibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3.2. Introducci´on al conocimiento cero . . . . . . . . . . . . . . . . . . . 13 2.4. Pruebas de conocimiento cero . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.5. Lenguajes en los protocolos. . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.6. M´as all´a de los lenguajes. . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3. Pruebas de conocimiento cero sobre lenguajes 17 3.1. Isomorfismodegrafos.............................. 17 3.2. Grafos3-coloreables............................... 19 3.3. Residuoscuadr´aticos .............................. 21 4. Pruebas para la identificaci´on 23 4.1. De la membres´ıa a la identificaci´on . . . . . . . . . . . . . . . . . . . . . . 23 4.2. Protocolos de Fiat y Shamir . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.3. Ejemplos..................................... 30 5. Pruebas no interactivas y firmas 33 5.1. Pruebas de conocimiento cero no interactivas . . . . . . . . . . . . . . . . . 33 5.2. Firmasdigitales................................. 37 5.2.1. Firma digital de Fiat y Shamir . . . . . . . . . . . . . . . . . . . . 37 5.2.2. Firma digital de Bellarre y Goldwasser . . . . . . . . . . . . . . . . 39 5.2.3. Firma digital de Schnorr . . . . . . . . . . . . . . . . . . . . . . . . 40 5.3. Ejemplos..................................... 41 6. Una aplicaci´on actual 45 6.1. Blockchain .................................... 45 6.2. Pruebas de rango de conocimiento cero . . . . . . . . . . . . . . . . . . . . 45 Conclusi´on 49 3 4´ INDICE GENERAL Bibliograf´ıa 52 Cap´ıtulo 1 Introducci´on Las pruebas de conocimiento cero son protocolos criptogr´aficos en los que participan dos entidades o participantes: el probador y el verificador. El probador debe demostrar al verificador que conoce una informaci´on sin revelarla. Las ´areas en las que va a centrarse el trabajo ser´an ´algebra, en particular, criptograf´ıa, y probabilidad. La aparici´on de las pruebas de conocimiento cero supone un planteamiento nuevo, puesto que no se transmite la informaci´on en s´ı, sino una garant´ıa de que se conoce esa informaci´on. En otros m´etodos de encriptaci´on se ocultaba la informaci´on que se quer´ıa mantener en secreto y exist´ıa la posibilidad de acceder a la informaci´on rompiendo el protocolo. La primera menci´on a las pruebas de conocimiento cero la realizan Goldwasser, Micali y Rackoff en 1985 [10], presentan las pruebas de conocimiento cero como una prueba interactiva para demostrar la pertenencia de un elemento a un lenguaje sin demostrar nada m´as que la pertenencia. Posteriormente, en 1987, Fiat y Shamir presentan un protocolo de identificaci´on [8] utilizando la idea de prueba de conocimiento cero interactiva de Goldwasser, Micali y Rackoff. Aqu´ı, se pasa de demostrar la pertenencia de un elemento a un lenguaje, a demostrar la identidad de un participante o entidad, bas´andose en el conocimiento de un secreto que solo el probador conoce. Adem´as de presentar un protocolo de identificaci´on, presentan un protocolo de firma digital. En 1988, Blum, Feldman y Micali presentan las pruebas de conocimiento cero no interactivas [3] que mejoran la idea de conocimiento cero haci´endola no interactiva, ya que en algunos contextos no era factible. Estas pruebas vuelven al problema de demostrar que un elemento pertenece a un lenguaje. Bellarre y Goldwasser, recogen la idea de prueba no interactiva de conocimiento cero y construyen un protocolo de firma digital en 1990 [2]. Actualmente, las pruebas de conocimiento cero se aplican en Blockchain [13] y, en general, en procesos en los que se necesita mantener un nivel de seguridad alto. La memoria que se presenta contiene una vista general de las pruebas de conocimiento cero en todas sus formas y variantes, as´ı como una evoluci´on del concepto y sus diferentes adaptaciones. Adem´as, contiene protocolos de este tipo de pruebas junto con ejemplos concretos. El trabajo se divide en seis cap´ıtulos: al final del cap´ıtulo en el que nos encontramos, ofrecemos un relato ejemplificador de lo que es una prueba de conocimiento cero. En el Cap´ıtulo 2, presentamos las pruebas de conocimiento cero, para ello aportamos unas 5 6CAP´ ITULO 1. INTRODUCCI ´ ON nociones previas para formalizar la definici´on de estas pruebas. En el Cap´ıtulo 3, mostramos tres casos concretos de pruebas de conocimiento cero sobre lenguajes y el desarrollo completo de uno de ellos en base a las definiciones del Cap´ıtulo 2. En el Cap´ıtulo 4, pasamos a las pruebas de conocimiento cero para la identificaci´on, se abordan tres pruebas de este tipo y se incluyen ejemplos de las mismas. En el Cap´ıtulo 5, se exponen las pruebas de conocimiento cero no interactivas, las firmas digitales y varios ejemplos de ellos. En el Cap´ıtulo 6, presentamos una aplicaci´on actual que tienen las pruebas de conocimiento cero y c´omo se ha adaptado la idea al blockchain. Por ´ultimo, incluimos una conclusi´on final del desarrollo del trabajo. 1.1. Ejemplo Explicaremos una prueba de conocimiento cero utilizando un relato para tener una idea general de lo que es una prueba de este tipo. Como ya sabemos, en las pruebas de conocimiento cero participan dos entidades: el probador y el verificador, donde el probador demuestra al verificador que conoce una informaci´on sin revelarla. En este relato nos encontramos a Paquita, que es el probador, a los periodistas, que son el verificador y la palabra secreta, que es la informaci´on que posee el probador y que no quiere que nadie conozca. Supongamos dos pueblos llamados Macondo y Bree situados en una isla, y que adem´as est´an separados por una monta˜na inaccesible. Cada pueblo tiene una cueva sin salida en su lado de la monta˜na. No existe ning´un tipo de conexi´on entre ambos pueblos porque ning´un habitante se atreve a echarse a la mar y porque ninguno es capaz de escalar la monta˜na. Paquita es una habitante de uno de estos pueblos, no revela de cu´al, y quiere demostrar al mundo que conoce una puerta secreta que conecta ambos pueblos. Esta puerta conectar´ıa las cuevas de cada pueblo y solo se abrir´ıa utilizando una palabra secreta que solo Paquita conoce. Como quiere que nadie conozca la palabra secreta se pone en contacto con unos periodistas para demostrarles que conoce la palabra m´agica sin dec´ırsela. Un equipo de periodistas for´aneos son los que comprobar´an que Paquita conoce la palabra secreta. El protocolo que se sigue es el siguiente: el equipo de periodistas se aleja de la isla y pide a Paquita que entre en la cueva de su pueblo. Cuando Paquita se encuentra dentro de la cueva, avisa a los periodistas que lanzan una moneda: si sale cara piden a Paquita que salga por la entrada de Macondo; si sale cruz, por la de Bree. Despu´es de lanzar la moneda, los periodistas van a la entrada de la cueva correspondiente. Paquita sale por la cueva que le piden, los periodistas vuelven a alejarse y Paquita regresa a su pueblo. Visto as´ı, podr´ıa pensarse que si Paquita se encuentra en la cueva de Bree y los periodistas le piden que salga por la entrada de Bree, Paquita no tendr´ıa por qu´e saberse la palabra m´agica. Por ello, este proceso se repite varias veces para reducir la probabilidad lo m´aximo posible de que Paquita salga por la misma cueva que entr´o. Al finalizar todo el proceso, Paquita ha demostrado al mundo que existe una puerta m´agica que une dos pueblos y que solo ella conoce la palabra que la abre. Si tenemos presente este ejemplo durante las siguientes p´aginas nos resultar´a m´as f´acil comprender las nociones que vamos a dar. Cap´ıtulo 2 Pruebas de conocimiento cero En este cap´ıtulo abordaremos las nociones previas necesarias para poder dar una definici´on formal de lo que es una prueba de conocimiento cero. Estas nociones incluyen las m´aquinas de Turing, los protocolos interactivos y los sistemas de pruebas interactivas. Adem´as, para poder definir lo que es el conocimiento cero formalmente, presentaremos el concepto de indistinguibilidad. 2.1. M´aquinas de Turing En esta secci´on presentamos la definici´on de m´aquina de Turing y de las variantes para poder definir con rigor las pruebas de conocimiento cero. La bibliograf´ıa sobre este tema era bastante escasa y fue necesario hacer una combinaci´on de toda la informaci´on encontrada sobre m´aquinas de Turing pero en particular de [5] y [6] , y del tipo de m´aquina de Turing que se necesitaba para formalizar la definici´on de prueba de conocimiento cero [10]. Los dos participantes de una prueba de conocimiento cero pueden pensarse como dos m´aquinas de Turing que interact´uan entre s´ı. Esto nos ser´a ´util para dar la definici´on formal de una prueba de conocimiento cero. Una m´aquina de Turing es un dispositivo te´orico que posee una memoria externa infinita denominada cinta, dividida en celdas; que adopta un estado interno en cada momento; y que contiene unas instrucciones. Cada una de las celdas contiene un s´ımbolo de un alfabeto o un espacio en blanco (#) y hay un selector que determina qu´e celda est´a leyendo la m´aquina en ese momento. En cuanto a los estados internos, hay dos que son los m´as especiales: el estado inicial, es decir, el estado interno de la m´aquina cuando se activa; y el estado final, que es el estado interno al que pasa la m´aquina y despu´es para. Las instrucciones de la m´aquina especifican que dados un estado interno y un s´ımbolo le´ıdo, entonces se pasa a otro estado interno, otro s´ımbolo y hacia d´onde debe moverse el selector de celdas. Podr´ıa darse el caso de que el estado interno o el s´ımbolo no cambiaran, as´ı como que el selector se mantuviera en el mismo sitio. Definici´on 2.1. Una m´aquina de Turing es una 6-´upla (Q, q0, qf, S, #, δ) donde: Qes un conjunto finito. Este conjunto contiene todos los estados internos de la m´aquina. 7 14 CAP´ ITULO 2. PRUEBAS DE CONOCIMIENTO CERO Definici´on 2.22. [11] Sea (A, B) un protocolo interactivo en L⊂ {0,1}∗y sea B∗una m´aquina de Turing interactiva cualquiera. Decimos que (A, B) es un protocolo interactivo de conocimiento cero perfecto ( resp. estad´ıstico, computacional), si la familia de variables aleatorias {hA, B∗i(x)}x∈Les perfectamente ( resp. estad´ısticamente, computacionalmente) aproximable en L. Vemos que lo que observa el verificador durante el protocolo y lo que genera una m´aquina de Turing probabil´ıstica ser´a indistinguible perfecta, estad´ıstica o computacionalmente. Por lo tanto, un protocolo interactivo puede ser de conocimiento cero perfecto, estad´ıstico o computacional. Una vez visto esto, pasemos a las pruebas de conocimiento cero. 2.4. Pruebas de conocimiento cero En esta secci´on tratamos finalmente la definici´on formal de una prueba de conocimiento cero, primero dando la versi´on m´as pr´actica y posteriormente la formal. Recordemos que una prueba de conocimiento cero es un protocolo criptogr´afico con dos entidades: el probador y el verificador, donde el probador debe demostrar al verificador que conoce una informaci´on secreta sin revelarla. [12] Las principales caracter´ısticas de las pruebas de conocimiento cero son: 1.- El verificador no puede obtener nada ´util del protocolo, es decir, no puede obtener informaci´on sensible del protocolo. 2.- El verificador no tiene capacidad de hacerse pasar por el probador que ha verificado, es decir, los mensajes que se intercambian en el protocolo no pueden utilizarse para hacerse pasar por el probador que se est´a verificando. 3.- La probabilidad de que el verificador acepte una declaraci´on falsa como verdadera es muy peque˜na. 4.- La probabilidad de que el verificador sea convencido de una declaraci´on que es verdadera es muy alta. Las pruebas de conocimiento cero son protocolos interactivos robustos (Definici´on 2.14), completos (Definici´on 2.13) y de conocimiento cero (Definici´on 2.22).Tambi´en puede pensarse como un sistema de pruebas interactivas (Definici´on 2.15) de conocimiento cero. Definici´on 2.23. [11] Sea (A, B) un sistema de pruebas interactivas en L⊂ {0,1}∗, (A, B) es de conocimiento cero perfecto (resp. estad´ıstico, computacional) si es un protocolo interactivo de conocimiento cero perfecto (resp. estad´ıstico, computacional). Si observamos las caracter´ısticas que tienen las pruebas de conocimiento cero, vemos que un sistema de pruebas de conocimiento cero tambi´en las cumplir´a: Las caracter´ısticas 1 y 2, las cumple debido a la propiedad de conocimiento cero del sistema de pruebas; la caracter´ıstica 3 es la robustez por ser un sistema de pruebas interactivas; y la 4 es la completitud, tambi´en de un sistema de pruebas interactivas. 2.5. LENGUAJES EN LOS PROTOCOLOS. 15 2.5. Lenguajes en los protocolos. Hasta ahora, las pruebas de conocimiento cero que hemos definido est´an basadas en demostrar la pertenencia de un elemento a un lenguaje. Esta idea, ser´a recogida por otros autores [8] para obtener otros tipos de pruebas de conocimiento cero que veremos en la siguiente secci´on y en el Cap´ıtulo 4. La seguridad de este tipo de pruebas reside en que demostrar que un elemento pertenece a un lenguaje es un problema de decisi´on. En esta secci´on daremos algunas nociones sobre estos problemas y la relaci´on que tienen con los lenguajes que se utilizan en las pruebas de conocimiento cero. Definici´on 2.24. Un problema es Psi existe un algoritmo que puede resolverlo en tiempo polin´omico. Si no puede resolverse en este tiempo, se dice que es NP. Definici´on 2.25. Un lenguaje es Psi demostrar que un elemento pertenece a ese lenguaje es un problema P. Lo an´alogo para los lenguajes NP. Podemos ver que si un lenguaje es P, el verificador podr´a probar que el elemento est´a en el lenguaje sin necesidad de interactuar con el probador. Por otro lado, si el lenguaje es NP al verificador le resultar´a m´as complicado probarlo. Es por esto que los lenguajes a los que se recurrir´a para las pruebas de conocimiento cero ser´an NP. En el siguiente cap´ıtulo explicaremos pruebas de conocimiento cero sobre distintos lenguajes. Los autores [11] [9] recurren a una nueva definici´on de lenguajes: Definici´on 2.26. Un lenguaje es un conjunto para el cual es computacionalmente dif´ıcil probar la membres´ıa de un elemento. Un lenguaje es computacionalmente dif´ıcil porque es un lenguaje P´o NP. Aunque, los lenguajes que veremos ser´an NP. Los lenguajes que veremos en el siguiente cap´ıtulo son los isomorfismos de grafos, los grafos 3-coloreables y los residuos cuadr´aticos. Estos lenguajes son v´alidos para todas las definiciones vistas en este cap´ıtulo. 2.6. M´as all´a de los lenguajes. Las pruebas de conocimiento cero demuestran el conocimiento de una informaci´on sin revelarla. Hemos visto que prueban la pertenencia a un lenguaje en las primeras menciones del conocimiento cero [9–11]. Esta idea evoluciona con Fiat y Shamir en [8] para dar soluci´on a la identificaci´on sin uso de contrase˜nas. Si un tercero intercepta la contrase˜na de un individuo, ´este podr´ıa hacerse pasar por ´el. El concepto b´asico de las pruebas de conocimiento cero para la identificaci´on es el siguiente: el probador, en conocimiento de un secreto que lo identifica, demuestra su identidad al verificador sin transmitirle ese secreto. Los conceptos que hemos tratado en este cap´ıtulo como la robustez, la completitud y la indistinguibilidad se basan en la pertenencia al lenguaje y se adaptar´an a la identificaci´on [8]. La completitud y la robustez se basaban en la pertenencia o no de un elemento a un lenguaje, en la identificaci´on se hace referencia al conocimiento o no de un secreto. 16 CAP´ ITULO 2. PRUEBAS DE CONOCIMIENTO CERO Definici´on 2.27. Sea (A, B) un protocolo interactivo, (A, B) es completo si la probabilidad de que Bacepte la identidad de Acuando Aposee el secreto, es muy cercana a 1. Definici´on 2.28. Sea (A, B) un protocolo interactivo, (A, B) es robusto si la probabilidad de que Bacepte la identidad de Acuando Ano posee el secreto, es muy cercana a 0. El concepto de indistinguibilidad se mantiene, es decir, se debe comprobar que la vista del verificador durante el protocolo es susceptible de ser generada por un simulador ajeno a la prueba. El matiz distinto es que las familias de variables aleatorias no se forman por los diferentes elementos del lenguaje, si no por otras variables que veremos en el Cap´ıtulo 4. Como vemos, la idea de no transmitir conocimiento se mantiene y estos autores la utilizan para crear algoritmos de identificaci´on y de firma que veremos en los Cap´ıtulos 4 y 5. Cap´ıtulo 3 Pruebas de conocimiento cero sobre lenguajes Despu´es de haber definido las pruebas de conocimiento cero sobre lenguajes en el cap´ıtulo anterior, en este cap´ıtulo vamos a explicar tres tipos de pruebas de conocimiento cero sobre lenguajes. Recordemos que en las pruebas de conocimiento cero sobre lenguajes, el probador demuestra al verificador que un elemento pertenece a un lenguaje sin dar m´as informaci´on que la pertenencia. En el cap´ıtulo anterior hab´ıamos definido los lenguajes como subconjuntos de {0,1}∗, ahora, como adelant´abamos en la Secci´on 2.5, se redefinen los lenguajes como conjuntos para los que demostrar que un elemento pertenece a ellos es computacionalmente dif´ıcil o, dicho de otra forma, lenguajes NP. Estos lenguajes mantienen todas las definiciones vistas hasta ahora [11]. Los lenguajes sobre los que vamos a construir pruebas de conocimiento cero son: los isomorfismos de grafos, los grafos 3-coloreables y los residuos cuadr´aticos. Como explicamos en la Secci´on 2.5, los lenguajes que vamos a utilizar son conjuntos para los que demostrar la pertenencia es un problema NP. A continuaci´on, explicamos los tres protocolos para pruebas de conocimiento cero sobre lenguajes: primero, presentamos la base matem´atica, luego, el problema de pertenencia, y finalmente, el protocolo. Tambi´en realizaremos un desarrollo m´as exhaustivo de la prueba de conocimiento cero sobre los grafos 3-coloreables utilizando las definiciones del cap´ıtulo anterior. Nota 3.1. En los pr´oximos apartados utilizaremos la notaci´on A→Bpara indicar el paso en el que Arealiza las computaciones oportunas y env´ıa el resultado a B. Lo an´alogo para B→A. 3.1. Isomorfismo de grafos En primer lugar, expondremos algunas nociones sobre grafos que vamos a utilizar en esta y en la siguiente secci´on. Sea Cun conjunto, denotamos por σ(C) al conjunto de todas las permutaciones del conjunto C. Si tomamos c∈RCestamos escogiendo un elemento de Caleatoriamente y con una distribuci´on de probabilidad uniforme. 17 18 CAP´ ITULO 3. PRUEBAS DE CONOCIMIENTO CERO SOBRE LENGUAJES Denotamos G(V, E) al grafo no dirigido con Vel conjunto de sus v´ertices y Eel conjunto de sus aristas. Llamamos nal tama˜no de Vymal tama˜no de E. Definici´on 3.1. Sean G(V, E) y H(V, F) dos grafos no dirigidos, son isomorfos si y solo si existe una permutaci´on π∈σ(V) de modo que (u, v)∈E⇔(π(u), π(v)) ∈F. Dicho de otro modo, si dos v´ertices son adyacentes en un grafo, las im´agenes por πlo ser´an en el otro grafo. El conjunto de los pares de grafos isomorfos es un lenguaje que denotamos por GI, donde GI ={(G, H) : ∃πde modo que H=πG}. Adem´as, decimos que un grafo H(V, F) es una copia isomorfa aleatoria del grafo G(V, E) si Hse obtiene de Gmediante π∈Rσ(V) y tomando F={(π(u), π(v)) : (u, v)∈E}. El problema del isomorfismo de grafos es el siguiente: dados dos grafos hay que determinar si son isomorfos (que pertenecen a GI). A continuaci´on, presentamos la prueba de conocimiento cero sobre el lenguaje GI Protocolo 3.1. Este protocolo puede consultarse en [9]. G0(V, E0) y G1(V, E1) son dos grafos no dirigidos que tanto el probador, A, y el verificador, B, conocen. φes un isomorfismo entre G0yG1, es decir, G1=φG0que conoce A. a) Fase previa.Adebe demostrar a Bque hay un isomorfismo entre G0yG1sin revelar φ. b) Intercambio de mensajes. Los siguientes pasos se repiten nveces, con nel n´umero de v´ertices de ambos grafos, y en todas las repeticiones, las elecciones aleatorias son nuevas. 1.- A→B: El probador toma π∈Rσ(V) y construye una copia aleatoria isomorfa de G1a la que denotamos H(V, F). El probador, A, env´ıa al verificador, B, el grafo H(V, F). 2.- B→A: El verificador, B, toma e∈R{0,1}y se lo env´ıa a A. 3.- A→B: El probador comprueba primero si e∈ {0,1}, si no fuera as´ı parar´ıa. Si e= 1, entonces el probador, A, env´ıa πaB; y si e= 0, A, env´ıa πφ aB. 4.- Una vez recibe Bla permutaci´on, comprueba si es un isomorfismo entre Gey H. Si lo es, continua con la siguiente iteraci´on; si no, rechaza y para. c) Finalizaci´on del protocolo. Cuando se completan las niteraciones con ´exito, el verificador, B, acepta y para. Observaci´on 3.1. El problema del isomorfismo de grafos se demostr´o que era un problema que se encontraba entre PyNP en 2016, fue demostrado por Babai en [1]. Por lo tanto, ser´ıa computacionalmente m´as f´acil romper este protocolo porque se puede encontrar un ismorfismo entre dos grafos. 3.2. GRAFOS 3-COLOREABLES 19 3.2. Grafos 3-coloreables Definici´on 3.2. Sea G(V, E) un grafo no dirigido, es un grafo 3-coloreable si existe una aplicaci´on φ:V→ {1,2,3}de tal manera que a todo par de v´ertices adyacentes se le asignan colores distintos, es decir, ∀(u, v)∈E, φ(u)6=φ(v). El conjunto de grafos no dirigidos que son 3-coloreables es un lenguaje que denotamos G3C. El problema de los grafos 3-coloreables es el siguiente: dado un grafo hay que determinar si es 3-coloreable. El problema es NP por lo que el lenguaje G3Ces NP [9]. Observaci´on 3.2. El inter´es del lenguaje 3-coloreable es debido a que demostrar que un grafo es 3-coloreable es un problema NP, algo que no ocurre con los grafos 4-coloreables. Para los grafos 4-coloreables asociados a un mapa existe un teorema que demuestra que todo grafo puede ser coloreado por cuatro colores sin que los v´ertices adyacentes tengan el mismo color. Ahora, presentamos una prueba de conocimiento cero sobre el lenguaje G3C. Protocolo 3.2. Este protocolo puede consultarse en [9]. a) Fase previa. G(V, E) es un grafo no dirigido que AyBconocen, con Vde tama˜no nyEde tama˜no m.φes una coloraci´on correcta que solo conoce A.Adebe demostrar a B que el grafo Ges 3-coloreable (que pertenece a G3C) sin revelar φ. b) Intercambio de mensajes. Los siguientes pasos se repiten m2veces y cada una de las veces las elecciones aleatorias son nuevas: 1.- A→B:Atoma π∈Rσ({1,2,3}), calcula π(φ(v)) ∀v∈V. Cada uno de los π(φ(v)) son encriptados1individualmente por Ay enviados a B. 2.- B→A:Bescoge una arista e= (u, v)∈Ey se la env´ıa a A. 3.- A→B:Acomprueba que e∈Ey env´ıa a Blas desencriptaciones de uyv. 4.- Brecibe la desencriptaci´on, desencripta uyvy comprueba que contienen diferentes elementos de {1,2,3}. Si los elementos de {1,2,3}son distintos, contin´ua con la siguiente iteraci´on. Si no puede desencriptar o los n´umeros que contienen son iguales, entonces Brechaza y para. De esta forma, el verificador no conocer´a la coloraci´on real del grafo porque la coloraci´on est´a oculta mediante π c) Final del protocolo. Si se completan las m2iteraciones con ´exito, entonces Bacepta y para. 1Se utiliza cualquier algoritmo de encriptaci´on que permita encriptarlos y desencriptarlos de manera individual 20 CAP´ ITULO 3. PRUEBAS DE CONOCIMIENTO CERO SOBRE LENGUAJES Proposici´on 3.1. El Protocolo 3.2 es una prueba de conocimiento cero computacional para G3C. Demostraci´on. Tenemos en cuenta que es un protocolo interactivo porque las entidades que participan en el protocolo pueden formalizarse como m´aquinas de Turing interactivas probabil´ısticas, siendo Buna m´aquina de Turing de tiempo esperado polinomial y A sin l´ımite computacional. Estas entidades interactuar´an como lo hacen las m´aquinas de Turing en los protocolos interactivos. Como una prueba de conocimiento cero computacional es un sistema de pruebas de conocimiento cero computacional vamos a probar que es completo, robusto y de conocimiento cero computacional. Utilizando la Definici´on 2.23: Completitud. Bas´andonos en la Definici´on 2.13, si el grafo de entrada G∈G3Centonces, cualquier par de v´ertices adyacentes que se tomen van a tener color distinto, por lo que la probabilidad de que el verificador acepte dicho grafo es 1. El Protocolo 3.2 es completo. Robustez. Utilizando la Definici´on 2.14, supongamos ahora que el grafo de entrada G /∈G3Clo que quiere decir que al menos habr´a un par de v´ertices adyacentes que no tendr´an la coloraci´on adecuada. La probabilidad de que cualquier verificador rechace este grafo es al menos 1/m que es la probabilidad de escoger la arista que une los v´ertices del mismo color. Por lo tanto, la probabilidad de que el verificador acepte el grafo es como mucho (m−1)/m en cada iteraci´on, que es la probabilidad de escoger un par de v´ertices bien coloreados. En total en todo el protocolo la probabilidad de que acepte un G /∈G3Ces como mucho ((m−1)/m)m2, una probabilidad ´ınfima y por consiguiente, el Protocolo 3.2 es robusto. Conocimiento cero computacional. Para esta demostraci´on utilizaremos las Definiciones 2.19 y 2.21. La informaci´on que obtiene el verificador en cada paso es π(φ(u)) yπ(φ(v)) donde (u, v) son v´ertices adyacentes escogidos aleatoriamente por el verificador, y donde πtambi´en es escogido aleatoriamente por el probador. Esta informaci´on es lo que conocemos como la vista del verificador durante el protocolo y es una variable aleatoria inducida por la aleatoriedad de la elecci´on de π. Como cada G∈G3Cda lugar a una variable aleatoria, construimos la familia de variables aleatorias que denotamos por {hA, Bi(G)}G∈G3C. Bas´andonos en la Definici´on 2.21 consideremos como simulador una m´aquina de Turing Mprobabil´ıstica que con entrada un grafo G∈G3Cnos devuelve dos enteros (i, j)∈R{1,2,3}con i6=j. El conjunto de las salidas de esta m´aquina de Turing es una familia de variables aleatorias que denotaremos por {M(G)}G∈G3C. Probemos que estas dos familias de variables aleatorias son computacionalmente indistinguibles (Definici´on 2.19). Primero, necesitamos construir al “juez”, que en el caso de la indistinguibilidad computacional es un circuito booleano: Sea C={Cy}nuestro juez con y∈ hA, Bi(G) ´o y∈M(G), y sean las muestras ytodas del mismo tama˜no por definici´on. Tenemos que P({hA, Bi(G)}, C, G) es la probabilidad de que el circuito devuelva un 1 al introducir un y∈ hA, Bi(G) y P({M(G)}, C, G) la probabilidad de que devuelva un 0 al introducir un y∈M(G). 3.3. RESIDUOS CUADR ´ ATICOS 21 Como vemos, los y∈ hA, Biy los y∈M(G) no guardan una relaci´on con su procedencia porque los y∈ {(1,2),(2,1),(1,3),(3,1),(2,3),(3,2)}sea cual sea su procedencia. Por lo que si calculamos |P({hA, Bi(G)}, C, G)−P({M(G)}, C, G)|(2.2) obtendremos un valor muy cercano a 0 porque las probabilidades de que acierte o falle son las mismas en cada caso. Por lo tanto, podemos afirmar que estas dos familias de variables aleatorias son computacionalmente indistinguibles, lo que convierte al Protocolo 3.2 en un sistema de pruebas interactivas de conocimiento cero computacional. 3.3. Residuos cuadr´aticos Vamos a fijar algunas nociones sobre residuos cuadr´aticos tomadas de [11] que utilizaremos tanto para definir el lenguaje como para presentar el problema de los residuos. Definici´on 3.3. Sea p∈Ny sea Z∗ pel conjunto de los invertibles m´odulo p. Entonces, un q∈Z∗ pes un residuo cuadr´atico m´odpsi existe un w∈Z∗ pde modo que w2=qm´od p. Puede determinarse en tiempo polinomial que q∈Z∗ p. Adem´as q∈Z∗ pes un residuo cuadr´atico m´od psi y solo si qes un residuo cuadr´atico m´odulo todos los factores primos de p. Definici´on 3.4. Denotamos por Qp(q) al operador: Qp(q) = 0 si qes un residuo cuadr´atico m´odp 1 en otro caso (3.1) Dados p∈N,q∈Z∗ py la factorizaci´on de p, el operador Qp(q) puede calcularse en tiempo polinomial. Definici´on 3.5. Sea q∈Z∗ py sea Qk i=1 pαi ila descomposici´on en primos de p, entonces el s´ımbolo de Jacobi de qm´od pse define como: q p= k Y i=1 q piαi (3.2) donde q pi= +1 si qes un residuo cuadr´atico m´odpiyq pi=−1 en otro caso. Recordemos que estos q pipara i= 1, ..., k son los s´ımbolos de Legendre. Es importante destacar, que si un elemento tiene s´ımbolo de Jacobi +1 no implica que sea un residuo cuadr´atico pero si al rev´es. Bas´andonos en esta definici´on, el s´ımbolo de Jacobi puede calcularse en tiempo polinomial. El lenguaje que utilizaremos es QR (del ingl´es quadratic resiudosity) y lo definimos de la siguiente forma: QR ={(p, q) : p∈N, q ∈Z∗ p, Qp(q) = 0}(3.3) 22 CAP´ ITULO 3. PRUEBAS DE CONOCIMIENTO CERO SOBRE LENGUAJES con pyqexpresados en binario. El problema de la residualidad cuadr´atica es calcular Qp(q) dados p∈N,q∈Z∗ py p q= +1, es decir, demostrar que (p, q)∈QR. El siguiente protocolo basar´a su funcionamiento en las siguientes caracter´ısticas de los residuos cuadr´aticos: sea p∈N,q, u ∈Z∗ p, entonces: Si Qp(q) = Qp(u)⇒Qp(qu) = 0. Si Qp(q)6=Qp(u)⇒Qp(qu) = 1. Todas las nociones sobre residuos cuadr´aticos vistas en esta secci´on ser´an necesarias para pr´oximas secciones. Protocolo 3.3. Este protocolo puede consultarse en [11]. Aquiere demostrar a Bque (p, q)∈QR sin mostrarle la evidencia por la que qes un residuo cuadr´atico m´odulo p. a) Fase previa. AyBconocen (p, q) y Aconoce la evidencia de que qes un residuo cuadr´atico m´odulo p. b) Intercambio de mensajes. Los siguientes pasos se repiten mveces y las elecciones aleatorias se hacen de nuevo en cada paso. mes el n´umero de d´ıgitos de pen binario. 1.- A→B:Aescoge aleatoriamente un residuo cuadr´atico m´odpque denotamos uy se lo env´ıa a B. 2.- B→A:Bescoge e∈R{0,1}y se lo env´ıa a A. 3.- A→B:Aescoge aleatoriamente + ´o −de v=±√uqem´od py se lo env´ıa a B. Brecibe v, calcula v2y comprueba que v2=uqe. Si no fuera as´ı rechazar´ıa y parar´ıa. c) Final del protocolo. Si se realizan las mrepeticiones con ´exito, entonces Bacepta y para. Cap´ıtulo 4 Pruebas de conocimiento cero para la identificaci´on En la Secci´on 2.6, al final de Cap´ıtulo 2, dimos un adelanto de lo que ser´ıan las pruebas de conocimiento cero adaptadas a la identificaci´on. En una prueba de conocimiento cero para la identificaci´on, el probador, en posesi´on de un secreto que lo identifica, demuestra al verificador su identidad, sin desvelarle el secreto. En este cap´ıtulo profundizaremos m´as en esta variante de pruebas de conocimiento cero. Realizaremos un desarrollo m´as completo de dos de los protocolos. 4.1. De la membres´ıa a la identificaci´on Fiat y Shamir [8] toman la idea de la identificaci´on a trav´es de pruebas de conocimiento cero y la combinan con las aportaciones de Goldwasser [10] (Cap´ıtulos 2 y 3) y el planteamiento de Shamir [17]. A continuaci´on, expondremos algunas ideas de [17] que nos ser´an ´utiles para describir las pruebas de conocimiento cero para la identificaci´on. Shamir propuso un protocolo criptogr´afico para que un grupo de usuarios se comunicasen entre ellos de forma segura sin la necesidad de intercambiar claves p´ublicas o privadas y sin recurrir a terceros. Aparec´ıan en este protocolo cadenas de valores que conten´ıan la informaci´on necesaria para que el usuario pudiera encriptar y firmar los mensajes que enviaba, y, desencriptar y verificar los mensajes que recib´ıa. Estas cadenas se denominaban tarjetas electr´onicas y cada usuario pose´ıa una. Adem´as, no necesitaban actualizarse cuando ya hab´ıan sido emitidas y entraba un nuevo usuario. En el protocolo de [17] aparec´ıa una nueva entidad: el centro de confianza, que es el que emit´ıa las tarjetas electr´onicas a los usuarios cuando se unen por primera vez al protocolo. Los centros de confianza desaparecen cuando se han emitido todas las tarjetas correspondientes haciendo que la actividad no dependa del centro. La utilidad del centro de confianza en el protocolo de Shamir [17] es la siguiente: el usuario se identifica mediante m´etodos no criptogr´aficos que dependen del contexto al centro de confianza (en [17] se escoge su nombre y correo electr´onico como su clave p´ublica), de manera que pueda identificarse, no retractarse y que para otro usuario esa identificaci´on sea v´alida. Cuando el usuario ya est´a identificado, el centro de confianza 23 30 CAP´ ITULO 4. PRUEBAS PARA LA IDENTIFICACI ´ ON Demostraci´on. Probaremos que es un protocolo completo, robusto y de conocimiento cero computacional: Completitud. Supongamos que Aconoce los s1, ..., sky en el paso 3 ha enviado y=rQk i=1 sei im´od naB. En el paso 4, Bsiempre obtendr´a que z=±xpor como est´an construidos los v1, ..., vk. Por ello, el protocolo es robusto. Robustez. Supongamos que un impostor A∗cualquiera no conoce los s1, ..., sky quiere hacerse pasar por A, para ello, tendr´ıa que escoger los e1, ..., ekque fuera a elegir Ben el paso 2 y adem´as, tomar yaleatorio y escoger x=y2Qk i=1 m´odn. La probabilidad de que acierte la cadena de bits eies de 2−k, y en total en el protocolo 2−kt. Como hemos visto en la Observaci´on 4.2, la probabilidad de que Bacepte la identidad de un impostor es 2−30, un valor ´ınfimo y por lo tanto, el protocolo es robusto. Conocimiento cero computacional. La demostraci´on de que es un protocolo de conocimiento cero computacional es an´aloga a la de la Proposicion 4.2. A continuaci´on compararemos los protocolos vistos en esta secci´on: El centro de confianza es com´un a los tres protocolos pero en cada uno realiza funciones distintas: en el Protocolo 4.1 es el centro de confianza el que otorga los secretos al probador, mientras que en los otros dos, es el propio probador el que escoge los valores. En todos los protocolos hace labor de supervisi´on y desaparece despu´es de que son adjudicadas las claves p´ublicas y privadas. El Protocolo 4.1 es el ´unico que incluye el uso de funciones DES y es tambi´en el m´as arcaico. Este tipo de funciones hoy en d´ıa han sido sustituidas por otras por razones de seguridad. 4.3. Ejemplos Los siguientes ejemplos se realizan con valores m´as peque˜nos que los que se tomar´ıan en una implementaci´on real. Su ´unico fin es clarificar los protocolos de identificaci´on expuestos en esta secci´on. Los c´alculos y la b´usqueda de n´umeros primos se ha hecho a trav´es de la herramienta Mathematica. Se incluyen ejemplos de los Protocolos 4.1, 4.2 y 4.3 Ejemplo 4.1. Utilizando las mismas notaciones que en el Protocolo 4.1: a) Preparaci´on. Se fijan los enteros k= 2 y t= 1. El centro de confianza escoge dos n´umeros primos p= 37 y q= 59, y publica n=pq = 2183. Publica una funci´on DES f(hemos utilizado una que proporciona Mathematica). Cuando Ase identifica al centro de confianza, ´este genera la cadena I= 29. Despu´es, el centro de confianza realiza lo siguiente para poder emitir la tarjeta: 4.3. EJEMPLOS 31 •Calcula un n´umero indeterminado de vj=f(I, j) y escoge los que son un residuo cuadr´atico m´odulo n. Por simplificar notaci´on: j= 1,2, luego v1= 100 yv2= 108 (a trav´es de Mathematica se ha comprobado que son residuos cuadr´aticos). •Calcula s1=v−1/2 1m´od nys2=v−1/2 2m´od ny obtenemos que s1= 655 m´od n ys2= 548 m´od n. •El centro de confianza emite la tarjeta electr´onica (I;s1, s2) para A. Intercambio de mensajes 1.- A→B:Aenv´ıa I= 29 y j= 1,2 a B. 2.- B→A:Bcalcula los v1, v2. 3.- A→B:Aescoge r= 327, calcula x=r2m´od n= 2145 m´od 2183 y env´ıa x= 2145 m´od 2183 a B. 4.- B→A:Bescoge como vector aleatorio (0,1) y se lo env´ıa a A. 5.- A→B:Acalcula y=rs2= 327 ·548 = 190 m´od 2183 y se lo env´ıa a B. 6.- Bcalcula y2= 1172 m´od 2183 e y2v2= 1172 ·108 = 2145 m´od 2183 y comprueba que y2v2=x. c) Finalizaci´on del protocolo Como los pasos solo se realizan una vez porque t= 1 entonces Bacepta la identidad de A. Ejemplo 4.2. Utilizando las mismas notaciones que en el Protocolo 4.2 Preparaci´on. El centro de confianza escoge los n´umeros primos p= 379 y q= 787. Calcula n=pq y publica el resultado n= 298273. El probador, A, toma un s∈Z∗ 298273. Escoge s= 127085 y calcula v=s2m´od n. Calcula s2= 16150597225 = 9094 m´od 298273 y publica v= 9094 m´od 298273 como su clave p´ublica. Intercambio de mensajes. Los siguientes mensajes se realizar´ıan tveces, como es una ejemplo sencillo, tomaremos t= 2. t= 1: •A→B:Atoma un raleatorio con 1 ≤r < 298273 y escoge r= 25868. Calcula x=r2m´od n⇒r2= 669153424 = 127085 m´od 298273 y env´ıa x= 127085 m´od 298273 a B. •B→A:Bescoge aleatoriamente e= 0 ´o e= 1. En este caso escoge e= 1 y se lo env´ıa a A. •A→B:Acalcula y=rsem´od n=rs m´od n⇒y=rs = 25868 ·127085 = 3287434780 = 168047 m´od 298273. Aenv´ıa y= 168047 m´od 298273 a B. 32 CAP´ ITULO 4. PRUEBAS PARA LA IDENTIFICACI ´ ON •Brecibe y, calcula y2m´od npor un lado y xvem´od n, por otro. y2= 28239794209 = 201388 m´od 298273 y xv = 127085·9094 = 1155710990 = 201388 m´od 298273. Como vemos y2=xv por lo tanto Bacepta y pasamos a la siguiente iteraci´on. t= 2: •A→B:Atoma un raleatorio con 1 ≤r < 298273 y escoge r= 29. Calcula x=r2m´od n⇒r2= 841 m´od 298273 y env´ıa x= 841 m´od 298273 a B. •B→A:Bescoge aleatoriamente e= 0 ´o e= 1. En este caso escoge e= 0 y se lo env´ıa a A. •A→B:Acalcula y=rsem´od n⇒y=rporque e= 0. Luego, como r= 29, entonces y= 29 m´od 298273. Aenv´ıa y= 29 m´od 298273 a B. •Brecibe y, calcula y2m´od npor un lado y xvem´od n=xm´od n, por otro. y2= 841 m´od 298273 y x= 841 m´od 298273. Como vemos y2=xv por lo tanto Bacepta. Finalizaci´on del protocolo Como se han completado las dos iteraciones con ´exito, entonces Baceptar´a la identidad de A. Ejemplo 4.3. Utilizando las mismas notaciones que en el Protocolo 4.3. En este caso los enteros seguros que se toman son k= 3 y t= 1 para simplificar el ejemplo, pero como vimos en el Protocolo 4.3 lo mejor es kt = 20. Preparaci´on. El centro de confianza escoge primos aleatorios congruentes a 3 m´od 4, p= 683, q= 811. Calcula n=pq y publica el entero Blum n= 553913. El probador, A, toma tres enteros aleatoriamente si∈Z∗ 553913 con i= 1,2,3. Aescoge s1= 157, s2= 43215, s3= 4646. Despu´es, calcula los viy elige aleatoriamente el signo: v1= 441845, v2= 338402, v3= 124423. Los vipara i= 1,2,3 ser´an la clave p´ublica de A. Intercambio de mensajes. •A→B:Atoma un raleatorio con 1 ≤r < n. Escoge r= 4527, un s´ımbolo + ´o −y calcula x=±r2m´od n⇒x= 20493729 = +552861 m´od 553913. Env´ıa aBel valor x= +552861 m´od 553913 •B→A:Btoma un vector de bits aleatorios (e1, e2, e3). Escoge (0,1,0) y se lo env´ıa a A. •A→B:Acalcula y=r(se1 1se2 2se3 3)⇒y=rs2⇒y= 4527 ·43215 = 195634305 = 103016 m´od 553913 y env´ıa a B y = 103016 m´od 553913. •El verificador ,B, calcula z=y2·(ve1 1ve2 2ve3 3), como el vector binario es (0,1,0), entonces z=y2·v2m´od n.y2= 10612296256 = 431002 m´od 553913 y z= y2·v2= 431002 ·338402 = 145851938804 = 552861 m´od 553913. Y vemos que z= +xporque z= 552861 m´od 553913 y x= 552861 m´od 553913. Finalizaci´on del protocolo. Como se cumple que z=x, entonces Bacepta la identidad de A. Cap´ıtulo 5 Pruebas de conocimiento cero no interactivas y firmas digitales En este cap´ıtulo presentamos las pruebas no interactivas de conocimiento cero y las firmas digitales. Hasta ahora, hab´ıamos visto las pruebas de conocimiento cero interactivas en las que el verificador propon´ıa una especie de desaf´ıo al probador y ´este respond´ıa. En este caso, el probador env´ıa un solo mensaje al verificador que le permite demostrar su conocimiento sobre algo. Las firmas digitales pueden pensarse como pruebas de conocimiento cero no interactivas en las que simplemente se entrega un mensaje que demuestra la autor´ıa del probador o pueden ser una variaci´on de una prueba interactiva de conocimiento cero. En la Secci´on 5.2.3 observaremos tres tipos de firmas digitales: una de ellas est´a basada en la prueba de conocimiento cero no interactiva de la Secci´on 5.1 y las otras dos, en protocolos interactivos de identificaci´on. 5.1. Pruebas de conocimiento cero no interactivas En esta secci´on abordaremos las principales nociones de las pruebas no interactivas de conocimiento cero y un protocolo de este tipo. Volvemos al problema de la pertenencia de un elemento a un lenguaje visto en los Cap´ıtulos 2 y 3, solo que ahora el planteamiento y la soluci´on que se da es distinta. En las pruebas de conocimiento no interactivas no hay intercambio de mensajes entre el verificador y el probador. El probador env´ıa solo una cadena de informaci´on al verificador que le permite comprobar que dice la verdad pero sigue existiendo un componente probabil´ıstico que explicaremos m´as adelante. Si pensamos en el ejemplo de la Secci´on 1.1, Paquita enviar´ıa a los periodistas un mensaje que les permitir´ıa saber que ella conoce la palabra secreta que abre el pasadizo entre los dos pueblos, no habr´ıa intercambio de mensajes de ning´un tipo. Blum, Feldman y Micali en [3] introducen las pruebas de conocimiento cero no interactivas y el problema que tratan es el mismo que en las pruebas interactivas: el probador debe demostrar al verificador la pertenencia de un elemento a un lenguaje. La diferencia con las pruebas interactivas es que el probador env´ıa al verificador solo una cadena con informaci´on, la cual le permite verificar que el probador sabe por qu´e el elemento pertenece 33 34 CAP´ ITULO 5. PRUEBAS NO INTERACTIVAS Y FIRMAS a ese lenguaje. Todas las definiciones y notaciones de m´aquinas de Turing de la Secci´on 2.1 ser´an utilizadas para formalizar la definici´on de prueba de conocimiento cero no interactiva. Los conceptos de completitud y robustez (Secci´on 2.2) sufren modificaciones, pero la idea principal se mantiene: si el elemento est´a en el lenguaje, el probador convence al verificador con una probabilidad cercana a 1 (completitud); y si el elemento no est´a en el lenguaje, el probador convence al verificador con una probabilidad muy cercana a 0 (robustez). En cuanto al conocimiento cero, el planteamiento es el mismo: la vista del verificador durante el protocolo puede ser simulada por una m´aquina de Turing probabil´ıstica ajena a la prueba. La principal diferencia con las pruebas interactivas es que el probador tiene acceso a la cinta aleatoria del verificador. La garant´ıa de que los protocolos sean de conocimiento cero est´a en que el contenido de esta cinta sea aleatorio, es decir, que no se manipule. Por el Cap´ıtulo 2, sabemos que una prueba de conocimiento cero es un sistema de pruebas de conocimiento cero, por lo tanto, vamos a definir un sistema de pruebas no interactivas de conocimiento cero. Para ello, necesitamos redefinir la completitud y la robustez. Para formalizar la definici´on de prueba no interactiva, recurriremos como en el Cap´ıtulo 2 a las m´aquinas de Turing y redefiniremos al probador y al verificador como m´aquinas de Turing: Definici´on 5.1. El probador, A, en una prueba de conocimiento cero no interactiva es una m´aquina de Turing probabil´ıstica con cinco cintas: Una cinta de entrada de solo lectura. Una cinta de trabajo de lectura y escritura. Una cinta aleatoria de solo lectura. Una cinta aleatoria adicional de solo lectura. Una cinta comunicaci´on de solo escritura. Definici´on 5.2. El verificador, Ben una prueba de conocimiento cero no interactiva es una m´aquina de Turing probabil´ıstica con cinco cintas: Una cinta de entrada de solo lectura. Una cinta de trabajo de lectura y escritura. Una cinta aleatoria de lectura. Una cinta de comunicaci´on de solo lectura. Una cinta de salida de solo escritura. Definici´on 5.3. Las dos m´aquinas de Turing de las Definiciones 5.1 y 5.2 forman un par de m´aquinas no interactivas si cumplen lo siguiente: 5.1. PRUEBAS DE CONOCIMIENTO CERO NO INTERACTIVAS 35 La cinta de entrada es com´un a ambas. La cinta de comunicaci´on de ambas es la misma. El probador solo escribe y el verificador solo lee. La cinta aleatoria del verificador es tambi´en visible para el probador. Al par de m´aquinas de Turing que cumple estas caracter´ısticas lo denotamos por (A, B) que es la misma notaci´on que para los sistemas de pruebas interactivas, por lo que siempre se˜nalaremos si da lugar a dudas, si se trata de una prueba interactiva o no interactiva. Observaci´on 5.1. Si comparamos con las pruebas interactivas que hab´ıamos visto hasta el Cap´ıtulo 3, nos encontramos con que la m´aquina de Turing que representa al verificador es distinta a la del probador: en el verificador la cinta de comunicaci´on es de solo lectura y en el probador, de solo escritura; y la cinta aleatoria del verificador, es tambi´en visible para el probador. Recordemos que si el verificador acepta que un elemento est´a en el lenguaje devuelve un 1, si no un 0. Definici´on 5.4. Sea (A, B) un par de m´aquinas de Turing no interactivas y Lun lenguaje, denotamos por [A(x), B(x)] a la distribuci´on de salida de Bcuando tiene como valor de entrada el elemento x∈L. Esta distribuci´on est´a inducida por las cintas aleatorias de las dos m´aquinas. Definici´on 5.5. Un par de m´aquinas de Turing como en la Definici´on 5.3 es un sistema de pruebas no interactivas si el probador no tiene l´ımite computacional, el verificador tiene tiempo esperado polinomial en funci´on del valor de entrada y se verifican las siguientes propiedades: Completitud. Sea un x∈Lsuficientemente grande se cumple que para cada c > 0: P([A(x), B(x)] = 1) >1−|x|−c(5.1) Robustez. Sea un x /∈Lsuficientemente grande se cumple que para cada c > 0: P([A(x), B(x)] = 0) >1−|x|−c(5.2) Una vez vista la definici´on de sistema de pruebas no interactivas vamos a definir un sistema de pruebas no interactivas de conocimiento cero, para ello necesitamos las definiciones y notaciones sobre conocimiento cero de la Secci´on 2.3 que no sufren modificaciones. Definici´on 5.6. Sea (A, B) un sistema de pruebas no interactivas, sea {hA, Bi(x)}x∈L la vista del verificador Bdurante la prueba que tiene como valor de entrada un x∈ L. Decimos que (A, B) es un sistema de pruebas no interactivas de conocimiento cero perfecto (resp. estad´ıstico, resp. computacional) en Lsi la familia de variables aleatorias {hA, Bi(x)}x∈Les perfectamente (resp. estad´ısticamente, resp. computacionalmente) aproximable en L 36 CAP´ ITULO 5. PRUEBAS NO INTERACTIVAS Y FIRMAS A continuaci´on mostramos el sistema de pruebas no interactivas que se propone en [3] que es una prueba de conocimiento cero no interactiva sobre el lenguaje G3Ck= {G(V, E)∈G3C:|V| ≤ k}. Para el desarrollo de este protocolo se necesitar´an las nociones de residuos cuadr´aticos dadas en la Secci´on 3.3 y utilizaremos el conjunto Z+1 p= {q∈Zp:q p= +1}. Protocolo 5.1. Puede consultarse en [3]. El probador, A, quiere demostrar al verificador, B, que un grafo G(V, E) est´a en G3Cksin aportarle una coloraci´on correcta. Ambos conocen G(V, E). Solo Aconoce una coloraci´on correcta de G(V, E). a) Preparaci´on. El probador realiza las siguientes acciones: 1.- Escoge aleatoriamente n1, n2, n3de modo que cada nisea producto de dos primos. 2.- Escoge aleatoriamente q1, q2, q3de modo que qi ni= 1 y qino sea un residuo cuadr´atico m´odulo nipara i= 1,2,3. 3.- Se asignan los colores correspondientes {1,2,3}al grafo G. 4.- A cada v´ertice del grafo con coloraci´on ipara i= 1,2,3 se le asigna una terna (v1, v2, v3)∈Z+1 n1×Z+1 n2×Z+1 n3distinta, donde se verifica que Qni(vi) = 0 y Qnj(vi) = 1 para j6=i. Al grafo con las nuevas asignaciones lo denominamos G0. 5.- Se escogen un n´umero indefinido de ternas aleatorias (z1, z2, z3)∈Z+1 n1×Z+1 n2× Z+1 n3y se asignan 8ka cada una de las aristas del grafo G. 6.- Para cada arista (a, b) del grafo G0(donde a= (a1, a2, a3) y b= (b1, b2, b3)) y para cada una de las 8kternas asignadas a cada arista, (z1, z2, z3), podremos computar solo una de las siguientes firmas: I.- (√z1,√z2,√z3). En el caso en el que cada zisea un residuo cuadr´atico m´odulo nipara i= 1,2,3. II.- (√q1z1,√z2,√z3). En el caso en el que z1no sea un residuo cuadr´atico m´odulo n1y los otros zisi sean un residuo cuadr´atico m´odulo nipara i= 2,3. III.- (√z1,√q2z2,√z3). Lo an´alogo al tipo II para z2. IV.- (√z1,√z2,√q3z3).Lo an´alogo al tipo II para z3. V.- (√a1z1,√a2z2,√a3z3). En el caso en el que dos de los zino sean residuos cuadr´aticos m´odulo ni. VI.- (√b1z1,√b2z2,√b3z3).En el caso en el que dos de los zino sean residuos cuadr´aticos m´odulo ni VII.- (√a1b1z1,√a2b2z2,√a3b3z3).En el caso en el que dos de los zino sean residuos cuadr´aticos m´odulo ni. VIII.- (√q1z1,√q2z2,√q3z3). En el caso en el que ning´un zisea residuo cuadr´atico m´odulo nipara i= 1,2,3. 5.2. FIRMAS DIGITALES 37 b) Mensaje enviado. El probador env´ıa al verificador los n1, n2, n3, q1, q2, q3, G0y las firmas de cada una de las ternas que hemos obtenido del paso 6. c) Final de la prueba. El verificador comprueba que los n1, n2, n3no son potencia de ning´un entero y que se cumple que (v1, v2, v3)∈Z+1 n1×Z+1 n2×Z+1 n3. Tambi´en comprueba que las firmas del paso 6 est´an bien hechas. Si se cumplen estas condiciones entonces el verificador acepta que el grafo Ges 3-coloreable Observaci´on 5.2. Ahora veamos unas observaciones sobre el Protocolo 5.1: En el paso 4, se asignan ternas a cada v´ertice de modo que para un v´ertice de color iel elemento vide la terna sea un residuo cuadr´atico m´odulo ni. En el paso 5, los zise escogen utilizando la cinta aleatoria que es com´un a probador y verificador. La elecci´on de 8kternas para cada arista es porque hay 8 tipos de firma y as´ı se logra que el protocolo sea m´as seguro, y por consiguiente, robusto [3]. En cuanto a la verificaci´on de la firma, recibe el grafo G0pero no puede acceder al color de los v´ertices porque no puede comprobar si un elemento es residuo cuadr´atico, ya que no conoce la descomposici´on de los ni. Para comprobar las 8kfirmas de cada arista, comprueba que el cuadrado de cada elemento de las ternas puede ser divisible por alg´un qi(firmas II, III, IV, VIII) o alguno de los vi(firmas V, VI, VII). Alguno podr´ıa tener la firma I, pero es por ello que se env´ıan tantas firmas, para que la probabilidad de que se tome siempre la firma I sea ´ınfima. 5.2. Firmas digitales En esta secci´on presentamos tres protocolos de firmas digitales. Cada uno est´a enfocado de una manera distinta pero todos est´an basados en pruebas de conocimiento cero interactivas y no interactivas. 5.2.1. Firma digital de Fiat y Shamir Fiat y Shamir [8] proponen esta firma digital que est´a basada en el Protocolo 4.1 de identificaci´on del cap´ıtulo anterior. Como dec´ıamos en la Secci´on 4.1, las tarjetas electr´onicas que emite el centro de confianza adem´as de permitir encriptar y desencriptar, tambi´en permiten firmar y verificar mensajes. Para este protocolo de firma partimos desde la fase previa del Protocolo 4.1, donde el probador Arecibe del centro de confianza la tarjeta electr´onica. Protocolo 5.2 (Firma Fiat-Shamir [8]).Supongamos que Aquiere firmar un mensaje m, mand´arselo a By que Bverifique que la firma es de A. 38 CAP´ ITULO 5. PRUEBAS NO INTERACTIVAS Y FIRMAS a) Preparaci´on. Se fijan los enteros kyt. El centro de confianza realiza los siguientes pasos: •Escoge dos n´umeros primos secretos pyq, y publica su producto n=pq. •Publica una funci´on DES, fque asigna cadenas arbitrarias a valores en Zn. El probador se identifica al centro de confianza mediante m´etodos no criptogr´aficos. Despu´es, el centro crea una cadena Ique contiene informaci´on sobre el usuario(nombre, direcci´on, correo) y sobre la tarjeta(fecha de espiraci´on, limitaciones de validez). Para crear esta tarjeta realizan los siguientes pasos: •Calcula un n´umero indeterminado de vj=f(I, j) para j= 0,1, .... •De todos los vjescoge kcualesquiera de modo que vjes un residuo cuadr´atico m´odulo n. Para simplificar la notaci´on tomaremos j= 1, ..., k. •Calcula sjque es la ra´ız cuadrada m´as peque˜na de v−1 jm´od npara j= 1, ..., k. •El centro emite como tarjeta para Ala cadena (I;s1, ..., sk). Los sjson el secreto de A. El firmante, A, realiza los siguientes pasos: 1.- Escoge enteros aleatoriamente ride modo que 1 ≤ri< n. Calcula xi= r2 im´od npara i= 1, ..., t. 2.- Calcula f(m, x1, ..., xt) con fla funci´on DES y toma los kt primeros bits como valores eij con 1 ≤i≤t, 1≤j≤k. 3.- Calcula yipara i= 1, ..., t: yi=riY eij =1 sjm´od n(5.1) b) Env´ıo de firma.Aenv´ıa I, m, la matriz eij,y todos los yiaB. c) Comprobaci´on de firma.Bcalcula vj=f(I, j) para j= 1, ..., k, zi=y2 iQeij =1 vjm´od npara i= 1, .., t y comprueba que los primeros kt bits de f(m, z1, ..., zt) son los eij. Para obtener este protocolo de firma se ha cambiado el papel que desempe˜na el verificador Ben el Protocolo 4.1 por la funci´on DES f. En esta firma,para conseguir un nivel de seguridad alto, se tiene que aumentar como m´ınimo a kt = 72 [8] y no kt = 20 (Protocolo 4.1 de identificaci´on). 5.2. FIRMAS DIGITALES 39 5.2.2. Firma digital de Bellarre y Goldwasser Bellare y Goldwasser [2] presentan un protocolo de firma digital basado en las pruebas no interactivas de conocimiento cero y las funciones pseudoaleatorias. Definici´on 5.7. Una funci´on pseudoaleatoria es una funci´on cuya imagen es computacionalmente f´acil de calcular y para la que no existe un algoritmo de tiempo polinomial probabil´ıstico que la diferencie de una funci´on aleatoria [15]. Las pruebas de conocimiento cero no interactivas que definen est´an basadas en las vistas en la Secci´on 5.1 de [3] pero incluyendo algunos cambios: la prueba se divide en dos fases: la fase preparatoria y la de demostraci´on. En la primera fase se establece alguna informaci´on com´un para probador y verificador (en relaci´on a las pruebas de la Secci´on 4.1 esa informaci´on com´un ser´ıa la cadena de bits aleatorios σ), e informaci´on privada para cada uno . En la segunda fase, el probador demuestra al verificador que conoce una informaci´on sin revelarla, utilizando la informaci´on de la primera etapa. El proceso de la primera etapa es independiente de lo que vaya a probarse en la segunda etapa. Nota 5.1. Una colecci´on de funciones pseudoaleatorias la denotamos as´ı Fk={fs:|s|= k}. Para la firma digital de Bellarre y Goldwasser basada en su propuesta de prueba no interactiva de conocimiento cero [2], la fase previa la realizar´ıa un centro de confianza y su funcionamiento ser´ıa el siguiente: el firmante (probador) recibe del centro de confianza una tarjeta electr´onica que le permite firmar los mensajes. Antes de pasar al protocolo haremos algunas aclaraciones: para este protocolo es necesaria tambi´en una prueba no interactiva de conocimiento cero verificable p´ublicamente para alg´un lenguaje NP; y, como ya hemos aclarado antes, la fase previa del protocolo para firma digital es sustituida por un centro de confianza al que se identifican los usuarios y ´estos reciben las claves para firmar y verificar. Nota 5.2. Sea (A, B) una prueba de conocimiento cero no interactiva denotamos (A, B)γ a la prueba de conocimiento cero no interactiva que tiene γcomo cinta aleatoria com´un. Nota 5.3. Denotamos Ea un algoritmo cualquiera de encriptaci´on de clave p´ublica probabil´ıstica. Protocolo 5.3 (Bellarre Goldwasser [2]).El probador A, quiere firmar un mensaje m yBdebe verificarlo. a) Preparaci´on. Todos los participantes en la firma obtienen del centro de confianza la clave p´ublica (1k, E, α, γ), su clave privada (r, s) y la funci´on pseudoaleatoria fs: 1.- kes un entero seguro. 2.- s∈R{0,1}es el ´ındice de la funci´on pseudoaleatoria. 3.- α=E(r, s) es una encriptaci´on de s. 4.- γes la informaci´on com´un de la prueba (A, B). El firmante calcula R=fs(m) 46 CAP´ ITULO 6. UNA APLICACI ´ ON ACTUAL dentro de un rango sin revelar al verificador ese valor. Este protocolo cuenta tambi´en con un centro de confianza que participa en la preparaci´on del protocolo. Saber si un valor est´a dentro de un rango puede resultar ´util en finanzas, probando que un salario es suficiente para alquilar o pedir una hipoteca, y tambi´en, para la localizaci´on, probando que algo o alguien est´a dentro de unos l´ımites geogr´aficos sin mostrar la localizaci´on exacta. Protocolo 6.1. [13] Un probador, A, quiere demostrar a un verificador, B, que un valor mse encuentra entre {a, a + 1, ..., b}. a) Preparaci´on. El centro de confianza realiza lo siguiente: 1.- Escoge dos primos pyqde modo que (p−1)/2 sea tambi´en un primo. Publica n=pq. 2.- Toma generadores de Z∗ pyZ∗ q,gyhrespectivamente. Los valores n, g, h son p´ublicos para el probador y el verificador. El probador quiere demostrar que m∈ {a, a + 1, ..., b}, esto se cumple si y solo si (m−a+ 1)(b−m+ 1) >0. El probador, A, lleva a cabo los siguientes pasos: 3.- Escoge un entero aleatorio ry calcula c=gmhrm´od n. 4.- Escoge un entero aleatorio, w, distinto de 0 y calcula: ◦c1=c ga−1m´od n. ◦c2=gb−1 cm´od n. ◦Toma un entero aleatorio r0y obtiene c0=cb−m+1 1hr0m´od n. ◦Toma un entero aleatorio r00 y obtiene c00 =c0w2hr00 m´od n. 5.- Escoge enteros no negativos m1, m2, m3, r1, r2, r3de modo que cumplan los siguiente: ◦m1+m2+m3=w2(m−a+ 1)(b−m+ 1). ◦r1+r2+r3=w2((b−m+ 1)r+r0) + r00. 6.- Calcula: ◦c0 1=gm1hr1m´od n. ◦c0 2=gm2hr2m´od n. ◦c0 3=gm3hr3m´od n. 7.- Tomando enteros aleatorios positivos syt, y se calcula: ◦x=sm1+m2+m3. ◦y=m1+tm2+m3. ◦u=sr1+r2+r3. ◦v=r1+tr2+r3 6.2. PRUEBAS DE RANGO DE CONOCIMIENTO CERO 47 b) Env´ıo de mensaje. El probador env´ıa al verificador la cadena: (c, c1, c2, c0, c00, c0 1, c0 2, c1c0 3, x, y, u, v) (6.1) c) Final del protocolo. El verificador comprueba que: 9.- Comprueba: ◦c1=c ga−1m´od n. ◦c2=gb+1 cm´od n. ◦c00 =c0 1c0 2c0 3m´od n. 10.- Comprueba: ◦c0 1c0 2c0 3=gxhum´od n. ◦c0 1c0 2c0 3=gyhvm´od n. 11.- Verifica que x > 0 e y > 0. Si se superan con ´exito los pasos 9, 10 y 11, el valor mse encuentra en el rango {a, ..., b}. Observaci´on 6.1. Veamos algunas observaciones sobre el protocolo anterior: Una opci´on m´as sencilla podr´ıa haber sido que el probador enviara xeydirectamente al verificador y que ´este comprobara que eran positivos. El problema que trae es que el probador puede escoger dos n´umeros aleatorios positivos y que el verificador aceptara, es por ello, que se recurren a otros valores que el verificador pueda comprobar. La elecci´on de los enteros aleatorios r0, r00, w, r1, r2, r3, m1, m2, m3se hace para utilizarlos para ocultar los valores de los que son potencias. La seguridad se basa en la dificultad de resolver un logaritmo discreto. El uso de este tipo de pruebas no interactivas resulta m´as c´omodo y seguro que una prueba interactiva. ´ Esto es debido a que muchas veces no es factible un intercambio de mensajes y por lo tanto, un solo mensaje y una comprobaci´on resultan m´as eficientes. ¿Cu´al es la utilidad de las pruebas de rango de conocimiento cero en el blockchain?Como hemos explicado, para registrar un nuevo bloque, ´este debe pasar una serie de verificaciones o pruebas. Las pruebas de conocimiento cero permiten comprobar que la informaci´on que se va a a˜nadir a un nuevo bloque es correcta sin poner en peligro dicha informaci´on. Por una parte, se realizar´ıan pruebas de conocimiento cero de identificaci´on y, por otra, dependiendo del contexto, una prueba de conocimiento cero de rango para determinar si el valor que se pretende a˜nadir es correcto. 48 CAP´ ITULO 6. UNA APLICACI ´ ON ACTUAL Conclusi´on El objetivo principal de este trabajo es dar una idea general de las pruebas de conocimiento cero, desde sus or´ıgenes como pruebas de membres´ıa hasta una de sus aplicaciones actuales, pasando por los protocolos de identificaci´on y de firma. Se ha hecho una revisi´on de la bibliograf´ıa m´as destacada sobre el tema y se ha estructurado cronol´ogicamente en el trabajo. Las pruebas de conocimiento cero permiten que el probador transmita al verificador que conoce una informaci´on sin revelarla. Estas pruebas tienen un amplio futuro por delante puesto que mantener una informaci´on en secreto puede resultar muy ´util. Hoy en d´ıa, es necesario seguir reinvent´andose en cuanto a seguridad, porque siempre puede haber impostores o trampas que pongan en peligro informaci´on delicada. A lo largo de todo el trabajo hemos podido observar la evoluci´on de la idea de conocimiento cero y como se ha ido adaptando seg´un las necesidades. En un primer momento, se presenta como la demostraci´on de la pertenencia de un elemento a un lenguaje a trav´es de un intercambio de mensajes (Cap´ıtulos 2 y 3), siendo un concepto m´as te´orico que pr´actico y con menos aplicaciones. Despu´es, los conceptos te´oricos se adaptan a la identificaci´on y se crean los primeros protocolos de identificaci´on de conocimiento cero (Cap´ıtulo 4), tambi´en interactivos. Posteriormente, se consiguen protocolos en los que no es necesario un intercambio de mensajes y se obtienen las pruebas no interactivas de conocimiento cero, que dan lugar a las firmas digitales de este tipo (Cap´ıtulo 5). Por ´ultimo, se describe una nueva adaptaci´on del concepto de prueba de conocimiento cero donde el probador demuestra al verificador que un valor pertenece a un rango sin mostrar dicho valor(Cap´ıtulo 6). Adem´as, se ofrece una aplicaci´on de este tipo de pruebas en la actualidad. Uno de los problemas a los que me he enfrentado al realizar este trabajo ha sido la escasez y la disparidad de bibliograf´ıa, y que ´esta estaba destinada a un p´ublico m´as t´ecnico que te´orico. En muchas ocasiones la labor del trabajo ha sido la de formalizar algunos conceptos que no resultaban del todo claros. Es el caso de una de las partes fundamentales de las pruebas de conocimiento cero, las m´aquinas de Turing probabil´ısticas, puesto que la bibliograf´ıa sobre este tema era casi inexistente y este trabajo pretend´ıa dar una definici´on de prueba de conocimiento cero lo m´as formalizada posible. Otro problema que encontr´e era que la mayor´ıa de protocolos de la bibliograf´ıa no estaban explicados de una manera clara y detallada, por lo que se ten´ıan que analizar minuciosamente para encontrar las bases te´oricas de los protocolos. A pesar de todo esto, he conseguido ampliar mi conocimiento sobre el tema que era el principal objetivo al realizar este trabajo. Tambi´en he desarrollado capacidad de an´alisis y s´ıntesis debido a la bibliograf´ıa dispar. 49 50 CAP´ ITULO 6. UNA APLICACI ´ ON ACTUAL Bibliograf´ıa [1] Babai, L. Graph isomorphism in quasipolynomial time. In Proceedings of the fortyeighth annual ACM symposium on Theory of Computing (2016), pp. 684–697. [2] Bellare, M., and Goldwasser, S. New paradigms for digital signatures and message authentication based on non-interactive zero knowledge proofs. In Advances in Cryptology—CRYPTO’89 Proceedings. [3] Blum, M., Feldman, P., and Micali, S. Non-interactive zero-knowledge and its applications. In Proceedings of the twentieth annual ACM symposium on Theory of computing (1988), pp. 103–112. [4] Cecilia Pastorino. Blockchain: qu´e es, c´omo funciona y c´omo se est´a usando en el mercado. https://www.welivesecurity.com/la-es/2018/09/04/ blockchain-que-es-como-funciona-y-como-se-esta-usando-en-el-mercado/. [5] Encyclopedia of Mathematics. Probabilistic Turing Machine. http://encyclopediaofmath.org/index.php?title=Probabilistic_Turing_ machine&oldid=31204. [6] Encyclopedia of Mathematics. Turing Machine. http:// encyclopediaofmath.org/index.php?title=Turing_machine&oldid=31220. [7] Feige, U., Fiat, A., and Shamir, A. Zero-knowledge proofs of identity. Journal of cryptology 1, 2 (1988), 77–94. [8] Fiat, A., and Shamir, A. How to prove yourself: Practical solutions to identification and signature problems. In Conference on the theory and application of cryptographic techniques (1986), Springer, pp. 186–194. [9] Goldreich, O., Micali, S., and Wigderson, A. Proofs that yield nothing but their validity or all languages in np have zero-knowledge proof systems. Journal of the ACM (JACM) 38, 3 (1991), 690–728. [10] Goldwasser, S., Micali, S., and Rackoff, C. The knowledge complexity of interactive proof-systems. In Proceedings of the seventeenth annual ACM symposium on Theory of computing (1985), pp. 291–304. [11] GOLDWASSER, S., MICALI, S., and RACKOFF, C. The knowledge complexityof interactive proof systems. SIAM J. COMPUT 18, 1 (1989), 186–208. 51 52 BIBLIOGRAF´ IA [12] Jain, G. Zero knowledge proofs: A survey. University of Pennsylvania (2008). [13] Koens, T., Ramaekers, C., and Van Wijk, C. Efficient zero-knowledge range proofs in ethereum. [14] Menezes, A. J., Katz, J., Van Oorschot, P. C., and Vanstone, S. A. Handbook of applied cryptography. CRC press, 1996. [15] Pass, R., and Shelat, A. A course in cryptograph. Theoretical Foundation of Cryptography (2010), 68–71. [16] Schnorr, C.-P. Efficient signature generation by smart cards. Journal of cryptology 4, 3 (1991), 161–174. [17] Shamir, A. Identity-based cryptosystems and signature schemes. In Workshop on the theory and application of cryptographic techniques (1984), Springer, pp. 47–53. [18] Stinson, D. R., and Paterson, M. Cryptography: theory and practice. CRC press, 2018.