STIR: Reed-Solomon Proximity Testing with Fewer Queries
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 O(logd+λ·loglogd), while FRI, a popular protocol, has query complexity O(λ·logd) (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× to 2.46× depending on the chosen parameters, with similar prover and verifier running times. For example, in order to achieve 128 bits of security for degree 226 and rate 1/4, STIR has argument size 114 KiB, compared to 211 KiB for FRI.
2-s2.0-85202289188
Weizmann Institute of Science Israel
École Polytechnique Fédérale de Lausanne
École Polytechnique Fédérale de Lausanne
Bar-Ilan University
2024
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 14929 LNCS
1611-3349
0302-9743
380
413
REVIEWED
EPFL
Event name | Event acronym | Event place | Event date |
Santa Barbara, United States | 2024-08-18 - 2024-08-22 | ||
Funder | Funding(s) | Grant Number | Grant URL |
Simons Foundation Collaboration on the Theory of Algorithmic Fairness | |||
Israeli Council for Higher Education | |||
Weizmann Data Science Research Center | |||
Show more |