Cryptology ePrint Archive: Report 2020/082

Random Walks and Concurrent Zero-Knowledge

Anand Aiyer and Xiao Liang and 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.

Category / Keywords: cryptographic protocols / Concurrent Zero-Knowledge, Optimistic Protocols, Average Case, Random Walks

Original Publication (with major differences): 18th International Conference on Applied Cryptography and Network Security (ACNS 2020)

Date: received 27 Jan 2020, last revised 22 Apr 2020

Contact author: liang1 at cs stonybrook edu, omkant at cs stonybrook edu

Available format(s): PDF | BibTeX Citation

Version: 20200422:235926 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]