A Lightweight Variant of Falcon for Efficient Post-Quantum Digital Signature
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 pos...
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-07-01
|
| Series: | Information |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2078-2489/16/7/564 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1839615901576462336 |
|---|---|
| author | Aigerim Kerimbayeva Maksim Iavich Yenlik Begimbayeva Sergiy Gnatyuk Sakhybay Tynymbayev Zhanerke Temirbekova Olga Ussatova |
| author_facet | Aigerim Kerimbayeva Maksim Iavich Yenlik Begimbayeva Sergiy Gnatyuk Sakhybay Tynymbayev Zhanerke Temirbekova Olga Ussatova |
| author_sort | Aigerim Kerimbayeva |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-a54e52a9e5bb4b5198ff8eb5f9824d44 |
| institution | Matheson Library |
| issn | 2078-2489 |
| language | English |
| publishDate | 2025-07-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Information |
| spelling | doaj-art-a54e52a9e5bb4b5198ff8eb5f9824d442025-07-25T13:25:07ZengMDPI AGInformation2078-24892025-07-0116756410.3390/info16070564A Lightweight Variant of Falcon for Efficient Post-Quantum Digital SignatureAigerim Kerimbayeva0Maksim Iavich1Yenlik Begimbayeva2Sergiy Gnatyuk3Sakhybay Tynymbayev4Zhanerke Temirbekova5Olga Ussatova6Department of Cybersecurity, Information Processing and Storage, Satbayev University, 22 Satbayev Str., Almaty 050013, KazakhstanSchool of Technology, Caucasus University, 1 Paata Saakadze Str., Tbilisi 0102, GeorgiaInstitute of Information and Computational Technologies CS MSHE RK, Energo University, 28 Shevchenko Str., Almaty 050010, KazakhstanFaculty of Computer Science and Technology, State University “Kyiv Aviation Institute”, 1 Liubomyra Huzara Ave., 03058 Kyiv, UkraineFaculty of Computer Technology and CyberSecurity, International Information Technology University, Manasa Str. 34/1, Almaty 050040, KazakhstanFaculty of Information Technology, Al-Farabi Kazakh National University KazNU, Str. 75/10, Almaty 050040, KazakhstanInstitute of Information and Computational Technologies CS MSHE RK, Energo University, 28 Shevchenko Str., Almaty 050010, KazakhstanConventional 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.https://www.mdpi.com/2078-2489/16/7/564post-quantum cryptographydigital signaturefast Fourier transformGaussian distributionNTRU lattices |
| spellingShingle | Aigerim Kerimbayeva Maksim Iavich Yenlik Begimbayeva Sergiy Gnatyuk Sakhybay Tynymbayev Zhanerke Temirbekova Olga Ussatova A Lightweight Variant of Falcon for Efficient Post-Quantum Digital Signature Information post-quantum cryptography digital signature fast Fourier transform Gaussian distribution NTRU lattices |
| title | A Lightweight Variant of Falcon for Efficient Post-Quantum Digital Signature |
| title_full | A Lightweight Variant of Falcon for Efficient Post-Quantum Digital Signature |
| title_fullStr | A Lightweight Variant of Falcon for Efficient Post-Quantum Digital Signature |
| title_full_unstemmed | A Lightweight Variant of Falcon for Efficient Post-Quantum Digital Signature |
| title_short | A Lightweight Variant of Falcon for Efficient Post-Quantum Digital Signature |
| title_sort | lightweight variant of falcon for efficient post quantum digital signature |
| topic | post-quantum cryptography digital signature fast Fourier transform Gaussian distribution NTRU lattices |
| url | https://www.mdpi.com/2078-2489/16/7/564 |
| work_keys_str_mv | AT aigerimkerimbayeva alightweightvariantoffalconforefficientpostquantumdigitalsignature AT maksimiavich alightweightvariantoffalconforefficientpostquantumdigitalsignature AT yenlikbegimbayeva alightweightvariantoffalconforefficientpostquantumdigitalsignature AT sergiygnatyuk alightweightvariantoffalconforefficientpostquantumdigitalsignature AT sakhybaytynymbayev alightweightvariantoffalconforefficientpostquantumdigitalsignature AT zhanerketemirbekova alightweightvariantoffalconforefficientpostquantumdigitalsignature AT olgaussatova alightweightvariantoffalconforefficientpostquantumdigitalsignature AT aigerimkerimbayeva lightweightvariantoffalconforefficientpostquantumdigitalsignature AT maksimiavich lightweightvariantoffalconforefficientpostquantumdigitalsignature AT yenlikbegimbayeva lightweightvariantoffalconforefficientpostquantumdigitalsignature AT sergiygnatyuk lightweightvariantoffalconforefficientpostquantumdigitalsignature AT sakhybaytynymbayev lightweightvariantoffalconforefficientpostquantumdigitalsignature AT zhanerketemirbekova lightweightvariantoffalconforefficientpostquantumdigitalsignature AT olgaussatova lightweightvariantoffalconforefficientpostquantumdigitalsignature |