### Scalable and Transparent Proofs over All Large Fields, via Elliptic Curves (ECFFT part II)

##### Abstract

Concretely efficient interactive oracle proofs (IOPs) are of interest due to their applications to scaling blockchains, their minimal security assumptions, and their potential future-proof resistance to quantum attacks. Scalable IOPs, in which prover time scales quasilinearly with the computation size and verifier time scales poly-logarithmically with it, have been known to exist thus far only over a set of finite fields of negligible density, namely, over "FFT-friendly" fields that contain a sub-group of size $2^k$. Our main result is to show that scalable IOPs can be constructed over any sufficiently large finite field, of size that is at least quadratic in the length of computation whose integrity is proved by the IOP. This result has practical applications as well, because it reduces the proving and verification complexity of cryptographic statements that are naturally stated over pre-defined finite fields which are not "FFT-friendly". Prior state-of-the-art scalable IOPs relied heavily on arithmetization via univariate polynomials and Reed--Solomon codes over FFT-friendly fields. To prove our main result and extend scalability to all large finite fields, we generalize the prior techniques and use new algebraic geometry codes evaluated on sub-groups of elliptic curves (elliptic curve codes). We also show a new arithmetization scheme that uses the rich and well-understood group structure of elliptic curves to reduce statements of computational integrity to other statements about the proximity of functions evaluated on the elliptic curve to the new family of elliptic curve codes. This paper continues our recent work that used elliptic curves and their subgroups to create FFT-based algorithms for polynomial manipulation over generic finite fields. However, our new IOP constructions force us to use new codes (ones that are not based on polynomials), and this poses a new set of challenges involving the more restricted automorphism group of these codes, and the constraints of Riemann-Roch spaces of strictly positive genus.

Available format(s)
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in TCC 2022
Keywords
Elliptic Curves STARK SNARK IOP STIK FRI FFT
Contact author(s)
eli @ starkware co
dancar @ starkware co
swastik @ cs toronto edu
david @ starkware co
History
2022-11-07: approved
See all versions
Short URL
https://ia.cr/2022/1542

CC BY

BibTeX

@misc{cryptoeprint:2022/1542,
author = {Eli Ben-Sasson and Dan Carmon and Swastik Kopparty and David Levit},
title = {Scalable and Transparent Proofs over All Large Fields, via Elliptic Curves (ECFFT part II)},
howpublished = {Cryptology ePrint Archive, Paper 2022/1542},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1542}},
url = {https://eprint.iacr.org/2022/1542}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.