Abstract
We investigate the design and proofs of zero-knowledge (ZK) interactive systems under what we call the “restricted random oracle model” which restrains the usage of the oracle in the protocol design to that of collapsing protocol rounds a la Fiat-Shamir heuristics, and limits the oracle programmability in the security proofs. We analyze subtleties resulting from the involvement of random oracles in the interactive setting and derive our methodology. Then we investigate the Feige-Shamir 4-round ZK argument for \(\mathcal{NP}\) in this model: First we show that a 2-round protocol is possible for a very interesting set of languages; we then show that while the original protocol is not concurrently secure in the public-key model, a modified protocol in our model is, in fact, concurrently secure in the bare public-key model. We point at applications and implications of this fact. Of possible independent interest is a concurrent attack against the Feige-Shamir ZK in the public-key model (for which it was not originally designed).
The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI: 10.1007/978-3-540-32732-5_32
Chapter PDF
Similar content being viewed by others
Keywords
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
Bellare, M., Boldyreva, A., Palacio, A.: An Uninstantiable Random-Oracle-Model Scheme for a Hybrid-Encryption Problem. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 171–188. Springer, Heidelberg (2004)
Bellare, M., Rogaway, P.: Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. In: ACM Conference on Computer and Communications Security, pp. 62–73 (1993)
Brickell, E., Camenisch, J., Chen, L.: Direct Anonymous Attestation. In: ACM’s CCS 2004 (2004)
Canetti, R., Goldreich, O., Goldwasser, S., Micali, S.: Resettable Zero-Knowledge. In: ACM Symposium on Theory of Computing, pp. 235–244 (2000)
Canetti, R., Goldreich, O., Halevi, S.: The Random Oracle Methodology, Revisited. In: ACM Symposium on Theory of Computing, pp. 209–218 (1998)
Canetti, R., Goldreich, O., Halevi, S.: On the Random-Oracle Methodology as Applied to Length-Restricted Signature Schemes. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 40–57. Springer, Heidelberg (2004)
Cramer, R.: Modular Design of Secure, yet Practical Cryptographic Protocols, PhD Thesis, University of Amsterdam (1996)
Cramer, R., Damgard, I., Schoenmakers, B.: Proof of partial knowledge and simplified design of witness hiding protocols. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 174–187. Springer, Heidelberg (1994)
Damgard, I.: Efficient concurrent zero-knowledge in the auxiliary string model. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 418–430. Springer, Heidelberg (2000)
Di Crescenzo, G., Ostrovsky, R.: On concurrent zero-knowledge with pre-processing (Extended abstract). In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 485–502. Springer, Heidelberg (1999)
Dolev, D., Dwork, C., Naor, M.: Non-Malleable Cryptography. SIAM Journal on Computing 30(2), 391–437 (2000); Preliminary version appears in STOC 1991
Dwork, C., Naor, M., Sahai, A.: Concurrent Zero-Knowledge. In: ACM Symposium on Theory of Computing, pp. 409–418 (1998); Full version to appear in Journal of the ACM
Feige, U.: Alternative Models for Zero-Knowledge Interactive Proofs. Ph.D. Thesis, Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel (1990)
Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987)
Feige, U., Shamir, A.: Zero knowledge proofs of knowledge in two rounds. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 526–544. Springer, Heidelberg (1990)
Goldreich, O.: Concurrent Zero-Knowledge with Timing (Revisited). In: ACM Symposium on Theory of Computing, pp. 332–340 (2002)
Goldreich, O., Krawczyk, H.: On the Composition of Zero-Knowledge Proof Systems. SIAM Journal on Computing 25(1), 169–192 (1996)
Goldwasser, S., Tauman, Y.: On the (In)security of the Fiat-Shamir Paradigm. In: IEEE Symposium on Foundations of Computer Science, pp. 102–115 (2003)
Guillou, L., Quisquater, J.J.: A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor Minimizing both Transmission and Memory. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 123–128. Springer, Heidelberg (1988)
Micali, S., Reyzin, L.: Soundness in the Public-Key Model. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 542–565. Springer, Heidelberg (2001)
Naor, M., Yung, M.: Public-Key Cryptosystems Provably Secure Against Chosen Ciphertext Attacks. In: ACM Symposium on Theory of Computing, pp. 427–437 (1990)
Nielsen, J.B.: Separating random oracle proofs from complexity theoretic proofs: The non-committing encryption case. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 111–126. Springer, Heidelberg (2002)
Pass, R.: On Deniabililty in the Common Reference String and Random Oracle Models. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 316–337. Springer, Heidelberg (2003)
Schnorr, C.: Efficient Signature Generation by Smart Cards. Journal of Cryptology 4(3), 24 (1991)
Shoup, V., Gennaro, R.: Securing Threshold Cryptosystems Against Chosen Ciphertext Attack. Journal of Cryptology 15(2), 75–96 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yung, M., Zhao, Y. (2006). Interactive Zero-Knowledge with Restricted Random Oracles. In: Halevi, S., Rabin, T. (eds) Theory of Cryptography. TCC 2006. Lecture Notes in Computer Science, vol 3876. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11681878_2
Download citation
DOI: https://doi.org/10.1007/11681878_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32731-8
Online ISBN: 978-3-540-32732-5
eBook Packages: Computer ScienceComputer Science (R0)