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.