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

##### 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.

Available format(s)
Category
Implementation
Publication info
Preprint.
Keywords
NTT FPGA FFT Number Theoretic Transform Goldilocks field Quasi-Streaming
Contact author(s)
ecesena @ jumpcrypto com
rmaganti @ jumpcrypto com
nicolas @ jumpcrypto com
History
2022-11-28: approved
See all versions
Short URL
https://ia.cr/2022/1657

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},
note = {\url{https://eprint.iacr.org/2022/1657}},
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.