Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

From Weak to Strong Zero-Knowledge and Applications

  • Conference paper

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

Included in the following conference series:

  • 1429Accesses

Abstract

The notion ofzero-knowledge [20] is formalized by requiring that for every malicious efficient verifierV*, there exists an efficient simulatorS that can reconstruct the view ofV* in a true interaction with the prover, in a way that is indistinguishable toevery polynomial-time distinguisher.Weak zero-knowledge weakens this notions by switching the order of the quantifiers and only requires that for every distinguisherD, there exists a (potentially different) simulatorSD.

In this paper we consider various notions of zero-knowledge, and investigate whether their weak variants are equivalent to their strong variants. Although we show (under complexity assumption) that for the standard notion of zero-knowledge, its weak and strong counterparts are not equivalent, for meaningful variants of the standard notion, the weak and strong counterparts are indeed equivalent. Towards showing these equivalences, we introduce new non-black-box simulation techniques permitting us, for instance, to demonstrate that the classical 2-round graph non-isomorphism protocol of Goldreich-Micali-Wigderson [18] satisfies a “distributional” variant of zero-knowledge.

Our equivalence theorem has other applications beyond the notion of zero-knowledge. For instance, it directly implies thedense model theorem of Reingold et al (STOC ’08), and the leakage lemma of Gentry-Wichs (STOC ’11), and provides a modular and arguably simpler proof of these results (while at the same time recasting these result in the language of zero-knowledge).

A full version of this paper is available athttps://eprint.iacr.org/2013/260

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. Althfer, I.: On sparse approximations to randomized strategies and convex combinations. Linear Algebra and its Applications 199(suppl.1), 339–355 (1994)

    Google Scholar 

  2. Barak, B.: How to go beyond the black-box simulation barrier. In: FOCS, pp. 106–115 (2001)

    Google Scholar 

  3. Barak, B., Sahai, A.: How to play almost any mental game over the net - concurrent composition via super-polynomial simulation. In: FOCS, pp. 543–552 (2005)

    Google Scholar 

  4. Barak, B., Shaltiel, R., Wigderson, A.: Computational analogues of entropy. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol. 2764, pp. 200–215. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  5. Bitansky, N., Paneth, O.: From the impossibility of obfuscation to a new non-black-box simulation technique. In: FOCS (2012)

    Google Scholar 

  6. Bitansky, N., Paneth, O.: On the impossibility of approximate obfuscation and applications to resettable cryptography. In: STOC (2013)

    Google Scholar 

  7. Boneh, D., Naor, M.: Timed commitments. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 236–254. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  8. Chung, K.-M., Kalai, Y.T., Liu, F.-H., Raz, R.: Memory delegation. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 151–168. Springer, Heidelberg (2011),http://dl.acm.org/citation.cfm?id=2033036.2033048

    Chapter  Google Scholar 

  9. Chung, K.M., Lui, E., Pass, R.: Can theories be tested? A cryptographic treatment of forecast testing. In: ITCS, pp. 47–56 (2013)

    Google Scholar 

  10. Chung, K.M., Pass, R., Seth, K.: Non-black-box simulation from one-way functions and applications to resettable security. In: STOC. ACM (2013)

    Google Scholar 

  11. Deng, Y., Goyal, V., Sahai, A.: Resolving the simultaneous resettability conjecture and a new non-black-box simulation strategy. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pp. 251–260. IEEE (2009)

    Google Scholar 

  12. Dwork, C., Naor, M., Reingold, O., Stockmeyer, L.: Magic functions: In memoriam: Bernard m. dwork 1923–1998. J. ACM 50(6), 852–921 (2003)

    Article MathSciNet  Google Scholar 

  13. Dziembowski, S., Pietrzak, K.: Leakage-resilient cryptography. In: 49th FOCS, pp. 293–302. IEEE Computer Society Press (2008)

    Google Scholar 

  14. Freund, Y., Schapire, R.E.: Adaptive game playing using multiplicative weights. Games and Economic Behavior 29(1), 79–103 (1999)

    Article MATH MathSciNet  Google Scholar 

  15. Frieze, A., Kannan, R.: Quick approximation to matrices and applications. Combinatorica 19(2), 175–220 (1999)

    Article MATH MathSciNet  Google Scholar 

  16. Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC 2011, pp. 99–108. ACM, New York (2011)

    Google Scholar 

  17. Goldreich, O.: A uniform-complexity treatment of encryption and zero-knowledge. Journal of Cryptology 6, 21–53 (1993)

    Article MATH MathSciNet  Google Scholar 

  18. 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), 690–728 (1991),http://doi.acm.org/10.1145/116825.116852

    Article MathSciNet  Google Scholar 

  19. Goldreich, O., Vadhan, S.P., Wigderson, A.: On interactive proofs with a laconic prover. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 334–345. Springer, Heidelberg (2001),http://dl.acm.org/citation.cfm?id=646254.684254

    Chapter  Google Scholar 

  20. Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC 1985, pp. 291–304. ACM (1985)

    Google Scholar 

  21. Halpern, J., Pass, R.: Game theory with costly computation: formulation and application to protocol security. In: Proceedings of the Behavioral and Quantitative Game Theory: Conference on Future Directions, BQGT 2010, p. 89:1. ACM, New York (2010),http://doi.acm.org/10.1145/1807406.1807495

  22. Impagliazzo, R.: Hard-core distributions for somewhat hard problems. In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science, FOCS 1995, pp. 538–545. IEEE Computer Society (1995)

    Google Scholar 

  23. Jetchev, D., Pietrzak, K.: How to fake auxiliary input. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 566–590. Springer, Heidelberg (2014)

    Chapter  Google Scholar 

  24. Lipton, R.J., Young, N.E.: Simple strategies for large zero-sum games with applications to complexity theory. In: Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, STOC 1994, pp. 734–740. ACM (1994)

    Google Scholar 

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

    Google Scholar 

  26. Pass, R., Rosen, A.: Bounded-concurrent secure two-party computation in a constant number of rounds. In: FOCS, pp. 404–413 (2003)

    Google Scholar 

  27. Pass, R., Rosen, A.: New and improved constructions of non-malleable cryptographic protocols. In: STOC 2005, pp. 533–542 (2005)

    Google Scholar 

  28. Reingold, O., Trevisan, L., Tulsiani, M., Vadhan, S.: Dense subsets of pseudorandom sets. In: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, pp. 76–85 (2008)

    Google Scholar 

  29. Sahai, A., Vadhan, S.: A complete problem for statistical zero knowledge. J. ACM 50(2), 196–249 (2003)

    Article MathSciNet  Google Scholar 

  30. Trevisan, L., Tulsiani, M., Vadhan, S.: Regularity, boosting, and efficiently simulating every high-entropy distribution. In: Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009, pp. 126–136. IEEE Computer Society (2009)

    Google Scholar 

  31. Vadhan, S., Zheng, C.J.: A uniform min-max theorem with applications in cryptography. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 93–110. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  32. Yao, A.C.: Theory and application of trapdoor functions. In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, SFCS 1982, pp. 80–91 (1982)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Academia Sinica, Taiwan

    Kai-Min Chung

  2. Cornell University, USA

    Edward Lui & Rafael Pass

Authors
  1. Kai-Min Chung

    You can also search for this author inPubMed Google Scholar

  2. Edward Lui

    You can also search for this author inPubMed Google Scholar

  3. Rafael Pass

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, New York University, 251 Mercer Street, 10012, New York, NY, USA

    Yevgeniy Dodis

  2. Department of Computer Science, Aarhus University, Åbogade 34, 8200, Aarhus N, Denmark

    Jesper Buus Nielsen

Rights and permissions

Copyright information

© 2015 International Association for Cryptologic Research

About this paper

Cite this paper

Chung, KM., Lui, E., Pass, R. (2015). From Weak to Strong Zero-Knowledge and Applications. In: Dodis, Y., Nielsen, J.B. (eds) Theory of Cryptography. TCC 2015. Lecture Notes in Computer Science, vol 9014. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46494-6_4

Download citation

Publish with us

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