Skip to content

Chaum-Pedersen Protocol

Table of contents

Open Table of contents

What it is

The Chaum-Pedersen Protocol allows one to prove the equality of a secret value xx given a set of two equations that hide the value xx 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. Furthermore we’ll be using an Elliptic Curve we call EE of order qq.

There are two points on this curve, GG and HH, what will be used throughout the protocol.

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

Next up she computes the two values UU and VV via xx and the curve points GG and HH: U=xGU = xG and V=xHV = xH. Those two values are shared with Bob.

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

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

It’s important that this value is random and never reused. She then multiplies rr by the two curve points GG and HH to get the values PP and QQ:

P=rGP = rG Q=rHQ = rH

Note that these two operations are “the same” as the computation done to derive UU and VV.

The values PP and QQ are now shared with Bob.

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

Alice computes e=r+cxmodqe = r + cx \mod q and sends ee to Bob.

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

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

Chaum-Pedersen Protocol

Why it works

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

Therefore the nonce rr masks the value xx.

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 xx (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:

logG(U)=logH(V)\log_G(U) = \log_H(V)

Additional Resources