Score:1

Properties of the bilinear pairing groups?

mp flag

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?

Morrolan avatar
ng flag
The second and third terms in the equality of the correctness proof you quote are identical - I suspect you might have a typo there.
Score:3
ng flag

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.

Aman Grewal avatar
gb flag
Saying $G_1 = G_2$ might be confusing to some people starting out. In most implementations, they are treated as different groups.
Morrolan avatar
ng flag
@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.
Aman Grewal avatar
gb flag
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).
Rory avatar
mp flag
Thank you @Morrolan !!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.