STIR: Reed–Solomon Proximity Testing with Fewer Queries

ePrint Report: STIR: Reed–Solomon Proximity Testing with Fewer Queries

Gal Arnon, Alessandro Chiesa, Giacomo Fenzi, Eylon Yogev

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 )$ …

bits complexity eprint report lambda oracle problem proof proximity query rate report stir testing