We work on the theoretical foundations and practical realizations of cryptographic proofs. This enables checking the correctness of a computation in zero knowledge, and much faster than re-running the computation. These cryptographic proofs have powerful applications in the real world.
Probabilistic proof systems play an important role in theoretical computer science, enabling beautiful applications to delegation of computation, zero knowledge, and hardness of approximation. Interactive proofs (IPs), multi-prover interactive proofs (MIPs), probabilistically checkable proofs (PCPs), and interactive oracle proofs (IOPs) are types of probabilistic proof systems. We study the capabilities and limitations of probabilistic proof systems.
Cryptographic proofs are protocols used to prove and to verify the correct execution of computations. By combining the powers of probabilistic proofs and cryptography, it is possible to achieve "paradoxical" properties such as zero knowledge (the cryptographic proof reveals no information beyond the correctness of the proved computation) and succinctness (the cryptographic proof can be checked exponentially faster than running the proved computation). This leads, e.g., to powerful notions such as zkSNARKs, which have found widespread deployment in practice. We study efficient constructions of zkSNARKs and more.
Proof-carrying data (PCD) is a cryptographic primitives that allows mutually distrustful parties to perform efficiently verifiable distributed computation. PCD has found applications in blockchains, image authentication, enforcing language semantics, and more. We study the theoretical foundations, efficient constructions, and applications of PCD and other related primitives.
Quantum computing impacts cryptography, making numerous cryptographic tools insecure. We investigate how quantum computing affects the construction and security of cryptographic proofs and related primitives, with the ultimate goal of providing post-quantum secure zkSNARKs that are as efficient as possible.
The above topics span complexity theory, cryptography, coding theory, and some systems security. Understanding these topics benefits from a solid background in discrete probability, abstract algebra, and properties of polynomials. Below is a list of useful courses at EPFL that helps assemble relevant background material.