Implementação em Tempo Constante de Amostragem de Gaussianas Discretas

• Jheyne N. Ortiz UNICAMP
• Diego F. Aranha UNICAMP
• Ricardo Dahab UNICAMP

DOI: https://doi.org/10.5753/sbseg.2015.20098

Abstract

Algorithms for discrete Gaussian sampling over lattices require discrete methods for sampling over integers. Considering that sampling from D_Λ,σ,c is a step when encrypting in certain modern lattice-based cryptosystems, sidechannel resistant implementations of discrete Gaussian sampling over integers are desirable. This work presents a constant-time implementation of the KnuthYao and Ziggurat methods comparing them with their variable-time counterparts. The Knuth-Yao constant-time implementation is applied to a Gaussian sampler over lattices.

References

Agrawal, S., Boneh, D., and Boyen, X. (2010). Efficient Lattice (H)IBE in the Standard Model. In Gilbert, H., editor, Advances in Cryptology – EUROCRYPT 2010, volume 6110 of Lecture Notes in Computer Science, pages 553–572. Springer Berlin Heidelberg.

Ajtai, M. (1996). Generating Hard Instances of Lattice Problems. Electronic Colloquium on Computational Complexity (ECCC), 3(7).

Buchmann, J., Cabarcas, D., Göpfert, F., Hülsing, A., and Weiden, P. (2014). Discrete Ziggurat: A Time-Memory Trade-Off for Sampling from a Gaussian Distribution over the Integers. In Lange, T., Lauter, K., and Lison?ek, P., editors, Selected Areas in Cryptography – SAC 2013, volume 8282 of Lecture Notes in Computer Science, pages 402–417. Springer Berlin Heidelberg.

Chen, Y. and Lin, D. (2014). Generic Constructions of Integrated PKE and PEKS. (2013):1–34.

de Clercq, R., Roy, S. S., Vercauteren, F., and Verbauwhede, I. (2015). Efficient software implementation of ring-LWE encryption. In Nebel, W. and Atienza, D., editors, Proceedings of the Design, Automation & Test in Europe Conference & Exhibition, DATE 2015, pages 339–344. ACM.

Ducas, L. and Prest, T. (2015). A Hybrid Gaussian Sampler for Lattices over Rings. Cryptology ePrint Archive, Report 2015/660. http://eprint.iacr.org/.

Dwarakanath, N. and Galbraith, S. (2014). Sampling from discrete Gaussians for lattice-based cryptography on a constrained device. Applicable Algebra in Engineering, Communication and Computing, 25(3):159–180.

Folláth, J. (2014). Gaussian Sampling in Lattice Based Cryptography. Tatra Mountains Mathematical Publications, 60(1):1–23.

Gentry, C., Peikert, C., and Vaikuntanathan, V. (2008). Trapdoors for Hard Lattices and New Cryptographic Constructions. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC ’08, pages 197–206, New York, NY, USA. ACM.

Hoffstein, J., Howgrave-Graham, N., Pipher, J., and Whyte, W. (2010). Practical Lattice-Based Cryptography: NTRUEncrypt and NTRUSign. In Nguyen, P. Q. and Vallée, B., editors, The LLL Algorithm, Information Security and Cryptography, pages 349–390. Springer Berlin Heidelberg.

Knuth, D. and Yao, A. (1976). Algorithms and Complexity: New Directions and Recent Results, chapter The Complexity of Nonuniform Random Number Generation. Academic Press, New York, j. f. traub edition.

Lyubashevsky, V., Peikert, C., and Regev, O. (2010). On Ideal Lattices and Learning with Errors over Rings. In Gilbert, H., editor, Advances in Cryptology – EUROCRYPT 2010, volume 6110 of Lecture Notes in Computer Science, pages 1–23. Springer Berlin Heidelberg.

Lyubashevsky, V. and Prest, T. (2015). Quadratic Time, Linear Space Algorithms for Gram-Schmidt Orthogonalization and Gaussian Sampling in Structured Lattices. Cryptology ePrint Archive, Report 2015/257. http://eprint.iacr.org/.

Marsaglia, G. and Tsang, W. W. (2000). The Ziggurat Method for Generating Random Variables. Journal of Statistical Software, 5(8):1–7.

Mochetti, K. and Dahab, R. (2014). Ideal Lattice-based (H)IBE Scheme. Technical Report IC-14-18, Institute of Computing, University of Campinas.

Pöppelmann, T. and Güneysu, T. (2014). Towards Practical Lattice-Based Public-Key Encryption on Reconfigurable Hardware. In Lange, T., Lauter, K., and Lisonek, P., editors, Selected Areas in Cryptography – SAC 2013, volume 8282 of Lecture Notes in Computer Science, pages 68–85. Springer Berlin Heidelberg.

Roy, S. S., Reparaz, O., Vercauteren, F., and Verbauwhede, I. (2014). Compact and Side Channel Secure Discrete Gaussian Sampling. Cryptology ePrint Archive, Report 2014/591. http://eprint.iacr.org/.

Shoup, V. (2015). Number Theory Library (NTL). Website. http://www.shoup.net/ntl/ - Último acesso em 24 de junho de 2015.

Stehlé, D., Steinfeld, R., Tanaka, K., and Xagawa, K. (2009). Efficient Public Key Encryption Based on Ideal Lattices. In Matsui, M., editor, Advances in Cryptology - ASIACRYPT 2009, volume 5912 of Lecture Notes in Computer Science, pages 617–635. Springer.