23-11-2012, 01:04 PM
How to Explain Zero-Knowledge Protocols to Your Children
Explain Zero-Knowledge.ppt (Size: 109.5 KB / Downloads: 45)
Background
1. The Fact:
Identifications and passwords are essential parts in a secured system in which they prevent unauthorized access to private materials.
The Problem:
Passwords are assigned to authorized personnel and are meant to be kept secret. But ironically, one often have to give out his/her password during authentication. That’s not very safe!
The Solution: Zero-Knowledge Protocol!
Introduction
Zero-Knowledge Protocols allow one party to access a secured area without having that party to give out any private or secret information.
Examples of Zero-Knowledge Protocols: a. Bizcard b. Fiat-Shamir Protocol c. Guillou-Quisquater’s Analogy
The Actors
1. The Prover (Bob): Bob has to prove that he knows some kind of secret (such as a password to a restricted area) but he doesn’t want to share it with anyone, not even the Verifier.
2. The Verifier (Alice): Alice has to verify whether Bob knows the secret or not. She can perform a series of experiment with Bob until she is ~100% certain whether Bob is authorized (or not).
3. The Malice (Oscar): Simply put, the bad guy who tries to cheat the security system.
The Fiat-Shamir Protocol
Fact: It is easier to compute x2 than x1/2.
Chosen is an arithmetic modulo n = pq, where p and q are primes.
Bob (the Prover) will choose a number s in Zn. He will keep s (private key) a secret but publish v = s2 mod n (public key).
During authentication, Bob will randomly choose a number r in Zn and sends x = r2 mod n to Alice (the Verifier).
After receiving x, Alice will randomly choose a number e, where e is in {0,1}, and send it to Bob.
After receiving e, Bob will send y = rse to Alice.
Alice will now need to check whether y2 mod n = xve mod n. If yes, Bob has passed the test. Alice might request Bob to perform the experiment as many times as she desires until she’s certain of Bob’s authority. Throughout the entire process, Alice will only need to work with the publicly known number x, e, & v and will learn nothing about the secret s.