Concurrent Zero-Knowledge with Timing, Revisited

  • Oded Goldreich
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3895)


Following Dwork, Naor, and Sahai (30th STOC, 1998), we consider concurrent executions of protocols in a semi-synchronized network. Specifically, we assume that each party holds a local clock such that bounds on the relative rates of these clocks as well as on the message-delivery time are a-priori known, and consider protocols that employ time-driven operations (i.e., time-out in-coming messages and delay out-going messages).

We show that the constant-round zero-knowledge proof for \({\cal NP}\) of Goldreich and Kahan (Jour. of Crypto., 1996) preserves its security when polynomially-many independent copies are executed concurrently under the above timing model.

We stress that our main result refers to zero-knowledge of interactive proofs, whereas the results of Dwork et. al. are either for zero-knowledge arguments or for a weak notion of zero-knowledge (called epsilon-knowledge) proofs.

Our analysis identifies two extreme schedulings of concurrent executions under the above timing model: the first is the case of parallel execution of polynomially-many copies, and the second is of concurrent execution of polynomially-many copies such that only a small (i.e., constant) number of copies are simultaneously active at any time (i.e., bounded simultaneity). Dealing with each of these extreme cases is of independent interest, and the general result (regarding concurrent executions under the timing model) is obtained by combining the two treatments.


