3
$\begingroup$

Is it possible to prove key-equivalence across elliptic curves of different order? Specifically:

  • Suppose I have a key $x$ valid for both curves listed below
  • On curve $g$ (for example, Curve25519) it maps to $X_1 = x*G$, where $G$ is the generator point for $g$
  • On curve $h$ (for example, Curve1174) it maps to $X_2 = x*H$, where $H$ is the generator point for $h$

Is it possible for me to submit some public proof that $X_1$ and $X_2$ are generated using the same key $x$, but without revealing the value of $x$?

Improve this question
$\endgroup$
5
  • $\begingroup$ This equality would be ill-defined in case of two different known orders of groups involved. $\endgroup$
    – Vadym Fedyukovych
    Commented Jul 8, 2018 at 10:08
  • $\begingroup$ What does ill-defined mean in this context? $\endgroup$
    – irakliy
    Commented Jul 8, 2018 at 17:27
  • $\begingroup$ A "smaller" ring element can be considered "equivalent" to more than one element of the "larger" ring, defined by the larger modulus. It is reasonable to ask for "equality of logarithms" in groups of the same order, or in the case of a group of a hidden order. $\endgroup$
    – Vadym Fedyukovych
    Commented Jul 9, 2018 at 16:28
  • $\begingroup$ Thank you - this makes sense. If I can force the value $x$ to be always smaller than the modulus of the "smaller" ring - this shouldn't be an issue, right? I'm thinking this could be done with the methodology provided in the answer if I require that $\frac{v}{u} < q$ (this would imply that $x < q$). $\endgroup$
    – irakliy
    Commented Jul 9, 2018 at 16:51
  • $\begingroup$ I've actually created a separate question for this here. $\endgroup$
    – irakliy
    Commented Jul 9, 2018 at 17:41

1 Answer 1

Reset to default
4
$\begingroup$

Yes you can. It is a proof of equality of discrete logarithms. Let's say the order of curve $g$ is $q$ and $h$ is $q'$, the tricky part is how to sample one challenge value that is uniform in both groups $Z_q$ and $Z_{q'}$. You cannot do it in either of the group because the value is not uniformly distributed in the other group. The trick is to sample the value uniformly random from $Z_{q\cdot q'}$, which would solve this problem.

The NIZK version of the proof thus requires a hash function $H:\{0,1\}^*\rightarrow Z_{q\cdot q'}$.

  1. The prover chooses $r\in_R Z_{q\cdot q'}$, computes the following: $t=r\cdot G$, $s = r\cdot H$, $u = H(G, H, X_1, X_2, t,s)$, $v=r+x\cdot u$. The proof is $(t,s,v)$.
  2. The verifier computes $u$ and verifies $v\cdot G=t + u\cdot X_1$ and $v\cdot H = s+ u\cdot X_2$.
Improve this answer
$\endgroup$
3
  • $\begingroup$ No, $t+u\cdot X_1$ is $t+(u\cdot X_1)$. Note that $u$ is an integer and $t$ is a point, so the two cannot be added together. Hash function needs to be a good cryptographic one and matches the size of the domain $Z_{q\cdot q'}$. $\endgroup$
    – Changyu Dong
    Commented Jun 19, 2018 at 17:34
  • $\begingroup$ I have asked a follow-up question here. I'm especially curious if when $q$ and $q'$ are very close to each other we can have $r$ and $u$ be smaller than $q$. $\endgroup$
    – irakliy
    Commented Jul 7, 2018 at 5:02
  • $\begingroup$ Why requiring challenge to be uniform? $\endgroup$
    – Vadym Fedyukovych
    Commented Jul 8, 2018 at 9:09

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.