CNS - 44 - Bilinear Maps

Let \(G_1, G_2\) and \(G_t\) be cylic groups of the same order, and let us write the operation of such groups using the multiplicative syntax.

Def: A bilinear map from \(G_1 \times G_2\) to \(G_t\) is a function \(e: G_1 \times G_2 \to G_t\) such that \(\forall u \in G_1, v \in G_2, a,b \in \mathbb{Z}\)

\[e(u^a, v^b) = e(u, v)^{ab}\]

Bilinear maps are also called pairings because they associate pairs of elements from \(G_1\) and \(G_2\) with elements in \(G_t\).

Observation: When these maps are used in practice we typically have that \(G_1 = G_2\) is an EC group, and \(G_t = \mathbb{Z}_p^*\).

Let \(e: G_1 \to G_2\) be a bilinear map, and let \(g_1, g_2\) be generators of \(G_1\) and \(G_2\). Then,

Def: The map \(e\) is an admissible bilinear map if \(e(g_1, g_2)\) generates \(G_t\) and \(e\) is efficiently computable.

This definition allows us to restrict our attention to only non-trivial bilinear maps.

Weil pairing and Tate pairing are more or less the only known examples. They are both computed using Miller's algorithm. An implementation of such pairings can be found in the following software library (https://crypto.stanford.edu/pbc/).

The traditional Diffie-Hellman problem we have seen is also known as "Computational Diffie-Hellman", which asks, given a generator \(g\) and two values \(g^a\), \(g^b\), we want to know the value of \(g^{ab}\).

The decisional Diffie-Hellman instead goes like this: once again we have a generator \(g\), two values \(g^a\), \(g^b\), and a third value \(\alpha\), which can either be \(g^{ab}\), or \(g^{z}\), where \(z\) is a random value. The problem then consists in decising whether \(\alpha\) is \(g^{ab}\) or \(g^z\). Most often this is also an hard problem.

We already mentioned that elliptic curves usually have a size that is smaller than \(\mathbb{Z}_p^*\). This is true, but in 1993 Menezes and other guys studied ellitpic curves and discovered that, for some curves, when they were admitting pairing, they found out a way to destroy the discrete log problem.

In particular, suppose that I'm working on an EC group of \(256\) bit size. Then in that group we know that the problem of finding the value \(k\) given \(g\) and \(g^k\) (points on the curve) is hard. But now, if we have a bilinear map \(e\), we can go from the EC group to the traditional \(\mathbb{Z}_p^*\) group and get

\[\begin{split} e(g, g^k) &= e(g, g)^k = \hat{g}^k \\ e(g, g) &= \hat{g} \\ \end{split}\]

This result is formalized in the following theorem:

Theorem: If there exists a bilinear map \(e: G \times G \to G_t\), then the discrete log problem in \(G\) is no harder than the discrete log problem in \(G_t\).

In a typical 2-party DH key exchange no interaction is needed, since each party can simply get the public key from the other and use its own private key to get the final result. Consider now a three party DH key exchange, where we have party A with \((a, g^a)\), party B with \((b, g^b)\) and party C with \((c, g^c)\). How can we come out with a protocol that makes every party compute \(g^{abc}\)?

In 200 Joux demonstrated that in a group that admits pairing, 3-party DH is trivial and not interactive. Indeed, if we have a group that admits pairing we can cheat DH once to get

\[e(g^b, g^c) = e(g, g)^{bc} = \hat{g}^{bc}\]

we can only do it once since in the destination group pairing does not apply anymore. Thus, in particolar, to make this scheme work we can can obtain the final term to the \(a\) (which we own)

\[\big[e(g, g)^{bc}\big]^a = \hat{g}^{abc}\]

The identity based encryption (ADI) problem was posed by Shamir in 1984, and it was solved in 2001 by Dan Boneh and it asked the following question: can we come up with a crypto system in which the public key can both be selected and also act as the name of the person involved?