1. bookVolume 2021 (2021): Issue 3 (July 2021)
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
access type Open Access

Foundations of Ring Sampling

Published Online: 27 Apr 2021
Page range: 265 - 288
Received: 30 Nov 2020
Accepted: 16 Mar 2021
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
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.

Keywords

[1] T. Aven. “Upper (Lower) Bounds on the Mean of the Maximum (Minimum) of a Number of Random Variables.” In: Journal of Applied Probability 22.3 (1985), pp. 723–728. issn: 00219002. url: http://www.jstor.org/stable/3213876.Search in Google Scholar

[2] M. Backes, S. Meiser, and M. Slowik. “Your Choice MATor(s).” In: PoPETs 2016.2 (Apr. 2016), pp. 40–60.Search in Google Scholar

[3] C. J. Corrado. “The Exact Distribution of the Maximum, Minimum and the Range of Multinomial/Dirichlet and Multivariate Hypergeometric Frequencies.” In: Statistics and Computing 21.3 (July 2011), 349–359. issn: 0960-3174. doi: 10. 1007/s11222-010-9174-3. url: https://doi.org/10.1007/s11222-010-9174-3.Search in Google Scholar

[4] Y. Deng, J. Pang, and P. Wu. “Measuring Anonymity with Relative Entropy.” In: FAST 2006. Ed. by T. Dimitrakos, F. Martinelli, P. Y. A. Ryan, and S. A. Schneider. Vol. 4691. Lecture Notes in Computer Science. Springer, 2006, pp. 65–79. doi: 10.1007/978-3-540-75227-1\_5. url: https://doi.org/10.1007/978-3-540-75227-1\_5.Search in Google Scholar

[5] C. Díaz, S. Seys, J. Claessens, and B. Preneel. “Towards Measuring Anonymity.” In: PET 2002. Ed. by R. Dingledine and P. F. Syverson. Vol. 2482. LNCS. Springer, Heidelberg, Apr. 2002, pp. 54–68. doi: 10.1007/3-540-36467-6_5.Search in Google Scholar

[6] Y. Dodis, R. Ostrovsky, L. Reyzin, and A. Smith. “Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data.” In: SIAM J. Comput. 38.1 (Mar. 2008), pp. 97–139. issn: 0097-5397. doi: 10.1137/060651380.Search in Google Scholar

[7] M. Edman, F. Sivrikaya, and B. Yener. “A Combinatorial Approach to Measuring Anonymity.” In: ISI 2007. IEEE, 2007, pp. 356–363. doi: 10.1109/ISI.2007.379497. url: https://doi.org/10.1109/ISI.2007.379497.Search in Google Scholar

[8] J. Geddes, R. Jansen, and N. Hopper. “How Low Can You Go: Balancing Performance with Anonymity in Tor.” In: PETS 2013. Ed. by E. De Cristofaro and M. K. Wright. Vol. 7981. LNCS. Springer, Heidelberg, July 2013, pp. 164–184. doi: 10.1007/978-3-642-39077-7_9.Search in Google Scholar

[9] A. Kumar, C. Fischer, S. Tople, and P. Saxena. “A Traceability Analysis of Monero’s Blockchain.” In: ESORICS 2017, Part II. Ed. by S. N. Foley, D. Gollmann, and E. Snekkenes. Vol. 10493. LNCS. Springer, Heidelberg, Sept. 2017, pp. 153–173. doi: 10.1007/978-3-319-66399-9_9.Search in Google Scholar

[10] J. K. Liu, V. K. Wei, and D. S. Wong. “Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups (Extended Abstract).” In: ACISP 04. Ed. by H. Wang, J. Pieprzyk, and V. Varadharajan. Vol. 3108. LNCS. Springer, Heidelberg, July 2004, pp. 325–335. doi: 10 . 1007/978 - 3 - 540 27800-9_28.Search in Google Scholar

[11] A. Mackenzie, S. Noether, and M. C. Team. Improving Obfuscation in the CryptoNote Protocol. Tech. rep. url: https://www.getmonero.org/resources/research-lab/pubs/MRL-0004.pdf.Search in Google Scholar

[12] M. Möser, K. Soska, E. Heilman, K. Lee, H. Heffan, S. Srivastava, K. Hogan, J. Hennessey, A. Miller, A. Narayanan, and N. Christin. “An Empirical Analysis of Traceability in the Monero Blockchain.” In: PoPETs 2018.3 (July 2018), pp. 143–163. doi: 10.1515/popets-2018-0025.Search in Google Scholar

