UC Santa Cruz

In the current era, many computations are being outsourced to third parties, whether to large cloud providers or to nodes in decentralized blockchains. As increasingly sensitive data is being operated on (e.g. financial and medical data), it is imperative that the data be protected and that the integrity of an outsourced computation is ensured.

The two cryptographic primitives Probabilistically Checkable Proofs and Fully Homomorphic Encryption enable verifiable and privacy preserving computations respectively, at the cost of high computational overhead.

Both primitives share common low level arithmetic operations, particularly math over polynomial rings. The number theoretic version of the traditional Fast Fourier Transform (FFT) for working over finite fields is called the Number The- oretic Transform (NTT), and is especially suited for FHE [34], [3], [33], [26], [41], [28], [37]. As far as we have seen in literature there has yet to be a paper demonstrating a hardware accelerator for ZKPs, particularly the variants of interest: ZK-STARKs [6] and ZK-SNARKs [10], however PCPs employ polynomial interpolation, evaluation, and Low-Degree Extensions, all of which are accelerated by NTTs.

By utilizing the recent hardware programming language Chisel [4], we created Buntterfly, an easily configurable open source NTT hardware generator that can be parameterized according to the workload (ZK-PCP or FHE) and target plat- form (Latency, Throughput, Area). Once the core modular arithmetic operators are in place, the flexibility of Chisel can allow different NTT architectures to be generated according to the target metric and target FPGA model. We demonstrate that instantiated NTT designs using Buntterfly on FPGAs can provide 64x speedup over optimized software NTTs. Buntterfly is flexible and can easily be extended to perform expensive operations such as Low-Degree Extensions for generating Reed-Solomon Codes [36] for PCPs, or large integer multiplication in FHE.