Abstract
We study the recently introduced notion of a simulation-sound trapdoor commitment (SSTC) scheme. In this paper, we present a new, simpler definition for an SSTC scheme that admits more efficient constructions and can be used in a larger set of applications. Specifically, we show how to construct SSTC schemes from any one-way functions, and how to construct very efficient SSTC schemes based on specific number-theoretic assumptions. We also show how to construct simulation-sound, non-malleable, and universally-composable zero-knowledge protocols using SSTC schemes, yielding, for instance, the most efficient universally-composable zero-knowledge protocols known. Finally, we explore the relation between SSTC schemes and non-malleable commitment schemes by presenting a sequence of implication and separation results, which in particular imply that SSTC schemes are non-malleable.
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
Barić, N., Pfitzmann, B.: Collision-free accumulators and fail-stop signature schemes without trees. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 480–494. Springer, Heidelberg (1997)
Beaver, D.: Adaptive zero-knowledge and computational equivocation. In: 28th ACM Symp. on Theory of Computing, pp. 629–638 (1996)
Blum, M.: Coin flipping by telephone. In: IEEE Spring COMPCOM, pp. 133–137 (1982)
Brassard, G., Chaum, D., Crépeau, C.: Minimum Disclosure Proofs of Knowledge. JCSS 37(2), 156–189 (1988)
Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. In: 42nd IEEE Symp. on Foundations of Computer Sci., pp. 136–145 (2001)
Canetti, R., Fischlin, M.: Universally composable commitments. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 19–40. Springer, Heidelberg (2001)
Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable twoparty computation. In: 34th ACM Symp. on Theory of Computing, pp. 494–503 (2002), Full version in ePrint archive, Report 2002/140, http://eprint.iacr.org/
Cook, S.A.: The complexity of theorem-proving procedures. In: 3rd IEEE Symp. on Foundations of Computer Sci., pp. 151–158 (1971)
Cramer, R., Damgård, I.: Zero-Knowledge Proofs for Finite Field Arithmetic, or: Can Zero-Knowledge Be for Free? In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 424–441. Springer, Heidelberg (1998)
Cramer, R., Damgård, I., Schoenmakers, B.: Proofs 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)
Cramer, R., Shoup, V.: Signature scheme based on the strong RSA assumption. ACM Trans. on Information and System Security 3(3), 161–185 (2000)
Damgård, I.: On the existence of bit commitment schemes and zero-knowledge proofs. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 17–29. Springer, Heidelberg (1990)
Damgård, 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)
Damgård, I., Groth, J.: Non-interactive and reusable non-malleable commitment schemes. In: 35th ACM Symp. on Theory of Computing, pp. 426–437 (2003)
Damgård, I., Nielsen, J.: Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 581–596. Springer, Heidelberg (2002), Full version in ePrint Archive, report 2001/091 (2001) http://eprint.iacr.org/
Di Crescenzo, G., Ishai, Y., Ostrovsky, R.: Non-interactive and non-malleable commitment. In: 30th ACM Symp. on Theory of Computing, pp. 141–150 (1998)
Di Crescenzo, G., Katz, J., Ostrovsky, R., Smith, A.: Efficient and Non- Interactive Non-Malleable Commitment. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 40–59. Springer, Heidelberg (2001)
Dolev, D., Dwork, C., Naor, M.: Non-malleable cryptography. SIAM J. on Comput. 30(2), 391–437 (2000); Also in 23rd ACM Symp. on Theory of Computing, pp. 542–552 (1991)
Even, S., Goldreich, O., Micali, S.: On-line/Off-line digital signatures. J. Cryptology 9(1), 35–67 (1996)
Feige, U., Shamir, A.: Witness Indistinguishable and Witness Hiding Protocols. In: 22nd ACM Symp. on Theory of Computing, pp. 416–426 (1990)
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)
Fischlin, M.: The Cramer-Shoup strong-RSA signature scheme revisited. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 116–129. Springer, Heidelberg (2002)
Fischlin, M., Fischlin, R.: Efficient non-malleable commitment schemes. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 413–431. Springer, Heidelberg (2000)
Garay, J.A., MacKenzie, P., Yang, K.: Strengthening Zero-Knowledge Protocols using Signatures. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol.��2656, pp. 177–194. Springer, Heidelberg (2003)
Gennaro, R.: Improved Proofs of Knowledge Secure under Concurrent Man-in-the-middle Attacks and their Applications. In ePrint Archive, report 2003/214 (2003), http://eprint.iacr.org/
Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or All languages in NP have zero-knowledge proof systems. J. ACM 38(3), 691–729 (1991)
Goldwasser, S., Micali, S., Rivest, R.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17, 281–308 (1988)
Jarecki, S., Lysyanskaya, A.: Adaptively Secure Threshold Cryptography: Introducing Concurrency, Removing Erasures. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 221–242. Springer, Heidelberg (2000)
Kravitz, D.W.: Digital signature algorithm. U.S. Patent 5,231,668, July 27 (1993)
Levin, L.A.: Universal sorting problems. Problemy Peredaci Informacii 9, 115–116 (1973); In Russian. Engl. trans.: Problems of Information Transmission 9, 265–266
MacKenzie, P., Yang, K.: On simulation-sound trapdoor commitments (full version). Available on the Cryptology ePrint Archive: http://eprint.iacr.org/2003/252
Naor, M.: Bit commitment Using Pseudo-Randomness. J. Cryptology 4(2), 151–158 (1991)
Naor, M., Ostrovsky, R., Venkatesan, R., Yung, M.: Perfect zero-knowledge arguments for NP can be based on general complexity assumptions. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 196–214. Springer, Heidelberg (1993)
Pedersen, T.P.: Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992)
Reyzin, L.: Zero-knowledge with public keys. Ph.D. Thesis, MIT (2001)
Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: 22nd ACM Symp. on Theory of Computing, pp. 387–394 (1990)
Sahai, A.: Non-malleable non-interactive zero knowledge and adaptive chosenciphertext security. In: 40th IEEE Symp. on Foundations of Computer Sci., pp. 543–553 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
MacKenzie, P., Yang, K. (2004). On Simulation-Sound Trapdoor Commitments. In: Cachin, C., Camenisch, J.L. (eds) Advances in Cryptology - EUROCRYPT 2004. EUROCRYPT 2004. Lecture Notes in Computer Science, vol 3027. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24676-3_23
Download citation
DOI: https://doi.org/10.1007/978-3-540-24676-3_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21935-4
Online ISBN: 978-3-540-24676-3
eBook Packages: Springer Book Archive