Et bevis på null kunnskap er en byggestein som brukes i kryptologi for autentisering og identifikasjon . Dette uttrykket betegner en sikker protokoll der en enhet, kalt en "bevisleverandør", matematisk beviser for en annen enhet, "verifikatoren", at et forslag er sant uten å avsløre annen informasjon enn proposisjonens sannhet.
I praksis kommer disse ordningene ofte i form av protokoller som "utfordring / respons" ( utfordring-respons ). Verifikatoren og bevisleverandøren utveksler informasjon, og kontrolløren sjekker om det endelige svaret er positivt eller negativt.
Engelsktalende bruker forkortelsen ZKIP for Zero Knowledge Interactive proof .
Det er også varianter uten interaksjon ( ikke-interaktivt null-kunnskapssikkerhet ). Disse kan konstrueres i den tilfeldige orakelmodellen av Fiat-Shamir heuristikk .
Jean-Jacques Quisquater og Louis Guillou publiserte i 1989 en artikkel med tittelen "How to explain zero-knowledge protocols to your children" (eller "Hvordan forklare barna dine protokollene uten bidrag fra kunnskap"). Det er en pedagogisk introduksjon til bevisbegrepet med null avsløring av kunnskap, basert på historien " Ali Baba og de førti tyvene ". Vi vurderer to personer: Alice (prover) og Bob (verifier). Vi vurderer også en hule med en gaffel: A og B. Vi kan gå fra A til B eller fra B til A ved å åpne en dør ved hjelp av et magisk ord. Alice vil bevise for Bob at hun kan det magiske ordet for å åpne døren, men vil ikke at Bob skal finne ut av det. Det handler om et "bevis på kunnskap" (Alice beviser for Bob at hun kjenner nøkkelen) men uten "informasjonsbidrag" (Alice holder henne hemmelig). For å gjøre dette vil Alice og Bob gjenta følgende scenario flere ganger.
Flere scenarier oppstår:
Hvis Alice ikke kjenner det magiske ordet, kan Bob bli villedet i tilfeller der forespørselen hans samsvarer med Alices nåværende posisjon. Forutsatt at hun følger protokollen (konsistenskriterium), vil Alice's feil bli ansett som bevis på manglende kunnskap. Bob kan stoppe umiddelbart, han er sikker på at Alice ikke kjenner det magiske ordet.
Ved å starte på nytt flere ganger fra trinn 1, kan Bob samle nok informasjon til å være ganske sikker på at Alice har det magiske ordet. For hvert nytt forsøk forbedrer han selvtilliten. Hvis Alice ikke er i besittelse av det magiske ordet, er det 50% sjanse for at hun vil gjøre en feil. Med N prøver er sannsynligheten for at Bob vil si at Alice har hemmeligheten når hun ikke har den .
For å sette dette parallelt med kryptografiske primitiver som en del av en "utfordring / respons" -protokoll, er det alltid en sjanse, uansett hvor liten, at svaret gitt av bevisleverandøren trekkes tilfeldig og at det tilsvarer det som ble forventet av verifisereren.
I dette eksemplet vurderer vi to identiske objekter, men som har en egenskap som skiller dem, altså to like kuler, men med forskjellige farger. Eksemplet kommer fra Oded Goldreich, som brukte to kort i to forskjellige drakter.
Eksemplet er basert på en fiktiv situasjon der to personer griper inn: den ene er fargeblind og den andre skiller farger. Det er to skiller baller utenfor fargene, rød og grønn. For fargeblind er de helt identiske. Målet er å bevise for den fargeblinde personen at personen som ser fargene er i stand til å skille kulene etter fargene, men uten at fargene (rød eller grønn blir avslørt).
Den fargeblinde personen plasserer kulene bak ryggen, tar deretter en av kulene og viser den til den andre personen. Hun legger det bak ryggen og velger deretter å vise en av ballene, enten den samme eller den andre med en sannsynlighet på 50%. Hun spør deretter "har jeg byttet baller?" ". Prosessen gjentas så mange ganger som nødvendig. Hvis protokollen gjentas nok ganger, og hvis den ikke-fargeblinde personen alltid gir det riktige svaret, vil den fargeblinde personen bli overbevist med en meget stor sannsynlighet for at partneren faktisk er i stand til å skille ballene etter fargen. Det er en nullkunnskapssikker protokoll, siden den aldri avslører kulenes farge.
Blant de kryptografiske bevisene som finnes, kan vi nevne:
Tre eiendommer må oppfylles:
De to første egenskapene er de samme som brukes til å definere et interaktivt bevissystem , som er et mer generelt begrep. Det er den tredje egenskapen som gir null kunnskap .
Bevissikkerheten kan klassifiseres i flere kategorier, i henhold til sikkerheten som forventes av de forskjellige sikkerhetskonseptene som tidligere er definert, det vil si robustheten og mangelen på kunnskap. Vi snakker da om:
Den første avviser ikke eksistensen av en metode (men denne, hvis den eksisterer, vil ikke ha en polynom kompleksitet), mens det perfekte beviset sikrer at ingen metode eksisterer (i henhold til informasjonsteorien ).
På samme måte, hvis robustheten er statistisk, vil begrepet "bevis" bli brukt, ellers hvis det er beregningsmessig, vil begrepet "argument" bli brukt for å betegne beviset.
En metode for å konstruere bevis uten kunnskapsinformasjon bruker såkalte Σ-protokoller (så kalt på grunn av treveiskommunikasjonen som minner om den greske bokstaven Sigma ). En protokoll Σ er en interaktiv protokoll mellom en beviser og en verifikator som involverer tre utvekslinger:
Sikkerheten til en protokoll Σ er veldig nær sikkerheten til et bevis uten kunnskapshensyn: konsistens, spesiell robusthet og null informasjon med en ærlig verifikator. Den generelle konstruksjonen består da av å pålegge verifisereren ærlighet ved å tvinge ham til å generere sin utfordring uavhengig av forpliktelsen gjennom et kryptografisk løfteopplegg .
Flere bevis uten kunnskapsopplysning er basert på denne konstruksjonen, for eksempel Schnorr-protokollen , eller Guillou-Quisquater- identifikasjonsordningen . En av grunnene kan være at det er lettere å arbeide med protokollene Σ, som også har gode regelmessighetsegenskaper: det er konstruksjoner for å utføre konjunksjonen og disjunksjonen av protokoller Σ. Egenskaper som vi ikke har på bevisene uten offentliggjøring av generisk kunnskap.
Dette er Shafi Goldwasser , Silvio Micali og Charles Rackoff som brukte for første gang i 1985, begrepet "bevis null kunnskap om kunnskap" , eller mer spesifikt dets engelske form, "null kunnskap bevis" i deres saksoppgave. Shafi Goldwasser og Silvio Micali mottok Turing -prisen i 2012 for arbeidet sitt.
Det var Oded Goldreich , Silvio Micali og Avi Wigderson som oppdaget at ved å anta eksistensen av kryptografiske primitiver, kan det opprettes et null-kunnskap- bevissystem for graffarging- problemet . Dette innebærer at alle problemer i NP har et slikt bevissystem.
Shafi Goldwasser bruker nå sitt arbeid innen QED-it , noe som har gjort ZKIP til sin kjernevirksomhet.