by Tomer Solberg

Polynomial arithmetic is at the heart of modern Zero Knowledge Proving (ZKP) systems. The Number Theoretic Transform (NTT) is a crucial tool in facilitating efficient computational complexity over large polynomials encountered in ZKPs. NTTs are dominated by the number of field multiplications.

In this short note we…

--

--

by Carol Danvers

“Pushing the Limits on NTT Computation”

Abstract:

We report on the Winograd-based implementation for the Number Theoretical Transform. It uses less multiplications than the better-known Cooley-Tuckey alternative. This optimization is important for very high order finite-fields. Unfortunately, the Winograd scheme is difficult to generalize for arbitrary sizes and is only known for small-size transforms. We open-source our hardware implementation for size 32 based on [1].

Carol Danvers

Read the full paper here:https://github.com/ingonyama-zk/papers/blob/main/Winograd_fft.pdf

Follow our Journey

Twitter:https://twitter.com/Ingo_zk

Github:https://github.com/ingonyama-zk

YouTube:https://www.youtube.com/@ingo_zk

Join us:https://www.ingonyama.com/careers

--

--

Ingonyama

Ingonyama means Lion. We are a next-generation semiconductor company, designing accelerators for Zero Knowledge cryptography.

Baidu