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.
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:
In addition, for security purposes, the discrete logarithm problem is required to be hard in both and .
We say that a map is a -multilinear map if it satisfies the following properties:
In addition, for security purposes, the discrete logarithm problem is required to be hard in .
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.