Ezagutza zero proba

Ezagutza zero probak (ingelesez Zero-Knowledge Proof, ZKP) kriptografia arloko protokoloen multzo bat dira. Protokolo hauen bidez, frogatzaile batek (prover) beste alde bati (verifier) baieztapen bat egia dela frogatu ahal dio, baieztapen hori egiaztatzeko beharrezkoa den informazio sekreturik agerian utzi gabe.Goldwasser, S.; Micali, S.; Rackoff, C. (1989). 
The Knowledge Complexity of Interactive Proof Systems.
SIAM Journal on Computing.

Ezagutza zero proben helburua ez da soilik baieztapen baten egiazkotasuna frogatzea, baizik eta egiaztapena egitean ez ematea informazio gehigarririk. Horregatik, protokolo mota hauek funtsezkoak dira pribatutasuna eta segurtasun informatikoa bermatzen dituzten sistema modernoetan.

Adierazpen baten froga sortu ahal izan beharko litzatekeela kontuan hartuta adierazpenarekin lotutako informazio sekretu jakin bat edukitzean bakarrik, egiaztatzaileak, ezagutza zero froga baten bidez adierazpenaren egiazkotasunaz konbentzitu ondoren ere, ezin izan beharko luke adierazpena hirugarrenei frogatu.

 Kontzeptu orokorra 
Ezagutza zero frogak probabilitatearen teoria eta konplexutasun konputazionala oinarrian definitzen dira. Protokolo horiek interaktiboak izan daitezke, bi aldeek mezuak trukatzen dituztenean, edo ez-interaktiboak, froga bakar baten bidez egiaztapena egin daitekeenean. 

 Historia 
Ezagutza zero frogak 1980ko hamarkadan definitu zituzten Shafi Goldwasser, Silvio Micali eta Charles Rackoff ikertzaileek. Haien lanek erakutsi zuten posible zela baieztapen matematikoak egiaztatzea informazio sekreturik azaldu gabe, eta, ondorioz,  kriptografia modernoaren oinarrietako bat bihurtu ziren.

Gainera, lehen ezagutza zero froga formala eman zuten arazo zehatz baterako eman zuen: m moduluarekiko hondar ez-koadratikoak erabakitzea. Lan horrek froga-sistema interaktiboen oinarriak ezarri zituen, eta egileek Gödel saria jaso zuten.

Ondoren, ikertzaileek erakutsi zuten elkarreragina gehitzeak frogatzeko behar den informazio-kopurua murriztu zezakeela. Geroago, beste lan batzuek frogatu zuten zenbait NP eta co-NP klaseetako zenbait arazok ezagutza zero frogak dituztela. Are gehiago, Goldreich, Micali eta Wigdersonen lanek erakutsi zuten, zifratze apurtezina edo norabide bakarreko funtzioak existitzen direla onartuz gero, NPko arazo guztiek ezagutza zero frogak izan ditzaketela. Goldreich, Oded (1985). «A zero-knowledge proof that a two-prime moduli is not a Blum integer».
Unpublished manuscript. 

Ikerketak aurrera egin ahala, frogatu zen IP = PSPACE klaseko arazo guztientzat ere posible direla ezagutza zero frogak, baldintza kriptografiko egokiak betez. Bestalde, hipotesi kriptografikoak saihesteko, frogatzaile anitzeko sistema interaktiboak garatu ziren; sistema horietan NP-ko hizkuntza guztiek ezagutza zero frogak izan ditzakete inolako suposizio konplexurik gabe.

Azkenik, Interneteko inguruneetan aldi berean exekutatzen diren protokoloek erronka berriak sortzen dituztela ikusi zen, eta horrek ezagutza zero frogaren aldaera berriak ekarri zituen, hala nola lekukoaren froga bereizezinak eta ezagutza zero froga ez-interaktiboak. Azken horietan, frogatzaileak eta egiaztatzaileak ausazko kate komun bat partekatzea nahikoa da, elkarreraginik gabe segurtasuna bermatzeko. Blum, Manuel; Feldman, Paul; Micali, Silvio (1988). «Non-interactive zero-knowledge and its applications». Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing. Wu, Huixin; Wang, Feng (2014). «A Survey of Noninteractive Zero Knowledge Proof System and Its Applications». The Scientific World Journal, 2014, Article ID 560484. doi:10.1155/2014/560484. PMID 24883407 

 Adibide intuitiboak 

 Ali Babaren kobazuloa 
Istorioan bi pertsonaiek parte hartzen dute: Peggyk, kobazulo batean ate magiko bat irekitzen duen hitza ezagutzen duena, eta Víctorrek, Peggyk benetan hitz hori ezagutzen duela ziurtatu nahi duenak.

Dilema horri konponbidea emateko, biak ados jarri ziren Peggyren ezagutza egiaztatzeko metodo batean, Peggyk hitza bera adierazi gabe. Peggy kobazuloan sartzen da bi bide posibleetako batetik, ausaz aukeratuta. Ondoren, Víctorrek adierazten dio zein bidetatik itzuli behar duen. Peggyk benetan hitz sekretua ezagutzen badu, atea ireki eta eskatutako bidetik itzuli ahal izango da, Víctorrek hasieran zein bide aukeratu zuen jakin gabe.

Peggyk hitza ezagutzen ez balu, bide zuzena ausaz bakarrik aukeratuko luke soilik, %50eko probabilitatearekin. Prozedura hau behin eta berriz errepikatzeak (adibidez, hogei aldiz) ia ezinezkoa egiten du hitza ez dakien norbaitek arrakasta izatea. Horrela, Víctor ia ziur egon daiteke Peggyk sekretua ezagutzen duela, Peggyk sekretua agerian jarri gabe.

Gainera, adibide honek puntu garrantzitsu bat azpimarratzen du: metodo honek Víctorri bakarrik ematen dio Peggyren ezagutza egiaztatzeko aukera, beste pertsona batzuek ezin dutelako hori egiaztatu edo hitz sekretua ezagutzeko aukerarik izan ere. Honek ezagutza zero frogen funtsa islatzen du: ezagutza modu fidagarrian frogatzea, informazio gehigarririk agerian utzi gabe.

 Non dago Wally? 
Ezagutza zero frogen beste adibide ezagun bat «Non dago Wally?» izenekoa da. Adibide honetan, frogatzaileak egiaztatzaileari frogatu nahi dio Where’s Wally? liburu bateko orrialde batean Wally non dagoen badakiela, haren kokapena zehazki adierazi gabe.Murtagh, Jack (2023ko uztailaren 1a).
«Where’s Wally? How to Mathematically Prove You Found Him without Revealing Where He Is».
Scientific American.

Horretarako, frogatzaileak panel beltz handi bat erabiltzen du, Wallyren tamainako zulo txiki batekin. Panela liburua baino handiagoa da alde guztietatik, horrela egiaztatzaileak ez dezan ikusi orriaren zein zatitan jartzen den. Ondoren, frogatzaileak panela orrialdearen gainean jartzen du, Wally zuloaren barruan geratzen den moduan.

Egiaztatzaileak zulotik begiratzean Wally ikus dezake, baina ezin du orrialdeko gainerako ezer ikusi. Horrela, frogatzaileak erakusten du Wally non dagoen badakiela, haren kokapenari buruzko informazio gehigarririk eman gabe.

Hala ere, adibide hau ez da ezagutza zero froga perfektua, frogatzaileak informazio apur bat ematen duelako, hala nola Wallyren gorputzaren orientazioa edo zati batzuk. Dena den, ezagutza zero frogen oinarrizko ideia ulertzeko adibide egokia eta intuitiboa da.

 Beste adibide klasiko bat 
Beste adibide batean, kolore desberdineko bi pilotak erabiltzen dira. Lagun bat kolore-itsua dela suposatuta, frogatu nahi zaio pilotak desberdinak direla, baina zein kolore duten adierazi gabe. Iterazio ugari egin ondoren, lagunak probabilitate handiarekin ondoriozta dezake pilotak ez direla berdinak, inolako informazio zehatzik jaso gabe.

 Definizio formala 
Ezagutza zero frogek hiru propietate nagusi bete behar dituzte:

 Osotasuna (completeness): baieztapena egiazkoa bada eta protokoloa behar bezala exekutatzen bada, egiaztatzaileak frogatzailea sinetsi behar du.
 Irmotasuna (soundness): baieztapena faltsua bada, ezinezkoa izan behar da egiaztatzaile zintzo bat engainatzea, salbu eta probabilitate oso txiki batekin.
 Ezagutza zero (zero-knowledge): egiaztatzaileak ez du baieztapenaren egiazkotasunaz haratago inolako informazio sekreturik eskuratu behar.

Propietate hauek probabilitatearen teoria eta konplexutasun konputazionalaren bidez definitzen eta frogatzen dira.

Ezagutza zero frogak ez dira froga matematikoak termino klasikoan, probabilitate txiki bat dagoelako, —sendotasun errorea— frogatzaile iruzurgile batek baieztapen faltsu bati buruz egiaztatzailea konbentzitzeko. Hau da, ezagutza zero frogak froga probabilistikoak dira, eta ez demostrazioak. Hala ere, badira teknikak sendotasun-errorea nahi bezain txikia bihurtzeko (adibidez, ehun edo mila erabaki bitarren gainean asmatzeak, hurrenez hurren 1/2100 edo 1/21000 eko sendotasun-errorea du). Iterazio kopurua handitzen den heinean, sendotasun errorea zero aldera hurbiltzen da.

 Ezagutza zero frogen motak 
 Froga interaktiboak 
