Paper 2022/560

Distributed Shuffling in Adversarial Environments

Kasper Green Larsen, Aarhus University
Maciej Obremski, National University of Singapore
Mark Simkin, Ethereum Foundation
Abstract

We study mix-nets in the context of cryptocurrencies. Here we have many computationally weak shufflers that speak one after another and want to joinlty shuffle a list of ciphertexts $(c_1, \dots, c_n)$. Each shuffler can only permute $k << n$ ciphertexts at a time. An adversary $\mathcal{A}$ can track some of the ciphertexts and adaptively corrupt some of the shufflers. We present a simple protocol for shuffling the list of ciphertexts efficiently. The main technical contribution of this work is to prove that our simple shuffling strategy does indeed provide good anonynmity guarantees and at the same time terminates quickly. Our shuffling algorithm provides a strict improvement over the current shuffling strategy in Ethereum's block proposer elections. Our algorithm is secure against a stronger adversary, provides provable security guarantees, and is comparably in efficiency to the current approach.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Shuffling Leader Election Mix-Nets
Contact author(s)
larsen @ cs au dk
obremski math @ gmail com
mark simkin @ etherum org
History
2022-10-12: last of 2 revisions
2022-05-10: received
See all versions
Short URL
https://ia.cr/2022/560
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/560,
      author = {Kasper Green Larsen and Maciej Obremski and Mark Simkin},
      title = {Distributed Shuffling in Adversarial Environments},
      howpublished = {Cryptology ePrint Archive, Paper 2022/560},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/560}},
      url = {https://eprint.iacr.org/2022/560}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.