Proof System Parallel Execution Parallel Composition Recursive Call Hybrid Simulator 
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.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Barak, B.: How to Go Beyond the Black-Box Simulation Barrier. In: 42nd FOCS, pp. 106–115 (2001)Google Scholar
  2. 2.
    Barak, B., Lindell, Y.: Strict Polynomial-time in Simulation and Extraction. In: 34th ACM Symposium on the Theory of Computing, pp. 484–493 (2002)Google Scholar
  3. 3.
    Bellare, M., Impagliazzo, R., Naor, M.: Does Parallel Repetition Lower the Error in Computationally Sound Protocols? In: 38th FOCS, pp. 374–383 (1997)Google Scholar
  4. 4.
    Bellare, M., Jakobsson, M., Yung, M.: Round-Optimal Zero-Knowledge Arguments based on any One-Way Function. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 280–305. Springer, Heidelberg (1997)Google Scholar
  5. 5.
    Bellare, M., Micali, S., Ostrovsky, R.: Perfect Zero-Knowledge in Constant Rounds. In: 22nd STOC, pp. 482–493 (1990)Google Scholar
  6. 6.
    Bellare, M., Micali, S., Ostrovsky, R.: The (True) Complexity of Statistical Zero Knowledge. In: 22nd STOC, pp. 494–502 (1990)Google Scholar
  7. 7.
    Brassard, G., Chaum, D., Crépeau, C.: Minimum Disclosure Proofs of Knowledge. JCSS 37(2), 156–189 (1988), Preliminary version by Brassard and Crépeau in 27th FOCS (1986) Google Scholar
  8. 8.
    Brassard, G., Crépeau, C., Yung, M.: Constant-Round Perfect Zero- Knowledge Computationally Convincing Protocols. Theoretical Computer Science 84, 23–52 (1991)zbMATHCrossRefMathSciNetGoogle Scholar
  9. 9.
    Canetti, R., Goldreich, O., Goldwasser, S., Micali, S.: Resettable Zero- Knowledge. In: 32nd STOC, pp. 235–244 (2000)Google Scholar
  10. 10.
    Canetti, R., Kilian, J., Petrank, E., Rosen, A.: Black-Box Concurrent Zero-Knowledge Requires (Almost) Logarithmically Many Rounds. SICOMP 32(1), 1–47 (2002), Preliminary version in 33rd STOC (2001)zbMATHMathSciNetGoogle Scholar
  11. 11.
    Damgård, L.: Efficient Concurrent Zero-Knowledge in the Auxiliary String Model. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 418–430. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  12. 12.
    Dolev, D., Dwork, C., Naor, M.: Non-Malleable Cryptography. SICOMP 30(2), 391–437 (2000), Preliminary version in 23rd STOC (1991)zbMATHMathSciNetGoogle Scholar
  13. 13.
    Dwork, C., Naor, M., Sahai, A.: Concurrent Zero-Knowledge. In: 30th STOC, pp. 409–418 (1998)Google Scholar
  14. 14.
    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)Google Scholar
  15. 15.
    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
  16. 16.
    Goldreich, O.: Foundation of Cryptography – Basic Tools. Cambridge University Press, Cambridge (2001)Google Scholar
  17. 17.
    Goldreich, O., Kahan, A.: How to Construct Constant-Round Zero- Knowledge Proof Systems for NP. J. of Crypto. 9(2), 167–189 (1996), Preliminary versions date to (1988)zbMATHCrossRefMathSciNetGoogle Scholar
  18. 18.
    Goldreich, O., Krawczyk, H.: On the Composition of Zero-Knowledge Proof Systems. In: SICOMP, February 1996, vol. 25(1), pp. 169–192 (1996), Preliminary version in 17th ICALP(1990)Google Scholar
  19. 19.
    Goldreich, O., Micali, S., Wigderson, A.: Proofs that Yield Nothing but their Validity or All Languages in NP Have Zero-Knowledge Proof Systems. JACM 38(1), 691–729 (1991), Preliminary version in 27th FOCS (1986)zbMATHMathSciNetGoogle Scholar
  20. 20.
    Goldreich, O., Oren, Y.: Definitions and Properties of Zero-Knowledge Proof Systems. J. of Crypto. 7(1), 1–32 (1994)zbMATHMathSciNetGoogle Scholar
  21. 21.
    Goldwasser, S., Micali, S.: Probabilistic Encryption. JCSS 28(2), 270–299 (1984), Preliminary version in 14th STOC (1982)zbMATHMathSciNetGoogle Scholar
  22. 22.
    Goldwasser, S., Micali, S., Rackoff, C.: Knowledge Complexity of Interactive Proofs. In: 17th STOC, pp. 291–304 (1985), This is a preliminary version of [23]Google Scholar
  23. 23.
    Goldwasser, S., Micali, S., Rackoff, C.: The Knowledge Complexity of Interactive Proof Systems. SICOMP 18, 186–208 (1989), Preliminary version in [22]zbMATHMathSciNetGoogle Scholar
  24. 24.
    Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A Pseudorandom Generator from any One-way Function. In: SICOMP, vol. 28(4), pp. 1364–1396 (1999); Preliminary versions by Impagliazzo et. al. in 21st STOC (1989) and Håstad in 22nd STOC (1990)Google Scholar
  25. 25.
    Kilian, J., Petrank, E.: Concurrent and resettable zero-knowledge in polylogarithmic rounds. In: 33rd STOC, pp. 560–569 (2001)Google Scholar
  26. 26.
    Kilian, J., Petrank, E., Rackoff, C.: Lower Bounds for Zero-Knowledge on the Internet. In: 39th FOCS, pp. 484–492 (1998)Google Scholar
  27. 27.
    Naor, M.: Bit Commitment using Pseudorandom Generators. J. of Crypto. 4, 151–158 (1991)zbMATHMathSciNetGoogle Scholar
  28. 28.
    Prabhakaran, M., Rosen, A., Sahai, A.: Concurrent Zero-Knowledge Proofs in Logarithmic Number of Rounds. In: 43rd IEEE Symposium on Foundations of Computer Science, pp. 366–375 (2002)Google Scholar
  29. 29.
    Richardson, R., Kilian, J.: On the Concurrent Composition of Zero- Knowledge Proofs. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 413–415. Springer, Heidelberg (1999)Google Scholar
  30. 30.
    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)CrossRefGoogle Scholar
  31. 31.
    Vadhan, S.: Probabilistic Proof Systems – Part I. IAS/Park City Mathematics Series, vol. 10, pp. 315–348 (2004)Google Scholar
  32. 32.
    Yao, A.C.: Theory and Application of Trapdoor Functions. In: 23rd FOCS, pp. 80–91 (1982)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Oded Goldreich
    • 1
  1. 1.Department of Computer Science and Applied MathematicsWeizmann Institute of ScienceIsrael

Personalised recommendations