ICTS:31740

Video URL

Efficient Cryptographic Proofs from RAA Codes

Efficient Cryptographic Proofs from RAA Codes

(2025). Efficient Cryptographic Proofs from RAA Codes. SciVideos. https://youtu.be/i6W8k_ZPtZ0

Efficient Cryptographic Proofs from RAA Codes. SciVideos, May. 05, 2025, https://youtu.be/i6W8k_ZPtZ0 

          @misc{ scivideos_ICTS:31740,
            doi = {},
            url = {https://youtu.be/i6W8k_ZPtZ0},
            author = {},
            keywords = {},
            language = {en},
            title = {Efficient Cryptographic Proofs from RAA Codes},
            publisher = {},
            year = {2025},
            month = {may},
            note = {ICTS:31740 see, \url{https://scivideos.org/icts-tifr/31740}}
          }
Nicolas Resch
Talk numberICTS:31740
Source RepositoryICTS-TIFR

Abstract

In this talk, we will introduce interactive oracle proofs (IOPs), which are an interactive generalization of probabilistically-checkable proofs (PCPs). IOPs can then be “compiled” into very efficient cryptographic proofs, which can be very short (say, polylogarithmic length) and admit very efficient verifiers (say, polylogarithmic time). One requirement that arises from practice is that the prover also be very efficient; ideally, running in linear time.

After introducing these concepts, I will outline how one can use error-correcting codes with efficient encoding algorithms to design efficient cryptographic proofs. We will then discuss Repeat-Accumulate-Accumulate (RAA) codes, which are a simple class of turbo codes offering extremely efficient encoding and near-GV bound minimum distance. We will spend a good portion of this presentation describing these codes, discussing the challenges which arise in their analysis, and surveying some open problems.