Abstract
Often the core difficulty in designing zero-knowledge protocols arises from having to consider every possible cheating verifier trying to extract additional information. We here consider a compiler which transforms protocols proven secure only with respect to the honest verifier into protocols which are secure against any (even cheating) verifier. Such a compiler, which preserves the zero-knowledge property of a statistically or computationally secure protocol was first proposed in [BMO] based on Discrte Logarithm problem. In this paper, we show how such a compiler could be constructed based on any one-way permutation using our recent method of interactive hashing [OVY-90, NOVY]. This applies to both statistically and computationally secure protocols, preserving their respective security. Our result allows us to utilize DES-like permutations for such a compiler.
Supported by NSF postdoctoral fellowship and ICSI. Part of this work was done at Bellcore and part at IBM T.J. Watson Research Center.
Chapter PDF
Similar content being viewed by others
References
M. Blum, and S. Micali “How to Generate Cryptographically Strong Sequences Of Pseudo-Random Bits” SIAM J. on Computing, Vol 13, 1984, pp. 850–864.
Bellare, M., S. Micali and R. Ostrovsky, “The (True) Complexity of Statistical Zero Knowledge” STOC 90.
G. Brassard, D. Chaum and C. Crépeau, Minimum Disclosure Proofs of Knowledge, JCSS, v. 37, pp 156–189.
Brassard, G., C. Crépeau, and M. Yung, “Everything in NP can be Argued in Perfect Zero Knowledge in a Bounded Number of Rounds,” ICALP 89. (also in Theoretical Computer Science, special issue of ICALP 89).
I. B. Damgaard, Collision Free Hash Functions and Public Key Signature Schemes, Eurocrypt, 1987.
Goldreich, O. and A. Kahn, personal communication.
O. Goldreich, R. Impagliazzo, L. Levin, R. Venkatesan, and D. Zuckerman, Security Preserving Amplification of Hardness, FOCS 90.
Goldreich, O., Y. Mansour, and M. Sipser, “Interactive Proof Systems: Provers that never Fail and Random Selection,” FOCS 87.
Goldreich, O., S. Micali, and A. Wigderson, “Proofs that Yield Nothing but their Validity”, FOCS 86.
Goldwasser, S., S. Micali, and C. Rackoff, “The Knowledge Complexity of Interactive Proofs,” SIAM J. Comput., 18(1), 186–208 (February 1989).
Goldwasser, S., S. Micali, and R. Rivest, “A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks,” SIAM J. Comput, 17(2), 281–308 (April 1988).
J. Hastad, “Pseudo-Random Generators under Uniform Assumptions” STOC 90
I. Impagliazzo, L. Levin and M. Luby, Pseudo-random generation from one-way functions, Proc. 21st Symposium on Theory of Computing, 1989, pp. 12–24.
M. Naor, R. Ostrovsky, R. Venkatesan, and M. Yung. “Perfect Zero-Knowledge Arguments for NP Can Be Based on General Complexity Assumptions”, Advances in Cryptology-Crypto’ 92, Lecture Notes in Computer Science, Springer, to appear.
Naor, M. and M. Yung, “Universal One-Way Hash Functions and their Cryptographic Applications,” STOC 89.
Oren Y., “On The Cunning Power of Cheating Verifiers: Some Observations About Zero Knowledge Proofs”, FOCS 87.
R. Ostrovsky, R. Venkatesan, and M. Yung. “Fair Games Against an All-Powerful Adversary”, SEQUENCES’ 91, Positano, June, 1991 (Proc. Springer Verlag), (also presented at Princeton Oct. 1990 Workshop on Complexity and Cryptography).
R. Ostrovsky, R. Venkatesan, M. Yung, Secure Commitment Against A Powerful Adversary, STACS 92, Springer Verlag LNCS Vol. 577, p. 439–448, 1992.
R. Ostrovsky, A. Wigderson One-Way Functions are Essential for Non-Trivial Zero-Knowledge, The second Israel Symposium on Theory of Computing and Systems (ISTCS93) 1993.
J. Rompel “One-way Functions are Necessary and Sufficient for Secure Signatures” STOC 90.
A. C. Yao, Theory and Applications of Trapdoor functions, Proceedings of the 23th Symposium on the Foundation of Computer Science, 1982, pp 80–91.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ostrovsky, R., Venkatesan, R., Yung, M. (1994). Interactive Hashing Simplifies Zero-Knowledge Protocol Design. In: Helleseth, T. (eds) Advances in Cryptology — EUROCRYPT ’93. EUROCRYPT 1993. Lecture Notes in Computer Science, vol 765. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48285-7_23
Download citation
DOI: https://doi.org/10.1007/3-540-48285-7_23
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57600-6
Online ISBN: 978-3-540-48285-7
eBook Packages: Springer Book Archive