Zero Knowledge

Hei. Jeg kunne like greit ha skrevet ‘Null viten’, men hvor kult klinger det?

20140219_125614

Ok, eventyr:

Det var en gang en kar som het Ali Baba. Hver dag gikk Ali Baba til markedet. En dag på markedet var Ali Baba (heretter AB) vitne til at en tyv stjal vesken til en gammel dame og stakk av med den. AB la seg på sprang etter tyven, og etter å ha jaget ham igjennom en dal kom de til en åpning i fjellet. Åpningen hadde to veier inn i fjellet; en til høgre og en til venstre. Siden AB ikke så hvilken av veiene tyven hadde løpt, tenkte han at dette er 50:50, så han valgte å løpe inn veien til høgre. Han løp noen titalls meter før han støtte på en fjellvegg og det var bom stopp.
Optimistisk som han var bestemte han seg for å snu og løpe inn veien til venstre, bare for å sjekke. Men akk; heller ikke venstre vei førte til noe mer enn en fjellvegg.

Uflaks, tenkte AB, og slo seg til ro med at tyven hadde sluppet unna.

DSC_0478

Rett som det er skjedde akkurat det samme igjen neste dag: AB tusler rundt på markedet, tyv stjeler veske, AB forfølger tyv inn i dal, tyv løper inn i hull i fjellet. Denne gangen bestemmer AB seg for å forfølge tyven inn til venstre, men også denne gangen løper AB rett på en fjellvegg.

Etter at dette har gjentatt seg hver dag i en uke begynner AB å lure. Han kan litt statistikk, og skjønner at det er totalt usannsynlig at tyven skal ha flaks med veivalget så mange ganger på rad.

Derfor gikk ikke AB til markedet neste dag, men gjemte seg heller inne i hulen, i håp om at en tyv på flukt skulle komme inn. Og tror du det ikke: Tyven kom, og idet han nærmet seg sa han

Sesam sesam, lukk deg opp!

og AB fikk til sin store forundring se at fjellveggen åpnet seg og tillot tyven å passere, slik at han kunne løpe ut av hulen på den andre siden. Straks tyven hadde passert, lukket fjellveggen seg og så ut som om ingenting mystisk hadde skjedd.

Igjen unslapp altså tyven, men AB var glad, for han hadde oppdaget hulens store hemmelighet.

20140211_153605

AB eksperimenterte lenge med hulen og de magiske ordene, og etter lang tid fant han ut hvordan han kunne endre passordet. Hva han endret det til, dog, det er det bare AB som vet.

La oss nå anta at AB vil bevise for oss at han kan de magiske ordene, men ikke vil at vi skal lære de magiske ordene selv. Det vi da må gjøre, er å bli med AB inn i hulen, men bare så langt at vi ser hvor han kommer ut, uten å høre de magiske ordene når han sier dem. For oss vil det være en smal sak å si “Kom ut på høgre side!” og se at AB faktisk kommer ut på høgre side. Sånn kan vi holde på en stund, la oss si 40 ganger på rad, og konkludere med at det er en million millions sjangse for at han får det til å klaffe hver gang, bare på flaks.

Ergo kan vi konkludere med at AB faktisk kan et hemmelig passord, uten å ha lært passordet selv.

20140219_102658

men. MEN! Hva om jeg ville fortelle noen, for eksempel min venn Hansi, om dette mystiske passordet? Måtte Hansi bli med meg til en basar i midtøsten? Nei, det må da vel holde at jeg filmer testen min med Ali Baba, slik at Hansi kan se at jeg roper “venstre!” og AB kommer ut på venstresiden, etc.
Hvis Hansi stoler blindt på meg vil han nok ta mitt ord på at testen ikke er planlagt på forhånd, og tro på at det finnes en magisk hule med et magisk passord som bare én mann vet om.
Hvis Hansi derimot besitter et minimum av kritisk sans vil han si “stopp en hel, hvordan vet jeg at ikke du og AB har planlagt hele opplegget, og prøver å lure oss til å tro at dere sitter på et hemmelig passord dere egentlig ikke har?”

og så jeg bare “In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true, without conveying any additional information apart from the fact that the statement is indeed true”.

20140223_100447

så egentlig hadde jeg ikke tenkt å fortelle en trivelig, spennende og lærerik historie. EGENTLIG er jeg bare en kjip eksistensialist som har vært sykemeldt i en uke, ikke vil være alene om å ikke skjønne en dritt og dessuten er litt frustrert over at det kjennes ut som alt er der ute, at universet er både komplett og konsistent, men at intellektene våre ikke evner å gripe det der lille, lille som skal til for å se sammenhengen.

20140219_161811

Så mange store tenkere
Så mange store tanker
Så liten Ingahjerne.

A zero-knowledge proof must satisfy three properties:

  1. Completeness: if the statement is true, the honest verifier (that is, one following the protocol properly) will be convinced of this fact by an honest prover.
  2. Soundness: if the statement is false, no cheating prover can convince the honest verifier that it is true, except with some small probability.
  3. Zero-knowledge: if the statement is true, no cheating verifier learns anything other than this fact. This is formalized by showing that every cheating verifier has some simulator that, given only the statement to be proven (and no access to the prover), can produce a transcript that “looks like” an interaction between the honest prover and the cheating verifier.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s