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 case study of concurrent schedules, forcing rounds for 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 or an existing session receives the next message with probability ; 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.
@misc{cryptoeprint:2020/082,
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},
url = {https://eprint.iacr.org/2020/082}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.