3
$\begingroup$

Generally, differential privacy adds noise to a query result, such as a sum or an average, in an interactive way.

Is there any way for implementing differential privacy such that noise will be added in an non-interactive way, record by record ?

Thanks in advance

$\endgroup$
  • 1
    $\begingroup$ To even attempt an answer I'd need you to further explain what you believe DP techniques do exactly and what you mean by "an interactive way". Also "record by record"? Are you wanting some sort of DP protection on non-cumulative values? That seems to violate the very definition of DP. $\endgroup$ – Thomas M. DuBuisson Feb 20 '17 at 22:00
  • $\begingroup$ In interactive way I mean an interface for which I can send queries to the database, and the result comes with noise. And yes, I want to know if there is some sort of DP protection on non-cumulative values $\endgroup$ – joao-prg Feb 20 '17 at 23:22
2
$\begingroup$

Yes, the classic example is Randomized response: when doing a survey with a yes/no question that is sensitive (for example, "are you currently an undocumented immigrant living in the US"), you ask each respondent to flip a coin first. If the coin hits tails, you tell them to answer randomly (by flipping a second coin), otherwise, ask them to answer honestly. Then, you remove 25% of the "yes" answers to take into account people who answered randomly, and you get a noisy total count that has differential privacy.

It corresponds to this idea of "adding noise to each record" instead of adding noise to the end-result (in this case, the total number of illegal immigrants). The main advantage is that you don't need a trusted third-party that has all the "real" data. The main disadvantage is that the result is more noisy for the same privacy property.

You can compute more complex statistics with this randomized response idea. For example, things like "which websites are most commonly used as home pages in Google Chrome" are computed using RAPPOR. The method is described in their paper.

More recently, Vincent Bindschaedler, Reza Shokri, and Carl Gunter have detailed a generic method to generate a synthetic dataset from real data, with differential privacy guarantees. It's not exactly "adding noise record by record", but it's similar to this idea of releasing not simply noisy statistics, but a full dataset that can be used for data mining.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.