Paper 2021/036

The Cryptographic Complexity of Anonymous Coins: A Systematic Exploration

Niluka Amarasinghe and Xavier Boyen and Matthew McKague

Abstract

The modern financial world has seen a significant rise in the use of cryptocurrencies in recent years, partly due to the convincing lures of anonymity promised by these schemes. Bitcoin, despite being considered as the most widespread among all, is claimed to have significant lapses in relation to its anonymity. Unfortunately, studies have shown that many cryptocurrency transactions can be traced back to their corresponding participants through the analysis of publicly available data, to which the cryptographic community has responded by proposing new constructions with improved anonymity claims. Nevertheless, the absence of a common metric for evaluating the level of anonymity achieved by these schemes has led to a number of disparate ad hoc anonymity definitions, making comparisons difficult. The multitude of these notions also hints at the surprising complexity of the overall anonymity landscape. In this study, we introduce such a common framework to evaluate the nature and extent of anonymity in (crypto)currencies and distributed transaction systems, irrespective of their implementation. As such, our work lays the foundation for formalising security models and terminology across a wide range of anonymity notions referenced in the literature, while showing how ``anonymity'' itself is a surprisingly nuanced concept.