Abstract
A two-party cryptographic protocol for evaluating any binary gate is presented. It is more efficient than previous two-party computations, and can even perform single-party (i.e. satisfiability) proofs more efficiently than known techniques. As in all earlier multiparty computations and satisfiability protocols, commitments are a fundamental building block. Each party in our approach encodes a single input bit as 2 bit commitments. These are then combined to form 5 bit commitments, which are permuted, and can then be opened to reveal the output of the gate.
Chapter PDF
Similar content being viewed by others
References
Brassard, G., Chaum, D. and Crepeau, C. “Minimal disclosure proofs of knowledge”. Journal of computer and system sciences, 37,2, october 1988, 156–189.
Brassard, G and Crepeau, C. “Zero-Knowledge Simulation of Boolean circuits.” Advances in Cryptology — Crypto’ 86, A.M. Odlyzko, Lecture Notes in Computer Science 263, 223–233, Springer-Verlag.
[GM] Goldwasser, S., and Micali, S., “Probabilistic encryption”, JCSS, 28,2, 1984, 270–299.
Goldreich, O., Micali, S., Wigderson, A. “How to prove all NP statements in Zero-knowledge” Advances in Cryptology — Crypto’ 86, A.M. Odlyzko, Lecture Notes in Computer Science 263, 171–185, Springer-Verlag.
Goldreich, O., Mansour, Y., Sipser, M. “Interactive Proof systems: Provers that never fail and random selection”. Symp. on Found. of Comp. Sc., 28, oct 87, 449–461.
Williams, H.C., “A modification of the RSA public-key encryption procedure.” IEEE Trans. Inform. Theory, 26(6), 726–729, November 1980.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1990 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
den Boer, B. (1990). More Efficient Match-Making and Satisfiability The Five Card Trick . In: Quisquater, JJ., Vandewalle, J. (eds) Advances in Cryptology — EUROCRYPT ’89. EUROCRYPT 1989. Lecture Notes in Computer Science, vol 434. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46885-4_23
Download citation
DOI: https://doi.org/10.1007/3-540-46885-4_23
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-53433-4
Online ISBN: 978-3-540-46885-1
eBook Packages: Springer Book Archive