A Machine-Checked Formalization of Sigma-Protocols

Date Added: May 2010
Format: PDF

Proofs of knowledge are two-party interactive protocols where one party, called the prover, convinces the other one, called the verifier, that she knows something. Typically, both parties share a common input x and something refers to a witness w of membership of the input x to an N P language. Proofs of knowledge are useful to enforce honest behavior of potentially malicious parties: the knowledge witness acts as an authentication token used to establish that the prover is a legitimate user of a service provided by the verifier, or as evidence that a message sent by the prover has been generated in accordance to the rules of a protocol.