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:
- 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
- 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:
- How would I go about selecting the two elliptic curves? For example, one choice could be
Curve1174, but that would restrict the value of $a$ to approximately 248 bits. Another choice could be
secp256r1and 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?
- How would I go about choosing the hash function $H$? For example, if the curves are
secp256r1, could I use
Blake2bwith 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?
- If the curve orders are really close to each other (like they are for
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$.