CryptoDB
STIR: Reed–Solomon Proximity Testing with Fewer Queries
| Authors: |
|
|---|---|
| Download: |
|
| 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
}