# Chaum-Pedersen protocol adapted to elliptic curves

Is it possible to adapt the Chaum-Pedersen protocol for using elliptic curves by simply replacing the exponentiation with scalar products?

For example, if g is a point in the curve, then g^k is the scalar multiplication k*g as defined for elliptic curves. Would that still work?

I took the diagram from here.

Update: In the verification process, there is this: g^s * y1^c, which would be like a product of points; as far as I know, point multiplication is not typically defined for elliptic curves. What is the equivalent operation there?

• Yes it would. Similarly for any cyclic group in which the discrete logarithm is hard. Commented Mar 29, 2023 at 20:33
• You'd need to choose the generator point $g$ carefully so that it has order $q$. Unlike what you'd do in this protocol for the multiplicative group, with elliptic curves you might as well have $q$ as close as possible to the number of points--you wouldn't choose $q$ to be quite a bit smaller than $p$. Also, you might to take care with invalid curve point attacks and subgroup confinement attacks. Commented Mar 29, 2023 at 23:39
• Thank you, I miss that in the verification process; there is this: g^s * y1^c. This would be like a product of points; as far as I know, point multiplication is not defined. What is the equivalent operation there? Commented Mar 30, 2023 at 6:04
• In additive notation, exponentiation becomes multiplication, and multiplication becomes addition. So it would be $s*G+c*Y_1$. The two operations are scalar multiplication (a point added to itself many times), and point addition. Commented Mar 30, 2023 at 6:15
• Thanks for that; it is crystal clear and makes full sense! Commented Mar 30, 2023 at 6:22

$$Y_1=xG$$ and $$Y_2=xH$$, where $$G$$ and $$H$$ are generator points on the curve and $$x$$ is a scalar.
We intend to prove discrete-log equivalence, along with knowledge of $$x$$.
We pick a uniformly random scalar $$k$$, and calculate the challenge $$c=H(kG\mathbin\| kH)$$, where $$H()$$ means to hash the input to a scalar value, and $$\mathbin\|$$ means concatenation.
The proof is $$(c,s)$$, where $$s=k-cx$$. This operation should be modulo the order of the group.
Verification: check $$c\overset{?}{=} H(sG + cY_1\mathbin\| sH+cY_2)$$