Abstract
This talk continues the discussion of interactive oracle proofs (IOPs), an interactive generalization of probabilistically-checkable proofs (PCPs). Such proofs offer extreme efficiency (theoretically and concretely), e.g., linear-time provers and polylogarithmic-time verifiers. To turn them into a cryptographic proof (i.e., a succinct argument), one additionally requires a polynomial commitment scheme, which allows for a prover to provide a short commitment to a polynomial P, and later can efficiently prove statements of the form “P(x)=y”.
In this work, we build on the code-switching technique of Ron-Zewi and Rothblum to construct multilinear polynomial commitment schemes (MLPCSs) over characteristic-2 fields, where the prover’s running time is inherited from the encoding time of the underlying error-correcting code. Crucially, we can employ codes without any “algebraic/multiplicative” properties, for which we only have error-correcting codes encodable in quasi-linear time. Our technique can be viewed as application of code interleaving.
To instantiate this construction, we utilize so-called Repeat-Accumulate-Accumulate 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.
Based on joint work Martijn Brehm, Binyi Chen, Ben Fisch, Ron D. Rothblum and Hadas Zeilberger.
Preprint: https://eprint.iacr.org/2024/1609.pdf