[13] R. E. Newman, I. S. Moskowitz, P. F. Syverson, and A. Serjantov. “Metrics for Trafic Analysis Prevention.” In: PET 2003. Ed. by R. Dingledine. Vol. 2760. LNCS. Springer, Heidelberg, Mar. 2003, pp. 48–65. doi: 10.1007/978-3-540-40956-4_4.Search in Google Scholar

[14] S. Noether, A. Mackenzie, and the Monero Research Lab. “Ring Confidential Transactions.” In: Ledger 1 (2016), pp. 1–18. issn: 2379-5980. doi: 10.5195/ledger.2016.34.Search in Google Scholar

[15] S. Noether, S. Noether, and A. Mackenzie. A Note on Chain Reactions in Traceability in CryptoNote 2.0. Tech. rep. url: https://ww.getmonero.org/resources/research-lab/pubs/MRL-0001.pdf.Search in Google Scholar

[16] R. L. Rivest, A. Shamir, and Y. Tauman. “How to Leak a Secret.” In: ASIACRYPT 2001. Ed. by C. Boyd. Vol. 2248. LNCS. Springer, Heidelberg, Dec. 2001, pp. 552–565. doi: 10.1007/3-540-45682-1_32.Search in Google Scholar

[17] A. Serjantov and G. Danezis. “Towards an Information Theoretic Metric for Anonymity.” In: PET 2002. Ed. by R. Dingledine and P. F. Syverson. Vol. 2482. LNCS. Springer, Heidelberg, Apr. 2002, pp. 41–53. doi: 10.1007/3-540-36467-6_4.Search in Google Scholar

[18] R. Shokri, G. Theodorakopoulos, G. Danezis, J.-P. Hubaux, and J.-Y. Le Boudec. “Quantifying Location Privacy: The Case of Sporadic Location Exposure.” In: PETS 2011. Ed. by S. Fischer-Hübner and N. Hopper. Vol. 6794. LNCS. Springer, Heidelberg, July 2011, pp. 57–76. doi: 10.1007/978-3-642-22263-4_4.Search in Google Scholar

[19] R. Shokri, G. Theodorakopoulos, J.-Y. Le Boudec, and J.-P. Hubaux. “Quantifying Location Privacy.” In: 2011 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, May 2011, pp. 247–262. doi: 10.1109/SP.2011.18.Search in Google Scholar

[20] G. Tóth and Z. Hornák. “Measuring Anonymity in a Non-adaptive, Real-Time System.” In: PET 2004. Ed. by D. M. Martin Jr. and A. Serjantov. Vol. 3424. LNCS. Springer, Heidelberg, May 2004, pp. 226–241. doi: 10.1007/11423409_14.Search in Google Scholar

[21] F. Tramèr, D. Boneh, and K. Paterson. “Remote Side-Channel Attacks on Anonymous Transactions.” In: USENIX Security 2020. Ed. by S. Capkun and F. Roesner. USENIX Association, Aug. 2020, pp. 2739–2756.Search in Google Scholar

[22] I. Wagner and D. Eckhoff. “Technical Privacy Metrics: A Systematic Survey.” In: ACM Comput. Surv. 51.3 (June 2018). issn: 0360-0300. doi: 10.1145/3168389. url: https://doi.org/10.1145/3168389.Search in Google Scholar

[23] D. A. Wijaya, J. Liu, R. Steinfeld, and D. Liu. “Monero Ring Attack: Recreating Zero Mixin Transaction Effect.” In: TrustCom/BigDataSE 2018. IEEE, 2018, pp. 1196–1201. doi: 10.1109/TrustCom/BigDataSE.2018.00165.Search in Google Scholar

[24] S. Xu and M. Yung. “Accountable ring signatures: a smart card approach.” In: Smart Card Research and Advanced Applications VI. Springer, 2004, pp. 271–286.Search in Google Scholar

[25] J. Yu, M. H. A. Au, and P. Esteves-Verissimo. “Re-thinking untraceability in the CryptoNote-style blockchain – The Sun Tzu survival problem.” In: CSF 2019. Ed. by S. Delaune and L. Jia. United States of America: IEEE, 2019, pp. 94–107.Search in Google Scholar

[26] L. von Ahn and N. J. Hopper. “Public-Key Steganography.” In: EUROCRYPT 2004. Ed. by C. Cachin and J. Camenisch. Vol. 3027. LNCS. Springer, Heidelberg, May 2004, pp. 323–341. doi: 10.1007/978-3-540-24676-3_20.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo