Cryptology ePrint Archive: Report 2012/610

Candidate Multilinear Maps from Ideal Lattices

Sanjam Garg and Craig Gentry and Shai Halevi

Abstract: We describe plausible lattice-based constructions with properties that approximate the sought-after multilinear maps in hard-discrete-logarithm groups, and show an example application of such multilinear maps that can be realized using our approximation. The security of our constructions relies on seemingly hard problems in ideal lattices, which can be viewed as extensions of the assumed hardness of the NTRU function.

Category / Keywords: public-key cryptography / Multilinear maps

Date: received 29 Oct 2012, last revised 17 Mar 2013

Contact author: sanjamg at cs ucla edu

Available format(s): PDF | BibTeX Citation

Note: Added description of attacks on the analogues of subgroup-membership and decision-linear

Version: 20130317:071334 (All versions of this report)

Short URL: ia.cr/2012/610

Discussion forum: Show discussion | Start new discussion