Abstract:

  Designing protocols that retain their zero-knowledge properties 
  when executed concurrently is a challenging problem. We present 
  a lower bound on the number of rounds in concurrent zero-knowledge 
  protocols. We show that in the context of black-box concurrent 
  zero-knowledge, ~Omega(log n) rounds of interaction are 
  essential for non-trivial proof systems (i.e., systems for languages
  that are not in BPP). This result achieves a substantial improvement
  over previous best lower bound, and is the first bound to rule out
  the possibility of constant-round concurrent zero-knowledge when 
  proven via black-box simulation. Furthermore, the bound is polynomially
  related to the number of rounds in the best known concurrent 
  zero-knowledge protocol for languages in NP.
   
  Joint work with Ran Canetti, Joe Kilian and Erez Petrank.