Non-Uniformly Sound Certificates with Applications to Concurrent Zero-Knowledge | SpringerLink
Skip to main content
Springer Nature Link
Log in

Non-Uniformly Sound Certificates with Applications to Concurrent Zero-Knowledge

  • Conference paper
  • First Online:
Advances in Cryptology – CRYPTO 2019 (CRYPTO 2019)

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

Included in the following conference series:

Abstract

We introduce the notion of non-uniformly sound certificates: succinct single-message (unidirectional) argument systems that satisfy a “best-possible security” against non-uniform polynomial-time attackers. In particular, no polynomial-time attacker with s bits of non-uniform advice can find significantly more than s accepting proofs for false statements. Our first result is a construction of non-uniformly sound certificates for all \(\mathbf{NP }\) in the random oracle model, where the attacker’s advice can depend arbitrarily on the random oracle.

We next show that the existence of non-uniformly sound certificates for \(\mathbf{P }\) (and collision resistant hash functions) yields a public-coin constant-round fully concurrent zero-knowledge argument for \(\mathbf{NP } \).

Supported in part by NSF Award CNS-1561209, NSF Award SATC-1617676, NSF Award SATC-1704788, and AFOSR Award FA9550-15-1-0262.

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
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 16015
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 20019
Price includes VAT (Japan)
  • 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

Similar content being viewed by others

