Advantages of bilinear map

Question

Consider the pairing $e: G_1*G_2 \to G_t$.

Why we are mapping element from group $G_1$ and group $G_2$ to an element in $G_t$. How are they used in cryptography? What advantages do they provide?

Answer 1

If we are to summarize things in one sentence, let's say that pairings allow for three-party mathematical protocols.

Consider for instance identity-based encryption. In a classical public-key cryptography system for encrypting messages (e.g. emails), the sender must know the recipient's public key in order to encrypt the message. Distribution of public keys is a known troublesome problem (less hard than distribution of secret keys, but hard nonetheless). IBE strives to make the recipient's public key actually equal to the recipient's name (or email address), because the sender already knows it. If you want to do IBE with, say, RSA, you usually end up with a centralized system in which there is a central system C through which all messages go. Every user knows one public key, the one of C, and encrypts the message with that public key. C decrypts the message, and reencrypts it with the intended recipient's public key (C knows all user's public keys).

This classical model for IBE does not scale well, because the central system must receive, decrypt, encrypt and send every email. Pairings resolve that by moving the central systems to mere mathematics. With pairings, the central system C still exists, but it needs not be invoked for every email. Things go more or less like this:

• The central system C has a private key, and the corresponding public key K is known to every user.
• Each user U obtains his private key K_U from C.
• When sender S wants to send an email to recipient R, he can "somehow" compute R's public key using only R's name (email address) and the central system public key K.
• Recipient R uses K_R to decrypt the message.

The pairing is what resides in this "somehow". It is a computation involving K, R's name, and some input from U. It moves C out of the physical picture. C is still there mathematically (and, in particular, C knows the private keys of every user, since C computes these private keys), but C needs not do anything in particular at the time the email is sent. This prevents C from becoming a network bottleneck when traffic increases.

In a similar way, pairings are convenient for electronic cash protocols (three-party protocols between buyer, merchant and bank, and we would prefer not to have to actually talk to the bank for each transaction).

Historically, pairings were a mathematical curiosity from the 1950s, shown practical for cryptography in 1986 by Miller, and first used to break elliptic curves. Indeed, a pairing from $G_1\times G_2$ to $G_3$ turns a discrete logarithm problem on $G_1$ into a discrete logarithm on $G_3$. For known pairings on elliptic curves, $G_1$ is an $n$-bit curve, and $G_3$ is a multiplicative subgroup in a finite field of size $kn$, where $k$ is the embedding degree of the curve. Sub-exponential algorithms for breaking DL on finite fields are known, so if $k$ is small, applying the pairing makes the DL problem easier.

Fortunately, for most curves as used in practice, $k$ is astronomically high, so the pairing does not break DL on these curves. Some specific curves (especially most supersingular curves) turned out to have very low embedding degrees, and, for them, pairings are a useful breaking tool.

Constructive uses of pairings (as for IBE) rely on using "slightly weakened" curves, i.e. curves for which the embedding degree is sufficiently small to allow the pairing to be efficiently computed, but not small enough to make DL on $G_3$ too easy. For instance, IBE would use an 800-bit supersingular curve of embedding degree 2; DL on a 1600-bit finite field is still way beyond what is technologically feasible. This still is a rather delicate dance which explains that a lot of cryptographers feel uneasy in the presence of a pairing.

Answer 2

You can multiply encrypted values. Consider for instance Paillier public key encryption. The encrypted values can be added by multiplying the ciphertexts because the ciphertext comes in the form of $g^mr^n$ where $m$ is the message (the $r$ are cancelled out by raising to the secret key). By multiplying two Paillier ciphertexts you add the exponents. So you have a sort of additive homomorphism. Generally you can evaluate affine circuits on the exponent ($g^{a+b+c+ \cdots}$) without pairings. But with pairings you can have multiplication on the exponent as well. That is that under some restriction an untrusted party can homomorphically evaluate a circuit that entails multiplication under some threshold value (BGN cryptosystem)

But this is not the only case that pairings are useful. The first major cryptographic use of pairings was to break the discrete logarithm problem in specific group (certain elliptic curve groups, MOV attack) by reducing it to the Discrete Logarithm problem over a simpler group.