Prova de coneixement zero

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 m. 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 dóna 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à

Peggy randomly takes either path A or B, while Victor waits outside.

Victor chooses an exit path.

Peggy reliably appears at the exit Victor names.

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 2²⁰, o 9,54× 10⁻⁷.

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?

Un exemple ben conegut d'una demostració de coneixement zero és l'exemple de "On és Wally?". En aquest exemple, el demostrador vol demostrar al verificador que sap on és en Wally en una pàgina d'un objecte d'anàlisi On és en Wally? llibre, sense revelar la seva ubicació al verificador.

El demostrador comença agafant una pissarra negra gran amb un petit forat, de la mida d'en Wally. El pissarra és el doble de la mida del llibre en ambdues direccions, de manera que el verificador no pot veure on a la pàgina el col·loca el demostrador. El demostrador col·loca el tauler sobre la pàgina de manera que Wally quedi al forat.

El verificador ara pot mirar a través del forat i veure en Wally, però no pot veure cap altra part de la pàgina. Per tant, el verificador ha demostrat al verificador que sap on és en Wally, sense revelar cap altra informació sobre la seva ubicació.

Aquest exemple no és una demostració perfecta de coneixement zero, perquè el demostrador sí que revela informació sobre la ubicació d'en Wally, com ara la posició del seu cos. Tanmateix, és una il·lustració decent del concepte bàsic d'una prova de coneixement zero.

Definició

Una demostració de coneixement zero d'alguna afirmació ha de complir tres propietats:

1. Completesa: si l'afirmació és certa, un verificador honest (és a dir, un que segueix el protocol correctament) estarà convençut d'aquest fet per un demostrador honest.
2. Solidesa: si l'afirmació és falsa, cap demostrador fraudulent pot convèncer un verificador honest que és certa, excepte amb una petita probabilitat.
3. Coneixement zero: si l'afirmació és certa, cap verificador aprèn res més que el fet que l'afirmació és certa. En altres paraules, només conèixer l'enunciat (no el secret) és suficient per imaginar un escenari que demostri que el demostrador coneix el secret. Això es formalitza mostrant que cada verificador té algun simulador que, donada només l'enunciat que s'ha de demostrar (i sense accés al verificador), pot produir una transcripció que "sembla" una interacció entre un verificador honest i el verificador en qüestió.

Les dues primeres són propietats de sistemes de demostració interactius més generals. El tercer és el que fa que la demostració sigui de coneixement zero.

Les demostracions de coneixement zero no són demostracions en el sentit matemàtic del terme perquè hi ha una petita probabilitat, l' error de solidesa, que un demostrador fraudulent pugui convèncer el verificador d'una afirmació falsa. En altres paraules, les proves de coneixement zero són "proves" probabilístiques en lloc de proves deterministes. Tanmateix, hi ha tècniques per disminuir l'error de solidesa a valors insignificants (per exemple, endevinar correctament cent o mil decisions binàries té un error de solidesa d'1/2 ¹⁰⁰ o 1/2 ¹⁰⁰⁰, respectivament. A mesura que augmenta el nombre de bits, l'error de solidesa disminueix cap a zero).

Una definició formal de coneixement zero ha d'utilitzar algun model computacional, el més comú dels quals és el d'una màquina de Turing. Siguin P, V i S màquines de Turing. Un sistema de demostració interactiu amb (P,V) per a un llenguatge L és de coneixement zero si per a qualsevol verificador de temps polinòmic probabilístic (PPT) ${\hat {V}}$ existeix un simulador PPT S tal que:

$\forall x\in L,z\in \{0,1\}^{*},\operatorname {View} _{\hat {V}}\left[P(x)\leftrightarrow {\hat {V}}(x,z)\right]=S(x,z),$

on View_{${\hat {V}}$}[P(x)↔${\hat {V}}$(x,z)] és un registre de les interaccions entre P(x) i V(x,z). El demostrador P es modela com a posseïdor d'una potència de càlcul il·limitada (a la pràctica, P sol ser una màquina de Turing probabilística). Intuïtivament, la definició estableix que un sistema de prova interactiu (P,V) és de coneixement zero si per a qualsevol verificador ${\hat {V}}$ existeix un simulador S eficient (depenent de ${\hat {V}}$ ) que pot reproduir la conversa entre P i ${\hat {V}}$ en qualsevol entrada donada. La cadena auxiliar z de la definició fa el paper de "coneixement previ" (incloses les monedes aleatòries de ${\hat {V}}$ ). La definició implica que ${\hat {V}}$ no pot utilitzar cap cadena de coneixement previ z per extreure informació de la seva conversa amb P, perquè si S també se li dóna aquest coneixement previ, aleshores pot reproduir la conversa entre ${\hat {V}}$ i P igual que abans.

La definició que es dóna és la de coneixement zero perfecte. El coneixement zero computacional s'obté exigint que les opinions del verificador ${\hat {V}}$ i el simulador només són computacionalment indistingibles, donada la cadena auxiliar.

Tipus de coneixement zero

Hi ha diversos tipus de proves de coneixement zero:

• Prova de coneixement: el coneixement està amagat a l'exponent com en l'exemple anterior.
• Prova indistingible entre testimonis: els verificadors no poden saber quin testimoni s'utilitza per produir la prova.

Els esquemes de prova de coneixement zero es poden construir a partir de diverses primitives criptogràfiques, com ara criptografia basada en hash, criptografia basada en emparellaments, computació multipartida o criptografia basada en gelosia.

Aplicacions

La recerca en proves de coneixement zero ha estat motivada per sistemes d'autenticació on una part vol demostrar la seva identitat a una segona part mitjançant informació secreta (com ara una contrasenya) però no vol que la segona part aprengui res sobre aquest secret. Això s'anomena "prova de coneixement de coneixement zero". Tanmateix, una contrasenya sol ser massa petita o insuficientment aleatòria per ser utilitzada en molts esquemes per a proves de coneixement de coneixement zero. Una prova de contrasenya de coneixement zero és un tipus especial de prova de coneixement zero que aborda la mida limitada de les contrasenyes

A l'abril de 2015, es va introduir el protocol de demostració única (un protocol Sigma). L'agost de 2021, Cloudflare, una empresa americana d'infraestructura i seguretat web, va decidir utilitzar el mecanisme de prova única per a la verificació web privada mitjançant maquinari del proveïdor.