# Multilinear Pairing in Cryptography

I want to create 2 Bilinear Pairing $e_1$,$e_2$ such that $$e_1:G_0 \times G_0 \rightarrow G_1$$ $$e_2:G_1 \times G_1 \rightarrow G_T$$

and use this to encrypt a message $M$ in the form $$M e_2(e_1(g,g),e_1(g,g))^{xy}$$ To decrypt the message, first one has to retrieve $e_1(g,g)^{x}$ and $e_1(g,g)^{y}$ using linear secret sharing scheme. Then, can calculate $$e_2(e_1(g,g)^{x}, e_1(g,g)^{y})=e_2(e_1(g,g), e_1(g,g))^{xy}$$ Ultimately one can retrieve $$M=\frac{M e_2(e_1(g,g),e_1(g,g))^{xy}}{e_2(e_1(g,g), e_1(g,g))^{xy}}$$ My question is whether it is possible to user this to create a cryptographic scheme? And also is it practical to implement using any existing crypto library? One idea is if it were possible to define $e_1$ as $e_1:G_0 \times G_0 \rightarrow G_0$, then we could define $e_2$ as $e_2:G_0 \times G_0 \rightarrow G_0$. And that serves our purpose. Since I am new in Pairing based cryptography, I do not know whether the solution is practical. It would be great if I get any help or lead from any of you guys. Thanks in advance.

## 1 Answer

Pairings, or bilinear maps, have indeed found a great deal of applications in crypto; hence, researchers have soon pointed out that further "degrees" of linearity (trilinear maps, etc.) would provide even more powerful applications.

Nowadays, multilinear maps are one of the most powerful cryptographic primitives. They are at the heart of indistinguishability obfuscation, witness encryption, multiparty key exchanges, among many other applications. As one can expect, building such a powerful primitive is not an easy task. The story of multilinear maps, which schemes have been created, which have been broken, etc., would be really long to tell (although I could try to look for some survey if you're interested). To make it short:

-The last thing you've described, $e: \mathbb{G}_0 \times \mathbb{G}_0 \mapsto \mathbb{G}_0$, is referred to as an ideal multilinear map. I know of a single paper which proposed such a scheme, and it was broken within a few months.

-There are currently two major constructions (and many variants of each of them) of graded encoding schemes, which are close variants of multilinear maps and are associated to some degree, which corresponds to its degree of linearity. The first scheme is usually called the GGH scheme and is based on ideal lattices; the second one relies on the hardness of factorization and is usually called the CLT scheme.

-The expected security of a graded encoding scheme is defined through a set of assumptions on the scheme which are conjectured to be intractables. The assumptions might require some particular components to be made available (one important case for multilinear maps is whether it provides encodings of the zero value). Different applications require different assumptions, so there's really a patchwork of schemes whose security is related to some assumption on some multilinear map. Essentially, most assumptions have been broken. Multilinear maps have suffered from a collection of very powerful attacks, denoted zeroizing attacks (a recent result seems to indicate that a new, an even more effective way of attacking multilinear maps has been discovered; it was introduced under the name of annihilation attacks). Zeroizing attacks have broken most assumptions on major candidate constructions, and I don't think many cryptographers would confidently advocate the use of these constructions as a safe choice.

However, it should be mentioned that this is not a full break. In particular, these attacks do not rule out several constructions of indistinguishability obfuscation from multilinear maps, which is one of the most important applications.

This was regarding security. Regarding efficiency, things are not better: even if they were really secure, current candidates are very slow. For multilinear maps of small degree (say, less than 10), an optimized implementation in a very simple setting might allow you to execute a protocol using them in a few minuts, but when parameters grow, the running time will soon make this solution entirely impractical. Indeed, building multilinear maps (or graded encoding schemes) with a better-understood security, and a better efficiency, is one of the major goals in theoretical cryptography.

• Thank you for the explanation. Seems like still its not possible to use multilinear pairing for a practical application. I need to figure out a way to solve my problem using Bilinear Pairing instead of Multilinear Pairing. – Azharul Islam May 4 '16 at 14:18