Welcome to the resource topic for 2024/390
Title:
STIR: Reed–Solomon Proximity Testing with Fewer Queries
Authors: Gal Arnon, Alessandro Chiesa, Giacomo Fenzi, Eylon Yogev
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 \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.
ePrint: https://eprint.iacr.org/2024/390
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .