Probabilistic proofs

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.

Succinct cryptographic proofs

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

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.

Post-quantum security

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.