Computationally convincing proofs of knowledge

DOI10.1007/BFB0020803MaRDI QIDQ4035674zbMATH OpenFDO

Authors Gilles Brassard, Claude Crépeau, Sophie Laplante, Christian Léger

Publication date 18 May 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0020803

zbMATH Keywords

computationally convincingprotocols

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Cryptography (94A60)

Review text

[For the entire collection see Zbl 0753.00019.] We give a more general definition of ``computationally convincing proof of knowledge capable of taking into account very nasty behaviour from the prover. We also prove that the constant-round arguments of [\textit{G. Brassard}, \textit{C. Crépeau} and \textit{M. Yung}, Theoret. Comput. Sci. 84, No. 1, 23-52 (1991; Zbl 0731.68032)] for NP-complete problems are proofs of knowledge according to our definition, which is much more difficult to prove than for the \(k\)-round protocols of [\textit{G. Brassard}, \textit{D. Chaum} and \textit{C. Crépeau}, J. Comput. Syst. Sci. 37, No. 2, 156-189 (1988; Zbl 0656.68109)]. Finally, we exhibit a protocol that forces us to question the full generality of our definition of ``computationally convincing: it may be that a more general definition is needed still, and that we do not yet know precisely when we should be convinced that a protocol is convincing.

Recommendations

• scientific article; zbMATH DE number 708820
• Constant-round perfect zero-knowledge computationally convincing protocols
• The knowledge complexity of interactive proof-systems
• Strong proofs of knowledge
• A note on constant-round zero-knowledge proofs of knowledge

Cited in

(11)

• Practical proofs of knowledge without relying on theoretical proofs of membership on languages
• Proving computational ability
• On probabilistic versus deterministic provers in the definition of proofs of knowledge
• scientific article; zbMATH DE number 1335878 (Why is no real title available?)
• Computationally-sound proofs
• scientific article; zbMATH DE number 1990814 (Why is no real title available?)
• Computationally Sound Proofs
• scientific article; zbMATH DE number 3999326 (Why is no real title available?)
• Argument of knowledge protocol for a Goppa codeword and for an error of a bounded weigth
• On separating proofs of knowledge from proofs of membership of languages and its application to secure identification schemes
• Constant-round perfect zero-knowledge computationally convincing protocols

This page was built for publication: Computationally convincing proofs of knowledge

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4035674)