nollkunskapsbevis

(zero-knowledge proof) – sätt att bevisa för någon annan att ett påstående är sant utan att man avslöjar något mer. Man avslöjar inga fakta eller andra omständigheter som ingår i beviset. Grundprincipen är enkel: man bevisar till exempel att man hittar i en labyrint genom att ta sig till utgången på kort tid – man behöver inte berätta hur man gjorde. – Nollkunskapsbevis har praktisk betydelse när man till exempel ska visa att man har löst en viss uppgift som man ska få betalt för. Beställaren vill inte betala förrän hon vet att utföraren verkligen har löst uppgiften, men utföraren vill inte lämna ifrån sig lösningen förrän hon vet att hon får betalt. Genom att använda ett lämpligt noll­kun­skaps­bevis kan utföraren visa att hon har löst uppgiften utan att visa hur lösningen ser ut. (Detta är tillämpligt främst på matematiska och logiska uppgifter.) – Nollkunskapsbevis har också användning i hantering av lösenord. Helst vill man inte att lösenord ska sändas över nätet. Man kan då använda ett nollkunskapsbevis som visar för servern att användaren har rätt lösenord, men som inte innehåller själva lösenordet. Ett exempel är när man skickar ett kondensat (hash) av lösenordet. – Nollkunskapsbevis är ofta baserade på sannolikhet, inte på total säkerhet. För att öka säkerheten upprepar man beviset på ett slumpartat sätt (inte exakt likadant). Om ett bevis ger, till exempel, 90 procents säkerhet, och man upprepar det med lyckat resultat tio gånger, är risken för att beviset ändå är fel 1-10 (en på tio miljarder). – I teorin om nollkunskapsbevis talar man om två roller:

  • sändaren (the prover) – den som ska bevisa något. Sändaren kallas ofta för Peggy;
  • kontrollanten (the verifier) – den som ska godkänna eller underkänna beviset. Kontrollanten kallas ofta för Victor.

– Forskningsfältet nollkunskapsbevis uppstod 1985 då Shafi Goldwasser, Silvio Micali och Charles Rackoff publicerade artikeln ”The knowledge complexity of interactive proof-systems” (länk). Benämningen zero‑knowledge proof har med tiden ersatt deras benämning interactive proof.

[matematik och logik] [ändrad 13 februari 2018]

Dagens ord: 2018-02-14