Implementing Candidate Graded Encoding Schemes from Ideal Lattices

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 κ " 52 (resp. κ " 38) and λ " 52 (resp. λ " 80).
Type de document :
Communication dans un congrès
Tetsu Iwata and Jung Hee Cheon. Asiacrypt 2015, Nov 2015, Auckland, New Zealand. Springer, Advances in Cryptology - 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings, Part 9453, 2015, Advances in Cryptology - 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings, Part 〈10.1007/978-3-662-48800-3_31〉
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01237355
Contributeur : Fabien Laguillaumie <>
Soumis le : mardi 8 décembre 2015 - 15:19:47
Dernière modification le : mercredi 16 mai 2018 - 11:24:10

Fichier

928.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Martin R. Albrecht, Catalin Cocis, Fabien Laguillaumie, Adeline Langlois. Implementing Candidate Graded Encoding Schemes from Ideal Lattices. Tetsu Iwata and Jung Hee Cheon. Asiacrypt 2015, Nov 2015, Auckland, New Zealand. Springer, Advances in Cryptology - 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings, Part 9453, 2015, Advances in Cryptology - 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings, Part 〈10.1007/978-3-662-48800-3_31〉. 〈hal-01237355〉

Partager

Métriques

Consultations de la notice

439

Téléchargements de fichiers

201