International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 01 April 2023

Héctor Masip-Ardevol, Marc Guzmán-Albiol, Jordi Baylina-Melé, Jose Luis Muñoz-Tapia
ePrint Report ePrint Report
STARK is a widely used transparent proof system that uses low-degree tests for proving the correctness of a computer program. STARK consumes an intermediate representation known as AIR that is more appropriate for programs with a relatively short and structured description. However, an AIR is not able to succinctly express non-equality constraints, leading to the incorporation of unwanted polynomials. We present the eSTARK protocol, a new probabilistic proof that generalizes the STARK family through the introduction of a more generic intermediate representa- tion called eAIR. We describe eSTARK in the polynomial IOP model, which com- bines the optimized version of the STARK protocol with the incorporation of three arguments into the protocol. We also explain various techniques that enhance the vanilla STARK complexity, including optimizations applied to polynomial computa- tions, and analyze the tradeoffs between controlling the constraint degree either at the representation of the AIR or inside the eSTARK itself.
Expand

Additional news items may be found on the IACR news page.