@NTT: Algorithm-Targeted NTT hardware acceleration via Design-Time Constant Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912846395211776 |
|---|---|
| author | Nabeel, Mohammed Hafez, Mahmoud Maniatakos, Michail |
| author_facet | Nabeel, Mohammed Hafez, Mahmoud Maniatakos, Michail |
| contents | The Number Theoretic Transform (NTT) is a critical computational bottleneck in many lattice-based postquantum cryptographic (PQC) algorithms. By leveraging the Fast Fourier Transform (FFT) algorithm, the NTT of a polynomial of degree N - 1 can be computed with a time complexity of O(N log N). Hardware implementation of NTT is generally preferred over software ones, as the latter are significantly slower due to complex memory access patterns and modular arithmetic operations. Achieving maximum throughput in hardware, however, typically demands a prohibitively large number of butterfly unit instantiations. In this work, we propose @NTT, which exploits the fact that the ring parameters in these algorithms are fixed, enabling design-time constant optimization and achieving the maximum throughput of N-point NTT per clock cycle with a compact hardware footprint. Our case study on the Dilithium NTT, implemented using the TSMC 28 nm library, operates at a clock frequency of 1.0 GHz with an area of 1.45 mm^2. On FPGA, the design achieves a throughput-per-LUT that is 5.2x higher than the state-of-the-art implementation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_17806 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | @NTT: Algorithm-Targeted NTT hardware acceleration via Design-Time Constant Optimization Nabeel, Mohammed Hafez, Mahmoud Maniatakos, Michail Cryptography and Security Hardware Architecture The Number Theoretic Transform (NTT) is a critical computational bottleneck in many lattice-based postquantum cryptographic (PQC) algorithms. By leveraging the Fast Fourier Transform (FFT) algorithm, the NTT of a polynomial of degree N - 1 can be computed with a time complexity of O(N log N). Hardware implementation of NTT is generally preferred over software ones, as the latter are significantly slower due to complex memory access patterns and modular arithmetic operations. Achieving maximum throughput in hardware, however, typically demands a prohibitively large number of butterfly unit instantiations. In this work, we propose @NTT, which exploits the fact that the ring parameters in these algorithms are fixed, enabling design-time constant optimization and achieving the maximum throughput of N-point NTT per clock cycle with a compact hardware footprint. Our case study on the Dilithium NTT, implemented using the TSMC 28 nm library, operates at a clock frequency of 1.0 GHz with an area of 1.45 mm^2. On FPGA, the design achieves a throughput-per-LUT that is 5.2x higher than the state-of-the-art implementation. |
| title | @NTT: Algorithm-Targeted NTT hardware acceleration via Design-Time Constant Optimization |
| topic | Cryptography and Security Hardware Architecture |
| url | https://arxiv.org/abs/2601.17806 |