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}^{a_{1}},\ldots ,g_{n}^{a_{n}})=e(g_{1},\ldots ,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}\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(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}\rightarrow G_{T}$ is a $n$-multilinear map if it satisfies the following properties:

1. All $G_{i}$ (for $1\leq i\leq n$) and $G_{T}$ are groups of same order;
2. if $a_{1},\ldots ,a_{n}\in \mathbb {Z}$ and $(g_{1},\ldots ,g_{n})\in G_{1}\times \cdots \times G_{n}$, then $e(g_{1}^{a_{1}},\ldots ,g_{n}^{a_{n}})=e(g_{1},\ldots ,g_{n})^{\prod _{i=1}^{n}a_{i}}$;
3. 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}$
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},\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_{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.