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 satisfy 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 parings, 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.

References

1. Dutta, Ratna; Barua, Rana; Sarkar, Palash (2004). "Pairing-Based Cryptographic Protocols : A Survey". e-Print IACR.
2. Boneh, Dan; Silverberg, Alice (2003). "Applications of Multilinear Forms to Cryptography". Contemporary Mathematics. 324: 71–90. doi:10.1090/conm/324/05731. ISBN 9780821832097. Retrieved 14 March 2018.
3. Albrecht, Martin R. "Are Graded Encoding Scheme broken yet?". Retrieved 14 March 2018.
4. Koblitz, Neal; Menezes, Alfred (2005). "Pairing-Based cryptography at high security levels". LNCS. 3796.
5. Garg, Sanjam; Gentry, Craig; Halevi, Shai (2013). "Candidate Multilinear Maps from Ideal Lattices". Advances in Cryptology -- EUROCRYPT 2013: 1–17.
6. Coron, Jean-Sébastien; Lepoint, Tancrède; Tibouchi, Mehdi (2013). "Practical Multilinear Maps over the Integers". Advances in Cryptology -- EUROCRYPT 2013. Lecture Notes in Computer Science. 8042: 476–493. doi:10.1007/978-3-642-40041-4_26. ISBN 978-3-642-40040-7.
7. Gentry, Craig; Gorbunov, Sergey; Halevi, Shai (2015). "Graph-Induced Multilinear Maps from Lattices". Theory of Cryptography: 498–527.