Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Non-Malleable Zero Knowledge: Black-Box Constructions and Definitional Relationships

  • Conference paper
Security and Cryptography for Networks (SCN 2014)

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

Included in the following conference series:

Abstract

This paper deals with efficient non-malleable zero-knowledge proofs for \(\mathcal{NP}\), based on general assumptions. We give the first construction of a simulation-sound zero-knowledge (\(\mathcal{ZK}\)) protocol for \(\mathcal{NP}\) based only on the black-box use of one-way functions. Constructing such a proof system has been an open question ever since the original work of Dolev, Dwork, and Naor [18]. In addition to the feasibility result, our protocol has a constant number of rounds, which is asymptotically optimal.

Traditionally, the term non-malleable zero-knowledge (NmZK) refers to the original definition of [18]; but today it is used loosely to also refer to simulation-soundness (simsound) [51], and simulation-extractability (SimExt) [47]. While SimExt implies NmZK, the common perception is that SimExt is strongest of the three notions. However, very few results about their exact relationship are known.

In the second part of this work, we provide further results about the exact relationship between these notions. We show that in the “static” case, if an NmZK protocol is also an argument-of-knowledge, then it is in fact SimExt. Furthermore, in the most strict sense of the definition, SimSound does not necessarily follow from SimExt. These results are somewhat surprising because they are opposite to the common perception that SimExt is the strongest of the three notions.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Barak, B.: Constant-round coin-tossing with a man in the middle or realizing the shared random string model. In: FOCS (2002)

    Google Scholar 

  2. Bellare, M., Desai, A., Pointcheval, D., Rogaway, P.: Relations among notions of security for public-key encryption schemes. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 26–45. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  3. Bellare, M., Fischlin, M., O’Neill, A., Ristenpart, T.: Deterministic encryption: Definitional equivalences and constructions without random oracles. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 360–378. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  4. Ben-David, A., Nisan, N., Pinkas, B.: Fairplaymp: a system for secure multi-party computation. In: ACM Conference on Computer and Communications Security (2008)

    Google Scholar 

  5. Blum, M.: How to prove a theorem so no one else can claim it. In: Proceedings of the International Congress of Mathematicians, pp. 1444–1451 (1987)

    Google Scholar 

  6. Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications (extended abstract). In: STOC, pp. 103–112 (1988)

    Google Scholar 

  7. Blum, M., Santis, A.D., Micali, S., Persiano, G.: Noninteractive zero-knowledge. SIAM J. Comput. 20(6), 1084–1118 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  8. Boldyreva, A., Cash, D., Fischlin, M., Warinschi, B.: Foundations of non-malleable hash and one-way functions. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 524–541. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  9. Boldyreva, A., Fehr, S., O’Neill, A.: On notions of security for deterministic encryption, and efficient constructions without random oracles. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 335–359. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  10. Canetti, R., Goldreich, O., Goldwasser, S., Micali, S.: Resettable zero-knowledge

    Google Scholar 

  11. Canetti, R., Lin, H., Pass, R.: Adaptive hardness and composable security in the plain model from standard assumptions. In: FOCS (2010)

    Google Scholar 

  12. Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party computation. In: Proc. 34th STOC, pp. 494–503 (2002)

    Google Scholar 

  13. Cook, S.A.: The complexity of theorem-proving procedures. In: STOC, pp. 151–158 (1971)

    Google Scholar 

  14. 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, p. 40. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  15. Crescenzo, G.D., Visconti, I.: On defining proofs of knowledge in the bare public key model. In: ICTCS (2007)

    Google Scholar 

  16. 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), http://link.springer.de/link/service/series/0558/papers/2139/21390566.pdf

    Chapter  Google Scholar 

  17. Dodis, Y., Wichs, D.: Non-malleable extractors and symmetric key cryptography from weak secrets. In: STOC (2009)

    Google Scholar 

  18. Dolev, D., Dwork, C., Naor, M.: Non-malleable cryptography (extended abstract). In: STOC (1991)

    Google Scholar 

  19. Dolev, D., Dwork, C., Naor, M.: Nonmalleable cryptography. SIAM J. Comput. 30(2), 391–437 (electronic) (2000), Preliminary version in STOC 1991

    Google Scholar 

  20. Dziembowski, S., Pietrzak, K., Wichs, D.: Non-malleable codes. In: ICS (2010)

    Google Scholar 

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

    Google Scholar 

  22. Feige, U., Shamir, A.: Witness indistinguishable and witness hiding protocols. In: Proc. 22nd STOC, pp. 416–426 (1990)

    Google Scholar 

  23. Garay, J.A., MacKenzie, P.D., Yang, K.: Strengthening zero-knowledge protocols using signatures. J. Cryptology 19(2) (2006)

    Google Scholar 

  24. Goldreich, O., Kahan, A.: How to construct constant-round zero-knowledge proof systems for NP. Journal of Cryptology 9(3), 167–189 (Summer 1996)

    Google Scholar 

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

    Google Scholar 

  26. Goyal, V.: Constant round non-malleable protocols using one way functions. In: STOC (2011)

    Google Scholar 

  27. Goyal, V., Lee, C.K., Ostrovsky, R., Visconti, I.: Constructing non-malleable commitments: A black-box approach. In: FOCS (2012)

    Google Scholar 

  28. Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85–103 (1972)

    Google Scholar 

  29. Katz, J., Yung, M.: Complete characterization of security notions for probabilistic private-key encryption. In: STOC, pp. 245–254 (2000)

    Google Scholar 

  30. Levin, L.A.: Problems, complete in “average” instance. In: STOC, p. 465 (1984)

    Google Scholar 

  31. Lin, H., Pass, R.: Non-malleability amplification. In: STOC, pp. 189–198 (2009)

    Google Scholar 

  32. Lin, H., Pass, R.: Constant-round non-malleable commitments from any one-way function. In: STOC (2011)

    Google Scholar 

  33. 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 

  34. Lin, H., Pass, R., Venkitasubramaniam, M.: A unified framework for concurrent security: universal composability from stand-alone non-malleability. In: STOC (2009)

    Google Scholar 

  35. Lindell, Y.: Parallel coin-tossing and constant-round secure two-party computation. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 171–189. Springer, Heidelberg (2001), http://link.springer.de/link/service/series/0558/papers/2139/21390171.pdf

    Chapter  Google Scholar 

  36. Lindell, Y.: Bounded-concurrent secure two-party computation without setup assumptions. In: Proc. 35th STOC, pp. 683–692 (2003)

    Google Scholar 

  37. Lindell, Y.: Constant round zero knowledge proofs of knowledge (2010), http://eprint.iacr.org/2010/487.pdf

  38. Lindell, Y.: Highly-efficient universally-composable commitments based on the DDH assumption. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 446–466. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  39. Malkhi, D., Nisan, N., Pinkas, B., Sella, Y.: Fairplay - secure two-party computation system. In: USENIX Security Symposium (2004)

    Google Scholar 

  40. Naor, M.: Bit commitment using pseudo-randomness (extended abstract). In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 128–136. Springer, Heidelberg (1990)

    Google Scholar 

  41. Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: STOC (1990)

    Google Scholar 

  42. Ostrovsky, R., Pandey, O., Visconti, I.: Efficiency preserving transformations for concurrent non-malleable zero knowledge. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 535–552. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  43. 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 

  44. Pandey, O., Pass, R., Vaikuntanathan, V.: Adaptive one-way functions and applications. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. CRYPTO, pp. 57–74. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  45. Pass, R.: Bounded-concurrent secure multi-party computation with a dishonest majority. In: Proc. 36th STOC, pp. 232–241 (2004)

    Google Scholar 

  46. Pass, R., Rosen, A.: Concurrent non-malleable commitments. In: FOCS (2005)

    Google Scholar 

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

    Google Scholar 

  48. Pass, R., Wee, H.: Constant-round non-malleable commitments from sub-exponential one-way functions. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 638–655. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  49. Prabhakaran, M., Rosen, A., Sahai, A.: Concurrent zero knowledge with logarithmic round-complexity. In: FOCS (2002)

    Google Scholar 

  50. Rosen, A.: A note on constant-round zero-knowledge proofs for NP. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 191–202. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  51. Sahai, A.: Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In: Proc. 40th FOCS, pp. 543–553 (1999)

    Google Scholar 

  52. Wee, H.: Black-box, round-efficient secure computation via non-malleability amplification. In: FOCS (2010)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Boston University and MIT, USA

    Abhishek Jain

  2. UIUC, USA

    Omkant Pandey

Authors
  1. Abhishek Jain
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Omkant Pandey
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. École Normale Supérieure & CNRS, 45 rue d’Ulm, 75005, Paris, France

    Michel Abdalla

  2. Dipartimento di Informatica, Università di Salerno, via Ponte don Melillo, 84084, Fisciano, Italy

    Roberto De Prisco

Rights and permissions

Reprints and permissions

Copyright information

© 2014 Springer International Publishing Switzerland

About this paper

Cite this paper

Jain, A., Pandey, O. (2014). Non-Malleable Zero Knowledge: Black-Box Constructions and Definitional Relationships. In: Abdalla, M., De Prisco, R. (eds) Security and Cryptography for Networks. SCN 2014. Lecture Notes in Computer Science, vol 8642. Springer, Cham. https://doi.org/10.1007/978-3-319-10879-7_25

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-10879-7_25

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-10878-0

  • Online ISBN: 978-3-319-10879-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation