Asymmetric Cryptography

5Pairing-Based Cryptography

Olivier BLAZY

Ecole Polytechnique, Palaiseau, France

With the emergence of public-key cryptography, through the seminal paper from Diffie and Hellman (1976), an emphasis has been placed on studying the discrete logarithm problem. Assuming a cyclic group (, ·) of order p, this problem consists of, given elements g, h in the group, finding a scalar s in _p such that h = g^s. In carefully chosen groups, this problem is assumed to be hard. In 1985, both Koblitz (1987) and Miller (1986) proposed to use elliptic curves to instantiate such groups.

In their paper, Diffie and Hellman presented an application through a key exchange (see Chapter 9). In such a protocol, two users commonly referred to as Alice and Bob want to obtain a shared secret key by exchanging information over a public channel. To do so, they each pick a random scalar a (respectively, b), then send g^a (respectively, g^b), and receiving the element from the other compute the shared key K = (g^b)^a (respectively, (g^a)^b). This leads to the introduction of the decisional Diffie–Hellman problem, where given g, g^a, g^b, g^c one has to guess whether c = ab. It is easy to see that if this problem is hard, then the discrete logarithm problem is hard.

A natural question quickly arises when looking at their protocol: ...