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
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.
