Generation of system-wide parameters for Falcon cryptosystem for 256, 384, 512 bits of security
DOI:
https://doi.org/10.30837/rt.2020.3.202.05Keywords:
algebraic lattice, attacks, security, system-wide parameters, signature, polynomial, Falcon.Abstract
Globally, the efforts of a significant number of crypto-theorists, mathematicians and cryptologists-practitioners are focused on the NIST PQC open competition. One of the main tasks of the competition consists in development and adoption of a post-quantum ES standard or standards. The finalists of the second stage of the NIST competition were three ES mechanisms – CRYSTALS-DILITHIUM, Falcon and Rainbow. In addition, three alternative candidates were identified that require more detailed research. In general, a comprehensive analysis of the finalists is an important task for cryptologists in the global cryptocommunity. Moreover, security, i.e. brining the cryptographic stability of two finalist candidates, to the ES standard – CRYSTALS-DILITHIUM and Falcon, is based on problems in the theory and practice of algebraic lattices. Studies show that among the ES schemes on lattices it differs slightly from other candidates and has prospects for the adoption as the Falcon algorithm standard. The main and dominant approach to the design of the Falcon ES mechanism is the use of the Fiat-Shamir transformation with interruptions. The sets of system-wide parameters that ensure resistance to all known and potential attacks should be found for the safe use of the Falcon ES. In the process of forming the requirements for ES within the competition, the NIST was interested only in sets of system-wide parameters up to 256 bits of classical security inclusive. However, according to the authors of this work, in the future it is advisable to provide at least 384 and 512 bits of security for classical cryptanalysis and at least 192 and 256 bits of security for quantum cryptanalysis. The article briefly considers the essence of the Falcon electronic signature (ES) algorithm. An analysis of possible attacks on the algorithm and the mechanisms of their implementation is also performed. The process of generating system-wide parameters for 256, 384, 512 stability bits is considered. Conclusions and recommendations are given. The objective of the work is the classification and initial analysis of known attacks on the ES Falcon cryptosystem, setting limits and developing practical algorithms for calculating (generating) system-wide parameters to provide not less than 256, 384 and 512 security bits for classical and not less than 128, 192 and 256 security bits for quantum cryptanalysis.References
Gorjan 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, Angela Robinson, Daniel Smith-Tone // 22 July 2020. Режим доступу: https://doi.org/10.6028/NIST.IR.8309.
Сryptography Standardization Process. Electronic resource]. Access mode: http://www.nist.gov/pqcrypto.
Post-Quantum Cryptography. Round 2 Submissions. [Electronic resource]. Access mode: https://csrc.nist.gov/Projects/post-quantum-cryptography/round-2-submissions.
Falcon. [Electronic resource]. Access mode: https://csrc.nist.gov/projects/post-quantum-cryptography/round-1-submissions.
Eike Kiltz, Vadim Lyubashevsky, and Christian Schaffner. A concrete treatment of fiat-shamir signatures in the quantum random-oracle model. Cryptology ePrint Archive, Report 2017/916, 2017. [Electronic resource]. Access mode: http://eprint.iacr.org/2017/916.
Dominique Unruh. Post-quantum security of fiat-shamir // IACR Cryptology ePrintArchive, 2017:398, 2017.
Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and newcryptographic constructions // Richard E. Ladner and Cynthia Dwork, editors,40th ACM STOC,pages 197–206. ACM Press, May 2008.
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
Daniele Micciancio and Michael Walter. Practical, predictable lattice basis reduction // Marc Fischlin and Jean-Sébastien Coron, editors,EUROCRYPT 2016, Part I, volume9665 ofLNCS, pages 820–849, Vienna, Austria, May 8–12, 2016. Springer, Heidelberg,Germany.
Thomas Prest. Sharper bounds in lattice-based cryptography using the Rényi divergence // Takagiand Peyrin [TP17], pages 347–374.
Martin R. Albrecht, Shi Bai, and Léo Ducas. A subfield lattice attack on overstretchedNTRU assumptions – cryptanalysis of some FHE and graded encoding schemes // Matthew Robshaw and Jonathan Katz, editors,CRYPTO 2016, Part I, volume 9814 ofLNCS, pages 153–178, Santa Barbara, CA, USA, August 14–18, 2016. Springer, Heidel-berg, Germany.
Thomas Prest.Gaussian Sampling in Lattice-Based Cryptography // Theses, École NormaleSupérieure, December 2015
Downloads
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).
