# Advantages of bilinear map

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?

• Compared to what? – mikeazo Dec 16 '13 at 14:52
• I think it is very hard to answer this question at it's current state within a reasonable amount of space... – DrLecter Dec 16 '13 at 14:56
• re 'too broad' votes: personally I think this is very near the edge, but I can't think of a more specific way of for a first intro to pairings? Googling it several promising looking papers come up, so this question suggests a lack of research? – Cryptographeur Dec 16 '13 at 18:46

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 KU 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 KR 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.

• Using supersingular curves is really a bit strange, because their embedding degree is at most $6$ (for rather unhandy curves based on characteristic $3$ fields). However, there are also "better" non-supersingular pairing friendly curves over fields of large prime characteristic such as Barreto-Naehrig (BN) curves having embedding degree $12$. Here the security/efficiency tradeoff is quite nice and one does not really need to feel that uneasy. – DrLecter Dec 16 '13 at 16:50
• Note that depending on what you want out of the pairing, you cannot necessarily use just any kind of curve. $G_1$ and $G_2$ of size $p$ prime, a computable one-way isomorphism from $G_1$ to $G_2$, easy hashing into $G_2$: you cannot have all three characteristics simultaneously. – Thomas Pornin Dec 16 '13 at 18:16
• I agree, but using supersingular curves as example make it look worse than it is ;) – DrLecter Dec 16 '13 at 18:37
• @ThomasPornin : $\:$ Why can't one have all three characteristics simultaneously? $\hspace{1.53 in}$ Do you just mean there's no known way to have all three characteristics simultaneously? $\hspace{1.01 in}$ – user991 Dec 16 '13 at 22:16
• Yes, that's it: no known way with currently known pairings and curve types. – Thomas Pornin Dec 16 '13 at 22:36

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.

• I wouldn't be confident that that was why they were 'first invented', but it probably is their main use – Cryptographeur Dec 16 '13 at 10:03
• Maybe i should rephrase: "The first use of pairing that we know is not for construction of cryptographic primitives but to break some hard assumptions as the DL in specific groups" – curious Dec 16 '13 at 10:04