{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:12:14Z","timestamp":1775913134685,"version":"3.50.1"},"reference-count":28,"publisher":"Privacy Enhancing Technologies Symposium Advisory Board","issue":"3","license":[{"start":{"date-parts":[[2019,7,1]],"date-time":"2019-07-01T00:00:00Z","timestamp":1561939200000},"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":[[2019,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>In this work we demonstrate that allowing differentially private leakage can significantly improve the concrete performance of secure 2-party computation (2PC) protocols. Specifically, we focus on the private set intersection (PSI) protocol of Rindal and Rosulek (CCS 2017), which is the fastest PSI protocol with security against malicious participants. We show that if differentially private leakage is allowed, the cost of the protocol can be reduced by up to 63%, depending on the desired level of differential privacy. On the technical side, we introduce a security model for differentially-private leakage in malicious-secure 2PC. We also introduce two new and improved mechanisms for \u201cdifferentially private histogram overestimates,\u201d the main technical challenge for differentially-private PSI.<\/jats:p>","DOI":"10.2478\/popets-2019-0034","type":"journal-article","created":{"date-parts":[[2019,7,20]],"date-time":"2019-07-20T09:31:19Z","timestamp":1563615079000},"page":"6-25","source":"Crossref","is-referenced-by-count":23,"title":["Cheaper Private Set Intersection via Differentially Private Leakage"],"prefix":"10.56553","volume":"2019","author":[{"given":"Adam","family":"Groce","sequence":"first","affiliation":[{"name":"Reed College ."}]},{"given":"Peter","family":"Rindal","sequence":"additional","affiliation":[{"name":"Visa Research ."}]},{"given":"Mike","family":"Rosulek","sequence":"additional","affiliation":[{"name":"Oregon State University ."}]}],"member":"35752","published-online":{"date-parts":[[2019,7,12]]},"reference":[{"key":"2022042411344025180_j_popets-2019-0034_ref_001_w2aab3b7b2b1b6b1ab1ab1Aa","doi-asserted-by":"crossref","unstructured":"[1] R. Bassily, A. Groce, J. Katz, and A. Smith. Coupled-worlds privacy: Exploiting adversarial uncertainty in statistical data privacy. In 54th FOCS, pages 439\u2013448. IEEE Computer Society Press, Oct. 2013.10.1109\/FOCS.2013.54","DOI":"10.1109\/FOCS.2013.54"},{"key":"2022042411344025180_j_popets-2019-0034_ref_002_w2aab3b7b2b1b6b1ab1ab2Aa","doi-asserted-by":"crossref","unstructured":"[2] A. Beimel, K. Nissim, and E. Omri. Distributed private data analysis: Simultaneously solving how and what. In D. Wagner, editor, CRYPTO 2008, volume 5157 of LNCS, pages 451\u2013468. Springer, Heidelberg, Aug. 2008.10.1007\/978-3-540-85174-5_25","DOI":"10.1007\/978-3-540-85174-5_25"},{"key":"2022042411344025180_j_popets-2019-0034_ref_003_w2aab3b7b2b1b6b1ab1ab3Aa","unstructured":"[3] M. Burkhart, M. Strasser, D. Many, and X. Dimitropoulos. Sepia: Privacy-preserving aggregation of multi-domain network events and statistics. Network, 1(101101), 2010."},{"key":"2022042411344025180_j_popets-2019-0034_ref_004_w2aab3b7b2b1b6b1ab1ab4Aa","doi-asserted-by":"crossref","unstructured":"[4] R. Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42nd FOCS, pages 136\u2013145. IEEE Computer Society Press, Oct. 2001.10.1109\/SFCS.2001.959888","DOI":"10.1109\/SFCS.2001.959888"},{"key":"2022042411344025180_j_popets-2019-0034_ref_005_w2aab3b7b2b1b6b1ab1ab5Aa","doi-asserted-by":"crossref","unstructured":"[5] D. Cash, S. Jarecki, C. S. Jutla, H. Krawczyk, M.-C. Rosu, and M. Steiner. Highly-scalable searchable symmetric encryption with support for Boolean queries. In R. Canetti and J. A. Garay, editors, CRYPTO 2013, Part I, volume 8042 of LNCS, pages 353\u2013373. Springer, Heidelberg, Aug. 2013.10.1007\/978-3-642-40041-4_20","DOI":"10.1007\/978-3-642-40041-4_20"},{"key":"2022042411344025180_j_popets-2019-0034_ref_006_w2aab3b7b2b1b6b1ab1ab6Aa","unstructured":"[6] T.-H. H. Chan, K.-M. Chung, B. Maggs, and E. Shi. Foundations of differentially oblivious algorithms. Cryptology ePrint Archive, Report 2017\/1033, 2017. http:\/\/eprint.iacr.org\/2017\/1033."},{"key":"2022042411344025180_j_popets-2019-0034_ref_007_w2aab3b7b2b1b6b1ab1ab7Aa","unstructured":"[7] M. Chase, R. Gilad-Bachrach, K. Laine, K. Lauter, and P. Rindal. Private collaborative neural network learning. Cryptology ePrint Archive, Report 2017\/762, 2017. https:\/\/eprint.iacr.org\/2017\/762."},{"key":"2022042411344025180_j_popets-2019-0034_ref_008_w2aab3b7b2b1b6b1ab1ab8Aa","doi-asserted-by":"crossref","unstructured":"[8] C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In S. Halevi and T. Rabin, editors, TCC 2006, volume 3876 of LNCS, pages 265\u2013284. Springer, Heidelberg, Mar. 2006.10.1007\/11681878_14","DOI":"10.1007\/11681878_14"},{"key":"2022042411344025180_j_popets-2019-0034_ref_009_w2aab3b7b2b1b6b1ab1ab9Aa","doi-asserted-by":"crossref","unstructured":"[9] E. Fenske, A. Mani, A. Johnson, and M. Sherr. Distributed measurement with private set-union cardinality. In B. M. Thuraisingham, D. Evans, T. Malkin, and D. Xu, editors, ACM CCS 17, pages 2295\u20132312. ACM Press, Oct. \/ Nov. 2017.10.1145\/3133956.3134034","DOI":"10.1145\/3133956.3134034"},{"key":"2022042411344025180_j_popets-2019-0034_ref_010_w2aab3b7b2b1b6b1ab1ac10Aa","doi-asserted-by":"crossref","unstructured":"[10] M. J. Freedman, K. Nissim, and B. Pinkas. Efficient private matching and set intersection. In C. Cachin and J. Camenisch, editors, EUROCRYPT 2004, volume 3027 of LNCS, pages 1\u201319. Springer, Heidelberg, May 2004.10.1007\/978-3-540-24676-3_1","DOI":"10.1007\/978-3-540-24676-3_1"},{"key":"2022042411344025180_j_popets-2019-0034_ref_011_w2aab3b7b2b1b6b1ab1ac11Aa","doi-asserted-by":"crossref","unstructured":"[11] O. Goldreich. Towards a theory of software protection and simulation by oblivious RAMs. In A. Aho, editor, 19th ACM STOC, pages 182\u2013194. ACM Press, May 1987.10.1145\/28395.28416","DOI":"10.1145\/28395.28416"},{"key":"2022042411344025180_j_popets-2019-0034_ref_012_w2aab3b7b2b1b6b1ab1ac12Aa","doi-asserted-by":"crossref","unstructured":"[12] X. He, A. Machanavajjhala, C. J. Flynn, and D. Srivastava. Composing differential privacy and secure computation: A case study on scaling private record linkage. In B. M. Thuraisingham, D. Evans, T. Malkin, and D. Xu, editors, ACM CCS 17, pages 1389\u20131406. ACM Press, Oct. \/ Nov. 2017.10.1145\/3133956.3134030","DOI":"10.1145\/3133956.3134030"},{"key":"2022042411344025180_j_popets-2019-0034_ref_013_w2aab3b7b2b1b6b1ab1ac13Aa","doi-asserted-by":"crossref","unstructured":"[13] Y. Huang, J. Katz, and D. Evans. Quid-Pro-Quo-tocols: Strengthening semi-honest protocols with dual execution. In 2012 IEEE Symposium on Security and Privacy, pages 272\u2013284. IEEE Computer Society Press, May 2012.10.1109\/SP.2012.43","DOI":"10.1109\/SP.2012.43"},{"key":"2022042411344025180_j_popets-2019-0034_ref_014_w2aab3b7b2b1b6b1ab1ac14Aa","unstructured":"[14] P. Kairouz, S. Oh, and P. Viswanath. Differentially private multi-party computation: Optimality of non-interactive randomized response. arXiv preprint arXiv:1407.1546, 2014."},{"key":"2022042411344025180_j_popets-2019-0034_ref_015_w2aab3b7b2b1b6b1ab1ac15Aa","unstructured":"[15] S. P. Kasiviswanathan and A. Smith. A note on differential privacy: Defining resistance to arbitrary side information. Cryptology ePrint Archive, Report 2008\/144, 2008. http:\/\/eprint.iacr.org\/2008\/144."},{"key":"2022042411344025180_j_popets-2019-0034_ref_016_w2aab3b7b2b1b6b1ab1ac16Aa","unstructured":"[16] G. Kellaris, G. Kollios, K. Nissim, and A. O\u2019Neill. Accessing data while preserving privacy. CoRR, abs\/1706.01552, 2017."},{"key":"2022042411344025180_j_popets-2019-0034_ref_017_w2aab3b7b2b1b6b1ab1ac17Aa","doi-asserted-by":"crossref","unstructured":"[17] V. Kolesnikov, P. Mohassel, B. Riva, and M. Rosulek. Richer efficiency\/security trade-offs in 2PC. In Y. Dodis and J. B. Nielsen, editors, TCC 2015, Part I, volume 9014 of LNCS, pages 229\u2013259. Springer, Heidelberg, Mar. 2015.10.1007\/978-3-662-46494-6_11","DOI":"10.1007\/978-3-662-46494-6_11"},{"key":"2022042411344025180_j_popets-2019-0034_ref_018_w2aab3b7b2b1b6b1ab1ac18Aa","unstructured":"[18] S. Mazloom and S. D. Gordon. Differentially private access patterns in secure computation. Cryptology ePrint Archive, Report 2017\/1016, 2017. http:\/\/eprint.iacr.org\/2017\/1016."},{"key":"2022042411344025180_j_popets-2019-0034_ref_019_w2aab3b7b2b1b6b1ab1ac19Aa","doi-asserted-by":"crossref","unstructured":"[19] P. Mohassel and M. Franklin. Efficiency tradeoffs for malicious two-party computation. In M. Yung, Y. Dodis, A. Kiayias, and T. Malkin, editors, PKC 2006, volume 3958 of LNCS, pages 458\u2013473. Springer, Heidelberg, Apr. 2006.10.1007\/11745853_30","DOI":"10.1007\/11745853_30"},{"key":"2022042411344025180_j_popets-2019-0034_ref_020_w2aab3b7b2b1b6b1ab1ac20Aa","unstructured":"[20] A. Narayan and A. Haeberlen. Djoin: Differentially private join queries over distributed databases. In C. Thekkath and A. Vahdat, editors, 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012, Hollywood, CA, USA, October 8\u201310, 2012, pages 149\u2013162. USENIX Association, 2012."},{"key":"2022042411344025180_j_popets-2019-0034_ref_021_w2aab3b7b2b1b6b1ab1ac21Aa","doi-asserted-by":"crossref","unstructured":"[21] M. Orr\u00f9, E. Orsini, and P. Scholl. Actively secure 1-out-of-N OT extension with application to private set intersection. In H. Handschuh, editor, CT-RSA 2017, volume 10159 of LNCS, pages 381\u2013396. Springer, Heidelberg, Feb. 2017.10.1007\/978-3-319-52153-4_22","DOI":"10.1007\/978-3-319-52153-4_22"},{"key":"2022042411344025180_j_popets-2019-0034_ref_022_w2aab3b7b2b1b6b1ab1ac22Aa","doi-asserted-by":"crossref","unstructured":"[22] R. Ostrovsky. Efficient computation on oblivious RAMs. In 22nd ACM STOC, pages 514\u2013523. ACM Press, May 1990.10.1145\/100216.100289","DOI":"10.1145\/100216.100289"},{"key":"2022042411344025180_j_popets-2019-0034_ref_023_w2aab3b7b2b1b6b1ab1ac23Aa","doi-asserted-by":"crossref","unstructured":"[23] A. Papadimitriou, A. Narayan, and A. Haeberlen. Dstress: Efficient differentially private computations on distributed data. In Proceedings of the Twelfth European Conference on Computer Systems, pages 560\u2013574. ACM, 2017.10.1145\/3064176.3064218","DOI":"10.1145\/3064176.3064218"},{"key":"2022042411344025180_j_popets-2019-0034_ref_024_w2aab3b7b2b1b6b1ab1ac24Aa","doi-asserted-by":"crossref","unstructured":"[24] V. Pappas, F. Krell, B. Vo, V. Kolesnikov, T. Malkin, S. G. Choi, W. George, A. D. Keromytis, and S. Bellovin. Blind seer: A scalable private DBMS. In 2014 IEEE Symposium on Security and Privacy, pages 359\u2013374. IEEE Computer Society Press, May 2014.10.1109\/SP.2014.30","DOI":"10.1109\/SP.2014.30"},{"key":"2022042411344025180_j_popets-2019-0034_ref_025_w2aab3b7b2b1b6b1ab1ac25Aa","doi-asserted-by":"crossref","unstructured":"[25] V. Rastogi and S. Nath. Differentially private aggregation of distributed time-series with transformation and encryption. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pages 735\u2013746. ACM, 2010.10.1145\/1807167.1807247","DOI":"10.1145\/1807167.1807247"},{"key":"2022042411344025180_j_popets-2019-0034_ref_026_w2aab3b7b2b1b6b1ab1ac26Aa","doi-asserted-by":"crossref","unstructured":"[26] P. Rindal and M. Rosulek. Malicious-secure private set intersection via dual execution. In B. M. Thuraisingham, D. Evans, T. Malkin, and D. Xu, editors, ACM CCS 17, pages 1229\u20131242. ACM Press, Oct. \/ Nov. 2017.10.1145\/3133956.3134044","DOI":"10.1145\/3133956.3134044"},{"key":"2022042411344025180_j_popets-2019-0034_ref_027_w2aab3b7b2b1b6b1ab1ac27Aa","unstructured":"[27] P. Schoppmann, A. Gasc\u00f3n, and B. Balle. Private nearest neighbors classification in federated databases. Cryptology ePrint Archive, Report 2018\/289, 2018. https:\/\/eprint.iacr.org\/2018\/289."},{"key":"2022042411344025180_j_popets-2019-0034_ref_028_w2aab3b7b2b1b6b1ab1ac28Aa","unstructured":"[28] S. Wagh, P. Cuff, and P. Mittal. Root oram: A tunable differentially private oblivious ram. arXiv preprint arXiv:1601.03378, 2016."}],"container-title":["Proceedings on Privacy Enhancing Technologies"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/content.sciendo.com\/view\/journals\/popets\/2019\/3\/article-p6.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.sciendo.com\/pdf\/10.2478\/popets-2019-0034","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T16:30:27Z","timestamp":1658334627000},"score":1,"resource":{"primary":{"URL":"https:\/\/petsymposium.org\/popets\/2019\/popets-2019-0034.php"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,1]]},"references-count":28,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2019,7,12]]},"published-print":{"date-parts":[[2019,7,1]]}},"alternative-id":["10.2478\/popets-2019-0034"],"URL":"https:\/\/doi.org\/10.2478\/popets-2019-0034","relation":{},"ISSN":["2299-0984"],"issn-type":[{"value":"2299-0984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,1]]}}}