A trend in cryptographic research (admittedly, motivated by challenges arising in blockchain technologies) is to design extremely efficient cryptographic proofs. These are schemes allowing a prover to convince a verifier that a certain statement is true (e.g., that the prover has enough money to make a certain payment), without revealing any additional information (e.g., exactly how much money the prover has in their bank account).
In this talk, we will discuss a modern method for constructing fast cryptographic proofs. One starts by designing an interactive oracle proof (IOP), which is an interactive generalization of a probabilistically-checkable proof (PCP). IOPs can then be “compiled” into very efficient cryptographic proofs, where the proof can be very short (say, polylogarithmic length), admit very efficient verifiers (say, polylogarithmic time), and provers (say, linear time).
After introducing these concepts, we will see how one can use error-correcting codes with efficient encoding algorithms to design efficient IOPs. Simply put, (linear) error-correcting codes are subspaces of a finite vector space, where given two distinct vectors from this subspace, they differ in many coordinates. After discussing what we can and cannot expect from error-correcting codes, we will introduce our specific choice for this task, namely, so-called repeat-accumulate-accumulate (RAA) codes.
Based on joint work with Martijn Brehm, Binyi Chen, Ben Fisch, Ron D. Rothblum, and Hadas Zeilberger. Paper available at https://eprint.iacr.org/2024/1609