Comparison of the quality of sampling algorithms from discrete normal distribution on NTRU lattices

Authors

  • I.D. Gorbenko Харківський національний університет імені В. Н. Каразіна, АТ “Інститут Інформаційних Технологій”, Ukraine https://orcid.org/0000-0003-4616-3449
  • С.О. Kandiy Харківський національний університет імені В. Н. Каразіна, АТ «Інститут Інформаційних технологій», Ukraine
  • Ye.V. Ostrianska АТ «Інститут Інформаційних технологій», Ukraine

DOI:

https://doi.org/10.30837/rt.2022.2.209.03

Keywords:

electronic signature, post-quantum cryptography, sampling algorithm, NTRU lattice

Abstract

Post-quantum cryptography is a field of research that studies cryptographic transformations protected against attacks using quantum computers. For many years, lattice-based cryptography has become one of the most promising solutions to protect against the threat of quantum computing. An important feature of the post-quantum period in cryptography is the significant uncertainty about the source data for cryptanalysis and countermeasures in the capabilities of quantum computers, their mathematical support and software, as well as the application of quantum cryptanalysis to existing cryptocurrencies and cryptoprotocol. The main methods are mathematical methods of electronic signature, which have undergone significant analysis and justification in the process of extensive research by cryptologists and mathematicians at the highest level. The security of signature schemes depends strongly on the standard deviation of the discrete Gaussian distribution, which has a sampling algorithm. In this paper, the most common variants of sampling algorithms were considered and analyzed, because the quality of all algorithms depends significantly on the structure of the lattice for which sampling takes place. A comparison of the quality of lattice sampling algorithms is highlighted. In particular, the paper considers Klein's algorithms (its modification is the Thomas Prest and Dukas algorithm), Peikert's algorithm and the floating-point sampling algorithm. Klein's sampling algorithm, in particular its modification, namely, the Dukas-Prest algorithm, gives the smallest vectors. Theoretically, it is much better than Klein's algorithm on NTRU lattices, but it requires the use of floating-point arithmetic, which complicates greatly the analysis of its security and tocreation of software or hardware implementation.

References

Gorhan Alagic Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process. NISTIR 8309 / Gorjan Alagic, Jacob Alperin-Sheriff, Daniel Apon, David Cooper, Quynh Dang, John Kelsey, Yi-Kai Liu, Carl Miller, Dustin Moody, Rene Peralta, Ray Perlner

Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler and Damien Stehlé CRYSTALS-Dilithium: Algorithm Specifications and Supporting Documentation. Access mode: https://pq-crystals.org/dilithium/data/dilithium-specification.pdf

Thomas Prest et Al. aFlcon: Fast-Fourier Lattice-basedCompact Signatures over NTRU. Access mode: https://falcon-sign.info/falcon.pdf

NISTR 8309. Status Report on the Second Round of the NIST Post-Quantum Cryptography Standartization Process. NIST, 2020. 39 p.

NIST Post-Quantum Cryptography Standartization Project : веб сайт. URL: https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization (дата звернення: 27.11.2020)

Craig Gentry, Chris Peikert, Vinod Vaikuntanathan How to Use a Short Basis: Trapdoors for Hard Lattices and New Cryptographic Constructions. -Access mode: https://eprint.iacr.org/2007/432.pdf

Phong Q. Nguyen, Oded Regev Learning a Parallelepiped: Cryptoanalysis of GGH and NTRU Signatures. Access mode: https://iacr.org/archive/eurocrypt2006/40040273/40040273.pdf

Thomas Espitau et all. MITAKA: A Simpler, Parallelizable Maskable Variant of Falcon. Access mode: https://eprint.iacr.org/2021/1486.pdf

Ducas L., Galbraith S., Prest T., Yu Y.: Integral matrix gram root and lattice gaussian sampling without floats // Canteaut A., Ishai Y. (eds.) EUROCRYPT 2020, Part II. LNCS, vol. 12106, pp. 608–637. Springer, Heidelberg (May 2020).

Thoms Prest Gaussian Sampling in Lattice-Based Cryptography. Access mode: https://tprest.github.io/pdf/pub/thesis-thomas-prest.pdf

Garillot F., Kondi Y., Mohassel P., Nikolaenko V. Threshold schnorr with stateless deterministic signing from standard assumptions // Malkin, T., Peikert, C.(eds.) Advances in Cryptology – CRYPTO 2021. pp. 127–156. Springer International Publishing, Cham (2021)

Fukumitsu M., Hasegawa S. A lattice-based provably secure multisignature scheme in quantum random oracle model // Nguyen, K., Wu, W., Lam, K.Y.,Wang, H. (eds.) Provable and Practical Security. pp. 45–64. Springer International Publishing, Cham (2020)

Esgin M.F., Steinfeld R., Sakzad A., Liu J.K., Liu D. Short lattice-based one-out-of-many proofs and applications to ring signatures. Cryptology ePrint Archive, Report 2018/773 (2018), https://ia.cr/2018/773

Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Prest, Thomas Ricosset, Gregor Seiler, William Whyte, Zhenfei Zhang. Falcon: Fast-Fourier Lattice-basedCompact Signatures over NTRU. [Electronic resource]. Access mode: https://falcon-sign.info/falcon.pdf.

PQC Standardization Process: Third Round Candidate Announcement. July 22, 2020. [Electronic resource]. Access mode: https://csrc.nist.gov/News/2020/pqc-third-round-candidate-announcement

Published

2022-06-24

How to Cite

Gorbenko, I. ., Kandiy С. ., & Ostrianska, Y. . (2022). Comparison of the quality of sampling algorithms from discrete normal distribution on NTRU lattices. Radiotekhnika, 2(209), 29–37. https://doi.org/10.30837/rt.2022.2.209.03

Issue

Section

Articles