Ezagutza zero froga interaktiboetan, frogatzaileak eta egiaztatzaileak mezuak trukatzen dituzte protokoloaren hainbat pausotan. Pausu horiek, normalean, erronka eta erantzun egituran antolatzen dira, frogatzaileak sekretua benetan ezagutzen duela frogatzeko.

 Froga ez-interaktiboak 
Ezagutza zero froga ez-interaktiboetan, frogatzaileak mezu bakar bat sortzen du, eta egiaztatzaileak modu independentean egiaztatzen du. Horrelako frogak sortzeko ohikoa da Fiat–Shamir heuristika erabiltzea, froga interaktiboak froga ez-interaktibo bihurtzeko.Fiat, A.; Shamir, A. (1986).
How to Prove Yourself: Practical Solutions to Identification and Signature Problems.
Advances in Cryptology – CRYPTO.

 Aplikazioak 
Ezagutza zero frogek gaur egun aplikazio ugari dituzte informatikaren eta kriptografiaren arloan. 

 Autentifikazio-sistema seguruetan: erabiltzaile batek pasahitz edo gako kriptografiko bat ezagutzen duela frogatu dezake, informazio hori bera agerian utzi gabe.Goldreich, O. (2001).
Foundations of Cryptography, Volume 1.
Cambridge University Press.
 Bloke-kateetan eta kriptomonetetan: transakzioak baliozkotzeko erabiltzen dira, datu sentikorrak partekatu gabe, hala nola zk-SNARK eta zk-STARK sistemetan.Ethereum Foundation.
Zero-Knowledge Proofs.
 Pribatutasuna bermatzen duten protokoloetan: identitatea eta datu pertsonalak babesteko mekanismoetan erabiltzen dira, informazioaren esposizioa minimizatuz.Agencia Española de Protección de Datos.
Pruebas de conocimiento cero y privacidad. 

 Web3 eta eskalagarritasuna 
Web3 arkitekturetan, ezagutza zero frogek sareen eskalagarritasuna eta eraginkortasuna hobetzen dituzte, egiaztapen-prozesuak optimizatuz eta, aldi berean, pribatutasuna mantenduz

 Ezagutza zero sistemen segurtasun ahuleziak 
Ezagutza zero frogak informazioa modu seguruan egiaztatzeko tresna indartsuak diren arren, horiek inplementatzen dituzten zirkuitu aritmetikoak arreta handiz diseinatu behar dira. Zirkuitu horiek murrizketa nahikorik ez badute, segurtasun-ahulezia sotil baina larriak sor daitezke.

Sistema horietan ohikoenetako ahulezietako bat logika azpimurriztua (ingelesez, underconstrained logic). Kasu horretan, murrizketa eskasek aukera ematen diote frogatzaile gaizto bati baieztapen oker baterako froga sortzeko, egiaztapena gainditzen badu ere. 2024an egindako eraso ezagunen sistematizazio batek erakutsi zuen SNARKetan oinarritutako sistemetako zirkuitu-mailan dokumentatutako akatsen %96 inguru zirkuitu azpimurriztuek eragindakoak zirela.  Chaliasos, Stefanos; Ernstberger, Jens; Theodore, David; Wong, David; Jahanara, Mohammad; Livshits, Benjamin (2024). «SoK: What Don’t We Know? Understanding Security Vulnerabilities in SNARKs». Proceedings of the 33rd USENIX Security Symposium (SEC ’24), 3855–3872. ISBN 978-1-939133-44-1. 

Ahulezia horiek maiz sortzen dira maila altuko logika maila baxuko murrizketa-sistemetara itzultzean, bereziki Circom edo Gnark bezalako domeinu espezifikoko lengoaiak erabiltzen direnean. Ikerketa berriek erakutsi dute determinismoaren frogapen formala egiteak —hau da, zirkuitu baten irteerak sarreretan soilik oinarrituta daudela bermatzeak— ahulezia mota osoak ezabatu ditzakeela. Pailoor, Shankara; Chen, Yanju; Wang, Franklyn; Rodríguez, Clara; Van Geffen, Jacob; Morton, Jason; Chu, Michael; Gu, Brian; Feng, Yu; Dillig, Işıl (2023). «Automated Detection of Under-Constrained Circuits in Zero-Knowledge Proofs». Proceedings of the ACM on Programming Languages, 7, 1510–1532. doi:10.1145/3591282. 

 Erreferentziak 

 Ikus, baita 
 Kriptografia
 Protokolo kriptografikoak
 Segurtasun informatikoa
 Konplexutasun konputazionala

Kategoria:Kriptografia
Kategoria:Informatika teorikoa
Kategoria:Segurtasun informatikoa
Kategoria:Algoritmoak