A bilinear map has to satisfy this property:

$e(aP,bQ) = e(P,Q)^{ab}$ for all $P,Q \in \mathbb{G} , a,b \in \mathbb{Z}_q$

so far so good.

My question now is related to this paper: https://eprint.iacr.org/2006/080.pdf

Under "4.1 Correctness" they do the following changes (I replaced some complex constructs with c, d and simplified it a little bit):

(1) $e(g_2^a \cdot c^d,g)=e(g_2,g)^a \cdot e(c,g)^d$

(2) $e(g_2,g)^a \cdot e(c,g)^d=e(g_2,g^a) \cdot e(c,g^d)$

And there is another change I saw somewhere else:

(3) $e(g_1, g_2) = e(g_2, g_1)$

So, for me it looks like I can pull down the exponent of a bilinear map $e$ to one of the arguments of $e$ (2). And that I can split one bilinear map $e$ into two bilinear maps in the way described in (1). Is this true in all scenarios? I assume this is not the case. I assume this is only possible in $\mathbb{Z}_q$. Or maybe only with generators? ... I am only guessing.

So these are my questions:

  • Under which conditions are (1), (2) and (3) valid changes?
  • Why are (1), (2) and (3) valid changes? I assume this is related to the bilinearity property mentioned above.

Regards, hyperion


(1), (2), and (3) are always valid changes as long as $\mathbb{G}$ is a cyclic group.

Note that you switched from additive notations at the beginning of your post to multiplicative notations later; I'll stick to multiplicative notations in my answer. Now, let me show that a bilinear map satisfying $e(g^a,h^b) = e(g,h)^{ab}$ for all $(g,h)\in\mathbb{G}$ and $(a,b)\in\mathbb{Z}_q$ will necessarily satisfy (1), (2), and (3). Let me denote (0) the first equation (that defines a bilinear map).

Everything follows relatively easily from the following observation: as $\mathbb{G}$ is a cyclic group, every element of $\mathbb{G}$ (except $1_{\mathbb{G}}$) is a generator: given $(g,h)\in\mathbb{G}$, you can always find $x\in\mathbb{Z}_q$ such that $h = g^x$. Therefore:

(1) Let me denote $(x_2,x_c)\in\mathbb{Z}_q^2$ two exponents such that $g_2=g^{x_2}$ and $c = g^{x_c}$. We get:

$e(g_2^a\cdot c^d,g) = e(g^{ax_2+x_cd},g)$ by writing $(g_2,c)$ "in base $g$"

$= e(g,g)^{ax_2+x_cd}$ by (0)

$= e(g,g)^{ax_2}\cdot e(g,g)^{x_cd}$

$= e(g^{ax_2},g)\cdot e(g,g^{x_cd})$ by applying (0) to the left and right terms

$= e(g_2^a,g)\cdot e(g,c^d)$

(2) The equality $e(g_2,g)^a \cdot e(c,g)^d=e(g_2,g^a) \cdot e(c,g^d)$ directly follows by applying (0) to the left and right terms, e.g. $e(g_2,g^a) = e(g_2^1,g^a) = e(g_2,g)^{a\cdot 1} = e(g_2,g)^a$.

(3) By now you should probably be able to deal with this one yourself: fix any base $g$, let $g_1 = g^{x_1}$ for some $x_1$ and $g_2 = g^{x_2}$ for some $x_2$. Then $e(g_1,g_2) = e(g^{x_1},g^{x_2}) = e(g,g)^{x_1x_2} = e(g,g)^{x_2x_1} = e(g^{x_2},g^{x_1}) = e(g_2,g_1)$, simply by applying (0) twice.

  • $\begingroup$ Hi, "Let me denote $(x_2,x_c) \in Z_q^2$" - is the 2 by intention? $\endgroup$ – hyperion Apr 21 '18 at 15:45
  • $\begingroup$ Yes, to make it more clear that those are exponents in base $g $ for $(g_2,g_c)$. $\endgroup$ – Geoffroy Couteau Apr 21 '18 at 15:53

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.