Paper 2022/1657

CycloneNTT: An NTT/FFT Architecture Using Quasi-Streaming of Large Datasets on DDR- and HBM-based FPGA Platforms

Kaveh Aasaraai, Jump Trading
Emanuele Cesena, Jump Crypto
Rahul Maganti, Jump Crypto
Nicolas Stalder, Jump Crypto
Javier Varela, Jump Trading
Kevin Bowers, Jump Trading
Abstract

Number-Theoretic-Transform (NTT) is a variation of Fast-Fourier-Transform (FFT) on finite fields. NTT is being increasingly used in blockchain and zero-knowledge proof applications. Although FFT and NTT are widely studied for FPGA implementation, we believe CycloneNTT is the first to solve this problem for large data sets ($\ge2^{24}$, 64-bit numbers) that would not fit in the on-chip RAM. CycloneNTT uses a state-of-the-art butterfly network and maps the dataflow to hybrid FIFOs composed of on-chip SRAM and external memory. This manifests into a quasi-streaming data access pattern minimizing external memory access latency and maximizing throughput. We implement two variants of CycloneNTT optimized for DDR and HBM external memories. Although historically this problem has been shown to be memory-bound, CycloneNTT's quasi-streaming access pattern is optimized to the point that when using HBM (Xilinx C1100), the architecture becomes compute-bound. On the DDR-based platform (AWS F1), the latency of the application is equal to the streaming of the entire dataset $\log N$ times to/from external memory. Moreover, exploiting HBM's larger number of channels, and following a series of additional optimizations, CycloneNTT only requires $\frac{1}{6}\log N$ passes.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
NTT FPGA FFT Number Theoretic Transform Goldilocks field Quasi-Streaming
Contact author(s)
kaasaraai @ jumptrading com
ecesena @ jumpcrypto com
rmaganti @ jumpcrypto com
nicolas @ jumpcrypto com
jvarela @ jumptrading com
kbowers @ jumptrading com
History
2022-11-28: approved
2022-11-28: received
See all versions
Short URL
https://ia.cr/2022/1657
License
Creative Commons Attribution-NonCommercial-NoDerivs
CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2022/1657,
      author = {Kaveh Aasaraai and Emanuele Cesena and Rahul Maganti and Nicolas Stalder and Javier Varela and Kevin Bowers},
      title = {{CycloneNTT}: An {NTT}/{FFT} Architecture Using Quasi-Streaming of Large Datasets on {DDR}- and {HBM}-based {FPGA} Platforms},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1657},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1657}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.