Welcome to the resource topic for 2022/560
Title:
Distributed Shuffling in Adversarial Environments
Authors: Kasper Green Larsen, Maciej Obremski, 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.
ePrint: https://eprint.iacr.org/2022/560
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 .