# Properties of the bilinear pairing groups?

I stumbled across this correctness of a scheme:

$$e(g^r, H(id)^x) = e(g^x, H(id))^r = e(g^x, H(id))^r$$

and have a hard time following the properties of the bilinear pairing. Does anyone know the "rules" for such pairings or where to read about them?

As far as I have learned I know that:

$$e(g^{xy}, g) = e(g,g)^{xy} = e(g^x, g^y)$$

but do these properties commute, and how is the correctness scheme above correct?

• The second and third terms in the equality of the correctness proof you quote are identical - I suspect you might have a typo there. Apr 21, 2022 at 12:22

In pairing-based cryptography, bilinear pairings are usually defined as follows:

Let $$G_1, G_2, G$$ be finite cyclic groups of the same order. A bilinear pairing is then a map $$e : G_1 \times G_2 \rightarrow G$$ which is bilinear, that is: $$e(p^a, q^b) = e(p, q)^{ab}$$

It is often also implied or required that:

• $$e$$ is not the trivial pairing which maps all inputs to the neutral element of $$G$$
• We have a way to compute $$e$$ 'efficiently'
• if $$g_1$$ is a generator of $$G_1$$, and $$g_2$$ of $$G_2$$, then $$e(g_1, g_2)$$ is a generator of $$G$$
• In some contexts $$G_1 = G_2$$ is used, that is $$e$$ will be of the form $$e : G_1 \times G_1 \Rightarrow G$$.

Thus, informally, a bilinear pairing allows to "pull out" the exponents (assuming multiplicative notation) of its inputs.

The correctness proof you quote is straight-forward, then: \begin{align} e(g^r,H(id)^x) & = e(g, H(id))^{rx} & \text{ bilinearity} \\ & = e(g, H(id))^{xr} & \text{ commutativity} \\ & = e(g^x, H(id)^r) & \text{ bilinearity} \end{align}

You can find a decent (I find) introduction into pairing-based cryptography in these lecture slides by John Bethencourt.

• Saying $G_1 = G_2$ might be confusing to some people starting out. In most implementations, they are treated as different groups. Apr 21, 2022 at 13:19
• @AmanGrewal Ah that's interesting. Most my exposure has been via a few papers in the threshold setting from a few years ago, which had usually used $G_1 = G_2$. I have slightly reworded the above, to be less absolute about this. Apr 21, 2022 at 18:55
• From my experience, you use pairings where $G_1, G_2 \subset G$. The pairing might be well-defined on all of $G \times G$, but libraries only implement the useful parts (for speed or ease of hashing into the curve). Apr 21, 2022 at 21:23
• Thank you @Morrolan !!
– Rory
Apr 25, 2022 at 13:57