Abstract
Recently there has been an interest in zero-knowledge protocols with stronger properties, such as concurrency, unbounded simulation soundness, non-malleability, and universal composability. In this paper, we show a novel technique to convert a large class of existing honest-verifier zero-knowledge protocols into ones with these stronger properties in the common reference string model. More precisely, our technique utilizes a signature scheme existentially unforgeable against adaptive chosen-message attacks, and transforms any Σ-protocol (which is honest-verifier zero-knowledge) into an unbounded simulation sound concurrent zero-knowledge protocol. We also introduce Ω-protocols, a variant of Σ-protocols for which our technique further achieves the properties of non-malleability and/or universal composability.
In addition to its conceptual simplicity, a main advantage of this new technique over previous ones is that it avoids the Cook-Levin theorem, which tends to be rather inefficient. Indeed, our technique allows for very efficient instantiation based on the security of some efficient signature schemes and standard number-theoretic assumptions. For instance, one instantiation of our technique yields a universally composable zero-knowledge protocol under the Strong RSA assumption, incurring an overhead of a small constant number of exponentiations, plus the generation of two signatures.
Chapter PDF
Similar content being viewed by others
Keywords
- Signature Scheme
- Commitment Scheme
- Common Input
- Common Reference String
- Universal Composability Framework
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
B. Barak. How to Go Beyond the Black-box Simulation Barrier. In 42nd IEEE Symp. on Foundations of Computer Sci., 106–115, 2001.
B. Barak. Constant-Round Coin-Tossing With a Man in the Middle or Realizing the Shared Random String Model. In 43rd IEEE Symp. on Foundations of Computer Sci., 345–355, 2002
N. Barić and B. Pfitzmann. Collision-free accumulators and fail-stop signature schemes without trees. In Advances in Cryptology — EUROCRYPT’ 97 (LNCS 1233), 480–494, 1997.
D. Boneh. The decision Diffie-Hellman problem. In Proceedings of the Third Algorithmic Number Theory Symp. (LNCS 1423), 48–63, 1998.
R. Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42nd IEEE Symp. on Foundations of Computer Sci., 136–145, 2001.
R. Canetti and M. Fischlin. Universally composable commitments. In Advances in Cryptology — CRYPTO 2001 (LNCS 2139), 19–40, 2001.
R. Canetti, J. Kilian, E. Petrank and A. Rosen. Concurrent zero-knowledge requires \( \tilde \Omega \) (log n) rounds. In 33rd ACM Symp. on Theory of Computing, 570–579, 2001.
R. Canetti, Y. Lindell, R. Ostrovsky and A. Sahai. Universally composable twoparty computation. In 34th ACM Symp. on Theory of Computing, 494–503, 2002. Full version in ePrint archive, Report 2002/140. http://eprint.iacr.org/, 2002.
R. Canetti and T. Rabin. Universal Composition with Joint State In ePrint archive, Report 2002/047, http://eprint.iacr.org/, 2002.
S. A. Cook. The complexity of theorem-proving procedures. In 3rd IEEE Symp. on Foundations of Computer Sci., 151–158, 1971.
R. Cramer, I. Damgård, and B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In Advances in Cryptology — CRYPTO’ 94 (LNCS 839), pages 174–187, 1994.
R. Cramer and V. Shoup. Signature scheme based on the strong RSA assumption. In ACM Trans. on Information and System Security 3(3):161–185, 2000.
I. Damgård. Efficient Concurrent Zero-Knowledge in the Auxiliary String Model. In Advances in Cryptology — EUROCRYPT 2000 (LNCS 1807), 418–430, 2000.
I. Damgård and J. Nielsen. Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor. In Advances in Cryptology — CRYPTO 2002 (LNCS 2442), 581–596, 2002. Full version in ePrint Archive, report 2001/091. http://eprint.iacr.org/, 2001.
A. De Santis, G. Di Crescenzo, R. Ostrovsky, G. Persiano and A. Sahai. Robust non-interactive zero knowledge. In Advances in Cryptology — CRYPTO 2001 (LNCS 2139), 566–598, 2001.
D. Dolev, C. Dwork and M. Naor. Non-malleable cryptography. SIAM J. on Comput., 30(2):391–437, 2000. Also in 23rd ACM Symp. on Theory of Computing, 542–552, 1991.
C. Dwork, M. Naor and A. Sahai. Concurrent zero-knowledge. In 30th ACM Symp. on Theory of Computing, 409–418, 1998.
C. Dwork and A. Sahai. Concurrent Zero-Knowledge: Reducing the Need for Timing Constraints. In Advances in Cryptology — CRYPTO’ 98 (LNCS 1462), 442–457, 1998.
T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. on Information Theory, 31:469–472, 1985.
S. Even, O. Goldreich, and S. Micali. On-line/Off-line digital signatures. J. Cryptology 9(1): 35–67 (1996).
U. Feige and A. Shamir. Witness Indistinguishable and Witness Hiding Protocols. In 22nd ACM Symp. on Theory of Computing, 416–426, 1990.
FIPS 186. Digital signature standard. Federal Information Processing Standards Publication 186, U.S. Dept. of Commerce/NIST, National Technical Information Service, Springfield, Virginia, 1994.
O. Goldreich, S. Micali and A. Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. In 19th ACM Symp. on Theory of Computing, 218–229, 1987.
O. Goldreich, S. Micali and A. Wigderson. Proofs that yield nothing but their validity or All languages in NP have zero-knowledge proof systems. J. ACM, 38(3):691–729, 1991.
S. Goldwasser, S. Micali and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1):186–208, February 1989.
S. Goldwasser, S. Micali and R. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput., 17:281–308, 1988.
S. Jarecki and A. Lysyanskaya. Adaptively Secure Threshold Cryptography: Introducing Concurrency, Removing Erasures. In Advances in Cryptology — EUROCRYPT’ 00 (LNCS 1807), 221–242, 2000.
J. Katz. Efficient and Non-Malleable Proofs of Plaintext Knowledge and Applications. In ePrint Archive, Report 2002/027, http://eprint.iacr.org/, 2002.
J. Kilian and E. Petrank. Concurrent and resettable zero-knowledge in polylogarithmic rounds. In 33rd ACM Symp. on Theory of Computing, 560–569, 2001.
D. W. Kravitz. Digital signature algorithm. U.S. Patent 5,231,668, 27 July 1993.
L. A. Levin. Universal sorting problems. Problemy Peredaci Informacii, 9:115–116, 1973. In Russian. Engl. trans.: Problems of Information Transmission 9:265–266.
P. MacKenzie, T. Shrimpton, and M. Jakobsson. Threshold passwordauthenticated key exchange. In Advances in Cryptology — CRYPTO 2002 (LNCS 2442), 385–400, 2002.
M. Naor and M. Yung. Public-key cryptosystems provably secure against chosen ciphertext attacks. In 22nd ACM Symp. on Theory of Computing, 427–437, 1990.
T. Okamoto and S. Uchiyama. A new public-key cryptosystem as secure as factoring. In Advances in Cryptology — EUROCRYPT’ 98 (LNCS 1403), 380–318, 1998.
P. Paillier. Public-key cryptosystems based on composite degree residue classes. In Advances in Cryptology — EUROCRYPT’ 99 (LNCS 1592), 223–238, 1999.
T. P. Pedersen. Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In Advances in Cryptology — CRYPTO’ 91 (LNCS 576), 129–140, 1991.
M. Prabhakaran, A. Rosen and A. Sahai. Concurrent zero knowledge with logarithmic round-complexity, In ePrint Archive, Report 2002/055, http://eprint.iacr.org, 2002. Also in 43rd IEEE Symp. on Foundations of Computer Sci., 366–375, 2002.
L. Reyzin. Zero-knowledge with public keys. Ph.D. Thesis, MIT, 2001.
J. Rompel. One-way functions are necessary and sufficient for secure signatures. In 22nd ACM Symp. on Theory of Computing, 387–394, 1990.
A. Sahai. Non-malleable non-interactive zero knowledge and adaptive chosenciphertext security. In 40th IEEE Symp. on Foundations of Computer Sci., 543–553, 1999.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 International Association for Cryptologic Research
About this paper
Cite this paper
Garay, J.A., MacKenzie, P., Yang, K. (2003). Strengthening Zero-Knowledge Protocols Using Signatures. In: Biham, E. (eds) Advances in Cryptology — EUROCRYPT 2003. EUROCRYPT 2003. Lecture Notes in Computer Science, vol 2656. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-39200-9_11
Download citation
DOI: https://doi.org/10.1007/3-540-39200-9_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-14039-9
Online ISBN: 978-3-540-39200-2
eBook Packages: Springer Book Archive