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,^[1] however, the problem of constructing such multilinear^[1] maps for ${\displaystyle n>2}$ seems much more difficult^[2] and the security of the proposed candidates is still unclear.^[3]

Definition

For n = 2

In this case, multilinear maps are mostly known as bilinear maps or pairings, and they are usually defined as follows:^[4] 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}}$.

General case (for any n)

We say that a map ${\displaystyle e:G_{1}\times \cdots \times G_{n}\rightarrow G_{T}}$ is a ${\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}}$.

Candidates

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,^[5] which is based on ideals of polynomial rings; CLT13,^[6] 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,^[7] which is based on graphs.