STIR: Reed–Solomon Proximity Testing with Fewer Queries

Gal Arnon; Alessandro Chiesa; Giacomo Fenzi; Eylon Yogev

Paper 2024/390

STIR: Reed–Solomon Proximity Testing with Fewer Queries

Gal Arnon

, Weizmann Institute of Science

Alessandro Chiesa, École Polytechnique Fédérale de Lausanne

Giacomo Fenzi

, École Polytechnique Fédérale de Lausanne

Eylon Yogev

, Bar-Ilan University

Abstract

We present STIR (Shift To Improve Rate), an interactive oracle proof of proximity (IOPP) for Reed-Solomon codes that achieves the best known query complexity of any concretely efficient IOPP for this problem. For bits of security, STIR has query complexity , while FRI, a popular protocol, has query complexity (including variants of FRI based on conjectured security assumptions). STIR relies on a new technique for recursively improving the rate of the tested Reed-Solomon code. We provide an implementation of STIR compiled to a SNARK. Compared to a highly-optimized implementation of FRI, STIR achieves an improvement in argument size that ranges from to depending on the chosen parameters, with similar prover and verifier running times. For example, in order to achieve 128 bits of security for degree and rate , STIR has argument size KiB, compared to KiB for FRI.

Note: Updated CRYPTO 2024 + minor correction to appendix B + minor corrections to protocol

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A major revision of an IACR publication in CRYPTO 2024
Keywords: interactive oracle proofs Reed-Solomon proximity testing
Contact author(s): gal arnon @ weizmann ac il
alessandro chiesa @ epfl ch
giacomo fenzi @ epfl ch
eylon yogev @ biu ac il
History: 2025-01-27: last of 4 revisions; 2024-03-03: received; See all versions
Short URL: https://ia.cr/2024/390
License: CC BY

BibTeX

@misc{cryptoeprint:2024/390,
      author = {Gal Arnon and Alessandro Chiesa and Giacomo Fenzi and Eylon Yogev},
      title = {{STIR}: Reed–Solomon Proximity Testing with Fewer Queries},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/390},
      year = {2024},
      url = {https://eprint.iacr.org/2024/390}
}