References

  1. Barak, B.: How to go beyond the black-box simulation barrier. In: 42nd Annual Symposium on Foundations of Computer Science, FOCS, pp. 106–115 (2001)

    Google Scholar 

  2. Barak, B., Goldreich, O.: Universal arguments and their applications. SIAM J. Comput. 38(5), 1661–1694 (2008)

    Article  MathSciNet  Google Scholar 

  3. Barak, B., Goldreich, O., Goldwasser, S., Lindell, Y.: Resettably-sound zero-knowledge and its applications. In: 42nd Annual Symposium on Foundations of Computer Science, FOCS, pp. 116–125 (2001)

    Google Scholar 

  4. Barak, B., Lindell, Y., Vadhan, S.P.: Lower bounds for non-black-box zero knowledge. J. Comput. Syst. Sci. 72(2), 321–391 (2006)

    Article  MathSciNet  Google Scholar 

  5. Barak, B., Ong, S.J., Vadhan, S.P.: Derandomization in cryptography. SIAM J. Comput. 37(2), 380–400 (2007)

    Article  MathSciNet  Google Scholar 

  6. Berman, I., Degwekar, A., Rothblum, R.D., Vasudevan, P.N.: Multi-collision resistant hash functions and their applications. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 133–161. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_5

    Chapter  Google Scholar 

  7. Bitansky, N., Kalai, Y.T., Paneth, O.: Multi-collision resistance: a paradigm for keyless hash functions. In: 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pp. 671–684 (2018)

    Google Scholar 

  8. Bitansky, N., Lin, H.: One-message zero knowledge and non-malleable commitments. In: Beimel, A., Dziembowski, S. (eds.) TCC 2018. LNCS, vol. 11239, pp. 209–234. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03807-6_8

    Chapter  Google Scholar 

  9. Brassard, G., Chaum, D., Crépeau, C.: Minimum disclosure proofs of knowledge. J. Comput. Syst. Sci. 37(2), 156–189 (1988)

    Article  MathSciNet  Google Scholar 

  10. Canetti, R., Goldreich, O., Goldwasser, S., Micali, S.: Resettable zero-knowledge (extended abstract). In: 32nd Annual ACM Symposium on Theory of Computing, STOC, pp. 235–244 (2000)

    Google Scholar 

  11. Canetti, R., Kilian, J., Petrank, E., Rosen, A.: Black-box concurrent zero-knowledge requires (almost) logarithmically many rounds. SIAM J. Comput. 32(1), 1–47 (2002)

    Article  MathSciNet  Google Scholar 

  12. Canetti, R., Lin, H., Paneth, O.: Public-coin concurrent zero-knowledge in the global hash model. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 80–99. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_5

    Chapter  Google Scholar 

  13. Chongchitmate, W., Ostrovsky, R., Visconti, I.: Resettably-sound resettable zero knowledge in constant rounds. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10678, pp. 111–138. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70503-3_4

    Chapter  Google Scholar 

  14. Chung, K., Lin, H., Pass, R.: Constant-round concurrent zero knowledge from p-certificates. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 50–59 (2013)

    Google Scholar 

  15. Chung, K.-M., Lin, H., Pass, R.: Constant-round concurrent zero-knowledge from indistinguishability obfuscation. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 287–307. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_14

    Chapter  Google Scholar 

  16. Coretti, S., Dodis, Y., Guo, S., Steinberger, J.P.: Random oracles and non-uniformity. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 227–258. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_9

    Chapter  Google Scholar 

  17. 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). https://doi.org/10.1007/3-540-45539-6_30

    Chapter  Google Scholar 

  18. 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, pp. 251–260 (2009)

    Google Scholar 

  19. Dwork, C., Naor, M., Sahai, A.: Concurrent zero-knowledge. J. ACM (JACM) 51(6), 851–898 (2004)

    Article  MathSciNet  Google Scholar 

  20. Dwork, C., Sahai, A.: Concurrent zero-knowledge: reducing the need for timing constraints. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 442–457. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055746

    Chapter  Google Scholar 

  21. Feige, U., Shamir, A.: Witness indistinguishable and witness hiding protocols. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, pp. 416–426. ACM (1990)

    Google Scholar 

  22. 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). https://doi.org/10.1007/3-540-47721-7_12

    Chapter  Google Scholar 

  23. Fortnow, L.: Kolmogorov complexity and computational complexity. Complexity of Computations and Proofs. Quaderni di Matematica, vol. 13 (2004)

    Google Scholar 

  24. Garg, S., Jain, A., Sahai, A.: Leakage-resilient zero knowledge. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 297–315. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_17

    Chapter  Google Scholar 

  25. Gennaro, R., Trevisan, L.: Lower bounds on the efficiency of generic cryptographic constructions. In: 41st Annual Symposium on Foundations of Computer Science, FOCS, pp. 305–313 (2000)

    Google Scholar 

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

    Google Scholar 

  27. Goldreich, O.: The Foundations of Cryptography - Volume 1, Basic Techniques. Cambridge University Press, Cambridge (2001)

    Book  Google Scholar 

  28. Goldreich, O.: Concurrent zero-knowledge with timing, revisited. In: 34th Annual ACM Symposium on Theory of Computing, STOC, pp. 332–340 (2002)

    Google Scholar 

  29. Goldreich, O., Håstad, J.: On the complexity of interactive proofs with bounded communication. Inf. Process. Lett. 67(4), 205–214 (1998)

    Article  MathSciNet  Google Scholar 

  30. Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989)

    Article  MathSciNet  Google Scholar 

  31. Goyal, V.: Non-black-box simulation in the fully concurrent setting. In: Symposium on Theory of Computing Conference, STOC, pp. 221–230. ACM (2013)

    Google Scholar 

  32. Goyal, V., Jain, A., Ostrovsky, R., Richelson, S., Visconti, I.: Constant-round concurrent zero knowledge in the bounded player model. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013. LNCS, vol. 8269, pp. 21–40. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-42033-7_2

    Chapter  MATH  Google Scholar 

  33. Gupta, D., Sahai, A.: On constant-round concurrent zero-knowledge from a knowledge assumption. In: Meier, W., Mukhopadhyay, D. (eds.) INDOCRYPT 2014. LNCS, vol. 8885, pp. 71–88. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13039-2_5

    Chapter  Google Scholar 

  34. Guruswami, V., Sudan, M.: Improved decoding of Reed-Solomon and algebraic-geometry codes. IEEE Trans. Inf. Theory 45(6), 1757–1767 (1999)

    Article  MathSciNet  Google Scholar 

  35. Guruswami, V., Umans, C., Vadhan, S.P.: Unbalanced expanders and randomness extractors from parvaresh-vardy codes. J. ACM 56(4), 20:1–20:34 (2009)

    Article  MathSciNet  Google Scholar 

  36. Haitner, I., Ishai, Y., Omri, E., Shaltiel, R.: Parallel hashing via list recoverability. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 173–190. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_9

    Chapter  Google Scholar 

  37. Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999)

    Article  MathSciNet  Google Scholar 

  38. Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, pp. 723–732. ACM (1992)

    Google Scholar 

  39. Kilian, J.: Improved efficient arguments. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 311–324. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-44750-4_25

    Chapter  Google Scholar 

  40. Kilian, J., Petrank, E.: Concurrent and resettable zero-knowledge in poly-loalgorithm rounds. In: 33rd Annual ACM Symposium on Theory of Computing, STOC, pp. 560–569 (2001)

    Google Scholar 

  41. Komargodski, I., Naor, M., Yogev, E.: White-box vs. black-box complexity of search problems: Ramsey and graph property testing. In: 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 622–632 (2017)

    Google Scholar 

  42. Komargodski, I., Naor, M., Yogev, E.: Collision resistant hashing for paranoids: dealing with multiple collisions. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 162–194. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_6

    Chapter  Google Scholar 

  43. Komargodski, I., Yogev, E.: On distributional collision resistant hashing. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10992, pp. 303–327. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_11

    Chapter  Google Scholar 

  44. Merkle, R.C.: A certified digital signature. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 218–238. Springer, New York (1990). https://doi.org/10.1007/0-387-34805-0_21

    Chapter  Google Scholar 

  45. Micali, S.: Computationally sound proofs. SIAM J. Comput. 30(4), 1253–1298 (2000)

    Article  MathSciNet  Google Scholar 

  46. Naor, M.: Bit commitment using pseudorandomness. J. Cryptol. 4(2), 151–158 (1991)

    Article  Google Scholar 

  47. Pandey, O., Prabhakaran, M., Sahai, A.: Obfuscation-based non-black-box simulation and four message concurrent zero knowledge for NP. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 638–667. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46497-7_25

    Chapter  Google Scholar 

  48. Pass, R.: Simulation in quasi-polynomial time, and its application to protocol composition. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 160–176. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_10

    Chapter  Google Scholar 

  49. Pass, R., Rosen, A., Tseng, W.D.: Public-coin parallel zero-knowledge for NP. J. Cryptol. 26(1), 1–10 (2013)

    Article  MathSciNet  Google Scholar 

  50. Pass, R., Tseng, W.D., Venkitasubramaniam, M.: Concurrent zero knowledge, revisited. J. Cryptol. 27(1), 45–66 (2014)

    Article  Google Scholar 

  51. Pass, R., Tseng, W.D., Wikström, D.: On the composition of public-coin zero-knowledge protocols. SIAM J. Comput. 40(6), 1529–1553 (2011)

    Article  MathSciNet  Google Scholar 

  52. Pass, R., Venkitasubramaniam, M.: On constant-round concurrent zero-knowledge. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 553–570. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78524-8_30

    Chapter  Google Scholar 

  53. Prabhakaran, M., Rosen, A., Sahai, A.: Concurrent zero knowledge with logarithmic round-complexity. In: 43rd Symposium on Foundations of Computer Science FOCS, pp. 366–375. IEEE Computer Society (2002)

    Google Scholar 

  54. Richardson, R., Kilian, J.: On the concurrent composition of zero-knowledge proofs. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 415–431. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_29

    Chapter  Google Scholar 

  55. Unruh, D.: Random oracles and auxiliary input. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 205–223. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74143-5_12

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Cornell Tech, New York, NY, 10044, USA

    Cody Freitag, Ilan Komargodski & Rafael Pass

Authors
  1. Cody Freitag
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ilan Komargodski
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Rafael Pass
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Cody Freitag .

Editor information

Editors and Affiliations

  1. Georgia Institute of Technology, Atlanta, GA, USA

    Alexandra Boldyreva

  2. University of California at San Diego, La Jolla, CA, USA

    Daniele Micciancio

Rights and permissions

Reprints and permissions

Copyright information

© 2019 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Freitag, C., Komargodski, I., Pass, R. (2019). Non-Uniformly Sound Certificates with Applications to Concurrent Zero-Knowledge. In: Boldyreva, A., Micciancio, D. (eds) Advances in Cryptology – CRYPTO 2019. CRYPTO 2019. Lecture Notes in Computer Science(), vol 11694. Springer, Cham. https://doi.org/10.1007/978-3-030-26954-8_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-26954-8_4

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-26953-1

  • Online ISBN: 978-3-030-26954-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation