2
$\begingroup$

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?

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

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Saying $G_1 = G_2$ might be confusing to some people starting out. In most implementations, they are treated as different groups. $\endgroup$ Apr 21, 2022 at 13:19
  • $\begingroup$ @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. $\endgroup$
    – Morrolan
    Apr 21, 2022 at 18:55
  • 1
    $\begingroup$ 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). $\endgroup$ Apr 21, 2022 at 21:23
  • $\begingroup$ Thank you @Morrolan !! $\endgroup$
    – Rory
    Apr 25, 2022 at 13:57

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.