In analogy to mathematical proofs, the goal of a proof system is for a prover to convince a verifier of the correctness of a claim. However, by contrast, probabilistic proofs allow the verifier to make mistakes, i.e., to accept false claims or reject true claims. Further, probabilistic proofs may have multiple rounds of interaction between the prover and the verifier, in which case they are also referred to as interactive proofs. These two relaxations revolutionized the theory of proofs. For instance, by trading absolute certainty for high probability and allowing interaction, it is possible to prove claims without revealing anything beyond their correctness, i.e., in zero-knowledge. Nowadays, zero-knowledge proofs are widely deployed; they are for instance essential in the public-key infrastructures (PKIs) that manage digital identities and secure communication channels on the internet.
Especially the theory of Σ-protocols provides a well-understood basis for the...
Show moreIn analogy to mathematical proofs, the goal of a proof system is for a prover to convince a verifier of the correctness of a claim. However, by contrast, probabilistic proofs allow the verifier to make mistakes, i.e., to accept false claims or reject true claims. Further, probabilistic proofs may have multiple rounds of interaction between the prover and the verifier, in which case they are also referred to as interactive proofs. These two relaxations revolutionized the theory of proofs. For instance, by trading absolute certainty for high probability and allowing interaction, it is possible to prove claims without revealing anything beyond their correctness, i.e., in zero-knowledge. Nowadays, zero-knowledge proofs are widely deployed; they are for instance essential in the public-key infrastructures (PKIs) that manage digital identities and secure communication channels on the internet.
Especially the theory of Σ-protocols provides a well-understood basis for the modular design of zero-knowledge proof systems in a wide variety of application domains. However, recently a new folding mechanism was introduced as a drop-in replacement for Σ-protocols, significantly reducing the communication costs in many practical scenarios.
In this dissertation, we show that the folding mechanism can be cast as a significant strengthening, rather than a replacement, of Σ-protocol theory, thereby reconciling it with the established theory. In addition, we close several gaps in the theory of probabilistic proofs that were exposed due to the introduction of these efficiency improvements.
Show less
