{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T01:08:22Z","timestamp":1766279302951,"version":"3.48.0"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031223648"},{"type":"electronic","value":"9783031223655"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"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":[[2022]]},"DOI":"10.1007\/978-3-031-22365-5_13","type":"book-chapter","created":{"date-parts":[[2022,12,21]],"date-time":"2022-12-21T03:04:30Z","timestamp":1671591870000},"page":"348-377","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Secure Sampling with\u00a0Sublinear Communication"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9563-9648","authenticated-orcid":false,"given":"Seung Geol","family":"Choi","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6797-641X","authenticated-orcid":false,"given":"Dana","family":"Dachman-Soled","sequence":"additional","affiliation":[]},{"given":"S. Dov","family":"Gordon","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8982-9688","authenticated-orcid":false,"given":"Linsheng","family":"Liu","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9045-748X","authenticated-orcid":false,"given":"Arkady","family":"Yerukhimovich","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,12,21]]},"reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"Acar, A., Celik, Z.B., Aksu, H., Uluagac, A.S., McDaniel, P.: Achieving secure and differentially private computations in multiparty settings. In 2017 IEEE Symposium on Privacy-Aware Computing (PAC), pp. 49\u201359. IEEE (2017)","DOI":"10.1109\/PAC.2017.12"},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Andoni, A., Krauthgamer, R., Onak, K.: Streaming algorithms via precision sampling. In: Ostrovsky, R., IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, 22\u201325 October 2011, pp. 363\u2013372. IEEE Computer Society (2011)","DOI":"10.1109\/FOCS.2011.82"},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Babai, L., Nisan, N., Szegedy, M.: Multiparty protocols and logspace-hard pseudorandom sequences (extended abstract). In: 21st ACM STOC, pp. 1\u201311. ACM Press (1989)","DOI":"10.1145\/73007.73008"},{"issue":"4","key":"13_CR4","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1016\/j.jcss.2003.11.006","volume":"68","author":"Z Bar-Yossef","year":"2004","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kumar, R., Sivakumar, D.: An information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci. 68(4), 702\u2013732 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"13_CR5","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/j.jcss.2011.04.004","volume":"78","author":"V Braverman","year":"2012","unstructured":"Braverman, V., Ostrovsky, R., Zaniolo, C.: Optimal sampling from sliding windows. J. Comput. Syst. Sci. 78(1), 260\u2013272 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"Champion, J., Shelat, A., Ullman, J.: Securely sampling biased coins with applications to differential privacy. In: Cavallaro, L., Kinder, J., Wang, X., Katz, J., (eds.) ACM CCS 2019, pp. 603\u2013614. ACM Press, (2019)","DOI":"10.1145\/3319535.3354256"},{"key":"13_CR7","unstructured":"Choi, S.G., Dachman-Soled, D., Gordon, S.D., Liu, L., Yerukhimovich, A.: Secure sampling with sublinear communication. Cryptology ePrint Archive, Paper 2022\/660 (2022). https:\/\/eprint.iacr.org\/2022\/660"},{"issue":"3","key":"13_CR8","doi-asserted-by":"publisher","first-page":"153","DOI":"10.2478\/popets-2020-0047","volume":"2020","author":"SG Choi","year":"2020","unstructured":"Choi, S.G., Dachman-Soled, D., Kulkarni, M., Yerukhimovich, A.: Differentially-private multi-party sketching for large-scale statistics. PoPETs 2020(3), 153\u2013174 (2020)","journal-title":"PoPETs"},{"key":"13_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-45204-8_1","volume-title":"Information Systems Security","author":"C Clifton","year":"2013","unstructured":"Clifton, C., Anandan, B.: Challenges and opportunities for security with differential privacy. In: Bagchi, A., Ray, I. (eds.) ICISS 2013. LNCS, vol. 8303, pp. 1\u201313. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-45204-8_1"},{"issue":"1","key":"13_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3297715","volume":"52","author":"G Cormode","year":"2019","unstructured":"Cormode, G., Jowhari, H.: L p samplers and their applications: a survey. ACM Comput. Surv. (CSUR) 52(1), 1\u201331 (2019)","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"13_CR11","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":"13_CR12","doi-asserted-by":"crossref","unstructured":"Elahi, T., Danezis, G., Goldberg, I.: PrivEx: private collection of traffic statistics for anonymous communication networks. In: Ahn, G.J., Yung, M., Li, N., (eds.) ACM CCS 2014, pp. 1068\u20131079. ACM Press (2014)","DOI":"10.1145\/2660267.2660280"},{"key":"13_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/978-3-662-64322-8_13","volume-title":"Financial Cryptography and Data Security","author":"R Eriguchi","year":"2021","unstructured":"Eriguchi, R., Ichikawa, A., Kunihiro, N., Nuida, K.: Efficient noise generation to achieve differential privacy with applications to secure multiparty computation. In: Borisov, N., Diaz, C. (eds.) FC 2021. LNCS, vol. 12674, pp. 271\u2013290. Springer, Heidelberg (2021). https:\/\/doi.org\/10.1007\/978-3-662-64322-8_13"},{"key":"13_CR14","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"927","DOI":"10.1007\/3-540-48224-5_75","volume-title":"ICALP 2001","author":"J Feigenbaum","year":"2001","unstructured":"Feigenbaum, J., Ishai, Y., Malkin, T., Nissim, K., Strauss, M., Wright, R.N.: Secure multiparty computation of approximations. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 927\u2013938. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-48224-5_75"},{"issue":"3","key":"13_CR15","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1145\/1159892.1159900","volume":"2","author":"J Feigenbaum","year":"2006","unstructured":"Feigenbaum, J., Ishai, Y., Malkin, T., Nissim, K., Strauss, M.J., Wright, R.N.: Secure multiparty computation of approximations. ACM Trans. Algorithms 2(3), 435\u2013472 (2006)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"13_CR16","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.tcs.2007.02.031","volume":"378","author":"S Ganguly","year":"2007","unstructured":"Ganguly, S.: Counting distinct items over update streams. Theoret. Comput. Sci. 378(3), 211\u2013222 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"Goryczka, S., Xiong, L., Sunderam, V.: Secure multiparty aggregation with differential privacy: a comparative study. In: Proceedings of the Joint EDBT\/ICDT 2013 Workshops, pp. 155\u2013163 (2013)","DOI":"10.1145\/2457317.2457343"},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: 30th ACM STOC, pp. 604\u2013613. ACM Press (1998)","DOI":"10.1145\/276698.276876"},{"key":"13_CR19","doi-asserted-by":"crossref","unstructured":"Jansen, R., Johnson, A.: Safely measuring tor. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S., (eds.) ACM CCS 2016, pp. 1553\u20131567. ACM Press (2016)","DOI":"10.1145\/2976749.2978310"},{"key":"13_CR20","doi-asserted-by":"crossref","unstructured":"Johnson, W.B. Lindenstrauss, J.: Extensions of lipschitz mappings into a hilbert space (1984)","DOI":"10.1090\/conm\/026\/737400"},{"key":"13_CR21","doi-asserted-by":"crossref","unstructured":"Jowhari, H., Saglam, M., Tardos, G.: Tight bounds for LP samplers, finding duplicates in streams, and related problems. In: Lenzerini, M., Schwentick, T., (eds.) Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2011, 12\u201316 June 2011, Athens, Greece, pp. 49\u201358. ACM (2011)","DOI":"10.1145\/1989284.1989289"},{"key":"13_CR22","doi-asserted-by":"crossref","unstructured":"Jowhari, H., Saglam, M., Tardos, G.: Tight bounds for LP samplers, finding duplicates in streams, and related problems. In: Proceedings of the Thirtieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 49\u201358 (2011)","DOI":"10.1145\/1989284.1989289"},{"key":"13_CR23","doi-asserted-by":"crossref","unstructured":"Kab\u00e1n, A.: Improved bounds on the dot product under random projection and random sign projection. In: Cao, L., Zhang, C., Joachims, T., Webb, G.I.B., Margineantu, D., Williams, G., (eds.) Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, 10\u201313 August 2015, pp. 487\u2013496. ACM (2015)","DOI":"10.1145\/2783258.2783364"},{"issue":"4","key":"13_CR24","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"B Kalyanasundaram","year":"1992","unstructured":"Kalyanasundaram, B., Schnitger, G.: The probabilistic communication complexity of set intersection. SIAM J. Discret. Math. 5(4), 545\u2013557 (1992)","journal-title":"SIAM J. Discret. Math."},{"key":"13_CR25","doi-asserted-by":"crossref","unstructured":"McSherry, F., Talwar, K.: Mechanism design via differential privacy. In: 48th FOCS, pp. 94\u2013103. IEEE Computer Society Press (2007)","DOI":"10.1109\/FOCS.2007.66"},{"key":"13_CR26","doi-asserted-by":"crossref","unstructured":"Melis, L., Danezis, G., De Cristofaro, E.: Efficient private statistics with succinct sketches. In: NDSS 2016. The Internet Society (2016)","DOI":"10.14722\/ndss.2016.23175"},{"key":"13_CR27","doi-asserted-by":"crossref","unstructured":"Monemizadeh, M., Woodruff, D.P.: 1-pass relative-error l$${}_{\\text{p}}$$-sampling with applications. In: Charikar, M., ed. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, 17\u201319 January 2010, pp. 1143\u20131160. SIAM (2010)","DOI":"10.1137\/1.9781611973075.92"},{"issue":"4","key":"13_CR28","doi-asserted-by":"publisher","first-page":"291","DOI":"10.2478\/popets-2021-0071","volume":"2021","author":"C Mouchet","year":"2021","unstructured":"Mouchet, C., Troncoso-Pastoriza, J., Bossuat, J.P., Hubaux, J.P.: Multiparty homomorphic encryption from ring-learning-with-errors. PoPETs 2021(4), 291\u2013311 (2021)","journal-title":"PoPETs"},{"key":"13_CR29","unstructured":"Pathak, M., Rane, S., Raj, B.: Multiparty differential privacy via aggregation of locally trained classifiers. In: Advances in Neural Information Processing Systems, vol. 23 (2010)"},{"key":"13_CR30","unstructured":"Pentyala, S., et al.: Training differentially private models with secure multiparty computation. arXiv preprint arXiv:2202.02625 (2022)"},{"key":"13_CR31","doi-asserted-by":"crossref","unstructured":"Prabhakaran, M.M., Prabhakaran, V.M.: On secure multiparty sampling for more than two parties. In 2012 IEEE Information Theory Workshop, pp. 99\u2013103. IEEE (2012)","DOI":"10.1109\/ITW.2012.6404773"},{"issue":"6","key":"13_CR32","doi-asserted-by":"publisher","first-page":"3413","DOI":"10.1109\/TIT.2014.2316011","volume":"60","author":"VM Prabhakaran","year":"2014","unstructured":"Prabhakaran, V.M., Prabhakaran, M.M.: Assisted common information with an application to secure two-party sampling. IEEE Trans. Inf. Theor. 60(6), 3413\u20133434 (2014)","journal-title":"IEEE Trans. Inf. Theor."},{"issue":"2","key":"13_CR33","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0304-3975(92)90260-M","volume":"106","author":"AA Razborov","year":"1992","unstructured":"Razborov, A.A.: On the distributional complexity of disjointness. Theor. Comput. Sci. 106(2), 385\u2013390 (1992)","journal-title":"Theor. Comput. Sci."},{"key":"13_CR34","doi-asserted-by":"crossref","unstructured":"Wails, R., Johnson, A., Starin, D., Yerukhimovich, A., Gordon, S.D.: Stormy: statistics in tor by measuring securely. In: Cavallaro, L., Kinder, J., Wang, X., Katz, J., (eds.) ACM CCS 2019, pp. 615\u2013632. ACM Press (2019)","DOI":"10.1145\/3319535.3345650"},{"key":"13_CR35","doi-asserted-by":"crossref","unstructured":"Woodruff, D.P., Zhong, P.: Distributed low rank approximation of implicit functions of a matrix. In: 2016 IEEE 32nd International Conference on Data Engineering (ICDE), pp. 847\u2013858. IEEE (2016)","DOI":"10.1109\/ICDE.2016.7498295"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-22365-5_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T01:02:23Z","timestamp":1766278943000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-22365-5_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031223648","9783031223655"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-22365-5_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"21 December 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TCC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Theory of Cryptography Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chicago, IL","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 November 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 November 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcc.iacr.org\/2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-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":"139","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":"60","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":"43% - 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":"3.1","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":"9.9","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"}]}}