User identification problem
- original Register on verifier’s system. Then we have a secret, i.e. password, which is known by each other. Submit password and check in database. If submit in plaintext, of course doesn’t make sense. Maybe we can entrypt it. But it’s still not a good idea.
-
improvement Actually, what a prover do in identification problem is try to convince verifier that prover have information of identical secret. In original idea, we just give some pieces of information of secret directly. A better method could be we don’t leak information of secret, but try to convince the proposal “prover know secret” is true.
An example is a user generate a public key and secret key. Like what we do in github, we submit public key to verifier. And verifier choose a random message, encrypt with public key and give ciphertext to prover. If prover own the private key, he can get the right message.
-
zero-knowledge Although prover don’t leak information about his secret, he leak something else, the message verifier choose. If there is honest verifier, everything is fine. But if there is a attacker, he try to fake your identification and send the ciphertext from real verifier to you. There is a problem.
Thus we must make sure another must know the plaintext before someone decide to reveal message.
Then a zero-knowledge version comes out.
- V choose a random bit, use public key to encrypt, give it to P.
- P decrypt with private key, and sends a commitment to the plaintext Commitment(m’;r) to V;
- V send m to P
- P check whether m=m’; If true, open commitment; Otherwise, stop protocol.
- V check whether accept or reject.
A principle of zero-knowledge is have the prover demonstrate something V already knows and make sure V does indeed knows in advance.
zero-knowledge
Give a definition. We just care about that the prover’s claim is true. If it’s false, prover just tell nonsense to verifier. Of course, there is no knowledge.
Thus zero-knowledge intuitively is everything V saw during the protocol can be simulate by X efficiently. X is the face that the prover’s claim is true.
Formmal definition is for any PPT V, there is PPT simulator Sv on input x, such that Sv* and (P, V) is comput indis, where on input x and $\delta$ only for V.
Note that Sv* can rewrite the conversion, but (P, V) must generate conversion with correct time ordering and one by one. That means sometimes, if it’s neccessary we can rewind Sv.