Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Efficiency Preserving Transformations for Concurrent Non-malleable Zero Knowledge

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNSC,volume 5978))

Included in the following conference series:

  • 1942Accesses

Abstract

Ever since the invention of Zero-Knowledge by Goldwasser, Micali, and Rackoff [1], Zero-Knowledge has become a central building block in cryptography - with numerous applications, ranging from electronic cash to digital signatures. The properties of Zero-Knowledge range from the most simple (and not particularly useful in practice) requirements, such as honest-verifier zero-knowledge to the most demanding (and most useful in applications) such as non-malleable and concurrent zero-knowledge. In this paper, we study the complexity ofefficient zero-knowledge reductions, from the first type to the second type. More precisely, under a standard complexity assumption (ddh), on input a public-coin honest-verifier statistical zero knowledge argument of knowledgeπ′ for a languageL we show a compiler that produces an argument systemπ forL that is concurrent non-malleable zero-knowledge (under non-adaptive inputs – which is the best one can hope to achieve [2,3]). Ifκ is the security parameter, the overhead of our compiler is as follows:

  • The round complexity ofπ is\(r+\tilde{O}(\log\kappa)\) rounds, wherer is the round complexity ofπ′.

  • The new prover\(\mathcal{P}\) (resp., the new verifier\(\mathcal{V}\)) incurs an additional overhead of (at most)\(r+{\kappa\cdot\tilde{O}(\log^2\kappa)}\) modular exponentiations. If tags of length\(\tilde{O}(\log\kappa)\) are provided, the overhead is only\(r+{\tilde{O}(\log^2\kappa)}\) modular exponentiations.

The only previous concurrent non-malleable zero-knowledge (under non-adaptive inputs) was achieved by Barak, Prabhakaran and Sahai [4]. Their construction, however, mainly focuses on afeasibility result rather than efficiency, and requires expensive\({\mathcal{NP}}\)-reductions.

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-642-11799-2_36

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

  1. Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems. In: Proc. 17th STOC, pp. 291–304 (1985)

    Google Scholar 

  2. Lindell, Y.: General composition and universal composability in secure multi-party computation. In: Proc. 44th FOCS, pp. 394–403 (2003)

    Google Scholar 

  3. Lindell, Y.: Lower bounds for concurrent self composition. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 203–222. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  4. Barak, B., Prabhakaran, M., Sahai, A.: Concurrent non-malleable zero knowledge. In: FOCS 2006 (2006); Full version on Cryptology ePrint Archive report,http://eprint.iacr.org/

  5. Dolev, D., Dwork, C., Naor, M.: Nonmalleable cryptography. SIAM Journal on Computing 30(2), 391–437 (2000); (electronic) Preliminary version in STOC 1991 (1991)

    Article MathSciNet MATH  Google Scholar 

  6. Garay, J.A., MacKenzie, P.D., Yang, K.: Strengthening zero-knowledge protocols using signatures. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 177–194. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  7. MacKenzie, P., Yang, K.: On Simulation-Sound Trapdoor Commitments. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 382–400. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  8. Gennaro, R.: Multi-trapdoor Commitments and Their Applications to Proof s of Knowledge Secure Under Concurrent Man-in-the-Middle Attacks. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 220–236. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  9. Damgård, I., Nielsen, J.B., Orlandi, C.: On the necessary and sufficient assumptions for uc computation. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978. Springer, Heidelberg (2010)

    Google Scholar 

  10. 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)

    Google Scholar 

  11. Canetti, R., Goldreich, O., Goldwasser, S., Micali, S.: Resettable zero-knowledge. In: Proc. 32th STOC, pp. 235–244 (2000)

    Google Scholar 

  12. Micciancio, D., Petrank, E.: Simulatable commitments and efficient concurrent zero-knowledge. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 140–159. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  13. Lin, H., Pass, R., Venkitasubramaniam, M.: Concurrent non-malleable commitments from any one-way function. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 571–588. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  14. Pass, R., Rosen, A.: New and improved constructions of non-malleable cryptographic protocols. In: Proc. 37th STOC (2005)

    Google Scholar 

  15. De Santis, A., Di Crescenzo, G., Ostrovsky, R., Persiano, G., Sahai, A.: Robust non-interactive zero knowledge. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 566–598. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  16. Mohassel, P., Franklin, M.K.: Efficiency tradeoffs for malicious two-party computation. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.) PKC 2006. LNCS, vol. 3958, pp. 458–473. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  17. Woodruff, D.P.: Revisiting the efficiency of malicious two-party computation. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 79–96. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  18. Lindell, Y., Pinkas, B.: An efficient protocol for secure two-party computation in the presence of malicious adversaries. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 52–78. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  19. Goyal, V., Mohassel, P., Smith, A.: Efficient two party and multi party computation against covert adversaries. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 289–306. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  20. Chase, M., Lysyanskaya, A.: Simulatable vrfs with applications to multi-theorem nizk. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 303–322. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  21. Groth, J., Ostrovsky, R., Sahai, A.: Perfect non-interactive zero knowledge for NP. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 339–358. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  22. Goldreich, O.: Foundations of Cryptography: Basic Tools. Cambridge University Press, Cambridge (2001)

    Book MATH  Google Scholar 

  23. Schnorr, C.P.: Efficient identification and signatures for smart cards (abstract). In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 688–689. Springer, Heidelberg (1990)

    Chapter  Google Scholar 

  24. Richardson, R., Kilian, J.: On the concurrent composition of zero-knowledge proofs. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 415–432. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  25. Prabhakaran, M., Rosen, A., Sahai, A.: Concurrent zero knowledge with logarithmic round-complexity. In: FOCS, pp. 366–375 (2002)

    Google Scholar 

  26. Di Crescenzo, G., Persiano, G., Visconti, I.: Constant-round resettable zero knowledge with concurrent soundness in the bare public-key model. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 237–253. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  27. Di Crescenzo, G., Visconti, I.: Concurrent zero knowledge in the public-key model. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 816–827. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  28. Visconti, I.: Efficient zero knowledge on the internet. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 22–33. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  29. Ostrovsky, R., Persiano, G., Visconti, I.: Constant-round concurrent nmwi and its relation to nmzk. Technical Report ECCC Report TR06-095, ECCC (2006)

    Google Scholar 

  30. Ostrovsky, R., Persiano, G., Visconti, I.: Constant-round concurrent non-malleable zero knowledge in the bare public-key model. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 548–559. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of California, Los Angeles, USA

    Rafail Ostrovsky & Omkant Pandey

  2. University of Salerno, Italy

    Ivan Visconti

Authors
  1. Rafail Ostrovsky

    You can also search for this author inPubMed Google Scholar

  2. Omkant Pandey

    You can also search for this author inPubMed Google Scholar

  3. Ivan Visconti

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Computer Science & Engineering Department, University of California,, 9500 Gilman Drive, La Jolla, 92093-5004, San Diego, CA, USA

    Daniele Micciancio

Rights and permissions

Copyright information

© 2010 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Ostrovsky, R., Pandey, O., Visconti, I. (2010). Efficiency Preserving Transformations for Concurrent Non-malleable Zero Knowledge. In: Micciancio, D. (eds) Theory of Cryptography. TCC 2010. Lecture Notes in Computer Science, vol 5978. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11799-2_32

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp