Comparison of the quality of sampling algorithms from discrete normal distribution on NTRU lattices
DOI:
https://doi.org/10.30837/rt.2022.2.209.03Keywords:
electronic signature, post-quantum cryptography, sampling algorithm, NTRU latticeAbstract
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
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).