Cryptographic multilinear map

A cryptographic ${\displaystyle n}$-multilinear map is a kind of multilinear map, that is, a function ${\displaystyle e:G_{1}\times \cdots \times G_{n}\rightarrow G_{T}}$ such that for any integers ${\displaystyle a_{1},\ldots ,a_{n}}$ and elements ${\displaystyle g_{i}\in G_{i}}$, ${\displaystyle 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 ${\displaystyle n>2}$ seems much more difficult² and the security of the proposed candidates is still unclear.³

In this case, multilinear maps are mostly known as bilinear maps or pairings, and they are usually defined as follows:⁴ Let ${\displaystyle G_{1},G_{2}}$ be two additive cyclic groups of prime order ${\displaystyle q}$, and ${\displaystyle G_{T}}$ another cyclic group of order ${\displaystyle q}$ written multiplicatively. A pairing is a map: ${\displaystyle e:G_{1}\times G_{2}\rightarrow G_{T}}$, which satisfies the following properties:

Bilinearity

${\displaystyle \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 ${\displaystyle g_{1}}$ and ${\displaystyle g_{2}}$ are generators of ${\displaystyle G_{1}}$ and ${\displaystyle G_{2}}$, respectively, then ${\displaystyle e(g_{1},g_{2})}$ is a generator of ${\displaystyle G_{T}}$.

Computability

There exists an efficient algorithm to compute ${\displaystyle e}$.

In addition, for security purposes, the discrete logarithm problem is required to be hard in both ${\displaystyle G_{1}}$ and ${\displaystyle G_{2}}$.

We say that a map ${\displaystyle e:G_{1}\times \cdots \times G_{n}\rightarrow G_{T}}$ is an ${\displaystyle n}$-multilinear map if it satisfies the following properties:

1. All ${\displaystyle G_{i}}$ (for ${\displaystyle 1\leq i\leq n}$) and ${\displaystyle G_{T}}$ are groups of same order;
2. if ${\displaystyle a_{1},\ldots ,a_{n}\in \mathbb {Z} }$ and ${\displaystyle (g_{1},\ldots ,g_{n})\in G_{1}\times \cdots \times G_{n}}$, then ${\displaystyle 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 ${\displaystyle g_{1},\ldots ,g_{n}}$ are generators of ${\displaystyle G_{1},\ldots ,G_{n}}$, respectively, then ${\displaystyle e(g_{1},\ldots ,g_{n})}$ is a generator of ${\displaystyle G_{T}}$
4. There exists an efficient algorithm to compute ${\displaystyle e}$.

In addition, for security purposes, the discrete logarithm problem is required to be hard in ${\displaystyle G_{1},\ldots ,G_{n}}$.

All the candidates multilinear maps are actually slightly generalizations of multilinear maps known as graded-encoding systems, since they allow the map ${\displaystyle e}$ to be applied partially: instead of being applied in all the ${\displaystyle n}$ values at once, which would produce a value in the target set ${\displaystyle G_{T}}$, it is possible to apply ${\displaystyle e}$ to some values, which generates values in intermediate target sets. For example, for ${\displaystyle n=3}$, it is possible to do ${\displaystyle y=e(g_{2},g_{3})\in G_{T_{2}}}$ then ${\displaystyle 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.