Assume we have an elliptic curve $E$ with a Tate (or Ate,...) pairing $G_1 \times G_2 \mapsto G_T$
Now the task is to find $g_1, g_1' \in G_1$ and $g_2, g_2' \in G_2$
such that the discrete logarithm $x$ is equal, i.e.
$g_1' = g_1^x$ and $g_2' = g_2^x$

That is easy, but now comes the hard part:
This has to be done without knowing $x$. Moreover, the constructor of the points has to provide a proof that he does not know $x$.

With just $g_1' = g_1^x$ alone, that would also be easy by hashing into the group $G_1$.

  • $\begingroup$ In case of $G_1 = G_2$ and fixed $g_1, g_2$, this looks like computational Diffie-Hellman problem. Proving no-knowledge could be the hard part. Any example considered acceptable? $\endgroup$ – Vadym Fedyukovych Oct 8 '15 at 20:14
  • $\begingroup$ Thank you for the tip. You are probably on the right track that this problem can be reduced to some kind of CDH problem. $\endgroup$ – user27950 Oct 8 '15 at 20:33
  • $\begingroup$ I assume a multiparty computation (where no one side knows the discrete log) is out of the question? $\endgroup$ – poncho Oct 9 '15 at 3:51
  • $\begingroup$ @poncho: yes, but in the post-Snowden age it's difficult to trust anyone, even groups could be infiltrated ... $\endgroup$ – user27950 Oct 9 '15 at 5:40
  • $\begingroup$ Well, if you can't think of anything else, there is a multiparty protocol where we pass values to each party member in succession; each party gets an intermediate set $g´_1, g´_2$ (along with a public $g_1, g_2$), and outputs $g'^r_1, g'^r_2$ (along with a ZKP that he knows the value $r$); that output would be forwarded to the next party. The final result has an exponent that depends on everone's $r$ $\endgroup$ – poncho Oct 9 '15 at 15:35

Your Answer

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