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

$\endgroup$
  • $\begingroup$ This equality would be ill-defined in case of two different known orders of groups involved. $\endgroup$ – Vadym Fedyukovych Jul 8 '18 at 10:08
  • $\begingroup$ What does ill-defined mean in this context? $\endgroup$ – irakliy Jul 8 '18 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 Jul 9 '18 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 Jul 9 '18 at 16:51
  • $\begingroup$ I've actually created a separate question for this here. $\endgroup$ – irakliy Jul 9 '18 at 17:41
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$.
$\endgroup$
  • $\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 Jun 19 '18 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 Jul 7 '18 at 5:02
  • $\begingroup$ Why requiring challenge to be uniform? $\endgroup$ – Vadym Fedyukovych Jul 8 '18 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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