Chaum-Pedersen protocol adapted to elliptic curves

gagiuntoli

3/29/24, 8:29 PM

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?

133

1 + 5

elliptic-curves

zero-knowledge-proofs

Daniel S

3/29/24, 8:33 PM

Yes it would. Similarly for any cyclic group in which the discrete logarithm is hard.

Myria

3/29/24, 11:39 PM

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.

gagiuntoli

3/30/24, 6:04 AM

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?

knaccc

3/30/24, 6:15 AM

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.

gagiuntoli

3/30/24, 6:22 AM

Thanks for that; it is crystal clear and makes full sense!

Score:0

Crypto

knaccc

3/30/24, 6:25 AM

After the Fiat–Shamir heuristic is applied, the non-interactive version would be:

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

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Chaum-Pedersen protocol adapted to elliptic curves

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.