💻 computer science

PIP-NTT: Towards a Scalable Memory-Parallelized Accelerator for Iterative NTT in PQC

The paper proposes PIP-NTT, a scalable and memory-parallelized hardware accelerator for iterative Number Theoretic Transforms in post-quantum cryptography that utilizes four smaller memory blocks and a multiplication-free rescaling architecture to achieve significantly higher area-time efficiency compared to existing designs.

Original authors: Malik Imran, Ayesha Khalid, Ciara Rafferty, Safiullah Khan, Muhammad Rashid, Maire O'Neill

Published 2026-07-22

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Malik Imran, Ayesha Khalid, Ciara Rafferty, Safiullah Khan, Muhammad Rashid, Maire O'Neill

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where the locks protecting your bank account, your private messages, and even national secrets are made of paper. For decades, we've relied on mathematical puzzles like factoring huge numbers to keep these locks secure. But scientists have discovered that future "quantum" computers, which operate on the strange rules of quantum physics, could tear these paper locks apart in seconds using a trick called Shor's algorithm. To stop this, cryptographers are building new, super-strong locks based on "lattices"—complex, multi-dimensional grids of numbers. These new locks are the heroes of "Post-Quantum Cryptography" (PQC). However, there's a catch: these new locks are incredibly heavy and slow to use because they require massive amounts of number-crunching. To make them practical for your phone or a smart thermostat, we need to build special, lightning-fast hardware engines that can perform these calculations efficiently without draining the battery or taking up too much space. This is the challenge tackled by a team of researchers who want to make these new digital locks fast enough for the real world.

The paper you're about to read introduces a new hardware engine called PIP-NTT, designed to speed up a specific, crucial math operation called the Number Theoretic Transform (NTT). Think of the NTT as a magical conveyor belt that rearranges a pile of numbers so they can be multiplied together instantly. In the world of lattice-based cryptography (like the ML-KEM scheme recently standardized by NIST), this operation is the heartbeat of the system. If the NTT is slow, the whole security system grinds to a halt. The researchers found that existing engines for this job were often stuck using a "ping-pong" memory system, where data had to bounce back and forth between two large storage bins, creating a traffic jam that slowed everything down. They also noticed that the final step of the process was using a heavy, energy-hungry method to clean up the numbers.

To fix this, the authors built a smarter, more streamlined engine. Instead of two giant storage bins, they used four smaller, faster bins working in parallel, allowing data to flow through the system without waiting in line. They also replaced the heavy cleanup step with a clever, multiplication-free trick that uses simple additions and doublings, saving a ton of space and power. By combining these memory tricks with a highly optimized "butterfly" unit (the tiny calculator that does the actual math), they created a design that is both incredibly fast and surprisingly small. When they tested their creation on a field-programmable gate array (FPGA)—a type of chip that can be reprogrammed to act like custom hardware—they found it was significantly more efficient than anything else currently in the literature. Specifically, their design achieved an "Area-Time Product" (a measure of how much space and time the chip needs to do a job) that was 2.67 times better than the most space-saving designs and 1.48 times better than the fastest high-speed designs. The result is a versatile, scalable engine that could help secure our digital future against the quantum threat without breaking the bank or the battery.

Technical Summary: PIP-NTT: Towards a Scalable Memory-Parallelized Accelerator for Iterative NTT in PQC

Problem Statement
Lattice-based Post-Quantum Cryptography (PQC), specifically schemes like ML-KEM (Kyber) and ML-DSA (Dilithium) standardized by NIST, relies heavily on the Number Theoretic Transform (NTT) for efficient polynomial multiplication. Existing hardware accelerators for iterative NTT face a trade-off between throughput and resource utilization. High-throughput designs often employ deep pipelining and large memory arrays or multiple butterfly units, which incur substantial area overhead unsuitable for resource-constrained platforms. Conversely, area-optimized designs frequently rely on "ping-pong" memory schemes and single butterfly units. While these reduce hardware footprint, they inherently limit scalability, parallelism, and frequency optimization, creating performance bottlenecks. Furthermore, the rescaling step required after the Inverse NTT (INTT) often involves costly modular multiplication or division, adding to the critical path delay.

