International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

STIR: Reed–Solomon Proximity Testing with Fewer Queries

Authors:
Gal Arnon , Weizmann Institute
Alessandro Chiesa , EPFL
Giacomo Fenzi , EPFL
Eylon Yogev , Bar-Ilan University
Download:
DOI: 10.1007/978-3-031-68403-6_12 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2024
Abstract: We present STIR (Shift To Improve Rate), a concretely efficient 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. Roughly, in order to achieve $\lambda$ bits of security, STIR has query complexity $O(\log d + \lambda \cdot \loglog d )$, while the popular FRI protocol (including variants based on conjectured security assumptions) has query complexity $O(\lambda \cdot \log d )$. STIR relies on a new technique for recursively reducing the degree of the function being tested while simultaneously improving the rate. We provide an implementation of STIR compiled to a SNARK. Compared to FRI, our implementation achieves an improvement in argument size that ranges from $1.25\times$ to $2.46\times$ depending on the chosen parameters. 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.
BibTeX
@inproceedings{crypto-2024-34144,
  title={STIR: Reed–Solomon Proximity Testing with Fewer Queries},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-68403-6_12},
  author={Gal Arnon and Alessandro Chiesa and Giacomo Fenzi and Eylon Yogev},
  year=2024
}