Today: Zero-knowledge proofs, Monday, April 13th


Zero-knowledge proof

Brilliant explanation for 3 year olds: How to Explain Zero-Knowledge Protocols to Your Children

We have a prover (Peggy) and a verifier (Victor) and some common input x which is the statement to be proved.

It's going to be an interactive proof, where Peggy and Victor are exchanging messages over multiple rounds. At the end, the Victor can accept the proof or reject it.

P   ---------------->   V



                        (P,V)(x) = True/False

The prover may be powerful (large computation power, or more commonly he knows something about why the statement x is true and he can use that).

Basic properties

"Quality control"


c = commit(v, r)
open(c) -> (v, r)

We wanted two properties out of a commitment scheme

Sudoku example

|   |   |   |
|   |   |   |
|   |   |   |

How can I convince you I know a solution to a Sudoku puzzle, without telling you anything about the solution?

Suppose we make up codes for the numbers, s.t. each number is a letter

1 2 3 4 5 6 7 8 9 

But this is a one to one mapping, so if we just translated our solution to this the verifier can just extract the solution and learn it.

If we use non-deterministic commitments for each letter, then we can hide the solution.

A challenge can be "open a commitment to a row/column/block". Note that now the verifier will learn some mappings. So now the verifier will want to ask again, which means you'd better remap so that he does not start learning the actual numbers.

The prover can't cheat because he commits himself to a certain "ciphertext" of the Sudoku so he has to make sure that his commitment is an actual solution, because the verifier could query it anywhere (block, row, column) and since the prover is committed he won't be able "change" or "tune" his answer.


Note: Verifier needs to make sure a unique set of 9 letters are used by the prover. Otherwise, the prover might use extra letters to cheat. If prover uses a set of 9*9 letters and carefully commits to the 9x9 table such that each row and column has unique letters, then, a clueless verifier would think the puzzle is solved no matter which (and how many) row or column he asked for.

Graph 3-colorability

Prover has a graph and knows a 3-coloring of the graph, where each vertex is assigned a color out of 3 colors s.t. no two adjacent vertices have the same color.

The prover's solution is the mapping from vertex to color.

Phase I:

If the prover does not know a coloring, then whatever I commit to has to be bad on some edge => verifier will discover it at some point

Note that the transcript of the zero-knowledge exchange looks random. It'll have a list of random vertices and random colors, so it seems no one should be able to learn anything from it.

Graph ismorphism

Hard to solve for two big graphs G and H.

The solution is a mapping from the vertex #s of the first graph to the vertex #s of the second graph: (1->c, 2->d, 4->a, 3->b)

As a prover, if I know the isomorphism, I can come up with a third graph J that is isomorphic to both of them (by just reordering the vertices randomly).

1 -> c -> u
2 -> d -> t
4 -> a -> r
3 -> b -> s

Verifier can now ask you to reveal the isomorphism from G to J or from H to J, but not both. Then the verifier actually checks the revealed isomorphism is correct: for every edge in G (or in H), he checks if that edge is also present in J (after remapping G nodes to J nodes according to the revealed isomorphism)

Note: It seems that verifier also has to make sure J has the same # of edges as G and H. Otherwise, the prover could provide a fully connected J whose edge checks always pass => any isomorphism the prover picks would pass.

ZK is complete.

ZK is sound.

Suppose G and H are not isomorphic, or the prover doesn't know the isomorphism (and doesn't have time to compute it). Can the prover trick the verifier? The prover can only commit to a single graph J (J is supposed to be isomorphic to both G and H) and also commit to the actual isomorphisms: the map mg from vertices(G) -> vertices(J) and the map mh from vertices(H) -> vertices(J).

If the prover does not know the isomorphism between G and H, the best he can do is come up with a J that is isomorphic to one of them. (Note that he cannot hope to come up with J isomorphic to both G and H because then he would have solved the isomorphism problem too fast). Then the prover commits to this J and to the mh and mg vertex maps, and hopes that the verifier picks the right map. Say prover chose H, then the prover hopes that the verifier will check J against H by asking for the mh vertex map. However, this cannot go on for too long. As tests are repeated k times, probability of the prover tricking the verifier is 1/2^k. If the verifier asks to check J against G, then the prover has to reveal mg, and the edge check between G and J via mg will fail.

Hamiltonian cycle

Prover and verifier have a graph G and prover knows a hamiltonian cycle in it.

Discrete log

Schnorr protocol for showing knowledge of the discrete log of y = g^x.

Schnorr protocol:

    P                                   V

k <--R-- Z_q
a = g^k                 a
            <------------------------ c <--R-- Z_q
r = cx + k              r
            ------------------------> checks if
                                        y^c * a = g^r <=>
                                        (g^x)^c * g^k = g^(cx + k) <=>
                                        g^(cx+k) = g^(cx+k) <=>
                                        x = x

If I don't know x what are your chances of catching me?


If can play the game, I know x:

Attack: If the prover uses the same k twice, then the verifier can extract x.

a = g^k

r = cx + k
r' = c'x + k
x = (r-r')/(c-c')

Theorem: Protocol is zero-knowledge.

Proof: After a round is over, verifier has a, c, r and they are all random elements of G_q. Prover hasn't given verifier any info because the verifier could compute a given c and r.