Methodology
The authors propose "PIP-NTT," a unified, pipelined, and memory-parallelized NTT accelerator designed to balance area efficiency with computational throughput. The methodology is built upon three core innovations:

Unified Pipelined Butterfly Unit (DSE): The authors conducted a comprehensive Design Space Exploration (DSE) of Cooley–Tukey (CT) and Gentleman–Sande (GS) butterfly units. They evaluated eight architectural variants, ranging from a non-pipelined baseline to designs utilizing both coarse-grained and fine-grained pipelining. The optimal design, an 8-stage pipelined butterfly unit (8SP-BU), integrates modular reduction (using the Barrett method) and arithmetic operations with registers placed strategically within the data path to maximize operating frequency while minimizing area overhead.
Multiplication-Free Rescaling: For the INTT rescaling step ( $a \cdot n^{-1} \mod q$ ), the authors exploit the specific congruence of the Kyber modulus ( $q=3329$ ), where $n^{-1} \equiv -13 \pmod{3329}$ . Instead of a complex shift-add circuit or division, they implement a lightweight architecture using modular doublings and additions to compute $13a$ , followed by a conditional negation. This eliminates the need for a general-purpose multiplier in this step.
Memory-Parallelization Strategy: To overcome the limitations of traditional ping-pong memory schemes without increasing total memory footprint, the authors introduce a technique using four smaller memory blocks (each of size $n/4$ ) instead of two larger blocks. Coefficients are stored in adjacent pairs. A multiplexer-based swap network reorders outputs based on the current stage's offset ( $\delta$ ). This allows two butterfly units to operate concurrently. When the offset is large ( $\delta \ge n/4$ ), all four memory blocks and both butterfly units are utilized; when the offset is small ( $\delta < n/4$ ), the system achieves partial parallelism with two active blocks. This strategy halves the required clock cycles compared to single-unit iterative designs while maintaining the same total memory capacity.

Key Contributions

Optimized Butterfly Architecture: A unified CT/GS butterfly unit achieving a frequency increase from 46 MHz (baseline) to 298 MHz through fine-grained pipelining, with only a 1.32× area overhead.
Efficient Rescaling: A multiplication-free rescaling architecture for the INTT that reduces Slice and LUT usage by 1.67× and 1.84×, respectively, compared to a standard 7-term shift-add implementation.
Scalable Memory Parallelism: A novel memory organization using four $n/4$ -sized blocks and a swap network to enable partial parallelism in iterative NTT, reducing clock cycles by 50% without increasing total memory cost.
Integrated Accelerator (PIP-NTT): A complete FPGA implementation integrating two optimized butterfly units and the memory-parallelization scheme, supporting both Forward (FNTT) and Inverse (INTT) transforms for Kyber parameters ( $n=256, q=3329$ ).

Experimental Results
The PIP-NTT design was implemented on Xilinx Virtex-7 and Artix-7 FPGA platforms.

Performance: The accelerator operates at 200 MHz, computing a single FNTT or INTT in 2.60 µs (520 clock cycles).
Efficiency: In terms of the Area-Time Product (ATP), PIP-NTT achieves:
- 2.67× higher efficiency compared to the most area-optimized NTT accelerators in the literature.
- 1.48× higher efficiency compared to the most high-speed NTT accelerators.
Resource Usage: The design utilizes 156 slices, 426 LUTs, and 379 Flip-Flops on the Virtex-7, demonstrating a highly compact footprint relative to its throughput.

Significance and Claims
The paper claims that PIP-NTT offers a versatile solution for future cryptographic hardware by effectively addressing the scalability and efficiency trade-offs inherent in iterative NTT designs. By decoupling parallelism from total memory cost through the proposed memory-parallelization strategy, the design enables high throughput under tight area constraints. The authors emphasize that the architecture is not limited to Kyber; the radix- and scheme-agnostic nature of the memory strategy and the modular design of the butterfly unit allow for adaptation to other PQC schemes (such as Dilithium) and varying ring sizes with minimal modifications. The work positions PIP-NTT as a balanced, resource-efficient approach suitable for diverse deployment scenarios, from embedded systems to data centers.

More like this