2
$\begingroup$

Is there an assumption that says from a tag $k\cdot e(g,g_1)^{rx}$ ($k,r$ are secret) it is difficult to forge it with some x': $k\cdot e(g,g_1)^{rx'}$, as long as you cannot solve DL in $\mathbb{G}_1$ or $\mathbb{G}_2$?

It is obvious that the only way to forge is to extract the randomness $r$ such that you forge with $k\cdot e(g,g_1)^{rx}\cdot e(g,g_1)^{rx'}$ for a valid forged tag $k\cdot e(g,g_1)^{r(x+x')}$.

But it is not obvious how to build the reduction from Dl. Assuming $\mathcal{B}$ receives $g^a$ either in $\mathbb{G}_1$ or $\mathbb{G}_2$,then it gives to $\mathcal{A}$ tags $k\cdot e(g,g_1)^{ax}$.

At some point we assume $\mathcal{A}$ forges with $e(g,g_1)^{ax'}$. How this can help $\mathcal{B}$ to output $a$ at his DL challenge?

Improve this question
$\endgroup$
2
$\begingroup$

It's unlikely that you'll be able to prove unforgeability from Discrete Log alone. You might need a new assumption altogether on bilinear maps.

Also, in the bilinear world, assuming discrete log is usually not enough to prove security. You need stronger assumptions such as Bilinear Diffie-Hellman or XDH, or the bilinear generic group model (see Appendix A of BBG05).

Improve this answer
$\endgroup$
4
  • $\begingroup$ I thought DL is the strongest assumption. XDH assumes DDH is hard in G1 for asymmetric pairings $\endgroup$ – curious Nov 26 '15 at 8:38
  • $\begingroup$ You were right about the other type of forgery by exponentiation. What about now? Assiming k is secret $\endgroup$ – curious Nov 26 '15 at 8:43
  • 1
    $\begingroup$ DL is the weakest assumption, as it assumes the least about the world. $\endgroup$ – klewi Nov 27 '15 at 15:35
  • $\begingroup$ Ok, i said DL is the strongest in the sense that breaking DL you break CDH and then DDH $\endgroup$ – curious Nov 28 '15 at 17:32

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.