Paper 2022/560

Distributed Shuffling in Adversarial Environments

Kasper Green Larsen and Maciej Obremski and Mark Simkin

Abstract

We formalize and study the problem of distributed shuffling in adversarial environments. In this setting, there are $m$ shufflers that have access to a public bulletin board that stores a vector $(c_1, \dots, c_n)$ of re-randomizable commitments. The shufflers repeatedly read $k$ of the $n$ commitments, with $k$ potentially much smaller than $n$, and shuffle them. An adversary has the ability to initially corrupt and then track some of the commitments throughout the shuffles and can adaptively corrupt a bounded number of shufflers in every single round. The goal of the distributed shuffling protocol is to hide the output locations of commitments that are not corrupted by the adversary. We present and analyze a protocol that solves this problem with essentially optimal shuffling complexity. As an exemplary data point, our protocol can shuffle a list of length $n$ with shuffles of size $k$, where $k \in \Omega(\lg^2 n)$, in the presence of an adversary that can corrupt $4n/5$ many shufflers in each round and can corrupt $4n/5$ commitments in the input vector. Our $m$-party shuffling protocol with $m \in \Omega(n/k)$ terminates in $\mathcal{O}(\lg n)$ rounds. We provide numerical benchmarks that validate our theoretically proven guarantees and in fact show that the number of rounds is not just theoretically, but also concretely small. Our shuffling protocol can either improve efficiency or lead to more secure solutions in multiple research domains, such as the design of mix-nets, single secret leader election protocols, and electronic voting.