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, [1] however, the problem of constructing such multilinear [1] maps for seems much more difficult [2] and the security of the proposed candidates is still unclear. [3]
In this case, multilinear maps are mostly known as bilinear maps or pairings, and they are usually defined as follows: [4] 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, [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.
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, [1] however, the problem of constructing such multilinear [1] maps for seems much more difficult [2] and the security of the proposed candidates is still unclear. [3]
In this case, multilinear maps are mostly known as bilinear maps or pairings, and they are usually defined as follows: [4] 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, [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.