TL;DR
This paper introduces LEAF, a novel hardware accelerator for the FALCON post-quantum signature verification process, specifically designed for resource-constrained devices. LEAF achieves significant reductions in resource usage and area-time product compared to existing state-of-the-art designs, making FALCON more practical for applications like IoT.
What Problem Does This Paper Address?
The advent of quantum computers poses a threat to current cryptographic systems, driving the development of post-quantum cryptography (PQC). The National Institute of Standards and Technology (NIST) has selected several PQC algorithms, including FALCON, which offers attractive features like compact key sizes and fast signature verification. However, FALCON's computational complexity has hindered the development of efficient hardware accelerators, especially for resource-limited environments. Existing hardware solutions often target high-performance applications, leaving a gap for lightweight and efficient implementations suitable for devices like those in the Internet of Things (IoT). This paper aims to fill that gap by presenting a lightweight and efficient hardware accelerator for FALCON's signature verification.
Methods
The LEAF accelerator employs several key strategies to achieve its lightweight and efficient design:
- Optimized Algorithmic Primitives:
- Modular Reduction: Instead of standard Montgomery or Barrett methods, LEAF uses a specialized algorithm tailored for the FALCON modulus (q=12,289) that reduces expensive multiplications to accumulations, requiring fewer pipeline stages.
- Number Theoretic Transform (NTT): A unified Constant-Geometry (CG) based NTT/INTT algorithm is used. This algorithm offers a simplified memory access pattern, reducing address management complexity. It also cleverly stores only forward NTT twiddle factors and dynamically computes inverse NTT twiddle factors, saving ROM usage.
- Hashing: A "mid-range" Keccak hashing core is utilized for the HashToPoint function, balancing resource usage with performance.
- Novel Data Dependency Flow and Scheduling: The paper proposes a new data dependency flow that meticulously schedules operations to maximize the utilization of a single Digital Signal Processor (DSP). This approach minimizes idle time and efficiently processes polynomial multiplications, subtractions, squarings, and accumulations.
- Hardware Architecture: LEAF is a full-hardware implementation comprising several modules: Decoding, Keccak Hashing Core, Data Memory (using block RAMs), Twiddle Memory (using ROM), a Polynomial Arithmetic Core (PAC) powered by a single DSP, a Norm Accumulator, and a Control Unit. The PAC is configurable to perform various arithmetic operations (NTT, INTT, multiplication, squaring) as needed.
Datasets
Not discussed in the paper. The evaluation relies on FPGA implementation results and comparisons with existing literature.
Key Insights and Ideas
- Lightweight Design for PQC is Crucial: The paper strongly advocates for and demonstrates the feasibility of lightweight hardware acceleration for PQC, opening doors for its adoption in resource-constrained environments like IoT.
- Tailoring Primitives for Specific Moduli: The success of the specialized modular reduction algorithm highlights the benefit of optimizing cryptographic primitives for the specific parameters of a given scheme, rather than relying on general-purpose methods.
- Unified NTT/INTT for Efficiency: The proposed unified CG-based NTT/INTT algorithm is a significant contribution, simplifying memory access and reducing ROM requirements, which are critical for lightweight designs.
- Single DSP Optimization: Demonstrating that a complex operation like FALCON signature verification can be efficiently handled by a single DSP through clever scheduling and dataflow is a key insight into resource-efficient hardware design.
- Trade-offs in PQC Acceleration: The paper implicitly shows that there's a spectrum of PQC hardware acceleration, from high-performance to lightweight, and LEAF carves out a valuable niche at the latter end.
Key Results
LEAF demonstrates significant improvements in resource utilization and performance metrics:
- Resource Usage: LEAF achieves 65% and 66% less aggregate resource usage (ENS) for FALCON-512 and FALCON-1024, respectively, compared to the state-of-the-art full-hardware accelerator [8].
- Area-Time Product (eATP): LEAF achieves 24% and 14% less equivalent area-time product (eATP) for FALCON-512 and FALCON-1024, respectively, compared to [8].
- Comparison with HLS/HW-SW Co-design: LEAF offers substantial reductions in eATP (97%-99%) compared to HLS-based and hardware-software co-design approaches.
- NTT Core Performance: The LEAF-NTT core itself shows competitive results, offering lower ENS and eATP compared to other NTT-based polynomial multiplication works, while also avoiding the latency penalty of bit-reversal re-ordering.
Limitations and Future Work
- Limitations:
- The paper acknowledges that some higher-radix NTT designs might outperform LEAF in eATP, but argues that LEAF's approach is more suitable for applications where message size is a concern and resource usage is paramount.
- While LEAF is efficient, it might not be the absolute fastest for applications that can tolerate much larger resource footprints.
- Future Work:
- Develop innovative techniques for other phases of FALCON (e.g., signature generation).
- Extend these design principles to other PQC schemes.
- Explore side-channel resistant acceleration techniques for FALCON.
Summary updated