STIR: Reed-Solomon Proximity Testing with Fewer Queries
summary
A new IOPP called STIR replaces FRI and preserves log D rounds and O(L) proof length while cutting query complexity roughly in half: for D=2^20, rate 1/4 and 100-bit security FRI uses ~400 queries and STIR ~200; for D=2^24 proof size drops from 177 KB to 107 KB and verifier hashes from 3.5k to 1.8k. Implementation in Rust with arkworks on a 192-bit field and 256-bit hash shows similar prover time and fewer verifier hashes. Core techniques are fold and shift, domain shift, and quotient-based consistency.
AI-written summary · about
chapters (15)
- 0:00Introduction
- 2:07Motivation for STIR
- 3:52Random Oracle model basics
- 5:37Reed-Solomon proximity
- 8:48STIR protocol goals
- 11:17Benchmarks and implementation
- 12:23Comparison with FRI protocol
- 16:21Recursive settings
- 17:23Security assumptions
- 18:05FRI technique overview
- 22:35STIR core technique
- 26:29Domain shift technique
- 29:42Protocol structure
- 30:25Open challenges
- 31:52Conclusion
related talks
44mIOP based Zero-Knowledge Proofs
57mPractical Groth16 Aggregation
18mInner Product Arguments
20mSNARKs from the sum-check protocol
32mSymmetric Cryptanalysis I
28mQuantum Proofing Sigstore: A Tale of Three Approaches
51mDistributed Zero-Knowledge Proofs and Applications to Secure Computation
37mFrontiers in Cryptography