Abstract
The Number Theoretic Transform (NTT) is a critical computational component for polynomial multiplication in lattice-based cryptography, the leading candidate for post-quantum security. However, implementing NTT efficiently on resource-constrained edge devices is challenging due to costly modular division and complex data dependencies. This paper presents BP-NTT, a hardware-algorithm co-design that accelerates NTT directly within standard SRAM caches. By introducing a bit-parallel modular multiplication algorithm and a tile-based data layout that enables "costless" shifts, BP-NTT achieves up to 29× higher throughput-per-area and 2.8–100× better energy efficiency compared to state-of-the-art accelerators.
Introduction: The Post-Quantum Bottleneck
As quantum computing advances, traditional public-key encryption schemes like RSA and ECC face obsolescence. Lattice-based cryptography has emerged as a robust alternative, but its primary operation—polynomial multiplication accelerated via the Number Theoretic Transform (NTT)—is computationally intensive.
Current hardware acceleration strategies for NTT face three primary hurdles. First, the "Memory Wall" creates a bottleneck where moving data between the processor and memory consumes more time and energy than the computation itself. Second, the mathematical complexity of modular multiplication is difficult to map onto parallel architectures. Finally, many existing In-Memory Computing (IMC) solutions rely on non-standard hardware like ReRAM, which is difficult to manufacture and often lacks the flexibility to handle varying security parameters.
The BP-NTT Architecture
BP-NTT addresses these challenges by repurposing standard 6T SRAM—the technology used in modern CPU caches—into a massive parallel computation engine. This approach requires less than a 2% area increase over conventional SRAM, making it highly practical for integration into existing chip architectures.
In-SRAM Bitline Computing
The system leverages bitline computing by activating multiple rows in an SRAM subarray simultaneously. By modifying the sense amplifiers, the hardware can perform fundamental bitwise logic (AND, NOR, XOR) and 1-bit shifts directly within the memory array. This eliminates the need to move data to a separate logic unit, effectively bypassing the memory wall.
Bit-Parallel Modular Multiplication
While many IMC designs are "bit-serial" (processing one bit at a time), BP-NTT introduces a novel bit-parallel algorithm based on Montgomery multiplication. This algorithm operates on entire words in parallel, significantly reducing the latency typically associated with in-memory arithmetic. To maximize speed, the design utilizes a carry-save-style approach, maintaining "Sum" and "Carry" vectors separately during computation to prevent the delays inherent in traditional carry propagation.
Tile-Based Data Layout and Costless Shifts
A significant innovation in BP-NTT is the "tile-based" data layout. Polynomial coefficients are organized into specific tiles within the SRAM. This organization allows the system to perform "costless shifts." Instead of physically moving data across the chip to align it for the next stage of the NTT, the system simply adjusts the row addresses it accesses. This architectural trick effectively performs data alignment for free, further boosting efficiency.
Evaluation and Key Insights
The researchers evaluated BP-NTT using parameters from NIST-standardized algorithms, including CRYSTALS-Dilithium and CRYSTALS-Kyber, as well as various Homomorphic Encryption (HE) benchmarks. The design was simulated at the 45nm technology node using a toolchain comprising PyMTL3 for hardware modeling and OpenRAM for SRAM generation.
Performance Metrics
Compared to state-of-the-art in-memory, ASIC, and FPGA solutions, BP-NTT demonstrates significant advantages:
- Throughput-per-Area: Provides up to 29× higher throughput per unit of area.
- Energy Efficiency: Achieves 10× to 138× better throughput-per-power (KNTT/mJ).
- Compact Footprint: For a 128-point NTT, BP-NTT requires only 4,288 SRAM cells, a fraction of the 500,000+ cells required by some ReRAM-based designs.
Placement and Security
Through roofline modeling, the authors determined that NTT kernels are primarily bounded by L1 and L2 cache bandwidth rather than main memory (DRAM) bandwidth. This justifies placing the BP-NTT accelerator in the Last-Level Cache (LLC). Furthermore, by keeping computation on-chip within the CPU's cache, BP-NTT maintains a "trusted computing base," preventing side-channel attackers from snooping on sensitive data as it travels to off-chip memory.
Conclusion and Future Work
BP-NTT represents a significant step forward in making post-quantum cryptography viable for edge devices. While it offers superior throughput and efficiency, it does face a trade-off in raw latency compared to highly specialized, hard-wired ASICs. Additionally, as coefficient bitwidths increase, the degree of parallelism within a single SRAM subarray naturally decreases.
Future research will focus on expanding the BP-NTT framework to support a wider array of cryptographic kernels, potentially evolving the design into a universal, programmable in-cache crypto-processor capable of handling the diverse demands of the post-quantum era.
Summary updated