Aarhus University Seal

Distributed Shuffling in Adversarial Environments

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

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

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 (c1, ..., cn). 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.

Original languageEnglish
Title of host publication4th Conference on Information-Theoretic Cryptography, ITC 2023
EditorsKai-Min Chung
PublisherDagstuhl Publishing
Publication yearJul 2023
Article number10
ISBN (electronic)9783959772716
Publication statusPublished - Jul 2023
Event4th Conference on Information-Theoretic Cryptography, ITC 2023 - Aarhus, Denmark
Duration: 6 Jun 20238 Jun 2023


Conference4th Conference on Information-Theoretic Cryptography, ITC 2023
SeriesLeibniz International Proceedings in Informatics, LIPIcs

Bibliographical note

Publisher Copyright:
© Kasper Green Larsen, Maciej Obremski, and Mark Simkin; licensed under Creative Commons License CC-BY 4.0 4th Conference on Information-Theoretic Cryptography (ITC 2023)

    Research areas

  • Distributed Computing, Shuffling

See relations at Aarhus University Citationformats

ID: 341391726