Cryptology ePrint Archive: Report 2014/928

Implementing Candidate Graded Encoding Schemes from Ideal Lattices

Martin R. Albrecht and Catalin Cocis and Fabien Laguillaumie and Adeline Langlois

Abstract: Multilinear maps have become popular tools for designing cryptographic schemes since a first approximate realisation candidate was proposed by Garg, Gentry and Halevi (GGH). This construction was later improved by Langlois, Stehlé and Steinfeld who proposed GGHLite which offers smaller parameter sizes. In this work, we provide the first implementation of such approximate multilinear maps based on ideal lattices. Implementing GGH-like schemes naively would not allow instantiating it for non-trivial parameter sizes. We hence propose a strategy which reduces parameter sizes further and several technical improvements to allow for an efficient implementation. In particular, since finding a prime ideal when generating instances is an expensive operation, we show how we can drop this requirement. We also propose algorithms and implementations for sampling from discrete Gaussians, for inverting in some Cyclotomic number fields and for computing norms of ideals in some Cyclotomic number rings. Due to our improvements we were able to compute a multilinear jigsaw puzzle for κappa=52 (resp. kappa=38) and lambda=52 (resp. lambda=80).

Category / Keywords: algorithms, implementation, lattice-based cryptography, cryptographic multilinear maps

Original Publication (in the same form): IACR-ASIACRYPT-2015

Date: received 12 Nov 2014, last revised 11 Sep 2015

Contact author: fabien laguillaumie at ens-lyon fr

Available format(s): PDF | BibTeX Citation

Version: 20150911:153435 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]