{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:15:03Z","timestamp":1778807703689,"version":"3.51.4"},"publisher-location":"Cham","reference-count":101,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030778828","type":"print"},{"value":"9783030778835","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-77883-5_16","type":"book-chapter","created":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T23:06:10Z","timestamp":1623798370000},"page":"463-488","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":31,"title":["On the Power of Multiple Anonymous Messages: Frequency Estimation and\u00a0Selection in the Shuffle Model of\u00a0Differential Privacy"],"prefix":"10.1007","author":[{"given":"Badih","family":"Ghazi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Noah","family":"Golowich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ravi","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rasmus","family":"Pagh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ameya","family":"Velingker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,6,16]]},"reference":[{"key":"16_CR1","unstructured":"Acharya, J., Canonne, C., Freitag, C., Tyagi, H.: Test without trust: optimal locally private distribution testing. In: AISTATS, pp. 2067\u20132076 (2019)"},{"key":"16_CR2","first-page":"51","volume":"97","author":"J Acharya","year":"2019","unstructured":"Acharya, J., Sun, Z.: Communication complexity in locally private distribution estimation and heavy hitters. ICML 97, 51\u201360 (2019)","journal-title":"ICML"},{"key":"16_CR3","unstructured":"Acharya, J., Sun, Z., Zhang, H.: Hadamard response: estimating distributions privately, efficiently, and with little communication. In: AISTATS, pp. 1120\u20131129 (2019)"},{"key":"16_CR4","unstructured":"Agarwal, N., Suresh, A.T., Yu, F.X.X., Kumar, S., McMahan, B.: cpSGD: communication-efficient and differentially-private distributed SGD. In: Advances in Neural Information Processing Systems, pp. 7564\u20137575 (2018)"},{"key":"16_CR5","unstructured":"Apple Differential Privacy Team: Learning with privacy at scale. Apple Mach. Learn. J. (2017). https:\/\/machinelearning.apple.com\/docs\/learning-with-privacy-at-scale\/appledifferentialprivacysystem.pdf"},{"key":"16_CR6","unstructured":"Balcer, V., Cheu, A.: Separating local & shuffled differential privacy via histograms. In: ITC, pp. 1:1\u20131:14 (2020)"},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"Balle, B., Bell, J., Gasc\u00f3n, A., Nissim, K.: Differentially private summation with multi-message shuffling. CoRR arXiv:1906.09116 (2019)","DOI":"10.1145\/3372297.3417242"},{"key":"16_CR8","unstructured":"Balle, B., Bell, J., Gasc\u00f3n, A., Nissim, K.: Improved summation from shuffling. arXiv:1909.11225 (2019)"},{"key":"16_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1007\/978-3-030-26951-7_22","volume-title":"Advances in Cryptology \u2013 CRYPTO 2019","author":"B Balle","year":"2019","unstructured":"Balle, B., Bell, J., Gasc\u00f3n, A., Nissim, K.: The privacy blanket of the shuffle model. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 638\u2013667. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-26951-7_22"},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"Balle, B., Bell, J., Gasc\u00f3n, A., Nissim, K.: Private summation in the multi-message shuffle model. arXiv:2002.00817 (2020)","DOI":"10.1145\/3372297.3417242"},{"key":"16_CR11","unstructured":"Bassily, R., Nissim, K., Stemmer, U., Thakurta, A.G.: Practical locally private heavy hitters. In: NIPS, pp. 2288\u20132296 (2017)"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"Bassily, R., Smith, A.: Local, private, efficient protocols for succinct histograms. In: STOC, pp. 127\u2013135 (2015)","DOI":"10.1145\/2746539.2746632"},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"Bassily, R., Smith, A.D., Thakurta, A.: Private empirical risk minimization: efficient algorithms and tight error bounds. In: FOCS, pp. 464\u2013473 (2014)","DOI":"10.1109\/FOCS.2014.56"},{"key":"16_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/978-3-642-40328-6_26","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A Beimel","year":"2013","unstructured":"Beimel, A., Nissim, K., Stemmer, U.: Private learning and sanitization: pure vs. approximate differential privacy. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) APPROX\/RANDOM -2013. LNCS, vol. 8096, pp. 363\u2013378. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40328-6_26"},{"issue":"5","key":"16_CR15","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0020-0190(79)90117-0","volume":"8","author":"JL Bentley","year":"1979","unstructured":"Bentley, J.L.: Decomposable searching problems. IPL 8(5), 244\u2013251 (1979)","journal-title":"IPL"},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"Bittau, A., et al.: Prochlo: strong privacy for analytics in the crowd. In: SOSP, pp. 441\u2013459 (2017)","DOI":"10.1145\/3132747.3132769"},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"Blum, A., Dwork, C., Nissim, K., McSherry, F.: Practical privacy: the SuLQ framework. In: PODS, pp. 128\u2013138 (2005)","DOI":"10.1145\/1065167.1065184"},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"Blum, A., Ligett, K., Roth, A.: A learning theory approach to non-interactive database privacy. In: STOC, pp. 609\u2013618 (2008)","DOI":"10.1145\/1374376.1374464"},{"key":"16_CR19","volume-title":"Concentration Inequalities: A Nonasmpytotic Theory of Independence","author":"S Boucheron","year":"2012","unstructured":"Boucheron, S., Lugosi, G., Massart, P.: Concentration Inequalities: A Nonasmpytotic Theory of Independence. Clarendon Press, Oxford (2012)"},{"key":"16_CR20","doi-asserted-by":"crossref","unstructured":"Bun, M., Nelson, J., Stemmer, U.: Heavy hitters and the structure of local privacy. In: PODS, pp. 435\u2013447 (2018)","DOI":"10.1145\/3196959.3196981"},{"key":"16_CR21","doi-asserted-by":"crossref","unstructured":"Bun, M., Nissim, K., Stemmer, U., Vadhan, S.: Differentially private release and learning of threshold functions. In: FOCS, pp. 634\u2013649 (2015)","DOI":"10.1109\/FOCS.2015.45"},{"issue":"3","key":"16_CR22","doi-asserted-by":"publisher","first-page":"26:1","DOI":"10.1145\/2043621.2043626","volume":"14","author":"TH Chan","year":"2011","unstructured":"Chan, T.H., Shi, E., Song, D.: Private and continual release of statistics. ACM Trans. Inf. Syst. Secur. 14(3), 26:1\u201326:24 (2011)","journal-title":"ACM Trans. Inf. Syst. Secur."},{"key":"16_CR23","doi-asserted-by":"crossref","unstructured":"Chan, T.H.H., Shi, E., Song, D.: Optimal lower bound for differentially private multi-part aggregation. In: European Symposium on Algorithms (2012)","DOI":"10.1007\/978-3-642-33090-2_25"},{"key":"16_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1007\/3-540-45465-9_59","volume-title":"Automata, Languages and Programming","author":"M Charikar","year":"2002","unstructured":"Charikar, M., Chen, K., Farach-Colton, M.: Finding frequent items in data streams. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 693\u2013703. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45465-9_59"},{"key":"16_CR25","unstructured":"Chaudhuri, K., Monteleoni, C.: Privacy-preserving logistic regression. In: NIPS, pp. 289\u2013296 (2008)"},{"key":"16_CR26","first-page":"1069","volume":"12","author":"K Chaudhuri","year":"2011","unstructured":"Chaudhuri, K., Monteleoni, C., Sarwate, A.D.: Differentially private empirical risk minimization. JMLR 12, 1069\u20131109 (2011)","journal-title":"JMLR"},{"issue":"1","key":"16_CR27","first-page":"2905","volume":"14","author":"K Chaudhuri","year":"2013","unstructured":"Chaudhuri, K., Sarwate, A.D., Sinha, K.: A near-optimal algorithm for differentially-private principal components. JMLR 14(1), 2905\u20132943 (2013)","journal-title":"JMLR"},{"key":"16_CR28","unstructured":"Chen, L., Ghazi, B., Kumar, R., Manurangsi, P.: On distributed differential privacy and counting distinct elements. arXiv:2009.09604 (2020)"},{"key":"16_CR29","doi-asserted-by":"crossref","unstructured":"Cheu, A., Smith, A.D., Ullman, J., Zeber, D., Zhilyaev, M.: Distributed differential privacy via mixnets. In: EUROCRYPT, pp. 375\u2013403 (2019)","DOI":"10.1007\/978-3-030-17653-2_13"},{"key":"16_CR30","unstructured":"Cormode, G.: Sketch techniques for approximate query processing. In: Foundations and Trends in Databases. Now Publishers (2011)"},{"issue":"2","key":"16_CR31","first-page":"1530","volume":"1","author":"G Cormode","year":"2008","unstructured":"Cormode, G., Hadjieleftheriou, M.: Finding frequent items in data streams. VLDB 1(2), 1530\u20131541 (2008)","journal-title":"VLDB"},{"key":"16_CR32","doi-asserted-by":"crossref","unstructured":"Cormode, G., Kulkarni, T., Srivastava, D.: Marginal release under local differential privacy. In: SIGMOD, pp. 131\u2013146 (2018)","DOI":"10.1145\/3183713.3196906"},{"key":"16_CR33","doi-asserted-by":"crossref","unstructured":"Cormode, G., Kulkarni, T., Srivastava, D.: Answering range queries under local differential privacy. In: Proceedings of International Conference on Management of Data (SIGMOD), pp. 1832\u20131834 (2019)","DOI":"10.1145\/3299869.3300102"},{"issue":"1","key":"16_CR34","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.jalgor.2003.12.001","volume":"55","author":"G Cormode","year":"2005","unstructured":"Cormode, G., Muthukrishnan, S.: An improved data stream summary: the Count-Min sketch and its applications. J. Algorithms 55(1), 58\u201375 (2005)","journal-title":"J. Algorithms"},{"issue":"1","key":"16_CR35","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1145\/1061318.1061325","volume":"30","author":"G Cormode","year":"2005","unstructured":"Cormode, G., Muthukrishnan, S.: What\u2019s hot and what\u2019s not: tracking most frequent items dynamically. TODS 30(1), 249\u2013278 (2005)","journal-title":"TODS"},{"key":"16_CR36","doi-asserted-by":"publisher","unstructured":"Cormode, G., Procopiuc, C., Srivastava, D., Shen, E., Yu, T.: Differentially private spatial decompositions. In: ICDE, pp. 20\u201331 (2012). https:\/\/doi.org\/10.1109\/ICDE.2012.16","DOI":"10.1109\/ICDE.2012.16"},{"key":"16_CR37","doi-asserted-by":"publisher","DOI":"10.1017\/9781108769938","volume-title":"Small Summaries for Big Data","author":"G Cormode","year":"2020","unstructured":"Cormode, G., Yi, K.: Small Summaries for Big Data. Cambridge University Press, Cambridge (2020). http:\/\/cormode.org\/ssbd"},{"key":"16_CR38","doi-asserted-by":"publisher","DOI":"10.1002\/0471200611","volume-title":"Elements of Information Theory","author":"TA Cover","year":"1991","unstructured":"Cover, T.A., Thomas, J.M.: Elements of Information Theory. Wiley, New York (1991)"},{"key":"16_CR39","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107337756","volume-title":"Secure Multiparty Computation","author":"R Cramer","year":"2015","unstructured":"Cramer, R., Damg\u00e5rd, I.B., Nielsen, J.B.: Secure Multiparty Computation. Cambridge University Press, Cambridge (2015)"},{"key":"16_CR40","unstructured":"Ding, B., Kulkarni, J., Yekhanin, S.: Collecting telemetry data privately. In: NIPS, pp. 3571\u20133580 (2017)"},{"key":"16_CR41","doi-asserted-by":"crossref","unstructured":"Duchi, J.C., Jordan, M.I., Wainwright, M.J.: Local privacy and statistical minimax rates. In: FOCS, pp. 429\u2013438 (2013)","DOI":"10.1109\/FOCS.2013.53"},{"issue":"521","key":"16_CR42","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1080\/01621459.2017.1389735","volume":"113","author":"JC Duchi","year":"2018","unstructured":"Duchi, J.C., Jordan, M.I., Wainwright, M.J.: Minimax optimal procedures for locally private estimation. JASA 113(521), 182\u2013201 (2018)","journal-title":"JASA"},{"key":"16_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11787006_1","volume-title":"Automata, Languages and Programming","author":"C Dwork","year":"2006","unstructured":"Dwork, C.: Differential privacy. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 1\u201312. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11787006_1"},{"key":"16_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1007\/11761679_29","volume-title":"Advances in Cryptology - EUROCRYPT 2006","author":"C Dwork","year":"2006","unstructured":"Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., Naor, M.: Our data, ourselves: privacy via distributed noise generation. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 486\u2013503. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11761679_29"},{"key":"16_CR45","doi-asserted-by":"crossref","unstructured":"Dwork, C., Lei, J.: Differential privacy and robust statistics. In: STOC, pp. 371\u2013380 (2009)","DOI":"10.1145\/1536414.1536466"},{"key":"16_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/11681878_14","volume-title":"Theory of Cryptography","author":"C Dwork","year":"2006","unstructured":"Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 265\u2013284. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11681878_14"},{"key":"16_CR47","doi-asserted-by":"crossref","unstructured":"Dwork, C., Naor, M., Pitassi, T., Rothblum, G.N.: Differential privacy under continual observation. In: STOC, pp. 715\u2013724 (2010)","DOI":"10.1145\/1806689.1806787"},{"key":"16_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"735","DOI":"10.1007\/978-3-662-48800-3_30","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2015","author":"C Dwork","year":"2015","unstructured":"Dwork, C., Naor, M., Reingold, O., Rothblum, G.N.: Pure differential privacy for rectangle queries via private partitions. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 735\u2013751. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48800-3_30"},{"key":"16_CR49","doi-asserted-by":"crossref","unstructured":"Dwork, C., Naor, M., Reingold, O., Rothblum, G.N., Vadhan, S.: On the complexity of differentially private data release: efficient algorithms and hardness results. In: STOC, pp. 381\u2013390 (2009)","DOI":"10.1145\/1536414.1536467"},{"key":"16_CR50","volume-title":"The Algorithmic Foundations of Differential Privacy","author":"C Dwork","year":"2014","unstructured":"Dwork, C., Roth, A.: The Algorithmic Foundations of Differential Privacy. Now Publishers Inc., Delft (2014)"},{"issue":"3\u20134","key":"16_CR51","first-page":"211","volume":"9","author":"C Dwork","year":"2014","unstructured":"Dwork, C., Roth, A., et al.: The algorithmic foundations of differential privacy. Found. Trends Theoret. Comput. Sci. 9(3\u20134), 211\u2013407 (2014)","journal-title":"Found. Trends Theoret. Comput. Sci."},{"key":"16_CR52","doi-asserted-by":"crossref","unstructured":"Edmonds, A., Nikolov, A., Ullman, J.: The power of factorization methods in local and central differential privacy. In: Symposium on the Theory of Computing (2020)","DOI":"10.1145\/3357713.3384297"},{"key":"16_CR53","unstructured":"Erlingsson, \u00da., et al.: Encode, shuffle, analyze privacy revisited: formalizations and empirical evaluation. arXiv preprint arXiv:2001.03618 (2020)"},{"key":"16_CR54","doi-asserted-by":"crossref","unstructured":"Erlingsson, \u00da., Feldman, V., Mironov, I., Raghunathan, A., Talwar, K., Thakurta, A.: Amplification by shuffling: from local to central differential privacy via anonymity. In: SODA, pp. 2468\u20132479 (2019)","DOI":"10.1137\/1.9781611975482.151"},{"key":"16_CR55","doi-asserted-by":"crossref","unstructured":"Erlingsson, \u00da., Pihur, V., Korolova, A.: RAPPOR: randomized aggregatable privacy-preserving ordinal response. In: CCS, pp. 1054\u20131067 (2014)","DOI":"10.1145\/2660267.2660348"},{"issue":"3","key":"16_CR56","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1145\/859716.859719","volume":"21","author":"C Estan","year":"2003","unstructured":"Estan, C., Varghese, G.: New directions in traffic measurement and accounting: focusing on the elephants, ignoring the mice. TOCS 21(3), 270\u2013313 (2003)","journal-title":"TOCS"},{"key":"16_CR57","unstructured":"Free Haven: Selected papers in anonymity. https:\/\/www.freehaven.net\/anonbib\/"},{"key":"16_CR58","doi-asserted-by":"crossref","unstructured":"Ghazi, B., Golowich, N., Kumar, R., Manurangsi, P., Pagh, R., Velingker, A.: Pure differentially private summation from anonymous messages. In: Information Theoretic Cryptography (ITC) (2020)","DOI":"10.1007\/978-3-030-45724-2_27"},{"key":"16_CR59","doi-asserted-by":"crossref","unstructured":"Ghazi, B., Manurangsi, P., Pagh, R., Velingker, A.: Private aggregation from fewer anonymous messages. arXiv:1909.11073 (2019)","DOI":"10.1007\/978-3-030-45724-2_27"},{"key":"16_CR60","unstructured":"Ghazi, B., Pagh, R., Velingker, A.: Scalable and differentially private distributed aggregation in the shuffled model. arXiv:1906.08320 (2019)"},{"key":"16_CR61","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Guha, S., Indyk, P., Kotidis, Y., Muthukrishnan, S., Strauss, M.J.: Fast, small-space algorithms for approximate histogram maintenance. In: STOC, pp. 389\u2013398 (2002)","DOI":"10.1145\/509907.509966"},{"key":"16_CR62","unstructured":"Greenberg, A.: Apple\u2019s \u201cdifferential privacy\u201d is about collecting your data - but not your data. Wired, 13 June 2016"},{"issue":"2","key":"16_CR63","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1145\/376284.375670","volume":"30","author":"M Greenwald","year":"2001","unstructured":"Greenwald, M., Khanna, S., et al.: Space-efficient online computation of quantile summaries. ACM SIGMOD Rec. 30(2), 58\u201366 (2001)","journal-title":"ACM SIGMOD Rec."},{"key":"16_CR64","unstructured":"Hardt, M., Ligett, K., McSherry, F.: A simple and practical algorithm for differentially private data release. In: NIPS, pp. 2339\u20132347 (2012). http:\/\/dl.acm.org\/citation.cfm?id=2999325.2999396"},{"key":"16_CR65","doi-asserted-by":"crossref","unstructured":"Hardt, M., Rothblum, G.N.: A multiplicative weights mechanism for privacy-preserving data analysis. In: FOCS, pp. 61\u201370 (2010)","DOI":"10.1109\/FOCS.2010.85"},{"issue":"1\u20132","key":"16_CR66","doi-asserted-by":"publisher","first-page":"1021","DOI":"10.14778\/1920841.1920970","volume":"3","author":"M Hay","year":"2010","unstructured":"Hay, M., Rastogi, V., Miklau, G., Suciu, D.: Boosting the accuracy of differentially private histograms through consistency. VLDB 3(1\u20132), 1021\u20131032 (2010). https:\/\/doi.org\/10.14778\/1920841.1920970","journal-title":"VLDB"},{"key":"16_CR67","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/978-3-642-31594-7_39","volume-title":"Automata, Languages, and Programming","author":"J Hsu","year":"2012","unstructured":"Hsu, J., Khanna, S., Roth, A.: Distributed private heavy hitters. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012. LNCS, vol. 7391, pp. 461\u2013472. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31594-7_39"},{"key":"16_CR68","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography from anonymity. In: FOCS, pp. 239\u2013248 (2006)","DOI":"10.1109\/FOCS.2006.25"},{"key":"16_CR69","unstructured":"Kairouz, P., Bonawitz, K., Ramage, D.: Discrete distribution estimation under local privacy. In: ICML, pp. 2436\u20132444 (2016)"},{"key":"16_CR70","doi-asserted-by":"crossref","unstructured":"Karnin, Z., Lang, K., Liberty, E.: Optimal quantile approximation in streams. In: FOCS, pp. 71\u201378 (2016)","DOI":"10.1109\/FOCS.2016.17"},{"key":"16_CR71","doi-asserted-by":"crossref","unstructured":"Kasiviswanathan, S.P., Lee, H.K., Nissim, K., Rashkodnikova, S., Smith, A.: What can we learn privately? In: FOCS, pp. 531\u2013540 (2008)","DOI":"10.1109\/FOCS.2008.27"},{"key":"16_CR72","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-540-78524-8_11","volume-title":"Theory of Cryptography","author":"J Kilian","year":"2008","unstructured":"Kilian, J., Madeira, A., Strauss, M.J., Zheng, X.: Fast private norm estimation and heavy hitters. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 176\u2013193. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78524-8_11"},{"key":"16_CR73","unstructured":"Lei, J.: Differentially private $$m$$-estimators. In: NIPS, pp. 361\u2013369 (2011)"},{"key":"16_CR74","doi-asserted-by":"crossref","unstructured":"Li, C., Hay, M., Rastogi, V., Milau, G., McGregor, A.: Optimizing linear counting queries under differential privacy. In: PODS, pp. 123\u2013134 (2010)","DOI":"10.1145\/1807085.1807104"},{"issue":"6","key":"16_CR75","first-page":"514","volume":"5","author":"C Li","year":"2012","unstructured":"Li, C., Miklau, G.: An adaptive mechanism for accurate query answering under differential privacy. VLDB 5(6), 514\u2013525 (2012)","journal-title":"VLDB"},{"key":"16_CR76","doi-asserted-by":"crossref","unstructured":"Li, N., Li, T., Venkatasubramanian, S.: $$t$$-closeness: privacy beyond $$k$$-anonymity and $$l$$-diversity. In: ICDE, pp. 106\u2013115 (2007)","DOI":"10.1109\/ICDE.2007.367856"},{"issue":"2","key":"16_CR77","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1145\/276305.276342","volume":"27","author":"GS Manku","year":"1998","unstructured":"Manku, G.S., Rajagopalan, S., Lindsay, B.G.: Approximate medians and other quantiles in one pass and with limited memory. ACM SIGMOD Rec. 27(2), 426\u2013435 (1998)","journal-title":"ACM SIGMOD Rec."},{"key":"16_CR78","doi-asserted-by":"crossref","unstructured":"McSherry, F., Talwar, K.: Mechanism design via differential privacy. In: FOCS, pp. 94\u2013103 (2007)","DOI":"10.1109\/FOCS.2007.66"},{"issue":"2","key":"16_CR79","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0167-6423(82)90012-0","volume":"2","author":"J Misra","year":"1982","unstructured":"Misra, J., Gries, D.: Finding repeated elements. Sci. Comput. Program. 2(2), 143\u2013152 (1982)","journal-title":"Sci. Comput. Program."},{"issue":"3","key":"16_CR80","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","volume":"12","author":"JI Munro","year":"1980","unstructured":"Munro, J.I., Paterson, M.S.: Selection and sorting with limited storage. TCS 12(3), 315\u2013323 (1980)","journal-title":"TCS"},{"key":"16_CR81","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S., Nikolov, A.: Optimal private halfspace counting via discrepancy. In: STOC, pp. 1285\u20131292 (2012)","DOI":"10.1145\/2213977.2214090"},{"key":"16_CR82","unstructured":"Nguyen, T., Xiao, X., Yang, Y., Hui, S.C., Shin, H., Shin, J.: Collecting and analyzing data from smart device users with local differential privacy. arXiv:1606.05053 (2016)"},{"key":"16_CR83","doi-asserted-by":"crossref","unstructured":"Nikolov, A., Talwar, K., Zhang, L.: On the geometry of differential privacy: the sparse and approximate cases. In: STOC, pp. 351\u2013360 (2013)","DOI":"10.1145\/2488608.2488652"},{"key":"16_CR84","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782","volume-title":"Analysis of Boolean Functions","author":"R O\u2019Donnell","year":"2014","unstructured":"O\u2019Donnell, R.: Analysis of Boolean Functions. Cambridge University Press, Cambridge (2014)"},{"issue":"14","key":"16_CR85","doi-asserted-by":"publisher","first-page":"1954","DOI":"10.14778\/2556549.2556576","volume":"6","author":"W Qardaji","year":"2013","unstructured":"Qardaji, W., Yang, W., Li, N.: Understanding hierarchical methods for differentially private histograms. VLDB 6(14), 1954\u20131965 (2013). https:\/\/doi.org\/10.14778\/2556549.2556576","journal-title":"VLDB"},{"issue":"2","key":"16_CR86","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1137\/S0040585X9797821X","volume":"45","author":"B Roos","year":"2006","unstructured":"Roos, B.: Binomial approximation to the Poisson binomial distribution: the Krawtchouk expansion. Theory Prob. Appl. 45(2), 258\u2013272 (2006)","journal-title":"Theory Prob. Appl."},{"key":"16_CR87","unstructured":"Shankland, S.: How Google tricks itself to protect Chrome user privacy. CNET, October 2014"},{"key":"16_CR88","doi-asserted-by":"crossref","unstructured":"Smith, A.D.: Privacy-preserving statistical estimation with optimal convergence rates. In: STOC, pp. 813\u2013822 (2011)","DOI":"10.1145\/1993636.1993743"},{"issue":"2","key":"16_CR89","first-page":"3","volume":"7","author":"T Steinke","year":"2016","unstructured":"Steinke, T., Ullman, J.: Between pure and approximate differential privacy. J. Priv. Confid. 7(2), 3\u201322 (2016)","journal-title":"J. Priv. Confid."},{"key":"16_CR90","doi-asserted-by":"crossref","unstructured":"Steinke, T., Ullman, J.: Tight lower bounds for differentially private selection. In: FOCS, pp. 552\u2013563 (2017)","DOI":"10.1109\/FOCS.2017.57"},{"key":"16_CR91","doi-asserted-by":"crossref","unstructured":"Stemmer, U.: Locally private k-means clustering. In: Proceedings of the 2020 Symposium on Discrete Algorithms (2020)","DOI":"10.1137\/1.9781611975994.33"},{"key":"16_CR92","unstructured":"Ullman, J.: Tight lower bounds for locally differentially private selection. arXiv:1802.02638 (2018)"},{"key":"16_CR93","series-title":"Information Security and Cryptography","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/978-3-319-57048-8_7","volume-title":"Tutorials on the Foundations of Cryptography","author":"S Vadhan","year":"2017","unstructured":"Vadhan, S.: The complexity of differential privacy. In: Lindell, Y. (ed.) Tutorials on the Foundations of Cryptography. ISC, pp. 347\u2013450. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-57048-8_7"},{"key":"16_CR94","unstructured":"Wagh, S., He, X., Machanavajjhala, A., Mittal, P.: DP-cryptography: marrying differential privacy and cryptography in emerging applications. CoRR abs\/2004.08887 (2020). https:\/\/arxiv.org\/abs\/2004.08887, to appear in Communications of the ACM"},{"key":"16_CR95","unstructured":"Wang, T., Blocki, J., Li, N., Jha, S.: Locally differentially private protocols for frequency estimation. In: USENIX Security, pp. 729\u2013745 (2017)"},{"key":"16_CR96","unstructured":"Wang, T., Xu, M., Ding, B., Zhou, J., Li, N., Jha, S.: Practical and robust privacy amplification with multi-party differential privacy. arXiv:1908.11515 (2019)"},{"issue":"309","key":"16_CR97","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1080\/01621459.1965.10480775","volume":"60","author":"SL Warner","year":"1965","unstructured":"Warner, S.L.: Randomized response: a survey technique for eliminating evasive answer bias. JASA 60(309), 63\u201369 (1965)","journal-title":"JASA"},{"issue":"489","key":"16_CR98","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1198\/jasa.2009.tm08651","volume":"105","author":"L Wasserman","year":"2010","unstructured":"Wasserman, L., Zhou, S.: A statistical framework for differential privacy. JASA 105(489), 375\u2013389 (2010)","journal-title":"JASA"},{"issue":"8","key":"16_CR99","first-page":"1200","volume":"23","author":"X Xiao","year":"2010","unstructured":"Xiao, X., Wang, G., Gehrke, J.: Differential privacy via wavelet transforms. TKDE 23(8), 1200\u20131214 (2010)","journal-title":"TKDE"},{"key":"16_CR100","doi-asserted-by":"crossref","unstructured":"Ye, M., Barg, A.: Optimal schemes for discrete distribution estimation under local differential privacy. In: ISIT, pp. 759\u2013763 (2017)","DOI":"10.1109\/ISIT.2017.8006630"},{"issue":"1","key":"16_CR101","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/s00453-011-9584-4","volume":"65","author":"K Yi","year":"2013","unstructured":"Yi, K., Zhang, Q.: Optimal tracking of distributed heavy hitters and quantiles. Algorithmica 65(1), 206\u2013223 (2013)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2021"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-77883-5_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,16]],"date-time":"2024-06-16T00:05:27Z","timestamp":1718496327000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-77883-5_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030778828","9783030778835"],"references-count":101,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-77883-5_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"16 June 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"EUROCRYPT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Zagreb","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Croatia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 October 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 October 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"40","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"eurocrypt2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/eurocrypt.iacr.org\/2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"HotCRP","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"400","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"78","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"20% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"at least 3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"21","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}