1
$\begingroup$

From this answer I understood how to prove key equivalence across two elliptic curves. Now, I'm trying to figure out some more practical aspects of implementing this. Before jumping into questions, here is the setup:

  • The two elliptic curves are $g_1$ and $g_2$ of orders $q_1$ and $q_2$ such that $q_1 < q_2$. The generator points are $G_1$ and $G_2$.
  • I have a secret value $a$ which is a 256-bit integer (it would probably need to be smaller than $q_1$).
  • I calculate points $A_1 = a ⋅ G_1$ and $A_2 = a ⋅ G_2$

I would like to prove to someone that $A_1$ and $A_2$ map to the same number without revealing the value of $a$. To do this, I can:

  1. Chose a random integer $r$ and calculate $T_1 = r ⋅ G_1$, $T_2 = r ⋅ G_2$, $u = H(G_1, G_2, A_1, A_2, T_1, T_2)$, and $v = r + a ⋅ u$, where $H$ is a hash function
  2. Share the proof as $(A_1, A_2, T_1, T_2, v)$

The verifier can check the proof by computing $u$ and checking that $v ⋅ G_1 = T_1 + u ⋅ A_1$ and $v ⋅ G_2 = T_2 + u ⋅ A_2$.


My questions are:

  1. How would I go about selecting the two elliptic curves? For example, one choice could be Curve25519 and Curve1174, but that would restrict the value of $a$ to approximately 248 bits. Another choice could be secp256k1 and secp256r1 and that should allow values of $a$ to be 255 bits (and it seems like the orders of these curves are also much closer together). Are there any other considerations?
  2. How would I go about choosing the hash function $H$? For example, if the curves are secp256k1 and secp256r1, could I use Blake2b with 255-bit output to generate the value of $u$? Could I make the output smaller (e.g. 200 bits) and if so, what would be the downside of that?
  3. If the curve orders are really close to each other (like they are for secp256k1 and secp256r1), could I restrict $r$ to 255-bit values? Or should I keep it at 512 bits? It seems to me that to hide $a$ effectively $r$ needs to be much bigger than $u$.
$\endgroup$
  • $\begingroup$ For (3), do you mean to ask how to prove to the verifier that $\alpha < q_1, q_2$? After all, for any pair of points $A_1, A_2$, there will always be an $\alpha < q_1q_2$ s.t. $A_1 = \alpha G_1$ and $A_2 = \alpha G_2$ (and if you know the discrete log of $A_1, A_2$, it's easy to compute) $\endgroup$ – poncho Jul 6 '18 at 20:29
  • $\begingroup$ I moved the last question out into a separate question here. $\endgroup$ – irakliy Jul 10 '18 at 4:58

Your Answer

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

Browse other questions tagged or ask your own question.