Paper 2022/942

Foundations of Coin Mixing Services

Noemi Glaeser, University of Maryland, Max Planck Institute for Security and Privacy
Matteo Maffei, TU Wien
Giulio Malavolta, Max Planck Institute for Security and Privacy
Pedro Moreno-Sanchez, IMDEA Software Institute
Erkan Tairi, TU Wien
Sri AravindaKrishnan Thyagarajan, Carnegie Mellon University

Coin mixing services allow users to mix their cryptocurrency coins and thus enable unlinkable payments in a way that prevents tracking of honest users' coins by both the service provider and the users themselves. The easy bootstrapping of new users and backwards compatibility with cryptocurrencies (such as Bitcoin) with limited support for scripts are attractive features of this architecture, which has recently gained considerable attention in both academia and industry. A recent work of Tairi et al. [IEEE S&P 2021] formalizes the notion of a coin mixing service and proposes A$^{2}$L, a new cryptographic protocol that simultaneously achieves high efficiency and interoperability. In this work, we identify a gap in their formal model and substantiate the issue by showing two concrete counterexamples: we show how to construct two encryption schemes that satisfy their definitions but lead to a completely insecure system. To amend this situation, we investigate secure constructions of coin mixing services. First, we develop the notion of blind conditional signatures (BCS), which acts as the cryptographic core for coin mixing services. We propose game-based security definitions for BCS and propose A$^{2}$L$^{+}$, a modified version of the protocol by Tairi et al. that satisfies our security definitions. Our analysis is in an idealized model (akin to the algebraic group model) and assumes the hardness of the one-more discrete logarithm problem. Finally, we propose A$^{2}$L$^\text{UC}$, another construction of BCS that achieves the stronger notion of UC-security (in the standard model), albeit with a significant increase in computation cost. This suggests that constructing a coin mixing service protocol secure under composition requires more complex cryptographic machinery than initially thought.

Available format(s)
Publication info
Published elsewhere. ACM CCS 2022
Blockchain Cryptocurrencies Mixing
Contact author(s)
nglaeser @ umd edu
matteo maffei @ tuwien ac at
giulio malavolta @ hotmail it
pedro moreno @ imdea org
erkan tairi @ tuwien ac at
t srikrishnan @ gmail com
2022-09-01: last of 4 revisions
2022-07-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Noemi Glaeser and Matteo Maffei and Giulio Malavolta and Pedro Moreno-Sanchez and Erkan Tairi and Sri AravindaKrishnan Thyagarajan},
      title = {Foundations of Coin Mixing Services},
      howpublished = {Cryptology ePrint Archive, Paper 2022/942},
      year = {2022},
      doi = {10.1145/3548606.3560637},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.