On Defeating Graph Analysis of Anonymous Transactions

Egger C, Lai RWF, Ronge V, Woo IKY, Yin HH (2022)

Publication Language: English

Publication Type: Conference contribution, Original article

Publication year: 2022

Publisher: Sciendo

City/Town: Warschau (Polen)

Book Volume: 2022 (3)

Pages Range: 538–557

Conference Proceedings Title: Proceedings on Privacy Enhancing Technologies

Event location: Sydney AU

URI: https://petsymposium.org/popets/2022/popets-2022-0085.pdf

DOI: 10.56553/popets-2022-0085

Open Access Link: https://petsymposium.org/popets/2022/popets-2022-0085.pdf

Abstract

In a ring-signature-based anonymous cryp-
tocurrency, signers of a transaction are hidden among
a set of potential signers, called a ring, whose size is
much smaller than the number of all users. The ring-
membership relations specified by the sets of transactions
thus induce bipartite transaction graphs, whose distribu-
tion is in turn induced by the ring sampler underlying the
cryptocurrency.
Since efficient graph analysis could be performed on
transaction graphs to potentially deanonymise signers, it
is crucial to understand the resistance of (the transaction
graphs induced by) a ring sampler against graph analy-
sis. Of particular interest is the class of partitioning ring
samplers. Although previous works showed that they
provide almost optimal local anonymity, their resistance
against global, e.g. graph-based, attacks were unclear.
In this work, we analyse transaction graphs induced by
partitioning ring samplers. Specifically, we show (partly
analytically and partly empirically) that, somewhat sur-
prisingly, by setting the ring size to be at least logarithmic
in the number of users, a graph-analysing adversary is no
better than the one that performs random guessing in
deanonymisation up to constant factor of 2.

Authors with CRIS profile

Christoph Egger Lehrstuhl für Informatik 13 (Angewandte Kryptographie) Wai Fu Lai Lehrstuhl für Informatik 13 (Angewandte Kryptographie) Viktoria Ronge 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:

Egger, C., Lai, R.W.F., Ronge, V., Woo, I.K.Y., & Yin, H.H. (2022). On Defeating Graph Analysis of Anonymous Transactions. In Kerschbaum, Florian; Mazurek, Michelle (Eds.), Proceedings on Privacy Enhancing Technologies (pp. 538–557). Sydney, AU: Warschau (Polen): Sciendo.

MLA:

Egger, Christoph, et al. "On Defeating Graph Analysis of Anonymous Transactions." Proceedings of the Privacy Enhancing Technologies Symposium, Sydney Ed. Kerschbaum, Florian; Mazurek, Michelle, Warschau (Polen): Sciendo, 2022. 538–557.

BibTeX: Download