BP-NTT: Fast and Compact in-SRAM Number Theoretic Transform with Bit-Parallel Modular Multiplication

Jingyao Zhang, Mohsen Imani, Elaheh Sadredini

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

Abstract

Number Theoretic Transform (NTT) is an essential mathematical tool for computing polynomial multiplication in promising lattice-based cryptography. However, costly division operations and complex data dependencies make efficient and flexible hardware design to be challenging, especially on resource-constrained edge devices. Existing approaches either focus on only limited parameter settings or impose substantial hardware overhead. In this paper, we introduce a hardware-algorithm methodology to efficiently accelerate NTT in various settings using in-cache computing. By leveraging an optimized bit-parallel modular multiplication and introducing costless shift operations, our proposed solution provides up to 29x higher throughput-per-area and 2.8-100x better throughput-per-area-per-joule compared to the state-of-the-art.
BibTeX
@inproceedings{zhang2023bp,
  author = {Jingyao Zhang and Mohsen Imani and Elaheh Sadredini},
  title = {{BP-NTT: Fast and Compact in-SRAM Number Theoretic Transform with Bit-Parallel Modular Multiplication}},
  booktitle = {DAC},
  year = {2023},
  url = {https://openreview.net/forum?id=PHya_4vVwI},
}
Figure