Cryptographic multilinear map explained

A cryptographic

n -multilinear map is a kind of multilinear map, that is, a function e:G _{1 x} … x G _{n} → G _{T} such that for any integers a _{1,} \ldots, a _{n} and elements g _{i} \in G _{i} , e(g ^{a _{1}} _{1} ,\ldots,g ^{a _{n}} _{n} ) = e(g _{1,\ldots,g} ^{\prod ^{n} _{i =1} a _{i}} ^{n)} , 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} x G _{2} → G _{T} , which satisfies the following properties:

Bilinearity:

\forall a,b \in F ^{*, \forall} _{q} 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 x} … x G _{n} → G _{T} is a n -multilinear map if it satisfies the following properties:

1. All

G _{i} (for 1 \le i \le n ) and G _{T} are groups of same order;

1. if

a _{1,} \ldots, a _{n} \in Z and (g _{1,} \ldots, g _{n)} \in G _{1} x … x G _{n} , then e(g ^{a _{1}} _{1} ,\ldots,g ^{a _{n}} _{n} ) = e(g _{1,\ldots,g} ^{\prod ^{n} _{i =1} a _{i}} ^{n)} ;

1. 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}

1. 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.