2026-07-26T00:57:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6308 2024-03-06T10:37:41Z ddc:004 open_access

Do Distributed Differentially-Private Protocols Require Oblivious Transfer? Goyal, Vipul Khurana, Dakshita Mironov, Ilya Pandey, Omkant Sahai, Amit Oblivious Transfer Distributed Differential Privacy Noisy Channels Weak Noisy Channels 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vipul Goyal and Dakshita Khurana and Ilya Mironov and Omkant Pandey and Amit Sahai 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.29 urn:nbn:de:0030-drops-63080 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.29 eng https://creativecommons.org/licenses/by/3.0/legalcode