The article discusses the analysis of the essence and protection possibilities of the Falcon post-quantum signature. The main properties of the Falcon signature are considered. An estimate of what resources and computing power is required to use successfully the Falcon signature. A structural analysis of the Falcon signature is performed. The GPV and Rabina frameworks are analyzed. Detailed conclusions are made regarding the conducted analyses. The stability and complexity of the GPV and Rabin frameworks are evaluated, the main structures and protocols of these frameworks are considered. A detailed analysis of the main properties of NTRU lattices is carried out, the main rules of factorization of the GPV and Rabin frameworks are considered. Fast Fourier sampling is investigated. Conclusions are made regarding each conducted study.
The article discusses the analysis of the essence and protection possibilities of the Falcon post-quantum signature. The main properties of the Falcon signature are considered. An estimate of what resources and computing power is required to use successfully the Falcon signature. A structural analysis of the Falcon signature is performed. The GPV and Rabina frameworks are analyzed. Detailed conclusions are made regarding the conducted analyses. The stability and complexity of the GPV and Rabin frameworks are evaluated, the main structures and protocols of these frameworks are considered. A detailed analysis of the main properties of NTRU lattices is carried out, the main rules of factorization of the GPV and Rabin frameworks are considered. Fast Fourier sampling is investigated. Conclusions are made regarding each conducted study.
This paper presents a comparative analysis of two lattice-based post-quantum digital signature schemes: FALCON and SOLMAE. FALCON which was finallty selected by NIST for PQC standardization, represents an efficient realization of the GPV framework over NTRU lattices. SOLMAE, inspired by FALCON, Mitaka, and Antrag, aims to improve implementation simplicity and performance while preserving strong security guarantees. Adopting a pedagogical approach, we provide algorithmic insights into both schemes and conduct practical evaluations using their Python implementations, focusing on key generation, signing, and verification procedures. Performance comparisons at two NIST security levels (512 and 1024 bits) highlight SOLMAE’s potential advantages in simplicity and execution time, suggesting its suitability for deployment in resource-constrained environments.
Falcon is an efficient and secure postquantum signature scheme for services based on quantum computing. It employs the hash-and-sign approach in conjunction with the Gentry, Peikert, and Vaikuntanathan (GPV) framework on Number Theory Research Unit (NTRU) lattices. This study evaluated the operation procedure and the capacity to run the Falcon scheme using a key length of 1024 bits on different hardware and software platforms, such as personal computers and Raspberry Pi 4 and Windows, Ubuntu, and Android operating systems. The following results were obtained: file sizes ranged from 30 to 5449268 KB, digital signature times ranged from 50 to 19500ms, and signature verification times ranged from 14 to 19000ms. The results show that the Falcon post-quantum signature scheme works stably and ensures execution speed on different platforms, similar to current digital signature schemes.
Conventional public-key cryptographic systems are increasingly threatened by advances in quantum computing, accelerating the need for robust post-quantum cryptographic solutions. Among these, Falcon, a compact lattice-based digital signature scheme, has emerged as a leading candidate in the NIST post-quantum standardization process due to its efficiency and theoretical security grounded in hard lattice problems. This work introduces Falcon-M, a modified version of the Falcon algorithm that significantly reduces implementation complexity. It does so by replacing Falcon’s intricate trapdoor-based key-generation mechanism with a simplified approach that utilizes randomized polynomial Gaussian sampling and fast Fourier transform (FFT) operations. Falcon-M incorporates SHA-512 hashing and discrete Gaussian sampling to preserve cryptographic soundness and statistical randomness while maintaining the core structure of Falcon’s signing and verification processes. We formally specify the Falcon-M algorithm, provide an updated pseudocode, and offer a comparative analysis with the original Falcon in terms of algorithmic complexity, security assumptions, and implementation overhead. Additionally, we present formal lemmas and theorems to ensure correctness and define theoretical bounds on forgery resistance. Although Falcon-M does not rely on a formal cryptographic trapdoor, we demonstrate that it achieves strong practical security based on assumptions related to the Short Integer Solution (SIS) problem. Falcon-M is thus well-suited for lightweight post-quantum applications, particularly in resource-constrained environments, such as embedded systems and Internet-of-Things (IoT) platforms.
The paper considers post-quantum projects of the Falcon and Dilithium electronic signature standards (ES), which are finalists of the NIST USA competition. The mathematical apparatus of algebraic lattices and appropriate methods are used in their construction. In further study and comparison of these post-quantum ES draft standards, both from a theoretical and practical standpoint, it is fundamental to substantiate the requirements for parameters and keys and in general to calculate the main indicators according to the accepted conditional and unconditional criteria. In such studies, it is important to determine the sufficiency of ensuring the guarantee of their security against classical, quantum, special and error-based attacks. This can be ensured, inter alia, through a reasonable choice of the sizes of common parameters and keys, and their practical construction in accordance with the adopted security model. However, when choosing the sizes of common parameters and keys, a significant contradiction arises between the properties of the draft of the Falcon and Dilithium ES standards, So increasing the size of the general parameters and keys leads to an increase in the complexity of transformations, and vice versa. The purpose of this article consists in analysis of problematic issues of choosing the size of parameter and keys for post-quantum ES projects based on mathematical methods of Falcon and Dilithium, and features of their implementation, including implementation according to the adopted security model. Comparative analysis of the stability and complexity of the Falcon and Dilithium ES draft standards depending on the size of the parameters and keys, including for 6 and 7 security levels. Development of proposals for decisions on the adoption of national post-quantum ES standards based on the mathematical methods Falcon and Dilithium. Determining the influence of unconditional, conditional and pragmatic criteria on the advantages when deciding on the ES standardization based on Falcon and Dilithium mathematical methods, including taking into account the availability of patents and the need to obtain licenses, etc.
An important feature of the post-quantum period in cryptography is the significant uncertainty regarding the source data for cryptanalysis and counteraction in terms of the capabilities of quantum computers, their mathematical and software, as well as the application of quantum cryptanalysis to existing cryptotransformations and cryptoprotocols. Mathematical methods of digital signature (DS) have been chosen as the main methods of NIST USA, which have undergone significant analysis and substantiation in the process of extensive research by cryptographers and mathematicians at the highest level. They are described in detail and studied at the first stage of the US NIST International Competition. In the second round, a number of decisions were made to merge some candidates for the post-quantum DS standard. 9 candidates were left for further research at the 2nd round: Crystals-Dilithium, Falcon, GeMSS, LUOV, MQDSS, Picnic, qTESLA, Rainbow and SPHINCS+. Three of them (Dilithium, Falcon, qTeSLA) are based on the stability of algebraic lattices (Lattice-based), four (GeMSS, LUOV, MQDSS, Rainbow) are based on multivariate transformations (MQ-transformations), one (SPHINCS+) is based on the stability of hash-function, one (Picnic) is based on the stability of the hash-function and block stream ciphers. During the 2nd round of the US NIST Competition the following finalist algorithms and alternative algorithms were selected as digital signatures according to the results of research on promising post-quantum cryptographic algorithms. As finalists algorithms such DS algorithms as Crystals-Dilithium, Falcon and Rainbow. Alternative algorithms are GeMSS, Picnic and SPHINCS+ were selected. This paper studies the peculiarities of construction of the digital signature algorithm considered as a candidate for the promising post-quantum standard of the NIST PQC competition – Picnic, also it analyzes the protection of the algorithm from known attacks. Data from the comparison of post-quantum algorithms such as digital signature are given. The description of the Picnic algorithm and its parameters are given.
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.