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(a P, b Q) = 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:

All $G_i$ (for $1 \le i \le n$ ) and $G_T$ are groups of same order;
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}$ ;
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$
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.

References

{{Reflist|refs=

{{cite journal|

last1=Dutta|first1=Ratna|

last2=Barua|first2=Rana|

last3=Sarkar|first3=Palash|

title=Pairing-Based Cryptographic Protocols : A Survey|journal=e-Print IACR|

date=2004|

url=https://eprint.iacr.org/2004/064}}

{{cite book|

last1=Boneh|first1=Dan|

date=2003|

volume=324|

pages=71–90|doi=10.1090/conm/324/05731|isbn=9780821832097|

url=http://crypto.stanford.edu/~dabo/abstracts/mlinear.html|

accessdate=14 March 2018}}

{{cite web|last1=Albrecht|first1=Martin R.|

title=Are Graded Encoding Schemes broken yet?|

url=http://malb.io/are-graded-encoding-schemes-broken-yet.html|

accessdate=14 March 2018}}

{{cite book|

last1=Koblitz|first1=Neal|

last2=Menezes|first2=Alfred|title=Cryptography and Coding |

chapter=Pairing-Based cryptography at high security levels|

series=Lecture Notes in Computer Science|

date=2005|

volume=3796|pages=13–36 |doi=10.1007/11586821_2|isbn=978-3-540-30276-6 }}

{{cite book|

last1=Coron|first1=Jean-Sébastien|

last2=Lepoint|first2=Tancrède|

date=2013|volume=8042|

pages=476–493|doi=10.1007/978-3-642-40041-4_26|isbn=978-3-642-40040-7|doi-access=free }}

{{cite book|

last1=Garg|first1=Sanjam|

last2=Gentry|first2=Craig|

date=2013|volume=7881 |doi=10.1007/978-3-642-38348-9_1|

pages=1–17|isbn=978-3-642-38347-2 }}

{{cite book|

last1=Gentry|first1=Craig|

last2=Gorbunov|first2=Sergey|

date=2015|volume=9015 |

pages=498–527|doi=10.1007/978-3-662-46497-7_20 |isbn=978-3-662-46496-0 |doi-access=free |via=SpringerLink }}

}}

Category:Cryptography

Category:Multilinear algebra