Paper 2014/928

Implementing Candidate Graded Encoding Schemes from Ideal Lattices

Martin R. Albrecht, Catalin Cocis, 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).

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in ASIACRYPT 2015
Keywords
algorithmsimplementationlattice-based cryptographycryptographic multilinear maps
Contact author(s)
fabien laguillaumie @ ens-lyon fr
History
2015-09-11: last of 5 revisions
2014-11-13: received
See all versions
Short URL
https://ia.cr/2014/928
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/928,
      author = {Martin R.  Albrecht and Catalin Cocis and Fabien Laguillaumie and Adeline Langlois},
      title = {Implementing Candidate Graded Encoding Schemes from Ideal Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2014/928},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/928}},
      url = {https://eprint.iacr.org/2014/928}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.