Private Frequency Aggregation With Pseudo-Random Encoding And Peer-Assist Transmission(PREPAT)

Comprehensive analysis of massive user data is the core value of many commercial applications.With the continuous improvement of the entire society's awareness and attention to privacy protection,it is becoming increasingly important and urgent to collect and statistically analyze users' overall data while promising valid privacy protection capabilities.Local differential privacy is currently one of the most important technical frameworks to solve such problems.This technology enables users to reasonably disturb the original input submitted by themselves,so as to obtain plausible deniability,to protect their privacy,while not requiring the involvement of a trusted third party server.At present,major companies including Google,Apple,and Microsoft have all applied local differential privacy technology in the data collection process.However,the current practical local differential privacy algorithms all have inherent defects.Due to the existence of random disturbances,systematic statistical errors cannot be avoided.At the same time,due to the limitations of transmission overhead and privacy budget,the scheme of expanding the collection scale to reduce errors is also facing many difficulties,these problems limit the large-scale practical application of localized differential privacy.Based on the existing research,this dissertation has the following contributions:1.A general solution to improve the localized differential privacy transmission overhead is proposed.A pseudo-random number generation algorithm can be used to transmit the unique heat vector representation of any element using a constant level of communication overhead.Premise of statistical availability and statistical availability of pseudo-random number generators,and guarantees thecorrectness of the algorithm.This paper proves the theoretical correctness of the scheme and experimentally verifies its safety and feasibility.2.Based on the transmission optimization scheme,a hierarchical retransmission frequency statistics optimization technology is proposed.The main idea of this technology is to allow the use of constant-level communication overhead advantages to assist in transmission by peer other users,creating more differences in low frequency input Disturbance version,so as to sample more low-frequency input to get better estimate for this type of input.This paper first proves the theoretical feasibility of the scheme,and then quantitatively clarifies the accuracy improvement and privacy guarantee that the technology can provide.3.The performance of this algorithm is evaluated in the actual scene using Baidu input method.In the actual scene where Baidu input method is applied,with additional pseudo-random computation cost,the algorithm has an evident improvement in accuracy and efficiency compared with the original scheme,and single transmission overhead is reduced to a constant level.