2014/07/06 by Peter Kairouz, Sewoong Oh, Kairouz, Peter +3 · 1 citation
Computer Science · #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Internet Traffic Analysis and Secure E-voting #Mobile Crowdsensing and Crowdsourcing #Privacy-Preserving Technologies in Data #cs.CR
paper · pdf · doi:10.48550/arxiv.1407.1546
21 pages, 2 figures
openalex publication_date 2014/07/06 · arxiv created 2014/10/07 · arxiv updated 2014/10/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of interactive function computation by multiple parties possessing a single bit each in a differential privacy setting (i.e., there remains an uncertainty in any specific party's bit even when given the transcript of the interactions and all the other parties' bits). Each party is interested in computing a function, which could differ from party to party, and there could be a central observer interested in computing a separate function. Performance at each party and the central observer is measured via the accuracy of the function computed. We allow for an arbitrary cost function to measure the distortion between the true and the computed function value. Our main result is the exact optimality of a simple non-interactive protocol: each party randomizes (sufficiently) and publishes its own bit. In other words, non-interactive randomized response is exactly optimal. Each party and the central observer then separately compute their respective function to maximize the appropriate notion of their accuracy measure. The optimality is very general: it holds for all types of functions, heterogeneous privacy conditions on the parties, all types of cost metrics, and both average and worst-case (over the inputs) measures of accuracy. Finally, the optimality result is simultaneous, in terms of maximizing accuracy at each of the parties and the central observer.