Quantum computing, an emerging technology, is set to challenge existing cryptographic algorithms. FALCON, a quantum-resistant digital signature, is difficult to implement due to its extensive noninteger polynomial operations. Tech giants like IBM, Intel, and Google are developing superconducting quantum processors. The National Institute of Standards and Technology (NIST) has initiated a post-quantum standardization process for new Post-Quantum Cryptography (PQC) algorithms. FALCON, known for its quantum security and efficiency, is expected to be popular for IoT applications. However, its implementation on resource-constrained devices is challenging. This paper proposes a processor optimized for FALCON applications on such devices.
Quantum Computing and Cryptography
Quantum computing is an emerging technology that is poised to reshape industries and challenge existing cryptographic algorithms. FALCON, a recent standard quantum-resistant digital signature, presents a challenging hardware implementation due to its extensive noninteger polynomial operations necessitating FFT over the ring Qxxn1. Several leading tech companies, including IBM, Intel, and Google, are currently working on developing superconducting quantum processors. Although these quantum computers are not yet powerful enough to pose a threat, they represent a significant step toward the development of more powerful quantum technology in the future.
Post-Quantum Cryptography and FALCON
To prepare for the post-quantum era, a new round of cryptosystem innovation has recently been initiated and become an active research topic. The National Institute of Standards and Technology (NIST) has launched a post-quantum standardization process for standardizing new Post-Quantum Cryptography (PQC) algorithms that remain secure even in worst-case scenarios when an attacker has a quantum computer. As a result of this standardization process, several Digital Signature (DS) and Key Encapsulation Mechanism (KEM) cryptosystems that are believed to be quantum-resistant have been identified and selected for standardization, such as SPHINCS, CRYSTALS-KYBER, CRYSTALS-Dilithium, and FALCON.
FALCON’s Advantages and Challenges
FALCON is a digital signature algorithm known for its quantum security and efficiency in terms of communication bandwidth and verification simplicity. It is expected to be a popular choice for IoT applications due to its smaller signature and public key size and faster verification process compared to other signature schemes like CRYSTALS-Dilithium. However, FALCON is not naturally hardware-friendly and this poses a challenge for implementation on resource-constrained devices typically found in IoT scenarios. These devices have low power budgets, limited computation capabilities, small memory, and/or low communication bandwidth. Any hardware implementation of FALCON should be designed to take into account these constraints.
FFT Calculations in FALCON
FALCON consists of three main stages: key generation, signing, and verification. The key generation and signing heavily rely on Fast Fourier Transform (FFT) calculations. In fact, FFT accounts for 26% and 48% of the total clock cycles at key generation and signing processes respectively. To claim meaningful security bounds for FALCON, FFT with double-precision Floating-Point (FP) arithmetic is required. However, this poses a significant limitation for resource-constrained devices that lack a Floating-Point Unit (FPU).
Proposed Processor for FFT/IFFT Operations
This paper introduces an ultralow power and compact processor tailored for FFT/IFFT operations over the ring, specifically optimized for FALCON applications on resource-constrained edge devices. The proposed processor incorporates various optimization techniques including twiddle factor compression and conflict-free scheduling. In an ASIC implementation using a 22 nm GF process, the proposed processor demonstrates an area occupancy of 0.015 mm2 and a power consumption of 1.26 mW at an operating frequency of 1.67 MHz. This suggests that the proposed hardware design offers a promising solution for implementing FALCON on resource-constrained devices.
“Area and Power Efficient FFT/IFFT Processor for FALCON Post-Quantum Cryptography“ is an article authored by Ghada Alsuhli, Hani Saleh, Mahmoud Al‐Qutayri, Baker Mohammad, and T. Stouraitis. The article was published on January 19, 2024, and can be accessed through its DOI reference https://doi.org/10.48550/arxiv.2401.10591. The source of the article is arXiv (Cornell University).
