Abstract
Zero-knowledge proofs are a powerful tool for the construction of several types of cryptographic protocols. Recently, motivated by practical considerations, such protocols have been investigated in a concurrent and asynchronous distributed model, where protocols have been proposed relying on various synchronization assumptions and unproven complexity assumptions.
In this paper we present the first constructions of proof systems that are concurrent zero-knowledge without relying on unproven complexity assumptions. Our techniques transform a non-concurrent zero-knowledge protocol into a concurrent zero-knowledge one. They apply to large classes of languages and preserve the type of zero-knowledge: if the original protocol is computational, statistical or perfect zero-knowledge, then so is the transformed one.
Copyright 2000, Telcordia Technologies, Inc. All Rights Reserved.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
M. Ben-Or, J. Hastad, J. Kilian, O. Goldreich, S. Goldwasser, S. Micali, and P. Rogaway, Everything Provable is Provable in Zero-Knowledge, CRYPTO 88.
T. Beth and Y. Desmedt, Identification Tokens-or: Solving the Chess Grandmaster Problem, in Proc. of CRYPTO 90.
M. Blum, How to Prove a Theorem So No One Else Can Claim It, in Proc. of the International Congress of Mathematicians, 1986.
R. Boppana, J. Håstad, and S. Zachos, Does co-NP have Short Interactive Proofs?, in Inf. Proc. Lett., vol. 25, May 1987.
I. Damgaard, Interactive Hashing Simplifies Zero-Knowledge Protocol Design Without Complexity Assumptions, in Proc. of CRYPTO 93.
A. De Santis, G. Di Crescenzo, G. Persiano and M. Yung, On Monotone Formula Closure of SZK, in Proc. of FOCS 94.
G. Di Crescenzo and R. Ostrovsky, On Concurrent Zero-Knowledge with Pre-Processing, in Proc. of CRYPTO 99.
G. Di Crescenzo, K. Sakurai and M. Yung, On Zero-Knowledge Proofs: “From Membership to Decision”, in Proc. of STOC 2000.
C. Dwork, M. Naor, and A. Sahai, Concurrent Zero-Knowledge, STOC 98.
C. Dwork and A. Sahai, Concurrent Zero-Knowledge: Reducing the Need for Timing Constraints, in Proc. of CRYPTO 98.
L. Fortnow, The Complexity of Perfect Zero-Knowledge, in Proc. of STOC 87.
O. Goldreich, S. Micali, and A. Wigderson, Proofs that Yield Nothing but their Validity or All Languages in NP Have Zero-Knowledge Proof Systems, in Journal of the ACM, vol. 38, n. 1, 1991.
S. Goldwasser, S. Micali, and C. Rackoff, The Knowledge Complexity of Interactive Proof-Systems, in SIAM Journal on Computing, vol. 18, n. 1, February 1989.
R. Impagliazzo and M. Yung, Direct Minimum-Knowledge Computation, in Proc. of CRYPTO 87.
J. Kilian, E. Petrank, and C. Rackoff, Lower Bounds for Zero-Knowledge on the Internet, in Proc. of FOCS 98.
R. Richardson and J. Kilian, On the Concurrent Composition of Zero-Knowledge Proofs, in Proc. of EUROCRYPT 99.
M. Tompa and H. Woll, Random Self-Reducibility and Zero-Knowledge Interactive Proofs of Possession of Information, in Proc. of FOCS 87.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Di Crescenzo, G. (2000). Removing Complexity Assumptions from Concurrent Zero-Knowledge Proofs. In: Du, DZ., Eades, P., Estivill-Castro, V., Lin, X., Sharma, A. (eds) Computing and Combinatorics. COCOON 2000. Lecture Notes in Computer Science, vol 1858. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44968-X_42
Download citation
DOI: https://doi.org/10.1007/3-540-44968-X_42
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67787-1
Online ISBN: 978-3-540-44968-3
eBook Packages: Springer Book Archive