Title: Efficient proofs of computational integrity from code-based interactive oracle proofs.
Abstract: Proofs of computational integrity are probabilistic proofs that enable a verifier
to check the correctness of an execution of a program, without having to run the
computation again. For practical concerns, such proofs should be short, easy to
generate and fast to verify. They may also have a zero-knowledge property, meaning
that a verifier can be convinced of a correctness of a result without getting any
information on a private input of the computation.
In recent years, proof systems (e.g. probabilistically checkable proofs, interactive
proofs, zero-knowledge proofs) have seen tremendous progress, which eventually
lead to real-world widespread deployment (e.g. Zcash, StarkEx). However, the most
commonly used general-purpose succinct non-interactive zero-knowledge proofs,
also called zk-SNARKs, requires a per-computation trusted setup to generate large
public parameters. In particular, the soundness of the scheme is compromised if
the secret hidden in the public parameters is leaked. To overcome this limitation,
several directions have been pursued with the aim to construct practical zk-SNARKs
without trusted setup. In particular, one of them relies heavily on properties
of Reed-Solomon codes, uses only lightweight cryptographic primitives and is
plausibly post-quantum secure.
In this talk, we will first review a fundamental construction of PCP-based succinct
non-interactive arguments for NP, dating back from the seminal works of Kilian and
Micali. Next, we will give an overview of how a long computation can be verified in
exponentially less time than redoing it. This practical scheme is known as STARK
and relies essentially on properties of low-degree polynomials. We will finally discuss
the problem of proximity to an error-correcting code, and how it is effectively solved
for Reed-Solomon codes.
Algorithmic Number Theory, Coding and Cryptography
