2021/12/14 by Fei Ma, Ping Wang, Ma, Fei +1
Computer Science · Medicine · #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data #SARS-CoV-2 detection and testing #Transplantation: Methods and Outcomes
paper · pdf · doi:10.48550/arxiv.2112.07397
openalex publication_date 2021/12/14 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
Randomized response, as a basic building-block for differentially private mechanism, has given rise to great interest and found various potential applications in science communities. In this work, we are concerned with three-elements randomized response (RR3) along with relevant applications to the analysis of weighted bipartite graph upon differentially private guarantee. We develop a principled framework for estimating statistics produced by RR3-based mechanisms, and then prove the corresponding estimations to be unbiased. At the same time, we study in detail several fundamental and significant members in RR3 family, and derive the closed-form solutions to unbiased estimations. Next, we show potential applications of several RR3-based mechanisms into the estimation of average degree and average weighted value on weighted bipartite graph when requiring local differential privacy guarantee. In the meantime, we determine the lower bounds for choice of relevant parameters by minimizing variance of statistics in order to design optimal RR3-based local differential private mechanisms, with which we optimize previous protocols in the literature and put forward a version that achieves the tight bound. Last but most importantly, we observe that in the analysis of relational data such as weighted bipartite graph, a portion of privacy budget in local differential private mechanism is sometimes "consumed" by mechanism itself accidentally, resulting to a more stronger privacy guarantee than we would get by simply sequential compositions.