Cryptographic Multilinear Map

A cryptographic $n$-multilinear map is a kind of multilinear map, that is, a function $e:G_1\times \cdots \times G_n \rightarrow G_T$ such that for any integers $a_1, \ldots, a_n$ and elements $g_i \in G_i$, $e(g_1^,\ldots,g_n^)=e(g_1,\ldots,g_n)^$, and which in addition is efficiently computable and satisfies some security properties. It has several applications on cryptography, as key exchange protocols, identity-based encryption, and broadcast encryption. There exist constructions of cryptographic 2-multilinear maps, known as bilinear maps, however, the problem of constructing such multilinear maps for $n > 2$ seems much more difficult and the security of the proposed candidates is still unclear.

Definition

For ''n'' = 2

In this case, multilinear maps are mostly known as bilinear maps or pairings, and they are usually defined as follows: Let $G_1, G_2$ be two additive cyclic groups of prime order $q$, and $G_T$ another cyclic group of order $q$ written multiplicatively. A pairing is a map: $e: G_1 \times G_2 \rightarrow G_T$, which satisfies the following properties:
; Bilinearity: $\forall a,b \in F_q^*,\ \forall P\in G_1, Q\in G_2:\ e(a P, b Q) = e(P,Q)^$
; Non-degeneracy: If $g_1$ and $g_2$ are generators of $G_1$ and $G_2$, respectively, then $e(g_1, g_2)$ is a generator of $G_T$.
; Computability: There exists an efficient algorithm to compute $e$.

In addition, for security purposes, the discrete logarithm problem is required to be hard in both $G_1$ and $G_2$.

General case (for any ''n'')

We say that a map $e:G_1\times \cdots \times G_n \rightarrow G_T$ is a $n$-multilinear map if it satisfies the following properties:
# All $G_i$ (for $1 \le i \le n$) and $G_T$ are groups of same order;
# if $a_1, \ldots, a_n \in \mathbb$ and $(g_1, \ldots, g_n) \in G_1 \times \cdots \times G_n$, then $e(g_1^,\ldots,g_n^)=e(g_1,\ldots,g_n)^$;
# the map is non-degenerate in the sense that if $g_1, \ldots, g_n$ are generators of $G_1, \ldots, G_n$, respectively, then $e(g_1, \ldots, g_n)$ is a generator of $G_T$
# There exists an efficient algorithm to compute $e$.

In addition, for security purposes, the discrete logarithm problem is required to be hard in $G_1, \ldots, G_n$.

Candidates

All the candidates multilinear maps are actually slightly generalizations of multilinear maps known as graded-encoding systems, since they allow the map $e$ to be applied partially: instead of being applied in all the $n$ values at once, which would produce a value in the target set $G_T$, it is possible to apply $e$ to some values, which generates values in intermediate target sets. For example, for $n = 3$, it is possible to do $y = e(g_2, g_3) \in G_$ then $e(g_1, y) \in G_T$.

The three main candidates are GGH13, which is based on ideals of polynomial rings; CLT13, which is based approximate GCD problem and works over integers, hence, it is supposed to be easier to understand than GGH13 multilinear map; and GGH15, which is based on graphs.

References

{{Reflist, refs=
{{cite journal,
last1=Dutta, first1=Ratna,
last2=Barua, first2=Rana,
last3=Sarkar, first3=Palash,
title=Pairing-Based Cryptographic Protocols : A Survey, journal=e-Print IACR,
date=2004,
url=https://eprint.iacr.org/2004/064

{{cite book,
last1=Boneh, first1=Dan,
last2=Silverberg, first2=Alice, title=Topics in Algebraic and Noncommutative Geometry , chapter=Applications of multilinear forms to cryptography , series=Contemporary Mathematics ,
date=2003,
volume=324,
pages=71–90, doi=10.1090/conm/324/05731, isbn=9780821832097,
url=http://crypto.stanford.edu/~dabo/abstracts/mlinear.html,
accessdate=14 March 2018

{{cite web, last1=Albrecht, first1=Martin R.,
title=Are Graded Encoding Scheme broken yet?,
url=http://malb.io/are-graded-encoding-schemes-broken-yet.html,
accessdate=14 March 2018

{{cite book,
last1=Koblitz, first1=Neal,
last2=Menezes, first2=Alfred, title=Cryptography and Coding ,
chapter=Pairing-Based cryptography at high security levels,
series=Lecture Notes in Computer Science,
date=2005,
volume=3796, pages=13–36 , doi=10.1007/11586821_2, isbn=978-3-540-30276-6

{{cite book,
last1=Coron, first1=Jean-Sébastien,
last2=Lepoint, first2=Tancrède,
last3=Tibouchi, first3=Mehdi, title=Advances in Cryptology – CRYPTO 2013 , chapter=Practical Multilinear Maps over the Integers , series=Lecture Notes in Computer Science,
date=2013, volume=8042,
pages=476–493, doi=10.1007/978-3-642-40041-4_26, isbn=978-3-642-40040-7, doi-access=free

{{cite book,
last1=Garg, first1=Sanjam,
last2=Gentry, first2=Craig,
last3=Halevi, first3=Shai, title=Advances in Cryptology – EUROCRYPT 2013 , chapter=Candidate Multilinear Maps from Ideal Lattices , series=Lecture Notes in Computer Science ,
date=2013, volume=7881 , doi=10.1007/978-3-642-38348-9_1,
pages=1–17, isbn=978-3-642-38347-2

{{cite book,
last1=Gentry, first1=Craig,
last2=Gorbunov, first2=Sergey,
last3=Halevi, first3=Shai, title=Theory of Cryptography , chapter=Graph-Induced Multilinear Maps from Lattices , series=Lecture Notes in Computer Science ,
date=2015, volume=9015 ,
pages=498–527, doi=10.1007/978-3-662-46497-7_20 , isbn=978-3-662-46496-0

Cryptography
Multilinear algebra