Paper 2020/082

Random Walks and Concurrent Zero-Knowledge

Anand Aiyer, Xiao Liang, Nilu Nalini, and Omkant Pandey


The established bounds on the round-complexity of (black-box) concurrent zero-knowledge (cZK) consider adversarial verifiers with complete control over the scheduling of messages of different sessions. Consequently, such bounds only represent a $\textit{worst}$ case study of concurrent schedules, forcing $\widetilde{\Omega}(\log n)$ rounds for $\textit{all}$ protocol sessions. What happens in "average" cases against random schedules? Must all sessions still suffer large number of rounds? Rosen and Shelat first considered such possibility, and constructed a cZK protocol that adjusts its round-complexity based on existing network conditions. While they provide experimental evidence for its average-case performance, no provable guarantees are known. In general, a proper framework for studying and understanding the average-case schedules for cZK is missing. We present the first theoretical framework for performing such average-case studies. Our framework models the network as a stochastic process where a new session is opened with probability $p$ or an existing session receives the next message with probability $1-p$; the existing session can be chosen either in a first-in-first-out (FIFO) or last-in-first-out (LIFO) order. These two orders are fundamental and serve as good upper and lower bounds for other simple variations. We also develop methods for establishing provable average-case bounds for cZK in these models. The bounds in these models turn out to be intimately connected to various properties of one-dimensional random walks that reflect at the origin. Consequently, we establish new and tight asymptotic bounds for such random walks, including: expected rate of return-to-origin, changes of direction, and concentration of "positive" movements. These results may be of independent interest. Our analysis shows that the Rosen-Shelat protocol is highly sensitive to even moderate network conditions, resulting in a large fraction of non-optimal sessions. We construct a more robust protocol by generalizing the "footer-free" condition of Rosen-Shelat which leads to significant improvements for both FIFO and LIFO models.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.18th International Conference on Applied Cryptography and Network Security (ACNS 2020)
Concurrent Zero-KnowledgeOptimistic ProtocolsAverage CaseRandom Walks
Contact author(s)
liang1 @ cs stonybrook edu
omkant @ cs stonybrook edu
2020-04-22: revised
2020-01-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Anand Aiyer and Xiao Liang and Nilu Nalini and Omkant Pandey},
      title = {Random Walks and Concurrent Zero-Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2020/082},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.