Implementação em Tempo Constante de Amostragem de Gaussianas Discretas
Resumo
Algoritmos de amostragem Gaussiana discreta sobre reticulados demandam métodos discretos de amostragem sobre inteiros. Considerando que a amostragem de DΛ,σ,c é um dos passos na encriptação em certos criptosistemas modernos baseados em reticulados, surge a preocupação por implementações resistentes a ataques por canais laterais. Este trabalho apresenta e discute implementações dos métodos Knuth-Yao e Ziggurat em tempo constante comparando-as com suas versões de tempo variável. A implementação em tempo constante do Knuth-Yao é aplicada na amostragem sobre reticulados.
Referências
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.
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.
Publicado
09/11/2015
Como Citar
ORTIZ, Jheyne N.; ARANHA, Diego F.; DAHAB, Ricardo.
Implementação em Tempo Constante de Amostragem de Gaussianas Discretas. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 15. , 2015, Florianópolis.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2015
.
p. 239-252.
DOI: https://doi.org/10.5753/sbseg.2015.20098.
