Welcome to the resource topic for 2020/082
Title:
Random Walks and Concurrent Zero-Knowledge
Authors: Anand Aiyer, Xiao Liang, Nilu Nalini, 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.
ePrint: https://eprint.iacr.org/2020/082
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .