Zero Knowledge Proofs: Å bevise uten å vise

La meg ta deg med på en spennende "Sci-fi"-reise, satt veldig snart, i en galakse nært, nært deg. Her er det ingen flyvende biler enda, men den kommende eIDAS-forordningen er i full blomst. Du har bestemt deg for å kjøpe bolig, og søker banken om lån. Banken gir deg et finansieringsbevis, som du får rett inn i din digitale lommebok. Når du går inn i budkrig om drømmeboligen kan du enkelt bruke lommeboken til å bevise at du har dekning for budene du gir. Megler kan med sikkerhet si at finansieringsbeviset du bruker er ditt, og at det er digitalt signert av banken.

Det høres kanskje ut som en vill feberdrøm, men det er dette vi i Kantega sitt eIDAS-team har jobbet med denne høsten. Finansieringsbeviset er gått fra å være en PDF i banken din, til et «Attesterbart Attributt» som du har full kontroll over. Et slikt attesterbart attributt er en liten samling av informasjon med noen helt spesielle egenskaper. Attributtet er kryptografisk signert på en slik måte at det kan bevises hvem som har laget det, hvem det er laget til, og at informasjonen i det ikke er tuklet med. Når du har fått det utstedt i din lommebok, kan du velge hvem du vil dele det med og når du vil dele det.

Når du presenterer finansieringsbeviset ditt som attesterbart attributt, må megler få bekreftet at finansieringen dekker de budene du gir. Men det er veldig viktig at megler ikke får vite hvor mye større bud du har mulighet til å gi. Budrunder er psykologisk spill, og slik informasjon kan gi store utslag på utfallet. Hvorfor skal selgeren av huset godta ditt bud hvis han eller hun vet at du enda har en million å gå på? Ditt attesterbare attributt må altså kunne bevise at det er stort nok, uten å avsløre hvor stort det er. For å klare det, må vi benytte oss av en teknologi som heter «Zero Knowledge Proof».

Eksempel fra høstens eIDAS-prosjekt. Finansieringsbevis presenteres som et Attesterbart Attributt.

Eksempel fra høstens eIDAS-prosjekt. Finansieringsbevis presenteres som et Attesterbart Attributt.

Zero Knowledge Proof

Zero Knowledge Proofs (ZKP), eller på norsk “Nullkunnskapsbevis”, er mer enn en munnfull å sette seg fullstendig inn i, men vi i eIDAS-teamet synes det er verdt å lære litt om det likevel. Spenn på deg sikkerhetsbeltet, så skal vi forsøke å komme oss trygt til den andre siden.

Det er tre typer bruk som står helt sentralt i ZKP for attesterbare attributter: 

1. Å vise frem bare deler av attributtet («SelectiveDisclosure», eller Selektiv Avsløring)
2. Å kunne slå sammen deler av flere attributter til et nytt attributt.
3. Å kunne utlede og bevise en påstand om attributtet uten å avsløre noe mer informasjon enn at påstanden er sann («PredicateProofs», eller Predikatbevis).

Så hva betyr det egentlig at ZKP tillater disse tre typene bruk? Se for deg at attributtet vårt er et helt vanlig førerkort:

Den første typen bruk, Selektiv Avsløring, ville vært om du for eksempel ønsket å vise frem at førerkortet var klasse B, men uten å vise frem noe annet som befinner seg på kortet. Kanskje høres det enkelt ut? Bare dekk til alle feltene på kortet med fingrene dine, og lag et hull der det står “B”. Men da skjuler du også alt som viser at dette er et ekte, gyldig førerkort, gitt av den norske stat, med alle feltene et førerkort må ha for å være gyldig. Legg til at i en digital versjon så må alt være kryptografisk signert, og du har en ordentlig vrien nøtt å knekke.

Den andre typen bruk er egentlig en slags videreføring av den første. Her skal du altså kunne slå sammen deler av førerkortet ditt med deler av et annet attributt, for eksempel vognkortet ditt. Kanskje må du samtidig bevise at du kan kjøre biler av type “B” og at bilen du sitter i faktisk er din?

Den tredje typen bruk, Predikatbevis, er på mange måter den aller mest spennende, og desidert den vanskeligste å få til. Dette handler om å utlede en påstand som ikke direkte står i attributtet, og bevise at den er sann uten å avsløre noe mer om det ekte attributtet. Altså: Forsøk å bevise med førerkortet ditt at du kommer fra et EU-land, uten å avsløre at det landet er Norge. Eller forsøk å bevise at førerkortet fortsatt er gyldig, uten å avsløre når det faktisk utløper. Slike bevis kan det være vanskelig å forestille seg at i det hele tatt er mulig.

Hvor er Willy?

Hvordan kan man bevise at man sitter på informasjon uten å avsløre hva den informasjonen er? Vi forsøker å illustrere med et eksempel. Det er kanskje ganske forenklet, men det bygger på mange av de samme prinsippene som et kryptografisk ZKP gjør.

Alice er verdens største fan av spillet “Hvor er Willy?”, men helt elendig på å løse det. Bob påstår at han har en metode for å finne å finne Willy øyeblikkelig, og at han er villig til å selge den til Alice. For å få bevis på at det stemmer, sender Alice en “Hvor er Willy?”-oppgave til Bob. Etter bare et sekund kommer bildet tilbake, med en ring rundt Willy. Ti ganger sender Alice slike oppgaver til Bob, og hun får svar på alle øyeblikkelig. Endelig er Alice overbevist, og kjøper metoden av Bob. Han beviste altså at han satt på en kunnskap, helt uten å vise frem hva kunnskapen var.

Ikke "Hvor er Willy?", men "Hvor er Abid, sjefen for Kantega sitt Oslo-kontor?". Bilde til venstre fra LaserGuided, CC BY 2.0 via Wikimedia Commons.

Ikke "Hvor er Willy?", men "Hvor er Abid, sjefen for Kantega sitt Oslo-kontor?". Bilde til venstre fra LaserGuided, CC BY 2.0 via Wikimedia Commons.

Til slutt

Teorien bak ZKP har eksistert i mange år, men det er først den siste tiden at vi har hatt nok regnekraft til å gjøre slike bevis innenfor tidsrammer som er praktisk anvendelige. Noen aspekter ved ZKP, slik som Predikatbevis er enda bare så vidt blitt testet i bruk.

Zero Knowledge Proofs er på vei, og mulighetsrommet er enormt. Mange mener at ZKP er helt nødvendig for at eIDAS-forordningen skal få ut sitt fulle potensiale, og det jobbes hardt for å få det som mangler på plass. Det er ingen tvil om at slik teknologi kommer til å bli helt sentral i en fremtid med digitale ID-lommebøker. 

Budprosessen vi har jobbet med i høst er et konkret eksempel på hvordan eIDAS-forordningen og Zero Knowledge Proofs kan forandre hverdagen til det bedre. Det er i hvert fall helt tydelig at både meglere og banker har mye å spare på å få finansieringsbeviset ut i dine digitale hender. Samtidig får du selv full kontroll over din data, og hvordan du deler den. Og hvem vet, kanskje kjøper du ditt neste drømmehjem med en ID-lommebok?

Hvis du vil fordype deg mer i teorien bak ZKP, finnes det mange gode ressurser der ute. Vi kan anbefale denne bloggartikkelen av Matthew Green, som forklarer teorien bak ZKP med et eksempel som går mer i dybden enn vårt. Selskapet Evernym har skrevet denne artikkelen om historien til ZKP, mer konkret til attesterbare attributter. Og til slutt, denne mer formelle definisjonen hentet fra W3C-standarden for attesterbare attributter.

Og helt til slutt. Min kollega Erling på eIDAS-teamet, har også skrevet utfyllende om bakgrunnen for- og ulike sider ved eIDAS. Om felles elektronisk ID i hele Europa og om sikker deling av personinformasjon på tvers av landegrenser.