Foundations of Ring Sampling

Ronge V, Egger C, Lai RWF, Schröder D, Yin HH (2021)

Publication Language: English

Publication Type: Journal article, Original article

Publication year: 2021

Journal

Proceedings on Privacy Enhancing Technologies

Book Volume: 2021

Pages Range: 265--288

Article Number: 47

Journal Issue: 3

DOI: 10.2478/popets-2021-0047

Abstract

A ring signature scheme allows the signer to sign on behalf of an ad hoc set of users, called a ring. The verifier can be convinced that a ring member signs, but cannot point to the exact signer. Ring signatures have become increasingly important today with their deployment in anonymous cryptocurrencies. Conventionally, it is implicitly assumed that all ring members are equally likely to be the signer. This assumption is generally false in reality, leading to various practical and devastating deanonymizing attacks in Monero, one of the largest anonymous cryptocurrencies. These attacks highlight the unsatisfactory situation that how a ring should be chosen is poorly understood.

We propose an analytical model of ring samplers towards a deeper understanding of them through systematic studies. Our model helps to describe how anonymous a ring sampler is with respect to a given signer distribution as an information-theoretic measure. We show that this measure is robust – it only varies slightly when the signer distribution varies slightly. We then analyze three natural samplers – uniform, mimicking, and partitioning – under our model with respect to a family of signer distributions modeled after empirical Bitcoin data. We hope that our work paves the way towards researching ring samplers from a theoretical point of view.

Authors with CRIS profile

Viktoria Ronge Lehrstuhl für Informatik 13 (Angewandte Kryptographie) Christoph Egger Lehrstuhl für Informatik 13 (Angewandte Kryptographie) Wai Fu Lai Lehrstuhl für Informatik 13 (Angewandte Kryptographie) Dominique Schröder Lehrstuhl für Informatik 13 (Angewandte Kryptographie)

Related research project(s)

Cyberkriminalität und forensische Informatik (Cybercrime) Oct. 1, 2019 - March 31, 2024

Involved external institutions

The Chinese University of Hong Kong (CUHK) CN China (CN)

How to cite

APA:

Ronge, V., Egger, C., Lai, R.W.F., Schröder, D., & Yin, H.H. (2021). Foundations of Ring Sampling. Proceedings on Privacy Enhancing Technologies, 2021(3), 265--288. https://dx.doi.org/10.2478/popets-2021-0047

MLA:

Ronge, Viktoria, et al. "Foundations of Ring Sampling." Proceedings on Privacy Enhancing Technologies 2021.3 (2021): 265--288.

BibTeX: Download