# Bilinear map assumpion

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

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

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