Chaum-Pedersen Protocol

Table of contents

What it is

The Chaum-Pedersen Protocol allows one to prove the equality of a secret value $x$ given a set of two equations that hide the value $x$ but can be publicly shared.

It’s an interactive Zero-Knowledge Proof protocol where a prover wants to convince a verifier that the aforementioned condition of equality holds true.

How it works

In this example let’s assume that Alice, the prover wants to convince Bob, the verifier. We’ll be using an Elliptic Curve $E$ of order $q$. All calculations are done $\bmod\ q$ if not stated otherwise.

There are two points on this curve, $G$ and $H$, what will be used throughout the protocol.

The first thing Alice does is to sample a random value $x$.

Next up she computes the two values $U$ and $V$ via $x$ and the curve points $G$ and $H$: $U = xG$ and $V = xH$. Those two values are shared with Bob.

Once done Alice samples a random value $r$ called a “nonce”:

It’s important that this value is random and never reused. She then multiplies $r$ by the two curve points $G$ and $H$ to get the values $P$ and $Q$:

Note that these two operations are “the same” as the computation done to derive $U$ and $V$.

The values $P$ and $Q$ are now shared with Bob.

Bob samples a random value $c$ called the “commitment” and sends it to Alice. This value should be random and not guessable by Alice.

Alice computes $e = r + cx$ and sends $e$ to Bob.

Bob can now calculate the following equations to see if the same secret value $x$ was used by Alice:

Why it works

Given that Alice samples the value $r$ randomly and adds it to the challenge multiplied by the secret value $x$, there’s no leakage of information regarding $x$ to Bob, because Bob can’t distinguish the value of $e$ from randomness.

Therefore the nonce $r$ masks the value $x$.

Similarity to the Schnorr Identification Protocol

The Chaum-Pedersen Protocol is similar in function to the Schnorr Identification Protocol. The main difference between the two protocols being that in Chaum-Pedersen we not only want to convince the verifier that we know the secret value $x$ (as it’s the case in the Schnorr Identification Protocol). We also want to prove that the discrete logarithm between the two values is the same:

References

The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.

• Nguyen Thoi Minh Quan - Intuitive Advanced Cryptography