Prova de coneiximent zero

En criptografia, un protocol de coneiximent zero o prova de coneiximent nul, també conegudes per les sigles ZKP (de l'anglés Zero Knowledge Proof), és un protocol criptográfico que establix un método per a que una de les parts prove a una atra que una declaració (generalment matemàtica) és certa, sense revelar res més que la veracitat de la declaració.

Eixemple intuïtiu

Hi ha una història ben coneguda que presenta algunes de les idees de proves de coneiximent zero, publicat per primera volta per Jean-Jacques Quisquater i uns atres en el seu artícul "Cóm explicar proves de coneiximent zero als teus fills". És una pràctica comuna per a etiquetar les dos parts en una prova de coneiximent zero com Peggy (el provador de la declaració, prover) i Victor (el verificador de la declaració, verifier).

En esta història, Peggy ha posat al descobert la paraula secreta que s'utilisa per a obrir una porta màgica en una cova. La cova té forma de círcul, en l'entrada en un costat i el bloqueig de la porta màgica a l'atre costat. Víctor diu que va a pagar-li pel secret, pero no fins que estiga segur de que ella realment ho sap. Peggy diu que va a dir-li el secret, pero no fins que reba els diners. Ells establixen un pla pel qual Peggy pot demostrar que coneix la paraula sense dir-li-la a Víctor.

En primer lloc, Víctor espera fòra de la cova mentres que Peggy ingressa. Ells etiqueten els camins a l'esquerra i dreta de l'entrada A i B. Peggy pren a l'encert qualsevol camí A o B. A continuació, Víctor entra en la cova i crida el nom de la ruta en la que vullgues que Peggy retorne, ya siga A o B, elegits a l'encert. Provar que ella realment coneix la paraula màgica és fàcil: ella obri la porta, si és necessari, i torna a lo llarc de la trayectòria desijada. Tinga en conte que Víctor no sap quin és el camí que ella ha elegit.

No obstant, supongam que no coneixia la paraula. Llavors, solament seria capaç de tornar pel camí si Victor donara el nom de la mateixa ruta per la que ella havia entrat. Ya que Victor elegiria A o B a l'encert, hi hauria una provabilitat del 50% d'encertar. Si tinguera que repetir este truc moltes voltes, per eixemple 20 voltes seguides, la seua provabilitat d'èxit seria pràcticament nula.

Per lo tant, si Peggy fiablemente apareix en l'eixida que Víctor nomena, es pot concloure que és molt provable que conega la paraula secreta.

Observe que també és possible demostrar que Peggy sap la paraula si ella entra en una ruta i retorna en una atra. Pero en este cas, Peggy prova a tot lo món que ella sap la paraula. En el sistema a on Peggy pren una ruta a l'encert sense dir-la a ningú, els de fòra poden pensar que Peggy i Víctor tenen un acort sobre l'orde de rutes que Víctor va a cridar, llavors Peggy solament va a demostrar el seu coneiximent de la paraula a Víctor.

Un atre eixemple: dos pilotes i un amic daltónico

Imagina que el teu amic Víctor és daltónico roig-vert (mentres que tu no ho eres) i que teniu dos pilotes: una roja i una atra verda, pero per lo demés idèntiques. A Víctor, les pilotes li semblen completament idèntiques. Víctor no creu que les pilotes siguen realment distinguibles. Vosté vol demostrar-li a Víctor que, en realitat, les boles tenen colors diferents, pero res més. En concret, no vol revelar qué bola és la roja i quin és la verda.

Est és el sistema de prova. Li dones les dos boles a Víctor i ell li les posa darrere de l'esquena. A continuació, agarra una de les boles, la trau de darrere de l'esquena i la mostra. A continuació, torna a colocar-la darrere de l'esquena i decidix mostrar només una de les dos boles, elegint una de les dos a l'encert en la mateixa provabilitat. Li preguntarà: "¿He canviat la bola?". Tot este procediment es repetix tantes voltes com siga necessari.

Per supost, observant el color de les boles es pot saber en certea si les ha canviat o no. En canvi, si les boles anaren del mateix color i, per lo tant, indistinguibles, és impossible encertar en una provabilitat superior al 50%.

Com la provabilitat de que hages encertat a l'encert en l'identificació de cada ronda és del 50%, la provabilitat d'haver encertat a l'encert en totes les rondes s'aproxima a zero ("solvència"). Si vosté i el seu amic repetixen esta "prova" vàries voltes (per eixemple, 20 voltes), el seu amic deuria convéncer-se ("completitud") de que les boles són efectivament de distint color.

La prova anterior és de coneiximent nul perque el teu amic mai deprén qué bola és verda i quin és roja; de fet, no adquirix cap coneiximent sobre cóm distinguir les boles ("coneiximent zero").

Vore també

• Protocol criptográfico