Pruebas de conocimiento cero

P uebas de conocimien o ce o Do iana He n´andez Fe n´andez T abajo de Fin de G ado Di igido po Jos´e Ignacio Iglesias Cu o F ancisco Jos´e Plaza Ma ´ın G ado en Ma em´a icas Facul ad de Ciencias Julio 2020 2 P uebas de conocimien o ce o Do iana He n´andez Fe n´andez T abajo de Fin de G ado Di igido po Jos´e Ignacio Iglesias Cu o F ancisco Jos´e Plaza Ma ´ın G ado en Ma em´a icas Facul ad de Ciencias Julio 2020 2 ´ Indice gene al 1. In oducci´on 5 1.1. Ejemplo ..................................... 6 2. P uebas de conocimien o ce o 7 2.1. M´aquinasdeTu ing............................... 7 2.2. P o ocolos y sis emas de p uebas in e ac i as . . . . . . . . . . . . . . . . . 9 2.3. Conocimien oce o ............................... 11 2.3.1. Indis inguibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3.2. In oducci´on al conocimien o ce o . . . . . . . . . . . . . . . . . . . 13 2.4. P uebas de conocimien o ce o . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.5. Lenguajes en los p o ocolos. . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.6. M´as all´a de los lenguajes. . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3. P uebas de conocimien o ce o sob e lenguajes 17 3.1. Isomo ismodeg a os.............................. 17 3.2. G a os3-colo eables............................... 19 3.3. Residuoscuad ´a icos .............................. 21 4. P uebas pa a la iden i icaci´on 23 4.1. De la memb es´ıa a la iden i icaci´on . . . . . . . . . . . . . . . . . . . . . . 23 4.2. P o ocolos de Fia y Shami . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.3. Ejemplos..................................... 30 5. P uebas no in e ac i as y i mas 33 5.1. P uebas de conocimien o ce o no in e ac i as . . . . . . . . . . . . . . . . . 33 5.2. Fi masdigi ales................................. 37 5.2.1. Fi ma digi al de Fia y Shami . . . . . . . . . . . . . . . . . . . . 37 5.2.2. Fi ma digi al de Bella e y Goldwasse . . . . . . . . . . . . . . . . 39 5.2.3. Fi ma digi al de Schno . . . . . . . . . . . . . . . . . . . . . . . . 40 5.3. Ejemplos..................................... 41 6. Una aplicaci´on ac ual 45 6.1. Blockchain .................................... 45 6.2. P uebas de ango de conocimien o ce o . . . . . . . . . . . . . . . . . . . . 45 Conclusi´on 49 3 4´ INDICE GENERAL Bibliog a ´ıa 52 Cap´ı ulo 1 In oducci´on Las p uebas de conocimien o ce o son p o ocolos c ip og ´a icos en los que pa icipan dos en idades o pa icipan es: el p obado y el e i icado . El p obado debe demos a al e i icado que conoce una in o maci´on sin e ela la. Las ´a eas en las que a a cen a se el abajo se ´an ´algeb a, en pa icula , c ip og a ´ıa, y p obabilidad. La apa ici´on de las p uebas de conocimien o ce o supone un plan eamien o nue o, pues o que no se ansmi e la in o maci´on en s´ı, sino una ga an ´ıa de que se conoce esa in o maci´on. En o os m´e odos de enc ip aci´on se ocul aba la in o maci´on que se que ´ıa man ene en sec e o y exis ´ıa la posibilidad de accede a la in o maci´on ompiendo el p o ocolo. La p ime a menci´on a las p uebas de conocimien o ce o la ealizan Goldwasse , Micali y Racko en 1985 [10], p esen an las p uebas de conocimien o ce o como una p ueba in e ac i a pa a demos a la pe enencia de un elemen o a un lenguaje sin demos a nada m´as que la pe enencia. Pos e io men e, en 1987, Fia y Shami p esen an un p o ocolo de iden i icaci´on [8] u ilizando la idea de p ueba de conocimien o ce o in e ac i a de Goldwasse , Micali y Racko . Aqu´ı, se pasa de demos a la pe enencia de un elemen o a un lenguaje, a demos a la iden idad de un pa icipan e o en idad, bas´andose en el conocimien o de un sec e o que solo el p obado conoce. Adem´as de p esen a un p o ocolo de iden i icaci´on, p esen an un p o ocolo de i ma digi al. En 1988, Blum, Feldman y Micali p esen an las p uebas de conocimien o ce o no in e ac i as [3] que mejo an la idea de conocimien o ce o haci´endola no in e ac i a, ya que en algunos con ex os no e a ac ible. Es as p uebas uel en al p oblema de demos a que un elemen o pe enece a un lenguaje. Bella e y Goldwasse , ecogen la idea de p ueba no in e ac i a de conocimien o ce o y cons uyen un p o ocolo de i ma digi al en 1990 [2]. Ac ualmen e, las p uebas de conocimien o ce o se aplican en Blockchain [13] y, en gene al, en p ocesos en los que se necesi a man ene un ni el de segu idad al o. La memo ia que se p esen a con iene una is a gene al de las p uebas de conocimien o ce o en odas sus o mas y a ian es, as´ı como una e oluci´on del concep o y sus di e en es adap aciones. Adem´as, con iene p o ocolos de es e ipo de p uebas jun o con ejemplos conc e os. El abajo se di ide en seis cap´ı ulos: al inal del cap´ı ulo en el que nos encon- amos, o ecemos un ela o ejempli icado de lo que es una p ueba de conocimien o ce o. En el Cap´ı ulo 2, p esen amos las p uebas de conocimien o ce o, pa a ello apo amos unas 5 6CAP´ ITULO 1. INTRODUCCI ´ ON nociones p e ias pa a o maliza la de inici´on de es as p uebas. En el Cap´ı ulo 3, mos a- mos es casos conc e os de p uebas de conocimien o ce o sob e lenguajes y el desa ollo comple o de uno de ellos en base a las de iniciones del Cap´ı ulo 2. En el Cap´ı ulo 4, pasa- mos a las p uebas de conocimien o ce o pa a la iden i icaci´on, se abo dan es p uebas de es e ipo y se incluyen ejemplos de las mismas. En el Cap´ı ulo 5, se exponen las p uebas de conocimien o ce o no in e ac i as, las i mas digi ales y a ios ejemplos de ellos. En el Cap´ı ulo 6, p esen amos una aplicaci´on ac ual que ienen las p uebas de conocimien o ce o y c´omo se ha adap ado la idea al blockchain. Po ´ul imo, incluimos una conclusi´on inal del desa ollo del abajo. 1.1. Ejemplo Explica emos una p ueba de conocimien o ce o u ilizando un ela o pa a ene una idea gene al de lo que es una p ueba de es e ipo. Como ya sabemos, en las p uebas de conocimien o ce o pa icipan dos en idades: el p obado y el e i icado , donde el p obado demues a al e i icado que conoce una in o maci´on sin e ela la. En es e ela o nos encon amos a Paqui a, que es el p obado , a los pe iodis as, que son el e i icado y la palab a sec e a, que es la in o maci´on que posee el p obado y que no quie e que nadie conozca. Supongamos dos pueblos llamados Macondo y B ee si uados en una isla, y que adem´as es ´an sepa ados po una mon a˜na inaccesible. Cada pueblo iene una cue a sin salida en su lado de la mon a˜na. No exis e ning´un ipo de conexi´on en e ambos pueblos po que ning´un habi an e se a e e a echa se a la ma y po que ninguno es capaz de escala la mon a˜na. Paqui a es una habi an e de uno de es os pueblos, no e ela de cu´al, y quie e demos a al mundo que conoce una pue a sec e a que conec a ambos pueblos. Es a pue a conec a ´ıa las cue as de cada pueblo y solo se ab i ´ıa u ilizando una palab a sec e a que solo Paqui a conoce. Como quie e que nadie conozca la palab a sec e a se pone en con ac o con unos pe iodis as pa a demos a les que conoce la palab a m´agica sin dec´ı sela. Un equipo de pe iodis as o ´aneos son los que comp oba ´an que Paqui a conoce la palab a sec e a. El p o ocolo que se sigue es el siguien e: el equipo de pe iodis as se aleja de la isla y pide a Paqui a que en e en la cue a de su pueblo. Cuando Paqui a se encuen a den o de la cue a, a isa a los pe iodis as que lanzan una moneda: si sale ca a piden a Paqui a que salga po la en ada de Macondo; si sale c uz, po la de B ee. Despu´es de lanza la moneda, los pe iodis as an a la en ada de la cue a co espondien e. Paqui a sale po la cue a que le piden, los pe iodis as uel en a aleja se y Paqui a eg esa a su pueblo. Vis o as´ı, pod ´ıa pensa se que si Paqui a se encuen a en la cue a de B ee y los pe iodis as le piden que salga po la en ada de B ee, Paqui a no end ´ıa po qu´e sabe se la palab a m´agica. Po ello, es e p oceso se epi e a ias eces pa a educi la p obabilidad lo m´aximo posible de que Paqui a salga po la misma cue a que en ´o. Al inaliza odo el p oceso, Paqui a ha demos ado al mundo que exis e una pue a m´agica que une dos pueblos y que solo ella conoce la palab a que la ab e. Si enemos p esen e es e ejemplo du an e las siguien es p´aginas nos esul a ´a m´as ´acil comp ende las nociones que amos a da . Cap´ı ulo 2 P uebas de conocimien o ce o En es e cap´ı ulo abo da emos las nociones p e ias necesa ias pa a pode da una de inici´on o mal de lo que es una p ueba de conocimien o ce o. Es as nociones incluyen las m´aquinas de Tu ing, los p o ocolos in e ac i os y los sis emas de p uebas in e ac i as. Adem´as, pa a pode de ini lo que es el conocimien o ce o o malmen e, p esen a emos el concep o de indis inguibilidad. 2.1. M´aquinas de Tu ing En es a secci´on p esen amos la de inici´on de m´aquina de Tu ing y de las a ian es pa a pode de ini con igo las p uebas de conocimien o ce o. La bibliog a ´ıa sob e es e ema e a bas an e escasa y ue necesa io hace una combinaci´on de oda la in o maci´on encon ada sob e m´aquinas de Tu ing pe o en pa icula de [5] y [6] , y del ipo de m´aquina de Tu ing que se necesi aba pa a o maliza la de inici´on de p ueba de conocimien o ce o [10]. Los dos pa icipan es de una p ueba de conocimien o ce o pueden pensa se como dos m´aquinas de Tu ing que in e ac ´uan en e s´ı. Es o nos se ´a ´u il pa a da la de inici´on o mal de una p ueba de conocimien o ce o. Una m´aquina de Tu ing es un disposi i o e´o ico que posee una memo ia ex e na in ini- a denominada cin a, di idida en celdas; que adop a un es ado in e no en cada momen o; y que con iene unas ins ucciones. Cada una de las celdas con iene un s´ımbolo de un al abe o o un espacio en blanco (#) y hay un selec o que de e mina qu´e celda es ´a leyendo la m´aquina en ese momen o. En cuan o a los es ados in e nos, hay dos que son los m´as especiales: el es ado inicial, es deci , el es ado in e no de la m´aquina cuando se ac i a; y el es ado inal, que es el es ado in e no al que pasa la m´aquina y despu´es pa a. Las ins ucciones de la m´aquina especi ican que dados un es ado in e no y un s´ımbolo le´ıdo, en onces se pasa a o o es ado in e no, o o s´ımbolo y hacia d´onde debe mo e se el selec o de celdas. Pod ´ıa da se el caso de que el es ado in e no o el s´ımbolo no cambia an, as´ı como que el selec o se man u ie a en el mismo si io. De inici´on 2.1. Una m´aquina de Tu ing es una 6-´upla (Q, q0, q , S, #, δ) donde: Qes un conjun o ini o. Es e conjun o con iene odos los es ados in e nos de la m´aquina. 7 14 CAP´ ITULO 2. PRUEBAS DE CONOCIMIENTO CERO De inici´on 2.22. [11] Sea (A, B) un p o ocolo in e ac i o en L⊂ {0,1}∗y sea B∗una m´aquina de Tu ing in e ac i a cualquie a. Decimos que (A, B) es un p o ocolo in e ac i o de conocimien o ce o pe ec o ( esp. es ad´ıs ico, compu acional), si la amilia de a iables alea o ias {hA, B∗i(x)}x∈Les pe ec amen e ( esp. es ad´ıs icamen e, compu acionalmen- e) ap oximable en L. Vemos que lo que obse a el e i icado du an e el p o ocolo y lo que gene a una m´aquina de Tu ing p obabil´ıs ica se ´a indis inguible pe ec a, es ad´ıs ica o compu acio- nalmen e. Po lo an o, un p o ocolo in e ac i o puede se de conocimien o ce o pe ec o, es ad´ıs ico o compu acional. Una ez is o es o, pasemos a las p uebas de conocimien o ce o. 2.4. P uebas de conocimien o ce o En es a secci´on a amos inalmen e la de inici´on o mal de una p ueba de conocimien o ce o, p ime o dando la e si´on m´as p ´ac ica y pos e io men e la o mal. Reco demos que una p ueba de conocimien o ce o es un p o ocolo c ip og ´a ico con dos en idades: el p obado y el e i icado , donde el p obado debe demos a al e i icado que conoce una in o maci´on sec e a sin e ela la. [12] Las p incipales ca ac e ´ıs icas de las p uebas de conocimien o ce o son: 1.- El e i icado no puede ob ene nada ´u il del p o ocolo, es deci , no puede ob ene in o maci´on sensible del p o ocolo. 2.- El e i icado no iene capacidad de hace se pasa po el p obado que ha e i icado, es deci , los mensajes que se in e cambian en el p o ocolo no pueden u iliza se pa a hace se pasa po el p obado que se es ´a e i icando. 3.- La p obabilidad de que el e i icado acep e una decla aci´on alsa como e dade a es muy peque˜na. 4.- La p obabilidad de que el e i icado sea con encido de una decla aci´on que es e dade a es muy al a. Las p uebas de conocimien o ce o son p o ocolos in e ac i os obus os (De inici´on 2.14), comple os (De inici´on 2.13) y de conocimien o ce o (De inici´on 2.22).Tambi´en puede pensa se como un sis ema de p uebas in e ac i as (De inici´on 2.15) de conocimien o ce o. De inici´on 2.23. [11] Sea (A, B) un sis ema de p uebas in e ac i as en L⊂ {0,1}∗, (A, B) es de conocimien o ce o pe ec o ( esp. es ad´ıs ico, compu acional) si es un p o o- colo in e ac i o de conocimien o ce o pe ec o ( esp. es ad´ıs ico, compu acional). Si obse amos las ca ac e ´ıs icas que ienen las p uebas de conocimien o ce o, emos que un sis ema de p uebas de conocimien o ce o ambi´en las cumpli ´a: Las ca ac e ´ıs icas 1 y 2, las cumple debido a la p opiedad de conocimien o ce o del sis ema de p uebas; la ca ac e ´ıs ica 3 es la obus ez po se un sis ema de p uebas in e ac i as; y la 4 es la comple i ud, ambi´en de un sis ema de p uebas in e ac i as. 2.5. LENGUAJES EN LOS PROTOCOLOS. 15 2.5. Lenguajes en los p o ocolos. Has a aho a, las p uebas de conocimien o ce o que hemos de inido es ´an basadas en demos a la pe enencia de un elemen o a un lenguaje. Es a idea, se ´a ecogida po o os au o es [8] pa a ob ene o os ipos de p uebas de conocimien o ce o que e emos en la siguien e secci´on y en el Cap´ı ulo 4. La segu idad de es e ipo de p uebas eside en que demos a que un elemen o pe e- nece a un lenguaje es un p oblema de decisi´on. En es a secci´on da emos algunas nociones sob e es os p oblemas y la elaci´on que ienen con los lenguajes que se u ilizan en las p uebas de conocimien o ce o. De inici´on 2.24. Un p oblema es Psi exis e un algo i mo que puede esol e lo en iempo polin´omico. Si no puede esol e se en es e iempo, se dice que es NP. De inici´on 2.25. Un lenguaje es Psi demos a que un elemen o pe enece a ese lenguaje es un p oblema P. Lo an´alogo pa a los lenguajes NP. Podemos e que si un lenguaje es P, el e i icado pod ´a p oba que el elemen o es ´a en el lenguaje sin necesidad de in e ac ua con el p obado . Po o o lado, si el lenguaje es NP al e i icado le esul a ´a m´as complicado p oba lo. Es po es o que los lenguajes a los que se ecu i ´a pa a las p uebas de conocimien o ce o se ´an NP. En el siguien e cap´ı ulo explica emos p uebas de conocimien o ce o sob e dis in os lenguajes. Los au o es [11] [9] ecu en a una nue a de inici´on de lenguajes: De inici´on 2.26. Un lenguaje es un conjun o pa a el cual es compu acionalmen e di ´ıcil p oba la memb es´ıa de un elemen o. Un lenguaje es compu acionalmen e di ´ıcil po que es un lenguaje P´o NP. Aunque, los lenguajes que e emos se ´an NP. Los lenguajes que e emos en el siguien e cap´ı ulo son los isomo ismos de g a os, los g a os 3-colo eables y los esiduos cuad ´a icos. Es os lenguajes son ´alidos pa a odas las de iniciones is as en es e cap´ı ulo. 2.6. M´as all´a de los lenguajes. Las p uebas de conocimien o ce o demues an el conocimien o de una in o maci´on sin e ela la. Hemos is o que p ueban la pe enencia a un lenguaje en las p ime as menciones del conocimien o ce o [9–11]. Es a idea e oluciona con Fia y Shami en [8] pa a da soluci´on a la iden i icaci´on sin uso de con ase˜nas. Si un e ce o in e cep a la con ase˜na de un indi iduo, ´es e pod ´ıa hace se pasa po ´el. El concep o b´asico de las p uebas de conocimien o ce o pa a la iden i icaci´on es el siguien e: el p obado , en conocimien o de un sec e o que lo iden i ica, demues a su iden idad al e i icado sin ansmi i le ese sec e o. Los concep os que hemos a ado en es e cap´ı ulo como la obus ez, la comple i ud y la indis inguibilidad se basan en la pe enencia al lenguaje y se adap a ´an a la iden i icaci´on [8]. La comple i ud y la obus ez se basaban en la pe enencia o no de un elemen o a un lenguaje, en la iden i icaci´on se hace e e encia al conocimien o o no de un sec e o. 16 CAP´ ITULO 2. PRUEBAS DE CONOCIMIENTO CERO De inici´on 2.27. Sea (A, B) un p o ocolo in e ac i o, (A, B) es comple o si la p obabi- lidad de que Bacep e la iden idad de Acuando Aposee el sec e o, es muy ce cana a 1. De inici´on 2.28. Sea (A, B) un p o ocolo in e ac i o, (A, B) es obus o si la p obabilidad de que Bacep e la iden idad de Acuando Ano posee el sec e o, es muy ce cana a 0. El concep o de indis inguibilidad se man iene, es deci , se debe comp oba que la is a del e i icado du an e el p o ocolo es suscep ible de se gene ada po un simulado ajeno a la p ueba. El ma iz dis in o es que las amilias de a iables alea o ias no se o man po los di e en es elemen os del lenguaje, si no po o as a iables que e emos en el Cap´ı ulo 4. Como emos, la idea de no ansmi i conocimien o se man iene y es os au o es la u ilizan pa a c ea algo i mos de iden i icaci´on y de i ma que e emos en los Cap´ı ulos 4 y 5. Cap´ı ulo 3 P uebas de conocimien o ce o sob e lenguajes Despu´es de habe de inido las p uebas de conocimien o ce o sob e lenguajes en el cap´ı ulo an e io , en es e cap´ı ulo amos a explica es ipos de p uebas de conocimien o ce o sob e lenguajes. Reco demos que en las p uebas de conocimien o ce o sob e lenguajes, el p obado demues a al e i icado que un elemen o pe enece a un lenguaje sin da m´as in o maci´on que la pe enencia. En el cap´ı ulo an e io hab´ıamos de inido los lenguajes como subconjun os de {0,1}∗, aho a, como adelan ´abamos en la Secci´on 2.5, se ede inen los lenguajes como conjun os pa a los que demos a que un elemen o pe enece a ellos es compu acionalmen e di ´ıcil o, dicho de o a o ma, lenguajes NP. Es os lenguajes man ienen odas las de iniciones is as has a aho a [11]. Los lenguajes sob e los que amos a cons ui p uebas de conocimien o ce o son: los isomo ismos de g a os, los g a os 3-colo eables y los esiduos cuad ´a icos. Como expli- camos en la Secci´on 2.5, los lenguajes que amos a u iliza son conjun os pa a los que demos a la pe enencia es un p oblema NP. A con inuaci´on, explicamos los es p o ocolos pa a p uebas de conocimien o ce o sob e lenguajes: p ime o, p esen amos la base ma em´a ica, luego, el p oblema de pe enencia, y inalmen e, el p o ocolo. Tambi´en ealiza emos un desa ollo m´as exhaus i o de la p ueba de conocimien o ce o sob e los g a os 3-colo eables u ilizando las de iniciones del cap´ı ulo an e io . No a 3.1. En los p ´oximos apa ados u iliza emos la no aci´on A→Bpa a indica el paso en el que A ealiza las compu aciones opo unas y en ´ıa el esul ado a B. Lo an´alogo pa a B→A. 3.1. Isomo ismo de g a os En p ime luga , expond emos algunas nociones sob e g a os que amos a u iliza en es a y en la siguien e secci´on. Sea Cun conjun o, deno amos po σ(C) al conjun o de odas las pe mu aciones del conjun o C. Si omamos c∈RCes amos escogiendo un elemen o de Calea o iamen e y con una dis ibuci´on de p obabilidad uni o me. 17 18 CAP´ ITULO 3. PRUEBAS DE CONOCIMIENTO CERO SOBRE LENGUAJES Deno amos G(V, E) al g a o no di igido con Vel conjun o de sus ´e ices y Eel conjun o de sus a is as. Llamamos nal ama˜no de Vymal ama˜no de E. De inici´on 3.1. Sean G(V, E) y H(V, F) dos g a os no di igidos, son isomo os si y solo si exis e una pe mu aci´on π∈σ(V) de modo que (u, )∈E⇔(π(u), π( )) ∈F. Dicho de o o modo, si dos ´e ices son adyacen es en un g a o, las im´agenes po πlo se ´an en el o o g a o. El conjun o de los pa es de g a os isomo os es un lenguaje que deno amos po GI, donde GI ={(G, H) : ∃πde modo que H=πG}. Adem´as, decimos que un g a o H(V, F) es una copia isomo a alea o ia del g a o G(V, E) si Hse ob iene de Gmedian e π∈Rσ(V) y omando F={(π(u), π( )) : (u, )∈E}. El p oblema del isomo ismo de g a os es el siguien e: dados dos g a os hay que de e - mina si son isomo os (que pe enecen a GI). A con inuaci´on, p esen amos la p ueba de conocimien o ce o sob e el lenguaje GI P o ocolo 3.1. Es e p o ocolo puede consul a se en [9]. G0(V, E0) y G1(V, E1) son dos g a os no di igidos que an o el p obado , A, y el e i icado , B, conocen. φes un isomo ismo en e G0yG1, es deci , G1=φG0que conoce A. a) Fase p e ia.Adebe demos a a Bque hay un isomo ismo en e G0yG1sin e ela φ. b) In e cambio de mensajes. Los siguien es pasos se epi en n eces, con nel n´ume o de ´e ices de ambos g a os, y en odas las epe iciones, las elecciones alea o ias son nue as. 1.- A→B: El p obado oma π∈Rσ(V) y cons uye una copia alea o ia isomo a de G1a la que deno amos H(V, F). El p obado , A, en ´ıa al e i icado , B, el g a o H(V, F). 2.- B→A: El e i icado , B, oma e∈R{0,1}y se lo en ´ıa a A. 3.- A→B: El p obado comp ueba p ime o si e∈ {0,1}, si no ue a as´ı pa a ´ıa. Si e= 1, en onces el p obado , A, en ´ıa πaB; y si e= 0, A, en ´ıa πφ aB. 4.- Una ez ecibe Bla pe mu aci´on, comp ueba si es un isomo ismo en e Gey H. Si lo es, con inua con la siguien e i e aci´on; si no, echaza y pa a. c) Finalizaci´on del p o ocolo. Cuando se comple an las ni e aciones con ´exi o, el e i- icado , B, acep a y pa a. Obse aci´on 3.1. El p oblema del isomo ismo de g a os se demos ´o que e a un p o- blema que se encon aba en e PyNP en 2016, ue demos ado po Babai en [1]. Po lo an o, se ´ıa compu acionalmen e m´as ´acil ompe es e p o ocolo po que se puede encon- a un ismo ismo en e dos g a os. 3.2. GRAFOS 3-COLOREABLES 19 3.2. G a os 3-colo eables De inici´on 3.2. Sea G(V, E) un g a o no di igido, es un g a o 3-colo eable si exis e una aplicaci´on φ:V→ {1,2,3}de al mane a que a odo pa de ´e ices adyacen es se le asignan colo es dis in os, es deci , ∀(u, )∈E, φ(u)6=φ( ). El conjun o de g a os no di igidos que son 3-colo eables es un lenguaje que deno amos G3C. El p oblema de los g a os 3-colo eables es el siguien e: dado un g a o hay que de e - mina si es 3-colo eable. El p oblema es NP po lo que el lenguaje G3Ces NP [9]. Obse aci´on 3.2. El in e ´es del lenguaje 3-colo eable es debido a que demos a que un g a o es 3-colo eable es un p oblema NP, algo que no ocu e con los g a os 4-colo eables. Pa a los g a os 4-colo eables asociados a un mapa exis e un eo ema que demues a que odo g a o puede se colo eado po cua o colo es sin que los ´e ices adyacen es engan el mismo colo . Aho a, p esen amos una p ueba de conocimien o ce o sob e el lenguaje G3C. P o ocolo 3.2. Es e p o ocolo puede consul a se en [9]. a) Fase p e ia. G(V, E) es un g a o no di igido que AyBconocen, con Vde ama˜no nyEde ama˜no m.φes una colo aci´on co ec a que solo conoce A.Adebe demos a a B que el g a o Ges 3-colo eable (que pe enece a G3C) sin e ela φ. b) In e cambio de mensajes. Los siguien es pasos se epi en m2 eces y cada una de las eces las elecciones alea o ias son nue as: 1.- A→B:A oma π∈Rσ({1,2,3}), calcula π(φ( )) ∀ ∈V. Cada uno de los π(φ( )) son enc ip ados1indi idualmen e po Ay en iados a B. 2.- B→A:Bescoge una a is a e= (u, )∈Ey se la en ´ıa a A. 3.- A→B:Acomp ueba que e∈Ey en ´ıa a Blas desenc ip aciones de uy . 4.- B ecibe la desenc ip aci´on, desenc ip a uy y comp ueba que con ienen di e en es elemen os de {1,2,3}. Si los elemen os de {1,2,3}son dis in os, con in´ua con la siguien e i e aci´on. Si no puede desenc ip a o los n´ume os que con ienen son iguales, en onces B echaza y pa a. De es a o ma, el e i icado no conoce ´a la colo aci´on eal del g a o po que la colo aci´on es ´a ocul a median e π c) Final del p o ocolo. Si se comple an las m2i e aciones con ´exi o, en onces Bacep a y pa a. 1Se u iliza cualquie algo i mo de enc ip aci´on que pe mi a enc ip a los y desenc ip a los de mane a indi idual 20 CAP´ ITULO 3. PRUEBAS DE CONOCIMIENTO CERO SOBRE LENGUAJES P oposici´on 3.1. El P o ocolo 3.2 es una p ueba de conocimien o ce o compu acional pa a G3C. Demos aci´on. Tenemos en cuen a que es un p o ocolo in e ac i o po que las en idades que pa icipan en el p o ocolo pueden o maliza se como m´aquinas de Tu ing in e ac i as p obabil´ıs icas, siendo Buna m´aquina de Tu ing de iempo espe ado polinomial y A sin l´ımi e compu acional. Es as en idades in e ac ua ´an como lo hacen las m´aquinas de Tu ing en los p o ocolos in e ac i os. Como una p ueba de conocimien o ce o compu acional es un sis ema de p uebas de conocimien o ce o compu acional amos a p oba que es comple o, obus o y de conoci- mien o ce o compu acional. U ilizando la De inici´on 2.23: Comple i ud. Bas´andonos en la De inici´on 2.13, si el g a o de en ada G∈G3Cen- onces, cualquie pa de ´e ices adyacen es que se omen an a ene colo dis in o, po lo que la p obabilidad de que el e i icado acep e dicho g a o es 1. El P o ocolo 3.2 es comple o. Robus ez. U ilizando la De inici´on 2.14, supongamos aho a que el g a o de en ada G /∈G3Clo que quie e deci que al menos hab ´a un pa de ´e ices adyacen es que no end ´an la colo aci´on adecuada. La p obabilidad de que cualquie e i icado echace es e g a o es al menos 1/m que es la p obabilidad de escoge la a is a que une los ´e ices del mismo colo . Po lo an o, la p obabilidad de que el e i icado acep e el g a o es como mucho (m−1)/m en cada i e aci´on, que es la p obabilidad de escoge un pa de ´e ices bien colo eados. En o al en odo el p o ocolo la p obabilidad de que acep e un G /∈G3Ces como mucho ((m−1)/m)m2, una p obabilidad ´ın ima y po consiguien e, el P o ocolo 3.2 es obus o. Conocimien o ce o compu acional. Pa a es a demos aci´on u iliza emos las De ini- ciones 2.19 y 2.21. La in o maci´on que ob iene el e i icado en cada paso es π(φ(u)) yπ(φ( )) donde (u, ) son ´e ices adyacen es escogidos alea o iamen e po el e- i icado , y donde π ambi´en es escogido alea o iamen e po el p obado . Es a in- o maci´on es lo que conocemos como la is a del e i icado du an e el p o ocolo y es una a iable alea o ia inducida po la alea o iedad de la elecci´on de π. Como cada G∈G3Cda luga a una a iable alea o ia, cons uimos la amilia de a iables alea o ias que deno amos po {hA, Bi(G)}G∈G3C. Bas´andonos en la De inici´on 2.21 conside emos como simulado una m´aquina de Tu ing Mp obabil´ıs ica que con en ada un g a o G∈G3Cnos de uel e dos en e os (i, j)∈R{1,2,3}con i6=j. El conjun o de las salidas de es a m´aquina de Tu ing es una amilia de a iables alea o ias que deno a emos po {M(G)}G∈G3C. P obemos que es as dos amilias de a iables alea o ias son compu acionalmen e indis inguibles (De inici´on 2.19). P ime o, necesi amos cons ui al “juez”, que en el caso de la indis inguibilidad compu acional es un ci cui o booleano: Sea C={Cy}nues o juez con y∈ hA, Bi(G) ´o y∈M(G), y sean las mues as y odas del mismo ama˜no po de inici´on. Tenemos que P({hA, Bi(G)}, C, G) es la p obabilidad de que el ci cui o de uel a un 1 al in oduci un y∈ hA, Bi(G) y P({M(G)}, C, G) la p obabilidad de que de uel a un 0 al in oduci un y∈M(G). 3.3. RESIDUOS CUADR ´ ATICOS 21 Como emos, los y∈ hA, Biy los y∈M(G) no gua dan una elaci´on con su p o- cedencia po que los y∈ {(1,2),(2,1),(1,3),(3,1),(2,3),(3,2)}sea cual sea su p o- cedencia. Po lo que si calculamos |P({hA, Bi(G)}, C, G)−P({M(G)}, C, G)|(2.2) ob end emos un alo muy ce cano a 0 po que las p obabilidades de que acie e o alle son las mismas en cada caso. Po lo an o, podemos a i ma que es as dos amilias de a iables alea o ias son compu acionalmen e indis inguibles, lo que con- ie e al P o ocolo 3.2 en un sis ema de p uebas in e ac i as de conocimien o ce o compu acional. 3.3. Residuos cuad ´a icos Vamos a ija algunas nociones sob e esiduos cuad ´a icos omadas de [11] que u ili- za emos an o pa a de ini el lenguaje como pa a p esen a el p oblema de los esiduos. De inici´on 3.3. Sea p∈Ny sea Z∗ pel conjun o de los in e ibles m´odulo p. En onces, un q∈Z∗ pes un esiduo cuad ´a ico m´odpsi exis e un w∈Z∗ pde modo que w2=qm´od p. Puede de e mina se en iempo polinomial que q∈Z∗ p. Adem´as q∈Z∗ pes un esiduo cuad ´a ico m´od psi y solo si qes un esiduo cuad ´a ico m´odulo odos los ac o es p imos de p. De inici´on 3.4. Deno amos po Qp(q) al ope ado : Qp(q) = 0 si qes un esiduo cuad ´a ico m´odp 1 en o o caso (3.1) Dados p∈N,q∈Z∗ py la ac o izaci´on de p, el ope ado Qp(q) puede calcula se en iempo polinomial. De inici´on 3.5. Sea q∈Z∗ py sea Qk i=1 pαi ila descomposici´on en p imos de p, en onces el s´ımbolo de Jacobi de qm´od pse de ine como: q p= k Y i=1 q piαi (3.2) donde q pi= +1 si qes un esiduo cuad ´a ico m´odpiyq pi=−1 en o o caso. Reco demos que es os q pipa a i= 1, ..., k son los s´ımbolos de Legend e. Es impo an e des aca , que si un elemen o iene s´ımbolo de Jacobi +1 no implica que sea un esiduo cuad ´a ico pe o si al e ´es. Bas´andonos en es a de inici´on, el s´ımbolo de Jacobi puede calcula se en iempo poli- nomial. El lenguaje que u iliza emos es QR (del ingl´es quad a ic esiudosi y) y lo de inimos de la siguien e o ma: QR ={(p, q) : p∈N, q ∈Z∗ p, Qp(q) = 0}(3.3) 22 CAP´ ITULO 3. PRUEBAS DE CONOCIMIENTO CERO SOBRE LENGUAJES con pyqexp esados en bina io. El p oblema de la esidualidad cuad ´a ica es calcula Qp(q) dados p∈N,q∈Z∗ py p q= +1, es deci , demos a que (p, q)∈QR. El siguien e p o ocolo basa ´a su uncionamien o en las siguien es ca ac e ´ıs icas de los esiduos cuad ´a icos: sea p∈N,q, u ∈Z∗ p, en onces: Si Qp(q) = Qp(u)⇒Qp(qu) = 0. Si Qp(q)6=Qp(u)⇒Qp(qu) = 1. Todas las nociones sob e esiduos cuad ´a icos is as en es a secci´on se ´an necesa ias pa a p ´oximas secciones. P o ocolo 3.3. Es e p o ocolo puede consul a se en [11]. Aquie e demos a a Bque (p, q)∈QR sin mos a le la e idencia po la que qes un esiduo cuad ´a ico m´odulo p. a) Fase p e ia. AyBconocen (p, q) y Aconoce la e idencia de que qes un esiduo cuad ´a ico m´odulo p. b) In e cambio de mensajes. Los siguien es pasos se epi en m eces y las elecciones alea o ias se hacen de nue o en cada paso. mes el n´ume o de d´ıgi os de pen bina io. 1.- A→B:Aescoge alea o iamen e un esiduo cuad ´a ico m´odpque deno amos uy se lo en ´ıa a B. 2.- B→A:Bescoge e∈R{0,1}y se lo en ´ıa a A. 3.- A→B:Aescoge alea o iamen e + ´o −de =±√uqem´od py se lo en ´ıa a B. B ecibe , calcula 2y comp ueba que 2=uqe. Si no ue a as´ı echaza ´ıa y pa a ´ıa. c) Final del p o ocolo. Si se ealizan las m epe iciones con ´exi o, en onces Bacep a y pa a. Cap´ı ulo 4 P uebas de conocimien o ce o pa a la iden i icaci´on En la Secci´on 2.6, al inal de Cap´ı ulo 2, dimos un adelan o de lo que se ´ıan las p uebas de conocimien o ce o adap adas a la iden i icaci´on. En una p ueba de conocimien o ce o pa a la iden i icaci´on, el p obado , en posesi´on de un sec e o que lo iden i ica, demues a al e i icado su iden idad, sin des ela le el sec e o. En es e cap´ı ulo p o undiza emos m´as en es a a ian e de p uebas de conocimien o ce o. Realiza emos un desa ollo m´as comple o de dos de los p o ocolos. 4.1. De la memb es´ıa a la iden i icaci´on Fia y Shami [8] oman la idea de la iden i icaci´on a a ´es de p uebas de conoci- mien o ce o y la combinan con las apo aciones de Goldwasse [10] (Cap´ı ulos 2 y 3) y el plan eamien o de Shami [17]. A con inuaci´on, expond emos algunas ideas de [17] que nos se ´an ´u iles pa a desc ibi las p uebas de conocimien o ce o pa a la iden i icaci´on. Shami p opuso un p o ocolo c ip og ´a ico pa a que un g upo de usua ios se comunica- sen en e ellos de o ma segu a sin la necesidad de in e cambia cla es p´ublicas o p i adas y sin ecu i a e ce os. Apa ec´ıan en es e p o ocolo cadenas de alo es que con en´ıan la in o maci´on necesa ia pa a que el usua io pudie a enc ip a y i ma los mensajes que en iaba, y, desenc ip a y e i ica los mensajes que ecib´ıa. Es as cadenas se denomina- ban a je as elec ´onicas y cada usua io pose´ıa una. Adem´as, no necesi aban ac ualiza se cuando ya hab´ıan sido emi idas y en aba un nue o usua io. En el p o ocolo de [17] apa ec´ıa una nue a en idad: el cen o de con ianza, que es el que emi ´ıa las a je as elec ´onicas a los usua ios cuando se unen po p ime a ez al p o ocolo. Los cen os de con ianza desapa ecen cuando se han emi ido odas las a je as co espondien es haciendo que la ac i idad no dependa del cen o. La u ilidad del cen o de con ianza en el p o ocolo de Shami [17] es la siguien e: el usua io se iden i ica median e m´e odos no c ip og ´a icos que dependen del con ex o al cen o de con ianza (en [17] se escoge su nomb e y co eo elec ´onico como su cla e p´ublica), de mane a que pueda iden i ica se, no e ac a se y que pa a o o usua io esa iden i icaci´on sea ´alida. Cuando el usua io ya es ´a iden i icado, el cen o de con ianza 23 30 CAP´ ITULO 4. PRUEBAS PARA LA IDENTIFICACI ´ ON Demos aci´on. P oba emos que es un p o ocolo comple o, obus o y de conocimien o ce o compu acional: Comple i ud. Supongamos que Aconoce los s1, ..., sky en el paso 3 ha en iado y= Qk i=1 sei im´od naB. En el paso 4, Bsiemp e ob end ´a que z=±xpo como es ´an cons uidos los 1, ..., k. Po ello, el p o ocolo es obus o. Robus ez. Supongamos que un impos o A∗cualquie a no conoce los s1, ..., sky quie e hace se pasa po A, pa a ello, end ´ıa que escoge los e1, ..., ekque ue a a elegi Ben el paso 2 y adem´as, oma yalea o io y escoge x=y2Qk i=1 m´odn. La p obabilidad de que acie e la cadena de bi s eies de 2−k, y en o al en el p o ocolo 2−k . Como hemos is o en la Obse aci´on 4.2, la p obabilidad de que Bacep e la iden idad de un impos o es 2−30, un alo ´ın imo y po lo an o, el p o ocolo es obus o. Conocimien o ce o compu acional. La demos aci´on de que es un p o ocolo de co- nocimien o ce o compu acional es an´aloga a la de la P oposicion 4.2. A con inuaci´on compa a emos los p o ocolos is os en es a secci´on: El cen o de con ianza es com´un a los es p o ocolos pe o en cada uno ealiza unciones dis in as: en el P o ocolo 4.1 es el cen o de con ianza el que o o ga los sec e os al p obado , mien as que en los o os dos, es el p opio p obado el que escoge los alo es. En odos los p o ocolos hace labo de supe isi´on y desapa ece despu´es de que son adjudicadas las cla es p´ublicas y p i adas. El P o ocolo 4.1 es el ´unico que incluye el uso de unciones DES y es ambi´en el m´as a caico. Es e ipo de unciones hoy en d´ıa han sido sus i uidas po o as po azones de segu idad. 4.3. Ejemplos Los siguien es ejemplos se ealizan con alo es m´as peque˜nos que los que se oma ´ıan en una implemen aci´on eal. Su ´unico in es cla i ica los p o ocolos de iden i icaci´on expues os en es a secci´on. Los c´alculos y la b´usqueda de n´ume os p imos se ha hecho a a ´es de la he amien a Ma hema ica. Se incluyen ejemplos de los P o ocolos 4.1, 4.2 y 4.3 Ejemplo 4.1. U ilizando las mismas no aciones que en el P o ocolo 4.1: a) P epa aci´on. Se ijan los en e os k= 2 y = 1. El cen o de con ianza escoge dos n´ume os p imos p= 37 y q= 59, y publica n=pq = 2183. Publica una unci´on DES (hemos u ilizado una que p opo ciona Ma hema ica). Cuando Ase iden i ica al cen o de con ianza, ´es e gene a la cadena I= 29. Despu´es, el cen o de con ianza ealiza lo siguien e pa a pode emi i la a je a: 4.3. EJEMPLOS 31 •Calcula un n´ume o inde e minado de j= (I, j) y escoge los que son un esiduo cuad ´a ico m´odulo n. Po simpli ica no aci´on: j= 1,2, luego 1= 100 y 2= 108 (a a ´es de Ma hema ica se ha comp obado que son esiduos cuad ´a icos). •Calcula s1= −1/2 1m´od nys2= −1/2 2m´od ny ob enemos que s1= 655 m´od n ys2= 548 m´od n. •El cen o de con ianza emi e la a je a elec ´onica (I;s1, s2) pa a A. In e cambio de mensajes 1.- A→B:Aen ´ıa I= 29 y j= 1,2 a B. 2.- B→A:Bcalcula los 1, 2. 3.- A→B:Aescoge = 327, calcula x= 2m´od n= 2145 m´od 2183 y en ´ıa x= 2145 m´od 2183 a B. 4.- B→A:Bescoge como ec o alea o io (0,1) y se lo en ´ıa a A. 5.- A→B:Acalcula y= s2= 327 ·548 = 190 m´od 2183 y se lo en ´ıa a B. 6.- Bcalcula y2= 1172 m´od 2183 e y2 2= 1172 ·108 = 2145 m´od 2183 y com- p ueba que y2 2=x. c) Finalizaci´on del p o ocolo Como los pasos solo se ealizan una ez po que = 1 en onces Bacep a la iden idad de A. Ejemplo 4.2. U ilizando las mismas no aciones que en el P o ocolo 4.2 P epa aci´on. El cen o de con ianza escoge los n´ume os p imos p= 379 y q= 787. Calcula n=pq y publica el esul ado n= 298273. El p obado , A, oma un s∈Z∗ 298273. Escoge s= 127085 y calcula =s2m´od n. Calcula s2= 16150597225 = 9094 m´od 298273 y publica = 9094 m´od 298273 como su cla e p´ublica. In e cambio de mensajes. Los siguien es mensajes se ealiza ´ıan eces, como es una ejemplo sencillo, oma emos = 2. = 1: •A→B:A oma un alea o io con 1 ≤ < 298273 y escoge = 25868. Calcula x= 2m´od n⇒ 2= 669153424 = 127085 m´od 298273 y en ´ıa x= 127085 m´od 298273 a B. •B→A:Bescoge alea o iamen e e= 0 ´o e= 1. En es e caso escoge e= 1 y se lo en ´ıa a A. •A→B:Acalcula y= sem´od n= s m´od n⇒y= s = 25868 ·127085 = 3287434780 = 168047 m´od 298273. Aen ´ıa y= 168047 m´od 298273 a B. 32 CAP´ ITULO 4. PRUEBAS PARA LA IDENTIFICACI ´ ON •B ecibe y, calcula y2m´od npo un lado y x em´od n, po o o. y2= 28239794209 = 201388 m´od 298273 y x = 127085·9094 = 1155710990 = 201388 m´od 298273. Como emos y2=x po lo an o Bacep a y pasamos a la siguien e i e aci´on. = 2: •A→B:A oma un alea o io con 1 ≤ < 298273 y escoge = 29. Calcula x= 2m´od n⇒ 2= 841 m´od 298273 y en ´ıa x= 841 m´od 298273 a B. •B→A:Bescoge alea o iamen e e= 0 ´o e= 1. En es e caso escoge e= 0 y se lo en ´ıa a A. •A→B:Acalcula y= sem´od n⇒y= po que e= 0. Luego, como = 29, en onces y= 29 m´od 298273. Aen ´ıa y= 29 m´od 298273 a B. •B ecibe y, calcula y2m´od npo un lado y x em´od n=xm´od n, po o o. y2= 841 m´od 298273 y x= 841 m´od 298273. Como emos y2=x po lo an o Bacep a. Finalizaci´on del p o ocolo Como se han comple ado las dos i e aciones con ´exi o, en onces Bacep a ´a la iden- idad de A. Ejemplo 4.3. U ilizando las mismas no aciones que en el P o ocolo 4.3. En es e caso los en e os segu os que se oman son k= 3 y = 1 pa a simpli ica el ejemplo, pe o como imos en el P o ocolo 4.3 lo mejo es k = 20. P epa aci´on. El cen o de con ianza escoge p imos alea o ios cong uen es a 3 m´od 4, p= 683, q= 811. Calcula n=pq y publica el en e o Blum n= 553913. El p obado , A, oma es en e os alea o iamen e si∈Z∗ 553913 con i= 1,2,3. Aescoge s1= 157, s2= 43215, s3= 4646. Despu´es, calcula los iy elige alea o iamen e el signo: 1= 441845, 2= 338402, 3= 124423. Los ipa a i= 1,2,3 se ´an la cla e p´ublica de A. In e cambio de mensajes. •A→B:A oma un alea o io con 1 ≤ < n. Escoge = 4527, un s´ımbolo + ´o −y calcula x=± 2m´od n⇒x= 20493729 = +552861 m´od 553913. En ´ıa aBel alo x= +552861 m´od 553913 •B→A:B oma un ec o de bi s alea o ios (e1, e2, e3). Escoge (0,1,0) y se lo en ´ıa a A. •A→B:Acalcula y= (se1 1se2 2se3 3)⇒y= s2⇒y= 4527 ·43215 = 195634305 = 103016 m´od 553913 y en ´ıa a B y = 103016 m´od 553913. •El e i icado ,B, calcula z=y2·( e1 1 e2 2 e3 3), como el ec o bina io es (0,1,0), en onces z=y2· 2m´od n.y2= 10612296256 = 431002 m´od 553913 y z= y2· 2= 431002 ·338402 = 145851938804 = 552861 m´od 553913. Y emos que z= +xpo que z= 552861 m´od 553913 y x= 552861 m´od 553913. Finalizaci´on del p o ocolo. Como se cumple que z=x, en onces Bacep a la iden i- dad de A. Cap´ı ulo 5 P uebas de conocimien o ce o no in e ac i as y i mas digi ales En es e cap´ı ulo p esen amos las p uebas no in e ac i as de conocimien o ce o y las i mas digi ales. Has a aho a, hab´ıamos is o las p uebas de conocimien o ce o in e ac i as en las que el e i icado p opon´ıa una especie de desa ´ıo al p obado y ´es e espond´ıa. En es e caso, el p obado en ´ıa un solo mensaje al e i icado que le pe mi e demos a su conocimien o sob e algo. Las i mas digi ales pueden pensa se como p uebas de conocimien o ce o no in e ac i- as en las que simplemen e se en ega un mensaje que demues a la au o ´ıa del p obado o pueden se una a iaci´on de una p ueba in e ac i a de conocimien o ce o. En la Secci´on 5.2.3 obse a emos es ipos de i mas digi ales: una de ellas es ´a basada en la p ueba de conocimien o ce o no in e ac i a de la Secci´on 5.1 y las o as dos, en p o ocolos in e ac i os de iden i icaci´on. 5.1. P uebas de conocimien o ce o no in e ac i as En es a secci´on abo da emos las p incipales nociones de las p uebas no in e ac i as de conocimien o ce o y un p o ocolo de es e ipo. Vol emos al p oblema de la pe enencia de un elemen o a un lenguaje is o en los Cap´ı ulos 2 y 3, solo que aho a el plan eamien o y la soluci´on que se da es dis in a. En las p uebas de conocimien o no in e ac i as no hay in e cambio de mensajes en e el e i icado y el p obado . El p obado en ´ıa solo una cadena de in o maci´on al e i i- cado que le pe mi e comp oba que dice la e dad pe o sigue exis iendo un componen e p obabil´ıs ico que explica emos m´as adelan e. Si pensamos en el ejemplo de la Secci´on 1.1, Paqui a en ia ´ıa a los pe iodis as un mensaje que les pe mi i ´ıa sabe que ella conoce la palab a sec e a que ab e el pasadizo en e los dos pueblos, no hab ´ıa in e cambio de mensajes de ning´un ipo. Blum, Feldman y Micali en [3] in oducen las p uebas de conocimien o ce o no in e - ac i as y el p oblema que a an es el mismo que en las p uebas in e ac i as: el p obado debe demos a al e i icado la pe enencia de un elemen o a un lenguaje. La di e encia con las p uebas in e ac i as es que el p obado en ´ıa al e i icado solo una cadena con in- o maci´on, la cual le pe mi e e i ica que el p obado sabe po qu´e el elemen o pe enece 33 34 CAP´ ITULO 5. PRUEBAS NO INTERACTIVAS Y FIRMAS a ese lenguaje. Todas las de iniciones y no aciones de m´aquinas de Tu ing de la Secci´on 2.1 se ´an u ilizadas pa a o maliza la de inici´on de p ueba de conocimien o ce o no in e ac i a. Los concep os de comple i ud y obus ez (Secci´on 2.2) su en modi icaciones, pe o la idea p incipal se man iene: si el elemen o es ´a en el lenguaje, el p obado con ence al e i icado con una p obabilidad ce cana a 1 (comple i ud); y si el elemen o no es ´a en el lenguaje, el p obado con ence al e i icado con una p obabilidad muy ce cana a 0 ( obus ez). En cuan o al conocimien o ce o, el plan eamien o es el mismo: la is a del e i- icado du an e el p o ocolo puede se simulada po una m´aquina de Tu ing p obabil´ıs ica ajena a la p ueba. La p incipal di e encia con las p uebas in e ac i as es que el p obado iene acceso a la cin a alea o ia del e i icado . La ga an ´ıa de que los p o ocolos sean de conocimien o ce o es ´a en que el con enido de es a cin a sea alea o io, es deci , que no se manipule. Po el Cap´ı ulo 2, sabemos que una p ueba de conocimien o ce o es un sis ema de p uebas de conocimien o ce o, po lo an o, amos a de ini un sis ema de p uebas no in e ac i as de conocimien o ce o. Pa a ello, necesi amos ede ini la comple i ud y la obus ez. Pa a o maliza la de inici´on de p ueba no in e ac i a, ecu i emos como en el Cap´ı ulo 2 a las m´aquinas de Tu ing y ede ini emos al p obado y al e i icado como m´aquinas de Tu ing: De inici´on 5.1. El p obado , A, en una p ueba de conocimien o ce o no in e ac i a es una m´aquina de Tu ing p obabil´ıs ica con cinco cin as: Una cin a de en ada de solo lec u a. Una cin a de abajo de lec u a y esc i u a. Una cin a alea o ia de solo lec u a. Una cin a alea o ia adicional de solo lec u a. Una cin a comunicaci´on de solo esc i u a. De inici´on 5.2. El e i icado , Ben una p ueba de conocimien o ce o no in e ac i a es una m´aquina de Tu ing p obabil´ıs ica con cinco cin as: Una cin a de en ada de solo lec u a. Una cin a de abajo de lec u a y esc i u a. Una cin a alea o ia de lec u a. Una cin a de comunicaci´on de solo lec u a. Una cin a de salida de solo esc i u a. De inici´on 5.3. Las dos m´aquinas de Tu ing de las De iniciones 5.1 y 5.2 o man un pa de m´aquinas no in e ac i as si cumplen lo siguien e: 5.1. PRUEBAS DE CONOCIMIENTO CERO NO INTERACTIVAS 35 La cin a de en ada es com´un a ambas. La cin a de comunicaci´on de ambas es la misma. El p obado solo esc ibe y el e i icado solo lee. La cin a alea o ia del e i icado es ambi´en isible pa a el p obado . Al pa de m´aquinas de Tu ing que cumple es as ca ac e ´ıs icas lo deno amos po (A, B) que es la misma no aci´on que pa a los sis emas de p uebas in e ac i as, po lo que siemp e se˜nala emos si da luga a dudas, si se a a de una p ueba in e ac i a o no in e ac i a. Obse aci´on 5.1. Si compa amos con las p uebas in e ac i as que hab´ıamos is o has a el Cap´ı ulo 3, nos encon amos con que la m´aquina de Tu ing que ep esen a al e i icado es dis in a a la del p obado : en el e i icado la cin a de comunicaci´on es de solo lec u a y en el p obado , de solo esc i u a; y la cin a alea o ia del e i icado , es ambi´en isible pa a el p obado . Reco demos que si el e i icado acep a que un elemen o es ´a en el lenguaje de uel e un 1, si no un 0. De inici´on 5.4. Sea (A, B) un pa de m´aquinas de Tu ing no in e ac i as y Lun lenguaje, deno amos po [A(x), B(x)] a la dis ibuci´on de salida de Bcuando iene como alo de en ada el elemen o x∈L. Es a dis ibuci´on es ´a inducida po las cin as alea o ias de las dos m´aquinas. De inici´on 5.5. Un pa de m´aquinas de Tu ing como en la De inici´on 5.3 es un sis ema de p uebas no in e ac i as si el p obado no iene l´ımi e compu acional, el e i icado iene iempo espe ado polinomial en unci´on del alo de en ada y se e i ican las siguien es p opiedades: Comple i ud. Sea un x∈Lsu icien emen e g ande se cumple que pa a cada c > 0: P([A(x), B(x)] = 1) >1−|x|−c(5.1) Robus ez. Sea un x /∈Lsu icien emen e g ande se cumple que pa a cada c > 0: P([A(x), B(x)] = 0) >1−|x|−c(5.2) Una ez is a la de inici´on de sis ema de p uebas no in e ac i as amos a de ini un sis ema de p uebas no in e ac i as de conocimien o ce o, pa a ello necesi amos las de ini- ciones y no aciones sob e conocimien o ce o de la Secci´on 2.3 que no su en modi icaciones. De inici´on 5.6. Sea (A, B) un sis ema de p uebas no in e ac i as, sea {hA, Bi(x)}x∈L la is a del e i icado Bdu an e la p ueba que iene como alo de en ada un x∈ L. Decimos que (A, B) es un sis ema de p uebas no in e ac i as de conocimien o ce o pe ec o ( esp. es ad´ıs ico, esp. compu acional) en Lsi la amilia de a iables alea o- ias {hA, Bi(x)}x∈Les pe ec amen e ( esp. es ad´ıs icamen e, esp. compu acionalmen e) ap oximable en L 36 CAP´ ITULO 5. PRUEBAS NO INTERACTIVAS Y FIRMAS A con inuaci´on mos amos el sis ema de p uebas no in e ac i as que se p opone en [3] que es una p ueba de conocimien o ce o no in e ac i a sob e el lenguaje G3Ck= {G(V, E)∈G3C:|V| ≤ k}. Pa a el desa ollo de es e p o ocolo se necesi a ´an las nociones de esiduos cuad ´a icos dadas en la Secci´on 3.3 y u iliza emos el conjun o Z+1 p= {q∈Zp:q p= +1}. P o ocolo 5.1. Puede consul a se en [3]. El p obado , A, quie e demos a al e i icado , B, que un g a o G(V, E) es ´a en G3Cksin apo a le una colo aci´on co ec a. Ambos conocen G(V, E). Solo Aconoce una colo aci´on co ec a de G(V, E). a) P epa aci´on. El p obado ealiza las siguien es acciones: 1.- Escoge alea o iamen e n1, n2, n3de modo que cada nisea p oduc o de dos p imos. 2.- Escoge alea o iamen e q1, q2, q3de modo que qi ni= 1 y qino sea un esiduo cuad ´a ico m´odulo nipa a i= 1,2,3. 3.- Se asignan los colo es co espondien es {1,2,3}al g a o G. 4.- A cada ´e ice del g a o con colo aci´on ipa a i= 1,2,3 se le asigna una e na ( 1, 2, 3)∈Z+1 n1×Z+1 n2×Z+1 n3dis in a, donde se e i ica que Qni( i) = 0 y Qnj( i) = 1 pa a j6=i. Al g a o con las nue as asignaciones lo denominamos G0. 5.- Se escogen un n´ume o inde inido de e nas alea o ias (z1, z2, z3)∈Z+1 n1×Z+1 n2× Z+1 n3y se asignan 8ka cada una de las a is as del g a o G. 6.- Pa a cada a is a (a, b) del g a o G0(donde a= (a1, a2, a3) y b= (b1, b2, b3)) y pa a cada una de las 8k e nas asignadas a cada a is a, (z1, z2, z3), pod emos compu a solo una de las siguien es i mas: I.- (√z1,√z2,√z3). En el caso en el que cada zisea un esiduo cuad ´a ico m´odulo nipa a i= 1,2,3. II.- (√q1z1,√z2,√z3). En el caso en el que z1no sea un esiduo cuad ´a ico m´odulo n1y los o os zisi sean un esiduo cuad ´a ico m´odulo nipa a i= 2,3. III.- (√z1,√q2z2,√z3). Lo an´alogo al ipo II pa a z2. IV.- (√z1,√z2,√q3z3).Lo an´alogo al ipo II pa a z3. V.- (√a1z1,√a2z2,√a3z3). En el caso en el que dos de los zino sean esiduos cuad ´a icos m´odulo ni. VI.- (√b1z1,√b2z2,√b3z3).En el caso en el que dos de los zino sean esiduos cuad ´a icos m´odulo ni VII.- (√a1b1z1,√a2b2z2,√a3b3z3).En el caso en el que dos de los zino sean esiduos cuad ´a icos m´odulo ni. VIII.- (√q1z1,√q2z2,√q3z3). En el caso en el que ning´un zisea esiduo cuad ´a ico m´odulo nipa a i= 1,2,3. 5.2. FIRMAS DIGITALES 37 b) Mensaje en iado. El p obado en ´ıa al e i icado los n1, n2, n3, q1, q2, q3, G0y las i mas de cada una de las e nas que hemos ob enido del paso 6. c) Final de la p ueba. El e i icado comp ueba que los n1, n2, n3no son po encia de ning´un en e o y que se cumple que ( 1, 2, 3)∈Z+1 n1×Z+1 n2×Z+1 n3. Tambi´en comp ueba que las i mas del paso 6 es ´an bien hechas. Si se cumplen es as condiciones en onces el e i icado acep a que el g a o Ges 3-colo eable Obse aci´on 5.2. Aho a eamos unas obse aciones sob e el P o ocolo 5.1: En el paso 4, se asignan e nas a cada ´e ice de modo que pa a un ´e ice de colo iel elemen o ide la e na sea un esiduo cuad ´a ico m´odulo ni. En el paso 5, los zise escogen u ilizando la cin a alea o ia que es com´un a p obado y e i icado . La elecci´on de 8k e nas pa a cada a is a es po que hay 8 ipos de i ma y as´ı se log a que el p o ocolo sea m´as segu o, y po consiguien e, obus o [3]. En cuan o a la e i icaci´on de la i ma, ecibe el g a o G0pe o no puede accede al colo de los ´e ices po que no puede comp oba si un elemen o es esiduo cuad ´a ico, ya que no conoce la descomposici´on de los ni. Pa a comp oba las 8k i mas de cada a is a, comp ueba que el cuad ado de cada elemen o de las e nas puede se di isible po alg´un qi( i mas II, III, IV, VIII) o alguno de los i( i mas V, VI, VII). Alguno pod ´ıa ene la i ma I, pe o es po ello que se en ´ıan an as i mas, pa a que la p obabilidad de que se ome siemp e la i ma I sea ´ın ima. 5.2. Fi mas digi ales En es a secci´on p esen amos es p o ocolos de i mas digi ales. Cada uno es ´a en o- cado de una mane a dis in a pe o odos es ´an basados en p uebas de conocimien o ce o in e ac i as y no in e ac i as. 5.2.1. Fi ma digi al de Fia y Shami Fia y Shami [8] p oponen es a i ma digi al que es ´a basada en el P o ocolo 4.1 de iden i icaci´on del cap´ı ulo an e io . Como dec´ıamos en la Secci´on 4.1, las a je as elec ´onicas que emi e el cen o de con ianza adem´as de pe mi i enc ip a y desenc ip a , ambi´en pe mi en i ma y e i ica mensajes. Pa a es e p o ocolo de i ma pa imos desde la ase p e ia del P o ocolo 4.1, donde el p obado A ecibe del cen o de con ianza la a je a elec ´onica. P o ocolo 5.2 (Fi ma Fia -Shami [8]).Supongamos que Aquie e i ma un mensaje m, mand´a selo a By que B e i ique que la i ma es de A. 38 CAP´ ITULO 5. PRUEBAS NO INTERACTIVAS Y FIRMAS a) P epa aci´on. Se ijan los en e os ky . El cen o de con ianza ealiza los siguien es pasos: •Escoge dos n´ume os p imos sec e os pyq, y publica su p oduc o n=pq. •Publica una unci´on DES, que asigna cadenas a bi a ias a alo es en Zn. El p obado se iden i ica al cen o de con ianza median e m´e odos no c ip og ´a i- cos. Despu´es, el cen o c ea una cadena Ique con iene in o maci´on sob e el usua- io(nomb e, di ecci´on, co eo) y sob e la a je a( echa de espi aci´on, limi aciones de alidez). Pa a c ea es a a je a ealizan los siguien es pasos: •Calcula un n´ume o inde e minado de j= (I, j) pa a j= 0,1, .... •De odos los jescoge kcualesquie a de modo que jes un esiduo cuad ´a ico m´odulo n. Pa a simpli ica la no aci´on oma emos j= 1, ..., k. •Calcula sjque es la a´ız cuad ada m´as peque˜na de −1 jm´od npa a j= 1, ..., k. •El cen o emi e como a je a pa a Ala cadena (I;s1, ..., sk). Los sjson el sec e o de A. El i man e, A, ealiza los siguien es pasos: 1.- Escoge en e os alea o iamen e ide modo que 1 ≤ i< n. Calcula xi= 2 im´od npa a i= 1, ..., . 2.- Calcula (m, x1, ..., x ) con la unci´on DES y oma los k p ime os bi s como alo es eij con 1 ≤i≤ , 1≤j≤k. 3.- Calcula yipa a i= 1, ..., : yi= iY eij =1 sjm´od n(5.1) b) En ´ıo de i ma.Aen ´ıa I, m, la ma iz eij,y odos los yiaB. c) Comp obaci´on de i ma.Bcalcula j= (I, j) pa a j= 1, ..., k, zi=y2 iQeij =1 jm´od npa a i= 1, .., y comp ueba que los p ime os k bi s de (m, z1, ..., z ) son los eij. Pa a ob ene es e p o ocolo de i ma se ha cambiado el papel que desempe˜na el e i- icado Ben el P o ocolo 4.1 po la unci´on DES . En es a i ma,pa a consegui un ni el de segu idad al o, se iene que aumen a como m´ınimo a k = 72 [8] y no k = 20 (P o ocolo 4.1 de iden i icaci´on). 5.2. FIRMAS DIGITALES 39 5.2.2. Fi ma digi al de Bella e y Goldwasse Bella e y Goldwasse [2] p esen an un p o ocolo de i ma digi al basado en las p uebas no in e ac i as de conocimien o ce o y las unciones pseudoalea o ias. De inici´on 5.7. Una unci´on pseudoalea o ia es una unci´on cuya imagen es compu acio- nalmen e ´acil de calcula y pa a la que no exis e un algo i mo de iempo polinomial p obabil´ıs ico que la di e encie de una unci´on alea o ia [15]. Las p uebas de conocimien o ce o no in e ac i as que de inen es ´an basadas en las is as en la Secci´on 5.1 de [3] pe o incluyendo algunos cambios: la p ueba se di ide en dos ases: la ase p epa a o ia y la de demos aci´on. En la p ime a ase se es ablece alguna in o maci´on com´un pa a p obado y e i icado (en elaci´on a las p uebas de la Secci´on 4.1 esa in o maci´on com´un se ´ıa la cadena de bi s alea o ios σ), e in o maci´on p i ada pa a cada uno . En la segunda ase, el p obado demues a al e i icado que conoce una in o maci´on sin e ela la, u ilizando la in o maci´on de la p ime a e apa. El p oceso de la p ime a e apa es independien e de lo que aya a p oba se en la segunda e apa. No a 5.1. Una colecci´on de unciones pseudoalea o ias la deno amos as´ı Fk={ s:|s|= k}. Pa a la i ma digi al de Bella e y Goldwasse basada en su p opues a de p ueba no in e ac i a de conocimien o ce o [2], la ase p e ia la ealiza ´ıa un cen o de con ianza y su uncionamien o se ´ıa el siguien e: el i man e (p obado ) ecibe del cen o de con ianza una a je a elec ´onica que le pe mi e i ma los mensajes. An es de pasa al p o ocolo ha emos algunas acla aciones: pa a es e p o ocolo es ne- cesa ia ambi´en una p ueba no in e ac i a de conocimien o ce o e i icable p´ublicamen e pa a alg´un lenguaje NP; y, como ya hemos acla ado an es, la ase p e ia del p o ocolo pa a i ma digi al es sus i uida po un cen o de con ianza al que se iden i ican los usua ios y ´es os eciben las cla es pa a i ma y e i ica . No a 5.2. Sea (A, B) una p ueba de conocimien o ce o no in e ac i a deno amos (A, B)γ a la p ueba de conocimien o ce o no in e ac i a que iene γcomo cin a alea o ia com´un. No a 5.3. Deno amos Ea un algo i mo cualquie a de enc ip aci´on de cla e p´ublica p obabil´ıs ica. P o ocolo 5.3 (Bella e Goldwasse [2]).El p obado A, quie e i ma un mensaje m yBdebe e i ica lo. a) P epa aci´on. Todos los pa icipan es en la i ma ob ienen del cen o de con ianza la cla e p´ublica (1k, E, α, γ), su cla e p i ada ( , s) y la unci´on pseudoalea o ia s: 1.- kes un en e o segu o. 2.- s∈R{0,1}es el ´ındice de la unci´on pseudoalea o ia. 3.- α=E( , s) es una enc ip aci´on de s. 4.- γes la in o maci´on com´un de la p ueba (A, B). El i man e calcula R= s(m) 46 CAP´ ITULO 6. UNA APLICACI ´ ON ACTUAL den o de un ango sin e ela al e i icado ese alo . Es e p o ocolo cuen a ambi´en con un cen o de con ianza que pa icipa en la p epa aci´on del p o ocolo. Sabe si un alo es ´a den o de un ango puede esul a ´u il en inanzas, p obando que un sala io es su icien e pa a alquila o pedi una hipo eca, y ambi´en, pa a la locali- zaci´on, p obando que algo o alguien es ´a den o de unos l´ımi es geog ´a icos sin mos a la localizaci´on exac a. P o ocolo 6.1. [13] Un p obado , A, quie e demos a a un e i icado , B, que un alo mse encuen a en e {a, a + 1, ..., b}. a) P epa aci´on. El cen o de con ianza ealiza lo siguien e: 1.- Escoge dos p imos pyqde modo que (p−1)/2 sea ambi´en un p imo. Publica n=pq. 2.- Toma gene ado es de Z∗ pyZ∗ q,gyh espec i amen e. Los alo es n, g, h son p´ublicos pa a el p obado y el e i icado . El p obado quie e demos a que m∈ {a, a + 1, ..., b}, es o se cumple si y solo si (m−a+ 1)(b−m+ 1) >0. El p obado , A, lle a a cabo los siguien es pasos: 3.- Escoge un en e o alea o io y calcula c=gmh m´od n. 4.- Escoge un en e o alea o io, w, dis in o de 0 y calcula: ◦c1=c ga−1m´od n. ◦c2=gb−1 cm´od n. ◦Toma un en e o alea o io 0y ob iene c0=cb−m+1 1h 0m´od n. ◦Toma un en e o alea o io 00 y ob iene c00 =c0w2h 00 m´od n. 5.- Escoge en e os no nega i os m1, m2, m3, 1, 2, 3de modo que cumplan los siguien e: ◦m1+m2+m3=w2(m−a+ 1)(b−m+ 1). ◦ 1+ 2+ 3=w2((b−m+ 1) + 0) + 00. 6.- Calcula: ◦c0 1=gm1h 1m´od n. ◦c0 2=gm2h 2m´od n. ◦c0 3=gm3h 3m´od n. 7.- Tomando en e os alea o ios posi i os sy , y se calcula: ◦x=sm1+m2+m3. ◦y=m1+ m2+m3. ◦u=s 1+ 2+ 3. ◦ = 1+ 2+ 3 6.2. PRUEBAS DE RANGO DE CONOCIMIENTO CERO 47 b) En ´ıo de mensaje. El p obado en ´ıa al e i icado la cadena: (c, c1, c2, c0, c00, c0 1, c0 2, c1c0 3, x, y, u, ) (6.1) c) Final del p o ocolo. El e i icado comp ueba que: 9.- Comp ueba: ◦c1=c ga−1m´od n. ◦c2=gb+1 cm´od n. ◦c00 =c0 1c0 2c0 3m´od n. 10.- Comp ueba: ◦c0 1c0 2c0 3=gxhum´od n. ◦c0 1c0 2c0 3=gyh m´od n. 11.- Ve i ica que x > 0 e y > 0. Si se supe an con ´exi o los pasos 9, 10 y 11, el alo mse encuen a en el ango {a, ..., b}. Obse aci´on 6.1. Veamos algunas obse aciones sob e el p o ocolo an e io : Una opci´on m´as sencilla pod ´ıa habe sido que el p obado en ia a xeydi ec a- men e al e i icado y que ´es e comp oba a que e an posi i os. El p oblema que ae es que el p obado puede escoge dos n´ume os alea o ios posi i os y que el e i i- cado acep a a, es po ello, que se ecu en a o os alo es que el e i icado pueda comp oba . La elecci´on de los en e os alea o ios 0, 00, w, 1, 2, 3, m1, m2, m3se hace pa a u ili- za los pa a ocul a los alo es de los que son po encias. La segu idad se basa en la di icul ad de esol e un loga i mo disc e o. El uso de es e ipo de p uebas no in e ac i as esul a m´as c´omodo y segu o que una p ueba in e ac i a. ´ Es o es debido a que muchas eces no es ac ible un in e cambio de mensajes y po lo an o, un solo mensaje y una comp obaci´on esul an m´as e icien es. ¿Cu´al es la u ilidad de las p uebas de ango de conocimien o ce o en el blockchain?Como hemos explicado, pa a egis a un nue o bloque, ´es e debe pasa una se ie de e i icaciones o p uebas. Las p uebas de conocimien o ce o pe mi en com- p oba que la in o maci´on que se a a a˜nadi a un nue o bloque es co ec a sin pone en pelig o dicha in o maci´on. Po una pa e, se ealiza ´ıan p uebas de conocimien o ce o de iden i icaci´on y, po o a, dependiendo del con ex o, una p ueba de conocimien o ce o de ango pa a de e mina si el alo que se p e ende a˜nadi es co ec o. 48 CAP´ ITULO 6. UNA APLICACI ´ ON ACTUAL Conclusi´on El obje i o p incipal de es e abajo es da una idea gene al de las p uebas de conoci- mien o ce o, desde sus o ´ıgenes como p uebas de memb es´ıa has a una de sus aplicaciones ac uales, pasando po los p o ocolos de iden i icaci´on y de i ma. Se ha hecho una e isi´on de la bibliog a ´ıa m´as des acada sob e el ema y se ha es uc u ado c onol´ogicamen e en el abajo. Las p uebas de conocimien o ce o pe mi en que el p obado ansmi a al e i icado que conoce una in o maci´on sin e ela la. Es as p uebas ienen un amplio u u o po delan e pues o que man ene una in o ma- ci´on en sec e o puede esul a muy ´u il. Hoy en d´ıa, es necesa io segui ein en ´andose en cuan o a segu idad, po que siemp e puede habe impos o es o ampas que pongan en pelig o in o maci´on delicada. A lo la go de odo el abajo hemos podido obse a la e oluci´on de la idea de conoci- mien o ce o y como se ha ido adap ando seg´un las necesidades. En un p ime momen o, se p esen a como la demos aci´on de la pe enencia de un elemen o a un lenguaje a a ´es de un in e cambio de mensajes (Cap´ı ulos 2 y 3), siendo un concep o m´as e´o ico que p ´ac ico y con menos aplicaciones. Despu´es, los concep os e´o icos se adap an a la iden i icaci´on y se c ean los p ime os p o ocolos de iden i icaci´on de conocimien o ce o (Cap´ı ulo 4), ambi´en in e ac i os. Pos e io men e, se consiguen p o ocolos en los que no es necesa io un in e cambio de mensajes y se ob ienen las p uebas no in e ac i as de conocimien o ce o, que dan luga a las i mas digi ales de es e ipo (Cap´ı ulo 5). Po ´ul imo, se desc ibe una nue a adap aci´on del concep o de p ueba de conocimien o ce o donde el p obado de- mues a al e i icado que un alo pe enece a un ango sin mos a dicho alo (Cap´ı ulo 6). Adem´as, se o ece una aplicaci´on de es e ipo de p uebas en la ac ualidad. Uno de los p oblemas a los que me he en en ado al ealiza es e abajo ha sido la es- casez y la dispa idad de bibliog a ´ıa, y que ´es a es aba des inada a un p´ublico m´as ´ecnico que e´o ico. En muchas ocasiones la labo del abajo ha sido la de o maliza algunos concep os que no esul aban del odo cla os. Es el caso de una de las pa es undamen- ales de las p uebas de conocimien o ce o, las m´aquinas de Tu ing p obabil´ıs icas, pues o que la bibliog a ´ıa sob e es e ema e a casi inexis en e y es e abajo p e end´ıa da una de inici´on de p ueba de conocimien o ce o lo m´as o malizada posible. O o p oblema que encon ´e e a que la mayo ´ıa de p o ocolos de la bibliog a ´ıa no es aban explicados de una mane a cla a y de allada, po lo que se en´ıan que analiza minuciosamen e pa a encon- a las bases e´o icas de los p o ocolos. A pesa de odo es o, he conseguido amplia mi conocimien o sob e el ema que e a el p incipal obje i o al ealiza es e abajo. Tambi´en he desa ollado capacidad de an´alisis y s´ın esis debido a la bibliog a ´ıa dispa . 49 50 CAP´ ITULO 6. UNA APLICACI ´ ON ACTUAL Bibliog a ´ıa [1] Babai, L. G aph isomo phism in quasipolynomial ime. In P oceedings o he o y- eigh h annual ACM symposium on Theo y o Compu ing (2016), pp. 684–697. [2] Bella e, M., and Goldwasse , S. New pa adigms o digi al signa u es and message au hen ica ion based on non-in e ac i e ze o knowledge p oo s. In Ad ances in C yp ology—CRYPTO’89 P oceedings. [3] Blum, M., Feldman, P., and Micali, S. Non-in e ac i e ze o-knowledge and i s applica ions. In P oceedings o he wen ie h annual ACM symposium on Theo y o compu ing (1988), pp. 103–112. [4] Cecilia Pas o ino. Blockchain: qu´e es, c´omo unciona y c´omo se es ´a usando en el me cado. h ps://www.weli esecu i y.com/la-es/2018/09/04/ blockchain-que-es-como- unciona-y-como-se-es a-usando-en-el-me cado/. [5] Encyclopedia o Ma hema ics. P obabilis ic Tu ing Machine. h p://encyclopediao ma h.o g/index.php? i le=P obabilis ic_Tu ing_ machine&oldid=31204. [6] Encyclopedia o Ma hema ics. Tu ing Machine. h p:// encyclopediao ma h.o g/index.php? i le=Tu ing_machine&oldid=31220. [7] Feige, U., Fia , A., and Shami , A. Ze o-knowledge p oo s o iden i y. Jou nal o c yp ology 1, 2 (1988), 77–94. [8] Fia , A., and Shami , A. How o p o e you sel : P ac ical solu ions o iden- i ica ion and signa u e p oblems. In Con e ence on he heo y and applica ion o c yp og aphic echniques (1986), Sp inge , pp. 186–194. [9] Gold eich, O., Micali, S., and Wigde son, A. P oo s ha yield no hing bu hei alidi y o all languages in np ha e ze o-knowledge p oo sys ems. Jou nal o he ACM (JACM) 38, 3 (1991), 690–728. [10] Goldwasse , S., Micali, S., and Racko , C. The knowledge complexi y o in e ac i e p oo -sys ems. In P oceedings o he se en een h annual ACM symposium on Theo y o compu ing (1985), pp. 291–304. [11] GOLDWASSER, S., MICALI, S., and RACKOFF, C. The knowledge com- plexi yo in e ac i e p oo sys ems. SIAM J. COMPUT 18, 1 (1989), 186–208. 51 52 BIBLIOGRAF´ IA [12] Jain, G. Ze o knowledge p oo s: A su ey. Uni e si y o Pennsyl ania (2008). [13] Koens, T., Ramaeke s, C., and Van Wijk, C. E icien ze o-knowledge ange p oo s in e he eum. [14] Menezes, A. J., Ka z, J., Van Oo scho , P. C., and Vans one, S. A. Handbook o applied c yp og aphy. CRC p ess, 1996. [15] Pass, R., and Shela , A. A cou se in c yp og aph. Theo e ical Founda ion o C yp og aphy (2010), 68–71. [16] Schno , C.-P. E icien signa u e gene a ion by sma ca ds. Jou nal o c yp ology 4, 3 (1991), 161–174. [17] Shami , A. Iden i y-based c yp osys ems and signa u e schemes. In Wo kshop on he heo y and applica ion o c yp og aphic echniques (1984), Sp inge , pp. 47–53. [18] S inson, D. R., and Pa e son, M. C yp og aphy: heo y and p ac ice. CRC p ess, 2018.