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

Cheaper Private Set Intersection via Differentially Private Leakage

Published Online: 12 Jul 2019
Page range: 6 - 25
Received: 30 Nov 2018
Accepted: 16 Mar 2019
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English

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 “differentially private histogram overestimates,” the main technical challenge for differentially-private PSI.

[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–448. IEEE Computer Society Press, Oct. 2013.Search in Google Scholar

[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–468. Springer, Heidelberg, Aug. 2008.Search in Google Scholar

[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.Search in Google Scholar

[4] R. Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42nd FOCS, pages 136–145. IEEE Computer Society Press, Oct. 2001.Search in Google Scholar

[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–373. Springer, Heidelberg, Aug. 2013.Search in Google Scholar

[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.Search in Google Scholar

[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.Search in Google Scholar

[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–284. Springer, Heidelberg, Mar. 2006.Search in Google Scholar

[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–2312. ACM Press, Oct. / Nov. 2017.Search in Google Scholar

[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–19. Springer, Heidelberg, May 2004.Search in Google Scholar

[11] O. Goldreich. Towards a theory of software protection and simulation by oblivious RAMs. In A. Aho, editor, 19th ACM STOC, pages 182–194. ACM Press, May 1987.Search in Google Scholar

[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–1406. ACM Press, Oct. / Nov. 2017.Search in Google Scholar

[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–284. IEEE Computer Society Press, May 2012.Search in Google Scholar

[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.Search in Google Scholar

[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.Search in Google Scholar

[16] G. Kellaris, G. Kollios, K. Nissim, and A. O’Neill. Accessing data while preserving privacy. CoRR, abs/1706.01552, 2017.Search in Google Scholar

[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–259. Springer, Heidelberg, Mar. 2015.Search in Google Scholar

[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.Search in Google Scholar

[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–473. Springer, Heidelberg, Apr. 2006.Search in Google Scholar

[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–10, 2012, pages 149–162. USENIX Association, 2012.Search in Google Scholar

[21] M. Orrù, 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–396. Springer, Heidelberg, Feb. 2017.Search in Google Scholar

[22] R. Ostrovsky. Efficient computation on oblivious RAMs. In 22nd ACM STOC, pages 514–523. ACM Press, May 1990.Search in Google Scholar

[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–574. ACM, 2017.Search in Google Scholar

[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–374. IEEE Computer Society Press, May 2014.Search in Google Scholar

[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–746. ACM, 2010.Search in Google Scholar

[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–1242. ACM Press, Oct. / Nov. 2017.Search in Google Scholar

[27] P. Schoppmann, A. Gascón, and B. Balle. Private nearest neighbors classification in federated databases. Cryptology ePrint Archive, Report 2018/289, 2018. https://eprint.iacr.org/2018/289.Search in Google Scholar

[28] S. Wagh, P. Cuff, and P. Mittal. Root oram: A tunable differentially private oblivious ram. arXiv preprint arXiv:1601.03378, 2016.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo