2
$\begingroup$

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

zk protocol

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?

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ Yes it would. Similarly for any cyclic group in which the discrete logarithm is hard. $\endgroup$
    – Daniel S
    Commented Mar 29, 2023 at 20:33
  • 3
    $\begingroup$ 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. $\endgroup$
    – Myria
    Commented Mar 29, 2023 at 23:39
  • $\begingroup$ 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? $\endgroup$
    – gagiuntoli
    Commented Mar 30, 2023 at 6:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – knaccc
    Commented Mar 30, 2023 at 6:15
  • $\begingroup$ Thanks for that; it is crystal clear and makes full sense! $\endgroup$
    – gagiuntoli
    Commented Mar 30, 2023 at 6:22

1 Answer 1

Reset to default
0
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.