(, δ)-Indistinguishable Mixing for Cryptocurrencies

Authors: Mingyu Liang (George Mason University), Ioanna Karantaidou (George Mason University), Foteini Baldimtsi (George Mason University), S. Dov Gordon (George Mason University), Mayank Varia (Boston University)

Volume: 2022
Issue: 1
Pages: 49–74
DOI: https://doi.org/10.2478/popets-2022-0004

Download PDF

Abstract: We propose a new theoretical approach for building anonymous mixing mechanisms for cryptocurrencies. Rather than requiring a fully uniform permutation during mixing, we relax the requirement, insisting only that neighboring permutations are similarly likely. This is defined formally by borrowing from the definition of differential privacy. This relaxed privacy definition allows us to greatly reduce the amount of interaction and computation in the mixing protocol. Our construction achieves O(n·polylog(n)) computation time for mixing n addresses, whereas all other mixing schemes require O(n2 ) total computation across all parties. Additionally, we support a smooth tolerance of fail-stop adversaries and do not require any trusted setup. We analyze the security of our generic protocol under the UC framework, and under a stand-alone, game-based definition. We finally describe an instantiation using ring signatures and confidential transactions.

Keywords: Anonymous Mixing, Cryptocurrency, Differential Privacy

Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs license.