Using Randomized Response for Differential Privacy Preserving Data Collection
Yue Wang, Xintao Wu, Donghui Hu · 2016
This paper studies how to enforce differential privacy by using the randomized response in the data collection scenario. Given a clien-t’s value, the randomized algorithm executed by the client reports to the untrusted server a perturbed value. The use of randomized response in surveys enables easy estimations of accurate popula-tion statistics while preserving the privacy of the individual respon-dents. We compare the randomized response with the standard Laplace mechanism which is based on query-output independent adding of Laplace noise. Our research starts from the simple case with one single binary attribute and extends to the general case with multiple polychotomous attributes. Wemeasure utility preservation in terms of the mean squared error of the estimate for various cal-culations including individual value estimate, proportion estimate, and various derived statistics. We theoretically derive the explic-it formula of the mean squared error of various derived statistics based on the randomized response theory and prove the random-ized response outperforms the Laplace mechanism. We evaluate our algorithms on YesiWell database including sensitive biomarker data and social network relationships of patients. Empirical evalu-ation results show effectiveness of our proposed techniques. Espe-cially the use of the randomized response for collecting data incurs fewer utility loss than the output perturbation when the sensitivity of functions is high.