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?


1 Answer 1


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).

  • $\begingroup$ I thought DL is the strongest assumption. XDH assumes DDH is hard in G1 for asymmetric pairings $\endgroup$
    – curious
    Nov 26, 2015 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, 2015 at 8:43
  • 1
    $\begingroup$ DL is the weakest assumption, as it assumes the least about the world. $\endgroup$
    – klewi
    Nov 27, 2015 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, 2015 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.