# Chaum-Pedersen Protocol

## 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”:

$r \overset{{\scriptscriptstyle\}}{\leftarrow} \mathbb{Z}_q$

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$:

$P = rG$ $Q = rH$

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:

\begin{aligned} eG &\overset{?}{=} R + cX \\ (r + cx)G &= rG + cxG \\ G(r + cx) &= G(r + cx) \end{aligned} \begin{aligned} eH &\overset{?}{=} Q + cV \\ (r + cx)H &= rH + cxH \\ H(r + cx) &= H(r + cx) \end{aligned}

## 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:

$\log_G(U) = \log_H(V)$

## 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.