License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2023.10
URN: urn:nbn:de:0030-drops-183385
Go to the corresponding LIPIcs Volume Portal

Larsen, Kasper Green ; Obremski, Maciej ; Simkin, Mark

Distributed Shuffling in Adversarial Environments

LIPIcs-ITC-2023-10.pdf (0.8 MB)


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₁, … , c_n). Each shuffler can only permute k << n ciphertexts at a time. An adversary 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 anonymity 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.

BibTeX - Entry

  author =	{Larsen, Kasper Green and Obremski, Maciej and Simkin, Mark},
  title =	{{Distributed Shuffling in Adversarial Environments}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-183385},
  doi =		{10.4230/LIPIcs.ITC.2023.10},
  annote =	{Keywords: Distributed Computing, Shuffling}

Keywords: Distributed Computing, Shuffling
Collection: 4th Conference on Information-Theoretic Cryptography (ITC 2023)
Issue Date: 2023
Date of publication: 21.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI