Amostragem Gaussiana na Criptografia Baseada em Reticulados
Abstract
In Lattice-Based Cryptography, some cryptosystems require sampling lattice points and integers over a distribution that, conventionally, follows a Gaussian function. This work presents a constant-time implementation of the Knuth-Yao method for Gaussian sampling over integers. For Gaussian sampling over lattices, the results refer to the sampling over NTRU lattices. Our experiments target an Intel Ivybridge desktop and all implementations are described using C++ language with support of the NTL library of Victor Shoup.
References
Bruinderink, L. G., H¨ulsing, A., Lange, T., and Yarom, Y. (2016). Flush, Gauss, and Reload – A Cache Attack on the BLISS Lattice-Based Signature Scheme. Cryptology ePrint Archive, Report 2016/300. http://eprint.iacr.org/.
Ducas, L., Durmus, A., Lepoint, T., and Lyubashevsky, V. (2013). Advances in Cryptology – CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, chapter Lattice Signatures and Bimodal Gaussians, pages 40–56. Springer Berlin Heidelberg, Berlin, Heidelberg.
Ducas, L. and Prest, T. (2015). A Hybrid Gaussian Sampler for Lattices over Rings.
Cryptology ePrint Archive, Report 2015/660. http://eprint.iacr.org/.
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.
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. (2012). On Ideal Lattices and Learning with Errors Over Rings. Cryptology ePrint Archive, Report 2012/230. http://eprint.iacr.org/.
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/.
Ducas, L., Durmus, A., Lepoint, T., and Lyubashevsky, V. (2013). Advances in Cryptology – CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, chapter Lattice Signatures and Bimodal Gaussians, pages 40–56. Springer Berlin Heidelberg, Berlin, Heidelberg.
Ducas, L. and Prest, T. (2015). A Hybrid Gaussian Sampler for Lattices over Rings.
Cryptology ePrint Archive, Report 2015/660. http://eprint.iacr.org/.
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.
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. (2012). On Ideal Lattices and Learning with Errors Over Rings. Cryptology ePrint Archive, Report 2012/230. http://eprint.iacr.org/.
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/.
Published
2016-07-04
How to Cite
ORTIZ, Jheyne N.; ARANHA, Diego F.; DAHAB, Ricardo.
Amostragem Gaussiana na Criptografia Baseada em Reticulados. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 1. , 2016, Porto Alegre.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 800-803.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2016.9769.
