Amostragem Gaussiana na Criptografia Baseada em Reticulados
Resumo
Na Criptografia Baseada em Reticulados, diversos esquemas requerem a amostragem de vetores de um reticulado e de inteiros seguindo uma distribuição que, convencionalmente, é uma função Gaussiana. Este trabalho apresenta uma implementação com tempo de execução constante para o método Knuth-Yao apropriado à amostragem Gaussiana sobre os inteiros. Para a amostragem de vetores de um reticulado, os resultados se referem à amostragem sobre reticulados NTRU. Os experimentos têm como alvo um computador pessoal Intel Ivybridge e as implementações são descritas em linguagem C++ com aporte da biblioteca NTL de Victor Shoup.
Referências
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/.
Publicado
04/07/2016
Como Citar
ORTIZ, Jheyne N.; ARANHA, Diego F.; DAHAB, Ricardo.
Amostragem Gaussiana na Criptografia Baseada em Reticulados. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (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.
