License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.29
URN: urn:nbn:de:0030-drops-63080
URL: http://drops.dagstuhl.de/opus/volltexte/2016/6308/
Go to the corresponding LIPIcs Volume Portal


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

Do Distributed Differentially-Private Protocols Require Oblivious Transfer?

pdf-format:
LIPIcs-ICALP-2016-29.pdf (0.6 MB)


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.

BibTeX - Entry

@InProceedings{goyal_et_al:LIPIcs:2016:6308,
  author =	{Vipul Goyal and Dakshita Khurana and Ilya Mironov and Omkant Pandey and Amit Sahai},
  title =	{{Do Distributed Differentially-Private Protocols Require Oblivious Transferl}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{29:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6308},
  URN =		{urn:nbn:de:0030-drops-63080},
  doi =		{10.4230/LIPIcs.ICALP.2016.29},
  annote =	{Keywords: Oblivious Transfer, Distributed Differential Privacy, Noisy Channels, Weak Noisy Channels}
}

Keywords: Oblivious Transfer, Distributed Differential Privacy, Noisy Channels, Weak Noisy Channels
Seminar: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 17.08.2016


DROPS-Home | Imprint | Privacy Published by LZI