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 vie},
author = {Ronge, Viktoria and Egger, Christoph and Lai, Russell W. F. and Schröder, Dominique and Yin, Hoover H.F.},
doi = {10.2478/popets-2021-0047},
faupublication = {yes},
journal = {Proceedings on Privacy Enhancing Technologies},
keywords = {Ring SignatureAnonymityMonero},
pages = {265--288},
peerreviewed = {Yes},
title = {{Foundations} of {Ring} {Sampling}},
volume = {2021},
year = {2021}
}
@inproceedings{faucris.230551975,
abstract = {Monero is the largest cryptocurrency with built-in cryptographic privacy features. The transactions are authenticated using zero-knowledge spend proofs, which provide a certain level of anonymity by hiding the source accounts from which the funds are sent among a set of other accounts. Due to its similarities to ring signatures, this core cryptographic component is called Ring Confidential Transactions (RingCT). Because of its practical relevance, several works attempt to analyze the security of RingCT. Since RingCT is rather complex, most of them are either informal, miss fundamental functionalities, or introduce undesirable trusted setup assumptions. Regarding efficiency, Monero currently deploys a scheme in which the size of the spend proof is linear in the ring size. This limits the ring size to only a few accounts, which in turn limits the acquired anonymity significantly and facilitates de-anonymization attacks. As a solution to these problems, we present the first rigorous formalization of RingCT as a cryptographic primitive. We then propose a generic construction of RingCT and prove it secure in our formal security model. By instantiating our generic construction with new efficient zero-knowledge proofs, we obtain Omniring, a fully-fledged RingCT scheme in the discrete logarithm setting that provides the highest concrete and asymptotic efficiency as of today. Omniring is the first RingCT scheme which 1) does not require a trusted setup or pairing-friendly elliptic curves, 2) has a proof size logarithmic in the size of the ring, and 3) allows to share the same ring between all source accounts in a transaction, thereby enabling significantly improved privacy level without sacrificing performance. Our zero-knowledge proofs rely on novel enhancements to the Bulletproofs framework (S&P 2018), which we believe are of independent interest.

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},
address = {Warschau (Polen)},
author = {Egger, Christoph and Lai, Russell W. F. and Ronge, Viktoria and Woo, Ivy K. Y. and Yin, Hoover H.F.},
booktitle = {Proceedings on Privacy Enhancing Technologies},
doi = {10.56553/popets-2022-0085},
editor = {Kerschbaum, Florian; Mazurek, Michelle},
faupublication = {yes},
pages = {538–557},
peerreviewed = {Yes},
publisher = {Sciendo},
title = {{On} {Defeating} {Graph} {Analysis} of {Anonymous} {Transactions}},
url = {https://petsymposium.org/popets/2022/popets-2022-0085.pdf},
venue = {Sydney},
volume = {2022 (3)},
year = {2022}
}
@inproceedings{faucris.304697496,
author = {Chow, Sherman S. M. and Egger, Christoph and Lai, Russell W. F. and Woo, Ivy K. Y. and Ronge, Viktoria},
booktitle = {36th IEEE Computer Security Foundations Symposium},
date = {2023-07-10/2023-07-13},
faupublication = {yes},
peerreviewed = {Yes},
title = {{On} {Sustainable} {Ring}-based {Anonymous} {Systems}},
venue = {Dubrovnik},
year = {2023}
}
@inproceedings{faucris.285594205,
abstract = {

Bitcoin and other cryptocurrencies have recently introduced support for Schnorr signatures whose cleaner algebraic structure, as compared to ECDSA, allows for simpler and more practical constructions of highly demanded ''t-of-n'' threshold signatures. However, existing Schnorr threshold signature schemes still fall short of the needs of real-world applications due to their assumption that the network is synchronous and due to their lack of robustness, i.e., the guarantee that t honest signers are able to obtain a valid signature even in the presence of other malicious signers who try to disrupt the protocol. This hinders the adoption of threshold signatures in the cryptocurrency ecosystem, e.g., in second-layer protocols built on top of cryptocurrencies.

In this work, we propose ROAST, a simple wrapper that turns a given threshold signature scheme into a scheme with a robust and asynchronous signing protocol, as long as the underlying signing protocol is semi-interactive (i.e., has one preprocessing round and one actual signing round), provides identifiable aborts, and is unforgeable under concurrent signing sessions. When applied to the state-of-the-art Schnorr threshold signature scheme FROST, which fulfills these requirements, we obtain a simple, efficient, and highly practical Schnorr threshold signature scheme.