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


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



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


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.


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:

Thomas Prest et Al. aFlcon: Fast-Fourier Lattice-basedCompact Signatures over NTRU. Access mode:

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: (дата звернення: 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:

Phong Q. Nguyen, Oded Regev Learning a Parallelepiped: Cryptoanalysis of GGH and NTRU Signatures. Access mode:

Thomas Espitau et all. MITAKA: A Simpler, Parallelizable Maskable Variant of Falcon. Access mode:

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:

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),

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:

PQC Standardization Process: Third Round Candidate Announcement. July 22, 2020. [Electronic resource]. Access mode:



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.




Most read articles by the same author(s)

1 2 3 4 > >>