Efficient Gaussian sampling for RLWE-based cryptography through a fast Fourier transform
Resumo
Quantum computing threatens classical cryptography, leading to the search for stronger alternatives. The cryptographic approach based on lattices is considered as a viable option. Schemes with that approach use Gaussian sampling, a design which brings along two concerns: efficiency and information leakage. This work adresses those concerns in the RLWE formulation, for digital signatures. Efficiency mitigation uses the central limit theorem, and the Walsh–Hadamard transform, whereas the information leakage risk is reduced via isochronous implementation. Up to 223 samples are queried, and the results are compared against those of a cumulative distribution table sampler. Statistical metrics show the suitability of the presented sampler in a number of contexts.
Palavras-chave:
Cryptology, Ring learning with errors, Discrete Gaussian sampling, Central limit theorem, Fast Walsh–Hadamard transform
Referências
Ajtai, M. (1996). Generating hard instances of lattice problems (extended abstract). In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, pages 99–108, New York, NY, USA. ACM. STOC ’96.
Alkim, E., Barreto, P. S. L. M., Bindel, N., Longa, P., and Ricardini, J. E. (2019). The Lattice-Based Digital Signature Scheme qTESLA. Cryptology ePrint Archive, Report 2019/085.
Alkim, E., Bos, J. W., Ducas, L., Longa, P., Mironov, I., Naehrig, M., Nikolaenko, V., Peikert, C., and Raghunathan, A. (2020). FrodoKEM Learning With Errors Key Encapsulation Algorithm Specifications And Supporting Documentation.
Bernstein, D. J., Hallgren, S., Vollmer, U., Buchmann, J., Dahmen, E., Szydlo, M., Overbeck, R., Sendrier, N., Micciancio, D., Regev, O., Ding, J., and Yang, B.-Y. (2008). Post Quantum Cryptography. Springer Publishing Company, Incorporated, Berlin Heidelberg, 1st edition.
Bernstein, D. J., Lange, T., Cayrel, P.-L., and Peters, C. (2022). Lattice-based public-key cryptography. http://pqcrypto.org/lattice.html, accessed on MAY 26th, 2022.
CSRC, N. (2022). Post-quantum cryptography. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/, accessed on MAY 26th, 2022.
Ducas, L., Durmus, A., Lepoint, T., and Lyubashevsky, V. (2013). Lattice Signatures and Bimodal Gaussians. Cryptology ePrint Archive, Report 2013/383.
Dwarakanath, N. C. and Galbraith, S. D. (2014). Sampling from discrete gaussians for lattice-based cryptography on a constrained device. Applicable Algebra in Engineering, Communications and Computing, 25(3):159–180.
Harwit, M. and Sloane, N. J. A. (1979). Appendix Hadamard and s-matrices, Walsh functions, pseudo-random sequences, and the fast Hadamard transform. In Hadamard Transform Optics, pages 200–228. Elsevier Inc.
Howe, J., Prest, T., Ricosset, T., and Rossi, M. (2019). Isochronous gaussian sampling: From inception to implementation with applications to the falcon signature scheme. Pages 1–23.
Kocher, P. C. (1996). Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In Koblitz, N., editor, Advances in Cryptology - CRYPTO ’96, pages 104–113, Berlin Heidelberg, Springer-Verlag. LNCS 1109.
Lyubashevsky, V., Peikert, C., and Regev, O. (2013). On ideal lattices and learning with errors over rings. J. ACM, 60(6):43:1–43:35.
Micciancio, D. (2022). Sampling, Lattice Cryptography. http://cseweb.ucsd.edu/daniele/LatticeLinks/Sampling.html, accessed on MAY 26th, 2022.
Micciancio, D. and Walter, M. (2018). Gaussian sampling over the integers: Efficient, generic, constant-time.
Ortiz, J. N., Aranha, D. F., and Dahab, R. (2015). Implementaça?o em Tempo Constante de Amostragem de Gaussianas Discretas. SBSeg 2015.
Peikert, C. (2014). Lattice Cryptography for the Internet. In Mosca, M., editor, Post-Quantum Cryptography 6th International Workshop, Lecture Notes in Computer Science, pages 197–219, Switzerland. Springer International Publishing.
Pöppelman, T., Alkim, E., Avanzi, R., Bos, J., Ducas, L., de la Piedra, A., Schwabe, P., and Stebila, D. (2019). NewHope Algorithm Specifications and Supporting Documentation. c/o Thomas Po?ppelmann, Infineon Technologies AG, Am Campeon 1-12, 85579 Neubiberg, Germany, version 1.03 edition.
Rader, C. M. (1969). A new method of generating Gaussian random variables by computer. Technical Report 1969-49, Massachusetts Institute of Technology, Lexington, Massachusetts.
Regev, O. (2009). On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6):34:1–34:40.
Reparaz, O., Balasch, J., and Verbauwhede, I. (2016). Dude, is my code constant time? Cryptology ePrint Archive, Report 2016/1123.
Sylvester, J. J. (1867). Lx. thoughts on inverse orthogonal matrices, simultaneous sign-successions, and tessellated pavements in two or more colours, with applications to newton’s rule, ornamental tile-work, and the theory of numbers. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 34(232):461–475.
Weisstein, E. W. (2021). Probability Density Function. From MathWorld–A Wolfram Web Resource.
Alkim, E., Barreto, P. S. L. M., Bindel, N., Longa, P., and Ricardini, J. E. (2019). The Lattice-Based Digital Signature Scheme qTESLA. Cryptology ePrint Archive, Report 2019/085.
Alkim, E., Bos, J. W., Ducas, L., Longa, P., Mironov, I., Naehrig, M., Nikolaenko, V., Peikert, C., and Raghunathan, A. (2020). FrodoKEM Learning With Errors Key Encapsulation Algorithm Specifications And Supporting Documentation.
Bernstein, D. J., Hallgren, S., Vollmer, U., Buchmann, J., Dahmen, E., Szydlo, M., Overbeck, R., Sendrier, N., Micciancio, D., Regev, O., Ding, J., and Yang, B.-Y. (2008). Post Quantum Cryptography. Springer Publishing Company, Incorporated, Berlin Heidelberg, 1st edition.
Bernstein, D. J., Lange, T., Cayrel, P.-L., and Peters, C. (2022). Lattice-based public-key cryptography. http://pqcrypto.org/lattice.html, accessed on MAY 26th, 2022.
CSRC, N. (2022). Post-quantum cryptography. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/, accessed on MAY 26th, 2022.
Ducas, L., Durmus, A., Lepoint, T., and Lyubashevsky, V. (2013). Lattice Signatures and Bimodal Gaussians. Cryptology ePrint Archive, Report 2013/383.
Dwarakanath, N. C. and Galbraith, S. D. (2014). Sampling from discrete gaussians for lattice-based cryptography on a constrained device. Applicable Algebra in Engineering, Communications and Computing, 25(3):159–180.
Harwit, M. and Sloane, N. J. A. (1979). Appendix Hadamard and s-matrices, Walsh functions, pseudo-random sequences, and the fast Hadamard transform. In Hadamard Transform Optics, pages 200–228. Elsevier Inc.
Howe, J., Prest, T., Ricosset, T., and Rossi, M. (2019). Isochronous gaussian sampling: From inception to implementation with applications to the falcon signature scheme. Pages 1–23.
Kocher, P. C. (1996). Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In Koblitz, N., editor, Advances in Cryptology - CRYPTO ’96, pages 104–113, Berlin Heidelberg, Springer-Verlag. LNCS 1109.
Lyubashevsky, V., Peikert, C., and Regev, O. (2013). On ideal lattices and learning with errors over rings. J. ACM, 60(6):43:1–43:35.
Micciancio, D. (2022). Sampling, Lattice Cryptography. http://cseweb.ucsd.edu/daniele/LatticeLinks/Sampling.html, accessed on MAY 26th, 2022.
Micciancio, D. and Walter, M. (2018). Gaussian sampling over the integers: Efficient, generic, constant-time.
Ortiz, J. N., Aranha, D. F., and Dahab, R. (2015). Implementaça?o em Tempo Constante de Amostragem de Gaussianas Discretas. SBSeg 2015.
Peikert, C. (2014). Lattice Cryptography for the Internet. In Mosca, M., editor, Post-Quantum Cryptography 6th International Workshop, Lecture Notes in Computer Science, pages 197–219, Switzerland. Springer International Publishing.
Pöppelman, T., Alkim, E., Avanzi, R., Bos, J., Ducas, L., de la Piedra, A., Schwabe, P., and Stebila, D. (2019). NewHope Algorithm Specifications and Supporting Documentation. c/o Thomas Po?ppelmann, Infineon Technologies AG, Am Campeon 1-12, 85579 Neubiberg, Germany, version 1.03 edition.
Rader, C. M. (1969). A new method of generating Gaussian random variables by computer. Technical Report 1969-49, Massachusetts Institute of Technology, Lexington, Massachusetts.
Regev, O. (2009). On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6):34:1–34:40.
Reparaz, O., Balasch, J., and Verbauwhede, I. (2016). Dude, is my code constant time? Cryptology ePrint Archive, Report 2016/1123.
Sylvester, J. J. (1867). Lx. thoughts on inverse orthogonal matrices, simultaneous sign-successions, and tessellated pavements in two or more colours, with applications to newton’s rule, ornamental tile-work, and the theory of numbers. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 34(232):461–475.
Weisstein, E. W. (2021). Probability Density Function. From MathWorld–A Wolfram Web Resource.
Publicado
12/09/2022
Como Citar
BARBADO JÚNIOR, Márcio.
Efficient Gaussian sampling for RLWE-based cryptography through a fast Fourier transform. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 22. , 2022, Santa Maria.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 195-208.
DOI: https://doi.org/10.5753/sbseg.2022.224430.
