Improved Polynomial Division in Cryptography
Arnab Roy
Abstract:
Several cryptographic primitives, especially succinct proofs of various forms, transform the satisfaction of high-level properties to the existence of a polynomial quotient between a polynomial that interpolates a set of values with a cleverly arranged divisor. Some examples are SNARKs, like Groth16, and polynomial commitments, such as KZG. Such a polynomial division naively takes time with Fast Fourier Transforms, and is usually the asymptotic bottleneck for these computations.
Several works have targeted specific constructions to optimize these computations and trade-off one-time setup costs with faster online computation times. In this paper, we present a unified approach to polynomial division related computations for a diverse set of schemes. We show how our approach provides a common abstract lens which recasts and improves existing approaches. Additionally, we present benchmarks for the Groth16 and the KZG systems, illustrating the significant practical benefits of our approach in terms of speed, memory, and parallelizability. We get a speedup of over the state-of-the-art in computing all openings for KZG commitments and a speed-up of about for Groth16 proofs when compared against the Rust Arkworks implementation. Although our Groth16 speedup is modest, our approach supports twice the number of gates as Arkworks and SnarkJS as it avoids computations at higher roots of unity. Conversely this reduces the need for employing larger groups for bigger circuits. For example, our approach can support gates with BN254, as compared to for coset-based approaches, without sacrificing computational advantages.
Our core technical contributions are novel conjugate representations and compositions of the derivative operator and point-wise division under the Discrete Fourier Transform. These allow us to leverage l'Hôpital's rule to efficiently compute polynomial division, where in the evaluation basis such divisions maybe of the form . Our techniques are generic with potential applicability to many existing protocols.
Bio:
Arnab designs cryptographic protocols focusing on decentralized systems with applications to finance and digital assets, working with researchers at Mysten Labs specializing in cryptography, distributed systems, language design and formal verification. His areas of research have spanned zero-knowledge, blockchain, secure communication, biometric authentication, data privacy, post-quantum cryptography, trusted hardware enclaves, machine learning and quantum-inspired algorithms. He has served as co-chair of the US NIST Big Data Security and Privacy SG, worked at Meta, Fujitsu, and IBM, and obtained his PhD in CS from Stanford, advised by Prof. John C. Mitchell.