Nollkunskapsbevis

Ett nollkunskapsbevis (eng. Zero-knowledge proof) eller nollkunskapsprotokoll är, inom kryptografi, ett sätt att bevisa ett sant påstående utan att avslöja någon information utöver faktumet att påståendet är sant. Bevisande parten ska även ha någon information som onekligen skulle kunna bevisa påståendet, men som parten vill hålla hemlig. Att bevisaren har den hemliga informationen bör komma fram i påståendet. Om påståendet endast hävdar faktumet att bevisaren har den hemliga informationen, kallas beviset istället för ett nollkunskapsbevis av kunskap.

Nollkunskapsbevis används i praktiken när bevisaren har information som har högt värde i hemligt tillstånd. Ett vanligt förekommande exempel är om man ska sälja en hemlig produkt till en beställare. Man vill inte visa produkten förrän man vet att man får betalt, och beställaren vill inte betala förrän den är helt säker på att man har produkten. Principen med ett nollkunskapsbevis är att man då ska kunna övertyga beställaren att man har produkten, utan att överhuvudtaget visa produkten.

Beviset utgår ifrån ett läge där en ärlig bevisare har någon hemlig information, men att den som verifierar inte gör det. Bevisaren bevisar därefter att vederbörande innehar denna information genom en rad kontroller. Trots "beviset" finns det en risk med varje kontroll, då en bevisare skulle kunna ta sig igenom kontrollen genom att gissa. Dock så kan en bevisare med hemliga informationen teoretiskt sätt klara oändligt med kontroller, och eftersom risken att vederbörande gissar rätt minskar med varje kontroll blir felet oändligt litet och därmed försumbart. I praktiken kan en verifierare givetvis inte ställa ett oändligt antal kontroller, men med säkra kontroller minskar felet fort.

Till exempel, ifall det finns en 90% chans att bevisaren har hemliga informationen efter en kontroll, och om denna kontroll blir sann 9 gånger, är risken att bevisaren inte har den hemliga informationen $10^{-9}$ (en på miljarden). Fler kontroller minskar risken för fel, men det finns alltid en chans för en fuskande bevisare att bevisa ett falskt påstående. Därför säger man att ett nollkunskapsbevis, till skillnad från traditionella matematiska bevis, inte är determinerat. På grund av hur ett nollkunskapsbevis är uppbyggt finns det alltid en risk att ett falskt påstående kan bevisas, även om det är högst osannolikt. Därför kallas nollkunskapsbevis istället för sannolika "bevis".

Bakgrund

Det finns situationer där en part behöver övertyga en annan part om att den har en viss hemlig information, utan att den andra parten får ta del av den hemliga informationen. Eftersom en fullständigt logisk lösning till problemet inte kan finnas forskas det mycket kring bästa möjliga sätt att hantera situationen.

Nollkunskapskonceptet framfördes först på 1980-talet av forskare Shafi Goldwasser, Silvio Micali och Charles Rackoff vid MIT. Forskarna arbetade med interaktiva system för bevis och relaterade problem. Dessa system jobbar utefter att en bevisande part kommunicerar med en bekräftande part för att övertyga bekräftaren att ett matematiskt påstående stämmer. 1985 publicerade vetenskapsmännen artikeln ”The knowledge complexity of interactive proof-systems”, och därmed uppkom nollkunskapsbevis som forskningsfält.

Tidigare hade mest forskning och arbete inom området haft en annorlunda utgångspunkt kring problemen; hur kan man lura bekräftaren att tro ett falskt påstående. Goldwasser, Micali och Rackoff vände på påståendet, och valde istället att undersöka vad som krävs för att man ska kunna lita på bevisaren.

Definition

För att ett bevis ska definieras som ett nollkunskapsbevis krävs det att det både är fullständigt, sunt och nollkunskapligt.

För att vara fullständigt bör den verifierande parten, till slut, övertygas om att beviset är sant, givet att bevisaren är ärlig. En oärlig bevisare skulle innebära att bevisaren presenterar falsk information eller ljuger i beviset.

Eftersom bevisaren inte visar den hemliga informationen kan den som verifierar aldrig vara helt säker på att bevisaren har den. Därför bör beviset vara sunt. Ett sunt bevis innebär att risken att bevisaren inte har den hemliga informationen är så liten att den är försumbar. Denna risk finns alltid på grund av hur ett nollkunskapsbevis fungerar, men minimeras genom att göra flera iterationer av kontroller som stärker bevisarens påstående. Med det i grunden, måste påståendet vara sant för att en bevisare ska kunna bevisa påståendet för verifierande parten, då ett falskt påstående aldrig kan klara alla möjliga kontroller.

Nollkunskapligheten betyder att en ärlig verifierande part inte lär sig något utöver att den ärliga bevisaren har hemliga informationen. Efter kontroller bör påståendet som bevisaren uttrycker alltid vara tillräcklig för att verifieraren ska kunna föreställa sig att bevisaren måste ha den hemliga informationen.

Fullständighets- och vettighetskraven är grundkraven för interaktiva bevis, som Goldwasser, Micali och Rackoff tidigare forskade på, och nollkunskapsbeviset är ett sorts interaktivt bevis.

Exempel

Ett klassiskt exempel på ett nollkunskapsbevis är följande situation:

Peggy har två biljardbollar som är identiska, förutom att en är röd och en grön. Hennes vän Victor är skeptisk att de faktiskt är olika, då han är färgblind och båda bollarna ser helt likadana ut för honom. Peggy vill visa för sin vän att de två bollarna har helt olika färger, dock vill hon inte att han ska veta om vilken som är röd och vilken som är grön.

Victor får sedan gröna bollen i ena handen, och den röda i den andra. Han lägger händerna bakom ryggen och väljer att antingen byta bollarna mellan händerna eller ha kvar dem som de låg. Sedan tar han fram händerna igen och Peggy får "gissa" om han bytte bollarna eller inte. Eftersom bollarna har olika färg så kan Peggy veta med 100% säkerhet om han bytte eller inte, men om bollarna var identiska skulle det ge Peggy en 50% chans att gissa rätt.

Då bollarna i detta läge faktiskt är olika färger vet Peggy med säkerhet om han bytt bollarna eller inte. Sedan upprepar de två vännerna denna kontroll, tills chansen för Peggy att kunna gissat rätt på alla kontroller blir så pass liten att Victor är övertygad om att de faktiskt är olika färger. Hade de sett likadana ut hade Peggy, vid något tillfälle, till slut svarat fel medan om hon visste det skulle hon aldrig gjort det.

Dessutom har Victor heller ingen möjlighet att på egen hand avgöra vilken färg varje biljardboll har, vilket gör beviset nollkunskapligt.

Tillämpningar

Inom kryptologi jobbas det bl.a. med identitetsbekräftelse, och då ska identiteter bevisas med hjälp av en viss hemlig identitetsinformation, utan att avslöja det för verifierande parten. Nollkunskapsteori används flitigt för att se till att ett bekräftelsesystem inte får del av informationen.

Ett exempel på ett vanligt bekräftelsesystem är lösenord på internet. Med hjälp av ett hemligt lösenord vill den bevisande parten bevisa sin identitet, utan att det bekräftande systemet får veta det hemliga lösenordet. Dock finns det ett problem med lösenord; eftersom de ofta är korta och begränsade fungerar inte många nollkunskapskontroller. Därför används en särskild sorts nollkunskapsbevis, nollkunskapliga lösenordbevis, som betraktar lösenords begränsningar.

Inom kryptografiska protokoll används nollkunskapsbevis för att både skydda användarens identitet samtidigt som det belönar ärlighet. Genom att använda sig av ett nollkunskapsbevis behöver användaren bete sig på ett särskilt sätt enligt protokollet. Detta sker naturligt med ett nollkunskapsbevis, då användaren behöver vara ärlig för att uppfylla fullständighetskravet och hemliga informationen, enligt nollkunskapskravet, inte sprids utanför användarens kunskap.

Se även

• Kategori:Kryptologi
• Kategori:Kryptografi
• Zero-knowledge proof (engelska wikipedia)
• E-legitimation