Igor Perić

Zero Knowledge Proofs (ZKP) are a mechanism of computing a mathematically verifiable cryptographic proof of a true statement without actually revealing any amount of information about the statement other than it holds true.

For instance, bank could use ZKP of your credit score to give you the loan without asking for your bank statements, ID, employment history, etc. Another great example is Crypto Idol, a singing contest completely judged by a neural network. You can’t cheat by submitting a false result because the leaderboard system won’t accept the result without a valid proof, which you can’t generate unless you actually run a network on your input. Neat, right?

Chaum-Pedersen ZKP Protocol

This protocol is used to authenticate a user with a server by proving the possession of a secret X (the password) without revealing the X itself. This can be thought as a password.

These are the steps:

1. Both prover (the client) and the verifier (the server) agree on four large prime integers G, H, P and Q
2. The client generates Y1 = G ^ X and Y2 = H ^ X and sends them to the server
3. The client generates a random number K and R2 = G ^ K and R2 = H ^ K and sends only R1 and R2 to the server (K stays private!)
4. The server generates a random number C as a challenge and sends it to the client
5. Client generates solution to the challenge as S = K – C * X and sends S to the server
6. Server verifies that R1 =G ^ S – Y1 ^ C and R2 = H ^ S – Y2 ^ C – if yes server knows the client indeed knows the password X.

Here is a diagram illustrating steps above:

A very important detail is left out until now for the sake of simplicity of the explanation: Y1, Y2, R1, R2 are computed modulo P and S is computed modulo Q. The strength of the protocol lies in the inability to compute the discrete logarithm in reasonable time. When given Y1 = G ^ X mod P it is impossible to confidently compute X given Y1, G and P due to the circular nature of modular arithmetics.

Apart from this, it is very important to note that random numbers K and C must be

1. regenerated on each interaction and
2. the generator must have uniform distribution

Let’s see what happens if any of these two cases are not fulfilled. Imagine the client decides to reuse K for two successive authentication steps, and the server generates two different challenges C1 and C2 and receives two correct solutions S1 = K – C1 * X and S2 = K – C2 * X. By subtracting these two equations the server could easily obtain clients password X like this: S2 – S1 = (K – C1 * X) – (K – C2 * X) => S2 – S1 = K – C1 * X – K + C2 * X => S1 – S2 = (C2 – C1) * X => (S2 – S1) / (C2 – C1) = X

If we assume the generator doesn’t have a uniform distribution but, for instance, draws a group of 1000 numbers more likely than others, the server could send many queries to determine those 1000 most frequent solutions client is sending back, and then brute force each of the 1000 * 1000 pairs similarly to the previous attack.

Implementation in Rust can be found in my GitHub repo: https://github.com/igorperic17/zkp-chaum-pedersen