Random Walks and Concurrent Zero-Knowledge

The established bounds on the round-complexity of (black-box) concurrent zero-knowledge consider adversarial verifiers with complete control over the scheduling of messages of different sessions. Consequently, such bounds only represent a worst case study of concurrent schedules, forcing rounds for 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 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 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; the existing session can be chosen either in a first-in-first-out or last-in-first-out 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 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 and models.