Secure Multi-party Differential Privacy
We study the problem of interactive function computation by multiple parties, each possessing a bit, in a differential privacy setting (i.e., there remains an uncertainty in any party's bit even when given the transcript of interactions and all the other parties' bits). Each party wants to compute 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 is measured via the accuracy of the function to be computed. We allow for an arbitrary cost metric to measure the distortion between the true and the computed function values. Our main result is the optimality of a simple non-interactive protocol: each party randomizes its bit (sufficiently) and shares the privatized version with the other parties. This optimality result 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.
This paper looks at the multiparty computation problem and shows that if the computation must be done under differential privacy, each party should essentially use randomized response independently on its own data. The main approach is to use a linear program to model the problem. They must do a fair bit of work to characterize the optimum policy, which is randomized response.This is a "heavy" review, although I do not have too many comments for this paper. I did not have adequate time to fully verify the proofs in the supplementary material.1)In (1) it might be worth clarifying again that the input has no probability distribution so this is not average over data sets. This is important because the discussion before (8) on protocol compatibility makes it seem like the input bits are in fact random.2)One issue I have with the manuscript is that the description of the analysis in the main document seems mostly like an advertisement for how hard and challenging it is without providing enough intuition or summary to really understand what is going on. Cramming a full journal paper into the NIPS format is hard, but I would encourage the authors to think of the reader who might want a little more formal vs. descriptive exposition. That is, there is no insight into the "novel transformation" mentioned before Section 3. It would be nice to see some of that transformation described in the main document.3) Similarly how might one give more depth to the statement "[w]e need to utilize the convex geometry of the problem in order to show that interaction is not necessary"?In the end is this geometric insight intuitive or counterintuitive?4) The fact that the optimality of non-interaction holds only for single bits is, to my mind, a major drawback of this work, and is in fact rather hidden in the exposition in the beginning of the paper, where a highlighted statement "non-interactive randomized response is exactly optimal" is made that seems to be very general. This is a kind of false advertising, since the single-bit case is made to seem like a toy example that contains the insights as opposed to perhaps a pathological example where parties have extremely limited information and few options. To be clear, I think this is an interesting result, but I think one should present it plainly, warts and all.5) Finally, the main concern I have with this paper is the fit with NIPS. This is fundamentally a paper about MPC and not really about learning, machine or otherwise. While there are some intersections, this feels very much like a TCS paper and may be of more interest, more impactful, and better received in a venue such as NIPS. That being said, I think it's a solid and interesting piece of work.Smaller issues: p2: The Sweeney paper [37] did not reveal the medical record of the governor. Please read the paper and state more accurately what was actually disclosed. p5-6: The sentence going across the page is not grammatical. p6: "but it turns out" p6: "the the" --> "the" AFTER AUTHOR FEEDBACK: I thank the authors for their responses. I think my score stands as-is. I'm still not convinced about the fit, especially given the limitation to 1-bit protocols (and indications that it does not extend to multi-bit protocols). I don't think the audience at NIPS will be as appreciative.