Asymmetric Cryptography

3Zero-Knowledge Proofs

Ivan VISCONTI

University of Salerno, Italy

3.1. Introduction

Consider the following typical scenario: Peggy claims something and then tells Victor: “It’s true, trust me”. Victor would like to get evidence that the claim is true since he does not fully trust Peggy. At the same time, Peggy does not want to reveal some confidential information that would prove the truthfulness of her claim. If Trinity, a third party that both Peggy and Victor fully trust, is willing to help, then Peggy could just reveal everything she knows about the claim to Trinity, and Trinity, once convinced that the claim is true, could inform Victor about the veracity of the claim, forgetting at the same time the information received from Peggy. Nevertheless, Peggy and Victor would like to resolve their disputes without involving others, and therefore they wonder, in the absence of a trusted third party, how Victor can be convinced of the veracity of a claim while still preserving Peggy’s privacy.

In 1985, Goldwasser et al. formalized the above two-party game introducing the notion of “interactive zero-knowledge proof system”. In the above scenario, Peggy would play the role of a prover P, while Victor would play the role of a verifier V. The claim is formalized as an instance x that is claimed to belong to a language L. Both P and V know x and the description of L and engage in some well-defined exchange of messages so that in the end P is able to convince V that x ∈ L. This is a ...