Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. STIR: Reed-Solomon Proximity Testing with Fewer Queries
 
conference paper

STIR: Reed-Solomon Proximity Testing with Fewer Queries

Arnon, Gal
•
Chiesa, Alessandro  
•
Fenzi, Giacomo  
Show more
Reyzin, Leonid
•
Stebila, Douglas
2024
Advances in Cryptology – CRYPTO 2024 - 44th Annual International Cryptology Conference, Proceedings
44th Annual International Cryptology Conference

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.

  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-031-68403-6_12
Scopus ID

2-s2.0-85202289188

Author(s)
Arnon, Gal

Weizmann Institute of Science Israel

Chiesa, Alessandro  

École Polytechnique Fédérale de Lausanne

Fenzi, Giacomo  

École Polytechnique Fédérale de Lausanne

Yogev, Eylon

Bar-Ilan University

Editors
Reyzin, Leonid
•
Stebila, Douglas
Date Issued

2024

Publisher

Springer Science and Business Media Deutschland GmbH

Published in
Advances in Cryptology – CRYPTO 2024 - 44th Annual International Cryptology Conference, Proceedings
Series title/Series vol.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 14929 LNCS

ISSN (of the series)

1611-3349

0302-9743

Start page

380

End page

413

Subjects

Interactive oracle proofs

•

Reed–Solomon proximity testing

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
COMPSEC  
Event nameEvent acronymEvent placeEvent date
44th Annual International Cryptology Conference

Santa Barbara, United States

2024-08-18 - 2024-08-22

FunderFunding(s)Grant NumberGrant URL

Simons Foundation Collaboration on the Theory of Algorithmic Fairness

Israeli Council for Higher Education

Weizmann Data Science Research Center

Show more
Available on Infoscience
January 26, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/244713
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés