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

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 $\lambda$ bits of security, STIR has query complexity $O(\log d + \lambda \cdot \log \log d )$, while FRI, a popular protocol, has query complexity $O(\lambda \cdot \log d )$ (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 $1.25\times$ to $2.46\times$ depending on the chosen parameters, with similar prover and verifier running times. For example, in order to achieve 128 bits of security for degree $2^{26}$ and rate $1/4$, STIR has argument size $114$ KiB, compared to $211$ KiB for FRI.

Available format(s)
Cryptographic protocols
Publication info
interactive oracle proofsReed-Solomon proximity testing
Contact author(s)
gal arnon @ weizmann ac il
alessandro chiesa @ epfl ch
giacomo fenzi @ epfl ch
eylon yogev @ biu ac il
2024-03-21: last of 2 revisions
2024-03-03: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.