{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T11:38:36Z","timestamp":1777549116019,"version":"3.51.4"},"reference-count":26,"publisher":"Privacy Enhancing Technologies Symposium Advisory Board","issue":"3","license":[{"start":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T00:00:00Z","timestamp":1619481600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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.<\/jats:p>\n               <jats:p>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 \u2013 it only varies slightly when the signer distribution varies slightly. We then analyze three natural samplers \u2013 uniform, mimicking, and partitioning \u2013 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.<\/jats:p>","DOI":"10.2478\/popets-2021-0047","type":"journal-article","created":{"date-parts":[[2021,4,29]],"date-time":"2021-04-29T01:03:58Z","timestamp":1619658238000},"page":"265-288","source":"Crossref","is-referenced-by-count":4,"title":["Foundations of Ring Sampling"],"prefix":"10.56553","volume":"2021","author":[{"given":"Viktoria","family":"Ronge","sequence":"first","affiliation":[{"name":"Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"Egger","sequence":"additional","affiliation":[{"name":"Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Russell W. F.","family":"Lai","sequence":"additional","affiliation":[{"name":"Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dominique","family":"Schr\u00f6der","sequence":"additional","affiliation":[{"name":"Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hoover H. F.","family":"Yin","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"35752","published-online":{"date-parts":[[2021,4,27]]},"reference":[{"key":"2022062314355098650_j_popets-2021-0047_ref_001_w2aab3b7c28b1b6b1ab1ab1Aa","doi-asserted-by":"crossref","unstructured":"[1] T. Aven. \u201cUpper (Lower) Bounds on the Mean of the Maximum (Minimum) of a Number of Random Variables.\u201d In: Journal of Applied Probability 22.3 (1985), pp. 723\u2013728. issn: 00219002. url: http:\/\/www.jstor.org\/stable\/3213876.10.2307\/3213876","DOI":"10.2307\/3213876"},{"key":"2022062314355098650_j_popets-2021-0047_ref_002_w2aab3b7c28b1b6b1ab1ab2Aa","doi-asserted-by":"crossref","unstructured":"[2] M. Backes, S. Meiser, and M. Slowik. \u201cYour Choice MATor(s).\u201d In: PoPETs 2016.2 (Apr. 2016), pp. 40\u201360.","DOI":"10.1515\/popets-2016-0004"},{"key":"2022062314355098650_j_popets-2021-0047_ref_003_w2aab3b7c28b1b6b1ab1ab3Aa","doi-asserted-by":"crossref","unstructured":"[3] C. J. Corrado. \u201cThe Exact Distribution of the Maximum, Minimum and the Range of Multinomial\/Dirichlet and Multivariate Hypergeometric Frequencies.\u201d In: Statistics and Computing 21.3 (July 2011), 349\u2013359. issn: 0960-3174. doi: 10. 1007\/s11222-010-9174-3. url: https:\/\/doi.org\/10.1007\/s11222-010-9174-3.10.1007\/s11222-010-9174-3","DOI":"10.1007\/s11222-010-9174-3"},{"key":"2022062314355098650_j_popets-2021-0047_ref_004_w2aab3b7c28b1b6b1ab1ab4Aa","doi-asserted-by":"crossref","unstructured":"[4] Y. Deng, J. Pang, and P. Wu. \u201cMeasuring Anonymity with Relative Entropy.\u201d 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\u201379. doi: 10.1007\/978-3-540-75227-1\\_5. url: https:\/\/doi.org\/10.1007\/978-3-540-75227-1\\_5.10.1007\/978-3-540-75227-1","DOI":"10.1007\/978-3-540-75227-1"},{"key":"2022062314355098650_j_popets-2021-0047_ref_005_w2aab3b7c28b1b6b1ab1ab5Aa","doi-asserted-by":"crossref","unstructured":"[5] C. D\u00edaz, S. Seys, J. Claessens, and B. Preneel. \u201cTowards Measuring Anonymity.\u201d In: PET 2002. Ed. by R. Dingledine and P. F. Syverson. Vol. 2482. LNCS. Springer, Heidelberg, Apr. 2002, pp. 54\u201368. doi: 10.1007\/3-540-36467-6_5.10.1007\/3-540-36467-6_5","DOI":"10.1007\/3-540-36467-6_5"},{"key":"2022062314355098650_j_popets-2021-0047_ref_006_w2aab3b7c28b1b6b1ab1ab6Aa","doi-asserted-by":"crossref","unstructured":"[6] Y. Dodis, R. Ostrovsky, L. Reyzin, and A. Smith. \u201cFuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data.\u201d In: SIAM J. Comput. 38.1 (Mar. 2008), pp. 97\u2013139. issn: 0097-5397. doi: 10.1137\/060651380.10.1137\/060651380","DOI":"10.1137\/060651380"},{"key":"2022062314355098650_j_popets-2021-0047_ref_007_w2aab3b7c28b1b6b1ab1ab7Aa","unstructured":"[7] M. Edman, F. Sivrikaya, and B. Yener. \u201cA Combinatorial Approach to Measuring Anonymity.\u201d In: ISI 2007. IEEE, 2007, pp. 356\u2013363. doi: 10.1109\/ISI.2007.379497. url: https:\/\/doi.org\/10.1109\/ISI.2007.379497.10.1109\/ISI.2007.379497"},{"key":"2022062314355098650_j_popets-2021-0047_ref_008_w2aab3b7c28b1b6b1ab1ab8Aa","doi-asserted-by":"crossref","unstructured":"[8] J. Geddes, R. Jansen, and N. Hopper. \u201cHow Low Can You Go: Balancing Performance with Anonymity in Tor.\u201d In: PETS 2013. Ed. by E. De Cristofaro and M. K. Wright. Vol. 7981. LNCS. Springer, Heidelberg, July 2013, pp. 164\u2013184. doi: 10.1007\/978-3-642-39077-7_9.10.1007\/978-3-642-39077-7_9","DOI":"10.1007\/978-3-642-39077-7_9"},{"key":"2022062314355098650_j_popets-2021-0047_ref_009_w2aab3b7c28b1b6b1ab1ab9Aa","doi-asserted-by":"crossref","unstructured":"[9] A. Kumar, C. Fischer, S. Tople, and P. Saxena. \u201cA Traceability Analysis of Monero\u2019s Blockchain.\u201d In: ESORICS 2017, Part II. Ed. by S. N. Foley, D. Gollmann, and E. Snekkenes. Vol. 10493. LNCS. Springer, Heidelberg, Sept. 2017, pp. 153\u2013173. doi: 10.1007\/978-3-319-66399-9_9.10.1007\/978-3-319-66399-9_9","DOI":"10.1007\/978-3-319-66399-9_9"},{"key":"2022062314355098650_j_popets-2021-0047_ref_010_w2aab3b7c28b1b6b1ab1ac10Aa","unstructured":"[10] J. K. Liu, V. K. Wei, and D. S. Wong. \u201cLinkable Spontaneous Anonymous Group Signature for Ad Hoc Groups (Extended Abstract).\u201d In: ACISP 04. Ed. by H. Wang, J. Pieprzyk, and V. Varadharajan. Vol. 3108. LNCS. Springer, Heidelberg, July 2004, pp. 325\u2013335. doi: 10 . 1007\/978 - 3 - 540 27800-9_28."},{"key":"2022062314355098650_j_popets-2021-0047_ref_011_w2aab3b7c28b1b6b1ab1ac11Aa","unstructured":"[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."},{"key":"2022062314355098650_j_popets-2021-0047_ref_012_w2aab3b7c28b1b6b1ab1ac12Aa","doi-asserted-by":"crossref","unstructured":"[12] M. M\u00f6ser, K. Soska, E. Heilman, K. Lee, H. Heffan, S. Srivastava, K. Hogan, J. Hennessey, A. Miller, A. Narayanan, and N. Christin. \u201cAn Empirical Analysis of Traceability in the Monero Blockchain.\u201d In: PoPETs 2018.3 (July 2018), pp. 143\u2013163. doi: 10.1515\/popets-2018-0025.10.1515\/popets-2018-0025","DOI":"10.1515\/popets-2018-0025"},{"key":"2022062314355098650_j_popets-2021-0047_ref_013_w2aab3b7c28b1b6b1ab1ac13Aa","doi-asserted-by":"crossref","unstructured":"[13] R. E. Newman, I. S. Moskowitz, P. F. Syverson, and A. Serjantov. \u201cMetrics for Trafic Analysis Prevention.\u201d In: PET 2003. Ed. by R. Dingledine. Vol. 2760. LNCS. Springer, Heidelberg, Mar. 2003, pp. 48\u201365. doi: 10.1007\/978-3-540-40956-4_4.10.1007\/978-3-540-40956-4_4","DOI":"10.21236\/ADA465471"},{"key":"2022062314355098650_j_popets-2021-0047_ref_014_w2aab3b7c28b1b6b1ab1ac14Aa","doi-asserted-by":"crossref","unstructured":"[14] S. Noether, A. Mackenzie, and the Monero Research Lab. \u201cRing Confidential Transactions.\u201d In: Ledger 1 (2016), pp. 1\u201318. issn: 2379-5980. doi: 10.5195\/ledger.2016.34.10.5195\/ledger.2016.34","DOI":"10.5195\/ledger.2016.34"},{"key":"2022062314355098650_j_popets-2021-0047_ref_015_w2aab3b7c28b1b6b1ab1ac15Aa","unstructured":"[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."},{"key":"2022062314355098650_j_popets-2021-0047_ref_016_w2aab3b7c28b1b6b1ab1ac16Aa","doi-asserted-by":"crossref","unstructured":"[16] R. L. Rivest, A. Shamir, and Y. Tauman. \u201cHow to Leak a Secret.\u201d In: ASIACRYPT 2001. Ed. by C. Boyd. Vol. 2248. LNCS. Springer, Heidelberg, Dec. 2001, pp. 552\u2013565. doi: 10.1007\/3-540-45682-1_32.10.1007\/3-540-45682-1_32","DOI":"10.1007\/3-540-45682-1_32"},{"key":"2022062314355098650_j_popets-2021-0047_ref_017_w2aab3b7c28b1b6b1ab1ac17Aa","doi-asserted-by":"crossref","unstructured":"[17] A. Serjantov and G. Danezis. \u201cTowards an Information Theoretic Metric for Anonymity.\u201d In: PET 2002. Ed. by R. Dingledine and P. F. Syverson. Vol. 2482. LNCS. Springer, Heidelberg, Apr. 2002, pp. 41\u201353. doi: 10.1007\/3-540-36467-6_4.10.1007\/3-540-36467-6_4","DOI":"10.1007\/3-540-36467-6_4"},{"key":"2022062314355098650_j_popets-2021-0047_ref_018_w2aab3b7c28b1b6b1ab1ac18Aa","doi-asserted-by":"crossref","unstructured":"[18] R. Shokri, G. Theodorakopoulos, G. Danezis, J.-P. Hubaux, and J.-Y. Le Boudec. \u201cQuantifying Location Privacy: The Case of Sporadic Location Exposure.\u201d In: PETS 2011. Ed. by S. Fischer-H\u00fcbner and N. Hopper. Vol. 6794. LNCS. Springer, Heidelberg, July 2011, pp. 57\u201376. doi: 10.1007\/978-3-642-22263-4_4.10.1007\/978-3-642-22263-4_4","DOI":"10.1007\/978-3-642-22263-4_4"},{"key":"2022062314355098650_j_popets-2021-0047_ref_019_w2aab3b7c28b1b6b1ab1ac19Aa","doi-asserted-by":"crossref","unstructured":"[19] R. Shokri, G. Theodorakopoulos, J.-Y. Le Boudec, and J.-P. Hubaux. \u201cQuantifying Location Privacy.\u201d In: 2011 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, May 2011, pp. 247\u2013262. doi: 10.1109\/SP.2011.18.10.1109\/SP.2011.18","DOI":"10.1109\/SP.2011.18"},{"key":"2022062314355098650_j_popets-2021-0047_ref_020_w2aab3b7c28b1b6b1ab1ac20Aa","doi-asserted-by":"crossref","unstructured":"[20] G. T\u00f3th and Z. Horn\u00e1k. \u201cMeasuring Anonymity in a Non-adaptive, Real-Time System.\u201d In: PET 2004. Ed. by D. M. Martin Jr. and A. Serjantov. Vol. 3424. LNCS. Springer, Heidelberg, May 2004, pp. 226\u2013241. doi: 10.1007\/11423409_14.10.1007\/11423409_14","DOI":"10.1007\/11423409_14"},{"key":"2022062314355098650_j_popets-2021-0047_ref_021_w2aab3b7c28b1b6b1ab1ac21Aa","unstructured":"[21] F. Tram\u00e8r, D. Boneh, and K. Paterson. \u201cRemote Side-Channel Attacks on Anonymous Transactions.\u201d In: USENIX Security 2020. Ed. by S. Capkun and F. Roesner. USENIX Association, Aug. 2020, pp. 2739\u20132756."},{"key":"2022062314355098650_j_popets-2021-0047_ref_022_w2aab3b7c28b1b6b1ab1ac22Aa","unstructured":"[22] I. Wagner and D. Eckhoff. \u201cTechnical Privacy Metrics: A Systematic Survey.\u201d In: ACM Comput. Surv. 51.3 (June 2018). issn: 0360-0300. doi: 10.1145\/3168389. url: https:\/\/doi.org\/10.1145\/3168389.10.1145\/3168389"},{"key":"2022062314355098650_j_popets-2021-0047_ref_023_w2aab3b7c28b1b6b1ab1ac23Aa","doi-asserted-by":"crossref","unstructured":"[23] D. A. Wijaya, J. Liu, R. Steinfeld, and D. Liu. \u201cMonero Ring Attack: Recreating Zero Mixin Transaction Effect.\u201d In: TrustCom\/BigDataSE 2018. IEEE, 2018, pp. 1196\u20131201. doi: 10.1109\/TrustCom\/BigDataSE.2018.00165.10.1109\/TrustCom\/BigDataSE.2018.00165","DOI":"10.1109\/TrustCom\/BigDataSE.2018.00165"},{"key":"2022062314355098650_j_popets-2021-0047_ref_024_w2aab3b7c28b1b6b1ab1ac24Aa","doi-asserted-by":"crossref","unstructured":"[24] S. Xu and M. Yung. \u201cAccountable ring signatures: a smart card approach.\u201d In: Smart Card Research and Advanced Applications VI. Springer, 2004, pp. 271\u2013286.","DOI":"10.1007\/1-4020-8147-2_18"},{"key":"2022062314355098650_j_popets-2021-0047_ref_025_w2aab3b7c28b1b6b1ab1ac25Aa","doi-asserted-by":"crossref","unstructured":"[25] J. Yu, M. H. A. Au, and P. Esteves-Verissimo. \u201cRe-thinking untraceability in the CryptoNote-style blockchain \u2013 The Sun Tzu survival problem.\u201d In: CSF 2019. Ed. by S. Delaune and L. Jia. United States of America: IEEE, 2019, pp. 94\u2013107.","DOI":"10.1109\/CSF.2019.00014"},{"key":"2022062314355098650_j_popets-2021-0047_ref_026_w2aab3b7c28b1b6b1ab1ac26Aa","doi-asserted-by":"crossref","unstructured":"[26] L. von Ahn and N. J. Hopper. \u201cPublic-Key Steganography.\u201d In: EUROCRYPT 2004. Ed. by C. Cachin and J. Camenisch. Vol. 3027. LNCS. Springer, Heidelberg, May 2004, pp. 323\u2013341. doi: 10.1007\/978-3-540-24676-3_20.10.1007\/978-3-540-24676-3_20","DOI":"10.1007\/978-3-540-24676-3_20"}],"container-title":["Proceedings on Privacy Enhancing Technologies"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.sciendo.com\/pdf\/10.2478\/popets-2021-0047","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T16:31:34Z","timestamp":1658334694000},"score":1,"resource":{"primary":{"URL":"https:\/\/petsymposium.org\/popets\/2021\/popets-2021-0047.php"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,27]]},"references-count":26,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2021,4,27]]},"published-print":{"date-parts":[[2021,7,1]]}},"alternative-id":["10.2478\/popets-2021-0047"],"URL":"https:\/\/doi.org\/10.2478\/popets-2021-0047","relation":{},"ISSN":["2299-0984"],"issn-type":[{"value":"2299-0984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,27]]}}}