Document Open Access Logo

Do Distributed Differentially-Private Protocols Require Oblivious Transfer?

Authors Vipul Goyal, Dakshita Khurana, Ilya Mironov, Omkant Pandey, Amit Sahai

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2016.29.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Subject Classification

Keywords
  • Oblivious Transfer
  • Distributed Differential Privacy
  • Noisy Channels
  • Weak Noisy Channels

Metrics

Abstract

We study the cryptographic complexity of two-party differentially-private protocols for a large natural class of boolean functionalities. Information theoretically, McGregor et al. [FOCS 2010] and Goyal et al. [Crypto 2013] demonstrated several functionalities for which the maximal possible accuracy in the distributed setting is significantly lower than that in the client-server setting. Goyal et al. [Crypto 2013] further showed that "highly accurate" protocols in the distributed setting for any non-trivial functionality in fact imply the existence of one-way functions. However, it has remained an open problem to characterize the exact cryptographic complexity of this class. In particular, we know that semi-honest oblivious transfer helps obtain optimally accurate distributed differential privacy. But we do not know whether the reverse is true. We study the following question: Does the existence of optimally accurate distributed differentially private protocols for any class of functionalities imply the existence of oblivious transfer (or equivalently secure multi-party computation)? We resolve this question in the affirmative for the class of boolean functionalities that contain an XOR embedded on adjacent inputs. We give a reduction from oblivious transfer to:

- Any distributed optimally accurate epsilon-differentially private protocol with epsilon > 0 computing a functionality with a boolean XOR embedded on adjacent inputs.

- Any distributed non-optimally accurate epsilon-differentially private protocol with epsilon > 0, for a constant range of non-optimal accuracies and constant range of values of epsilon, computing a functionality with a boolean XOR embedded on adjacent inputs.

Enroute to proving these results, we demonstrate a connection between optimally-accurate twoparty differentially-private protocols for functions with a boolean XOR embedded on adjacent inputs, and noisy channels, which were shown by Crépeau and Kilian [FOCS 1988] to be sufficient for oblivious transfer.

Cite As Get BibTex

Vipul Goyal, Dakshita Khurana, Ilya Mironov, Omkant Pandey, and Amit Sahai. Do Distributed Differentially-Private Protocols Require Oblivious Transfer?. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.29

Author Details

Vipul Goyal
Dakshita Khurana
Ilya Mironov
Omkant Pandey
Amit Sahai

References

  1. Amos Beimel, Kobbi Nissim, and Eran Omri. Distributed private data analysis: Simultaneously solving how and what. In Wagner [42], pages 451-468. URL: http://dx.doi.org/10.1007/978-3-540-85174-5_25.
  2. Hai Brenner and Kobbi Nissim. Impossibility of differentially private universally optimal mechanisms. In focs2010 [16], pages 71-80. URL: http://dx.doi.org/10.1109/FOCS.2010.13.
  3. Benny Chor and Eyal Kushilevitz. A zero-one law for boolean privacy (extended abstract). In David S. Johnson, editor, STOC, pages 62-72. ACM, 1989. URL: http://dx.doi.org/10.1145/73007.73013.
  4. Benny Chor and Eyal Kushilevitz. A zero-one law for Boolean privacy. SIAM J. Discrete Math., 4(1):36-47, 1991. URL: http://dx.doi.org/10.1137/0404004.
  5. Claude Crépeau and Joe Kilian. Weakening security assumptions and oblivious transfer (abstract). In Shafi Goldwasser, editor, CRYPTO, volume 403 of Lecture Notes in Computer Science, pages 2-7. Springer, 1988. URL: http://dx.doi.org/10.1007/0-387-34799-2_1.
  6. Ivan Damgård, Joe Kilian, and Louis Salvail. On the (im)possibility of basing oblivious transfer and bit commitment on weakened security assumptions. In Jacques Stern, editor, Advances in Cryptology - EUROCRYPT'99, International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, May 2-6, 1999, Proceeding, volume 1592 of Lecture Notes in Computer Science, pages 56-73. Springer, 1999. URL: http://dx.doi.org/10.1007/3-540-48910-X_5.
  7. Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In Frank Neven, Catriel Beeri, and Tova Milo, editors, PODS, pages 202-210. ACM, 2003. URL: http://dx.doi.org/10.1145/773153.773173.
  8. Cynthia Dwork. Differential privacy. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, ICALP (2), volume 4052 of Lecture Notes in Computer Science, pages 1-12. Springer, 2006. URL: http://dx.doi.org/10.1007/11787006_1.
  9. Cynthia Dwork. A firm foundation for private data analysis. Commun. ACM, 54(1):86-95, 2011. URL: http://dx.doi.org/10.1145/1866739.1866758.
  10. Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Serge Vaudenay, editor, EUROCRYPT, volume 4004 of Lecture Notes in Computer Science, pages 486-503. Springer, 2006. URL: http://dx.doi.org/10.1007/11761679_29.
  11. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin, editors, TCC, volume 3876 of Lecture Notes in Computer Science, pages 265-284. Springer, 2006. URL: http://dx.doi.org/10.1007/11681878_14.
  12. Cynthia Dwork, Frank McSherry, and Kunal Talwar. The price of privacy and the limits of LP decoding. In David S. Johnson and Uriel Feige, editors, STOC, pages 85-94. ACM, 2007. URL: http://dx.doi.org/10.1145/1250790.1250804.
  13. Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil P. Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In Mitzenmacher [38], pages 381-390. URL: http://dx.doi.org/10.1145/1536414.1536467.
  14. Cynthia Dwork and Kobbi Nissim. Privacy-preserving datamining on vertically partitioned databases. In Matthew K. Franklin, editor, CRYPTO, volume 3152 of Lecture Notes in Computer Science, pages 528-544. Springer, 2004. URL: http://dx.doi.org/10.1007/978-3-540-28628-8_32.
  15. Cynthia Dwork and Sergey Yekhanin. New efficient attacks on statistical disclosure control mechanisms. In Wagner [42], pages 469-480. URL: http://dx.doi.org/10.1007/978-3-540-85174-5_26.
  16. 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA. IEEE Computer Society, 2010. Google Scholar
  17. Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan. Universally utility-maximizing privacy mechanisms. In Mitzenmacher [38], pages 351-360. URL: http://dx.doi.org/10.1145/1536414.1536464.
  18. Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. In Alfred V. Aho, editor, STOC, pages 218-229. ACM, 1987. URL: http://dx.doi.org/10.1145/28395.28420.
  19. Vipul Goyal, Ilya Mironov, Omkant Pandey, and Amit Sahai. Accuracy-privacy tradeoffs for two-party differentially private protocols. In Ran Canetti and Juan A. Garay, editors, CRYPTO (1), volume 8042 of Lecture Notes in Computer Science, pages 298-315. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40041-4_17.
  20. Mangesh Gupte and Mukund Sundararajan. Universally optimal privacy mechanisms for minimax agents. In Jan Paredaens and Dirk Van Gucht, editors, PODS, pages 135-146. ACM, 2010. URL: http://dx.doi.org/10.1145/1807085.1807105.
  21. Iftach Haitner, Eran Omri, and Hila Zarosim. Limits on the usefulness of random oracles. Theory of Cryptography Conference (TCC, to appear), 2013. Google Scholar
  22. Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Schulman [40], pages 705-714. URL: http://dx.doi.org/10.1145/1806689.1806786.
  23. Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam Smith, and Jonathan Ullman. The price of privately releasing contingency tables and the spectra of random matrices with correlated rows. In Schulman [40], pages 775-784. URL: http://dx.doi.org/10.1145/1806689.1806795.
  24. Dakshita Khurana, Daniel Kraschewski, Hemanta K. Maji, Manoj Prabhakaran, and Amit Sahai. All complete functionalities are reversible, 2015. Google Scholar
  25. Dakshita Khurana, Hemanta K. Maji, and Amit Sahai. Black-box separations for differentially private protocols. In Palash Sarkar and Tetsu Iwata, editors, Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014, Proceedings, Part II, volume 8874 of Lecture Notes in Computer Science, pages 386-405. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-45608-8_21.
  26. Joe Kilian. Founding cryptography on oblivious transfer. In Janos Simon, editor, STOC, pages 20-31. ACM, 1988. URL: http://dx.doi.org/10.1145/62212.62215.
  27. Joe Kilian. A general completeness theorem for two-party games. In STOC, pages 553-560. ACM, 1991. URL: http://dx.doi.org/10.1145/103418.103475.
  28. Joe Kilian. More general completeness theorems for secure two-party computation. In F. Frances Yao and Eugene M. Luks, editors, STOC, pages 316-324. ACM, 2000. URL: http://dx.doi.org/10.1145/335305.335342.
  29. Joe Kilian, Eyal Kushilevitz, Silvio Micali, and Rafail Ostrovsky. Reducibility and completeness in private computations. SIAM J. Comput., 29(4):1189-1208, 2000. URL: http://dx.doi.org/10.1137/S0097539797321742.
  30. Daniel Kraschewski, Hemanta K. Maji, Manoj Prabhakaran, and Amit Sahai. A full characterization of completeness for two-party randomized function evaluation. In Phong Q. Nguyen and Elisabeth Oswald, editors, Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings, volume 8441 of Lecture Notes in Computer Science, pages 659-676. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-642-55220-5_36.
  31. Robin Künzler, Jörn Müller-Quade, and Dominik Raub. Secure computability of functions in the it setting with dishonest majority and applications to long-term security. In Reingold [39], pages 238-255. URL: http://dx.doi.org/10.1007/978-3-642-00457-5_15.
  32. Eyal Kushilevitz. Privacy and communication complexity. In FOCS, pages 416-421. IEEE, 1989. URL: http://dx.doi.org/10.1109/SFCS.1989.63512.
  33. Hemanta K. Maji, Manoj Prabhakaran, and Mike Rosulek. Complexity of multi-party computation problems: The case of 2-party symmetric secure function evaluation. In Reingold [39], pages 256-273. URL: http://dx.doi.org/10.1007/978-3-642-00457-5_16.
  34. Hemanta K. Maji, Manoj Prabhakaran, and Mike Rosulek. A zero-one law for cryptographic complexity with respect to computational uc security. In Tal Rabin, editor, CRYPTO, volume 6223 of Lecture Notes in Computer Science, pages 595-612. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14623-7_32.
  35. Hemanta K. Maji, Manoj Prabhakaran, and Mike Rosulek. A unified characterization of completeness and triviality for secure function evaluation. In Steven D. Galbraith and Mridul Nandi, editors, INDOCRYPT, volume 7668 of Lecture Notes in Computer Science, pages 40-59. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-34931-7_4.
  36. Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, and Salil P. Vadhan. The limits of two-party differential privacy. In focs2010 [16], pages 81-90. URL: http://dx.doi.org/10.1109/FOCS.2010.14.
  37. Ilya Mironov, Omkant Pandey, Omer Reingold, and Salil P. Vadhan. Computational differential privacy. In Shai Halevi, editor, CRYPTO, volume 5677 of Lecture Notes in Computer Science, pages 126-142. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-03356-8_8.
  38. Michael Mitzenmacher, editor. Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009. ACM, 2009. Google Scholar
  39. Omer Reingold, editor. Theory of Cryptography, 6th Theory of Cryptography Conference, TCC 2009, San Francisco, CA, USA, March 15-17, 2009. Proceedings, volume 5444 of Lecture Notes in Computer Science. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-00457-5.
  40. Leonard J. Schulman, editor. Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010. ACM, 2010. Google Scholar
  41. Jonathan Ullman and Salil P. Vadhan. PCPs and the hardness of generating private synthetic data. In Yuval Ishai, editor, TCC, volume 6597 of Lecture Notes in Computer Science, pages 400-416. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-19571-6_24.
  42. David Wagner, editor. Advances in Cryptology - CRYPTO 2008, 28th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2008. Proceedings, volume 5157 of Lecture Notes in Computer Science. Springer, 2008. Google Scholar
  43. Jürg Wullschleger. Oblivious transfer from weak noisy channels. In TCC, pages 332-349, 2009. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact