Paper 2020/082

Random Walks and Concurrent Zero-Knowledge

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

Abstract

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.