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\to G_T$ such that for any integers $a_1,\dots ,a_n$ and elements $g_i\in G_i$, $e(g_1^{a_1},\dots ,g_n^{a_n})=e(g_1,\dots ,g_n{)}^{\prod _{i=1}^n{a}_i}$, 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\to G_T$, which satisfies the following properties:

Bilinearity

$\mathrm{\forall }a,b\in F_q^{*},\mathrm{\forall }P\in G_1,Q\in G_2:e(aP,bQ)=e(P,Q{)}^{ab}$

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\to G_T$ is a $n$-multilinear map if it satisfies the following properties:

1. All $G_i$ (for $1\le i\le n$) and $G_T$ are groups of same order;
2. if $a_1,\dots ,a_n\in \mathbb{Z}$ and $(g_1,\dots ,g_n)\in G_1\times \cdots \times G_n$, then $e(g_1^{a_1},\dots ,g_n^{a_n})=e(g_1,\dots ,g_n{)}^{\prod _{i=1}^n{a}_i}$;
3. the map is non-degenerate in the sense that if $g_1,\dots ,g_n$ are generators of $G_1,\dots ,G_n$, respectively, then $e(g_1,\dots ,g_n)$ is a generator of $G_T$
4. 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,\dots ,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_{T_2}$ 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.