En criptografia, una prova de coneixement zero és un protocol en què una part (el demostrador) pot convèncer una altra part (el verificador) que una afirmació determinada és certa, sense transmetre al verificador cap informació més enllà del mer fet que aquesta afirmació és certa. La intuïció subjacent a les demostracions de coneixement zero és que és trivial demostrar la possessió de la informació rellevant simplement revelant-la; la part difícil és demostrar aquesta possessió sense revelar aquesta informació (ni cap aspecte d'ella).
Atès que només s'hauria de poder generar una prova d'una afirmació quan es disposa de certa informació secreta relacionada amb l'afirmació, el verificador, fins i tot després d'haver-se convençut de la veracitat de l'afirmació, no hauria de poder demostrar-la a tercers.
Les proves de coneixement zero poden ser interactives, és a dir, que el demostrador i el verificador intercanvien missatges segons algun protocol, o no interactives, és a dir, que el verificador està convençut per un únic missatge del demostrador i no cal cap altra comunicació. En el model estàndard, la interacció és necessària, excepte per a les demostracions trivials dels problemes BPP. En els models comuns de cadenes aleatòries i oracles aleatoris, existeixen proves de coneixement zero no interactives. L'heurística de Fiat-Shamir es pot utilitzar per transformar certes proves interactives de coneixement zero en no interactives.
Història Les proves de coneixement zero van ser concebudes per primera vegada el 1985 per Shafi Goldwasser, Silvio Micali i Charles Rackoff en el seu article "La complexitat del coneixement dels sistemes de prova interactius". Aquest article va introduir la jerarquia IP dels sistemes de prova interactius ( vegeu sistema de prova interactiu) i va concebre el concepte de complexitat del coneixement, una mesura de la quantitat de coneixement sobre la prova transferida del demostrador al verificador. També van donar la primera demostració de coneixement zero per a un problema concret, el de decidir no residus quadràtics mod . Juntament amb un article de László Babai i Shlomo Moran, aquest article històric va inventar sistemes de demostració interactius, pels quals els cinc autors van guanyar el primer Premi Gödel el 1993.
En les seves pròpies paraules, Goldwasser, Micali i Rackoff diuen:
De particular interès és el cas on aquest coneixement addicional és essencialment 0 i mostrem que és possible demostrar interactivament que un nombre és quadràtic sense residus mòdul m, alliberant 0 coneixement addicional. Això és sorprenent, ja que no es coneix cap algorisme eficient per decidir la residuositat quadràtica mod m quan no es dona la factorització de m. A més, totes les demostracions NP conegudes per a aquest problema presenten la factorització prima de m. Això indica que afegir interacció al procés de demostració pot disminuir la quantitat de coneixement que s'ha de comunicar per demostrar un teorema.
El problema quadràtic sense residus té tant un algorisme NP com un algorisme co-NP, i per tant es troba a la intersecció de NP i co-NP. Això també va ser cert per a diversos altres problemes per als quals es van descobrir posteriorment demostracions de coneixement zero, com ara un sistema de demostració no publicat d'Oded Goldreich que verificava que un mòdul de dos nombres primers no és un enter de Blum.
Oded Goldreich, Silvio Micali i Avi Wigderson van anar un pas més enllà, demostrant que, assumint l'existència d'un xifratge indestructible, es pot crear un sistema de prova de coneixement zero per al problema de coloració de grafs NP-complets amb tres colors. Com que tots els problemes de NP es poden reduir eficientment a aquest problema, això significa que, sota aquesta suposició, tots els problemes de NP tenen demostracions de coneixement zero. La raó de la suposició és que, com en l'exemple anterior, els seus protocols requereixen xifratge. Una condició suficient que es cita habitualment per a l'existència d'un xifratge indestructible és l'existència de funcions unidireccionals, però és concebible que alguns mitjans físics també ho puguin aconseguir.
A més d'això, també van demostrar que el problema de noisomorfisme de grafs, el complement del problema d'isomorfisme de grafs, té una demostració de coneixement zero. Aquest problema és a co-NP, però actualment no se sap si pertany a NP ni a cap classe pràctica. De manera més general, Russell Impagliazzo i Moti Yung, així com Ben-Or et al., demostrarien que, assumint també funcions unidireccionals o xifratge irrompible, hi ha proves de coneixement zero per a tots els problemes en IP. = PSPACE, o en altres paraules, qualsevol cosa que es pugui demostrar mitjançant un sistema de demostració interactiu es pot demostrar amb coneixement zero.
Com que no els agradava fer suposicions innecessàries, molts teòrics van buscar una manera d'eliminar la necessitat de funcions unidireccionals. Una manera de fer-ho va ser amb sistemes de prova interactius amb múltiples provadors (vegeu sistema de prova interactiu), que tenen múltiples provadors independents en lloc de només un, permetent al verificador "interrogar" els provadors de forma aïllada per evitar ser enganyat. Es pot demostrar que, sense cap suposició d'intractabilitat, tots els llenguatges de NP tenen demostracions de coneixement zero en un sistema d'aquest tipus.
Exemples abstractes La cova d'Alí Babà
Hi ha una història ben coneguda que presenta les idees fonamentals de les proves de coneixement zero, publicada per primera vegada el 1990 per Jean-Jacques Quisquater i altres al seu article "Com explicar els protocols de coneixement zero als vostres fills". Les dues parts en la història de la prova de coneixement zero són la Peggy com a demostradora de l'afirmació, i el Victor, el verificador de l'afirmació.
En aquesta història, la Peggy ha descobert la paraula secreta que s'utilitza per obrir una porta màgica en una cova. La cova té forma d'anell, amb l'entrada a un costat i la porta màgica bloquejant el costat oposat. En Víctor vol saber si la Peggy coneix la paraula secreta; però la Peggy, que és una persona molt reservada, no vol revelar el seu coneixement (la paraula secreta) a en Víctor ni revelar el fet del seu coneixement al món en general.
Etiqueten els camins esquerre i dret des de l'entrada A i B. Primer, en Víctor espera fora de la cova mentre la Peggy hi entra. La Peggy pren el camí A o el B; en Víctor no pot veure quin camí pren. Aleshores, en Víctor entra a la cova i crida el nom del camí que vol que ella utilitzi per tornar, ja sigui A o B, escollit a l'atzar. Si realment sàpiga la paraula màgica, és fàcil: obre la porta, si cal, i torna pel camí desitjat.
Tanmateix, suposem que ella no coneixia la paraula. Aleshores, només podria tornar pel camí anomenat si en Víctor li donés el nom del mateix camí pel qual ella havia entrat. Com que en Víctor escolliria A o B a l'atzar, tindria un 50% de probabilitats d'endevinar correctament. Si repetissin aquest truc moltes vegades, per exemple 20 vegades seguides, la seva probabilitat d'anticipar amb èxit totes les peticions de Víctor es reduiria a 1 de 220, o 9,54× 10−7.
Així, si la Peggy apareix repetidament a la sortida que anomena en Víctor, pot concloure que és extremadament probable que la Peggy, de fet, conegui la paraula secreta.
Una nota al marge respecte als observadors externs: fins i tot si en Victor porta una càmera oculta que grava tota la transacció, l'única cosa que la càmera gravarà és, en un cas, en Victor cridant "A!" i la Peggy apareixent a A, o en l'altre cas, en Victor cridant "B!" i la Peggy apareixent a B. Una gravació d'aquest tipus seria trivial per a dues persones qualsevol per falsificar-la (només caldria que la Peggy i en Victor s'acordessin prèviament sobre la seqüència d'A i B que en Victor cridarà). Una gravació així segurament no convindrà mai ningú més que els participants originals. De fet, fins i tot una persona que va ser present com a observadora a l'experiment original no n'hauria d'estar convençuda, ja que Victor i Peggy podrien haver orquestrat tot "l'experiment" de principi a fi.
A més, si en Víctor tria els seus A i B llançant una moneda a la càmera, aquest protocol perd la seva propietat de coneixement zero; el llançament de moneda a la càmera probablement seria convincent per a qualsevol persona que veiés la gravació més tard. Així, tot i que això no revela la paraula secreta a Victor, sí que permet que Victor convenci el món en general que Peggy té aquest coneixement, en contra dels desitjos declarats de Peggy. Tanmateix, la criptografia digital generalment "llança monedes a l'aire" basant-se en un generador de nombres pseudoaleatoris, que és similar a una moneda amb un patró fix de cara i creu conegut només pel propietari de la moneda. Si la moneda de Victor es comportés d'aquesta manera, aleshores seria possible que Victor i Peggy haguessin falsejat l'experiment, de manera que l'ús d'un generador de nombres pseudoaleatoris no revelaria el coneixement de Peggy al món de la mateixa manera que ho faria l'ús d'una moneda llançada al aire.
La Peggy podria demostrar-li a en Víctor que coneix la paraula màgica, sense revelar-li-la, en un sol intent. Si tant en Víctor com la Peggy van junts a l'entrada de la cova, en Víctor pot veure com la Peggy entra per A i surt per B. Això demostraria amb certesa que la Peggy coneix la paraula màgica, sense revelar-li-la a en Víctor. Tanmateix, una prova així podria ser observada per un tercer o enregistrada per Victor, i seria convincent per a qualsevol. En altres paraules, la Peggy no podia refutar aquesta prova al·legant que havia confabulat amb en Victor i, per tant, ja no controla qui sap del seu coneixement.
Dues pilotes i l'amic daltònic Imagina't que el teu amic "Víctor" és daltònic al vermell i al verd (mentre que tu no) i que tens dues pilotes: una vermella i una verda, però idèntiques per la resta. A en Víctor, les pilotes li semblen completament idèntiques. En Víctor dubta que les boles siguin realment distingibles. Vols demostrar-li a en Víctor que les boles són en realitat de colors diferents, però res més. En particular, no voleu revelar quina pilota és la vermella i quina és la verda.
Aquí teniu el sistema de demostració: li doneu les dues pilotes a en Víctor i ell les guarda a l'esquena. A continuació, agafa una de les pilotes, la treu de darrere l'esquena i la mostra. Aleshores la torna a col·locar a l'esquena i després tria revelar només una de les dues boles, triant-ne una a l'atzar amb la mateixa probabilitat. Et preguntarà: "He canviat la pilota?" Tot aquest procediment es repeteix tantes vegades com calgui.
Mirant els colors de les boles, és clar que pots dir amb certesa si les ha canviat o no. D'altra banda, si les boles fossin del mateix color i, per tant, indistingibles, la vostra capacitat per determinar si s'ha produït un canvi no seria millor que una endevinalla aleatòria. Com que la probabilitat que haguéssiu aconseguit identificar aleatòriament cada interruptor/no interruptor és del 50%, la probabilitat d'haver aconseguit aleatòriament tots els interruptors/no interruptors s'aproxima a zero.
En múltiples proves, la taxa d'èxit convergiria estadísticament al 50%, i no es podria aconseguir un rendiment significativament millor que l'atzar. Si tu i el teu amic repetiu aquesta "prova" diverses vegades (per exemple, 20 vegades), el teu amic s'hauria de convèncer que les boles són realment de colors diferents.
La demostració anterior és de coneixement zero perquè el teu amic mai aprèn quina pilota és verda i quina és vermella; de fet, no adquireix cap coneixement sobre com distingir les boles.
On és Wally?