Key equivalence across different elliptic curves 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$?
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'}$.


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)$.
The verifier computes $u$ and verifies $v\cdot G=t + u\cdot X_1$ and $v\cdot H = s+ u\cdot X_2$.