An Improved Christofides Mechanism for Local Differential Privacy Framework

The development of Internet technology enables an analysis on the whole population rather than a certain number of samples, and leads to increasing requirement for privacy protection. Local differential privacy (LDP) is an effective standard of privacy measurement; however, its large variance of mean estimation causes challenges in application. To address this problem, this paper presents a new LDP approach, an improved Christofides mechanism. It compared four statistical survey methods for conducting surveys on sensitive topics -- modified Warner, Simmons, Christofides, and the improved Christofides mechanism. Specifically, Warner, Simmons and Christofides mechanisms have been modified to draw a sample from the population without replacement, to decrease variance. Furthermore, by drawing cards without replacement based on modified Christofides mechanism, we introduce a new mechanism called the improved Christofides mechanism, which is found to have the smallest variance under certain assumption when using LDP as a measurement of privacy leakage. The assumption is do satisfied usually in the real world. Actually, we decrease the variance to 28.7% of modified Christofides mechanism's variance in our experiment based on the HCOVANY dataset -- a real world dataset of IPUMS USA. This means our method gets a more accurate estimate by using LDP as a measurement of privacy leakage. This is the first time the improved Christofides mechanism is proposed for LDP framework based on comparative analysis of four mechanisms using LDP as the same measurement of privacy leakage.