Cryptographic multilinear map


A cryptographic -multilinear map is a kind of multilinear map, that is, a function such that for any integers and elements,, 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 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 be two additive cyclic groups of prime order, and another cyclic group of order written multiplicatively. A pairing is a map:, which satisfies the following properties:
; Bilinearity:
; Non-degeneracy: If and are generators of and, respectively, then is a generator of.
; Computability: There exists an efficient algorithm to compute.
In addition, for security purposes, the discrete logarithm problem is required to be hard in both and.

General case (for any ''n'')

We say that a map is a -multilinear map if it satisfies the following properties:
  1. All and are groups of same order;
  2. if and, then ;
  3. the map is non-degenerate in the sense that if are generators of, respectively, then is a generator of
  4. There exists an efficient algorithm to compute.
In addition, for security purposes, the discrete logarithm problem is required to be hard in.

Candidates

All the candidates multilinear maps are actually slightly generalizations of multilinear maps known as graded-encoding systems, since they allow the map to be applied partially: instead of being applied in all the values at once, which would produce a value in the target set, it is possible to apply to some values, which generates values in intermediate target sets. For example, for, it is possible to do then.
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.