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,[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]

Definition

edit

For n = 2

edit

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:

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)

edit

We say that a map   is a  -multilinear map if it satisfies the following properties:

  1. All   (for  ) 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

edit

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.

References

edit
  1. ^ a b Dutta, Ratna; Barua, Rana; Sarkar, Palash (2004). "Pairing-Based Cryptographic Protocols : A Survey". e-Print IACR.
  2. ^ Boneh, Dan; Silverberg, Alice (2003). "Applications of multilinear forms to cryptography". Topics in Algebraic and Noncommutative Geometry. Contemporary Mathematics. Vol. 324. pp. 71–90. doi:10.1090/conm/324/05731. ISBN 9780821832097. Retrieved 14 March 2018.
  3. ^ Albrecht, Martin R. "Are Graded Encoding Scheme broken yet?". Retrieved 14 March 2018.
  4. ^ Koblitz, Neal; Menezes, Alfred (2005). "Pairing-Based cryptography at high security levels". Cryptography and Coding. Lecture Notes in Computer Science. Vol. 3796. pp. 13–36. doi:10.1007/11586821_2. ISBN 978-3-540-30276-6.
  5. ^ Garg, Sanjam; Gentry, Craig; Halevi, Shai (2013). "Candidate Multilinear Maps from Ideal Lattices". Advances in Cryptology – EUROCRYPT 2013. Lecture Notes in Computer Science. Vol. 7881. pp. 1–17. doi:10.1007/978-3-642-38348-9_1. ISBN 978-3-642-38347-2. Archived from the original on Jun 18, 2022 – via SpringerLink.
  6. ^ Coron, Jean-Sébastien; Lepoint, Tancrède; Tibouchi, Mehdi (2013). "Practical Multilinear Maps over the Integers". Advances in Cryptology – CRYPTO 2013. Lecture Notes in Computer Science. Vol. 8042. pp. 476–493. doi:10.1007/978-3-642-40041-4_26. ISBN 978-3-642-40040-7. Archived from the original on Jan 20, 2022 – via SpringerLink.
  7. ^ Gentry, Craig; Gorbunov, Sergey; Halevi, Shai (2015). "Graph-Induced Multilinear Maps from Lattices". Theory of Cryptography. Lecture Notes in Computer Science. Vol. 9015. pp. 498–527. doi:10.1007/978-3-662-46497-7_20. ISBN 978-3-662-46496-0. Archived from the original on Apr 19, 2022 – via SpringerLink.