基于图论与互信息量的差分隐私度量模型

差分隐私是数据发布、数据挖掘领域内隐私保护的重要工具,但其强度和效果仅能后验评估,且高度依赖于经验性选择的隐私预算。文中提出一种基于图论和互信息量的差分隐私量化模型和隐私泄露量计算方法。利用信息论通信模型重构了差分隐私保护框架,构造了差分隐私信息通信模型和隐私度量模型;基于图的距离正则和点传递提出隐私泄露互信息量化方法,证明并计算了差分隐私泄露量的信息量上界。分析和对比表明,该隐私泄露上界与原始数据集的属性数量、属性值数量以及隐私预算参数具有较好的函数关系,且计算限制条件较少。文中所提方法优于现有方法,能够为差分隐私算法的设计及评价、隐私泄露风险评估提供理论支撑。

Privacy Metric Model of Differential Privacy via Graph Theory and Mutual Information

Differential privacy is an important tool for privacy preserving in many fields,such as data publishing and data mining.However,the strength and effectiveness of differential privacy cannot be evaluated previously,and highly rely on empirical selection of privacy budget.To this end,a privacy metric model and a privacy leakage method via graph theory and mutual information were proposed.This work models differential privacy as an information theoretic communication channel,and constructs an information channel and privacy metric model for differential privacy.Then,a mutual information based privacy metric method is proposed by employing the distance-regular and vertex-transitive of graphs,the upper bound of this metric is proofed,and an explicit formula is proposed for the bound.Delicate analysis and comparison show that the proposed upper bound has a function relationship limited by fewer computational constraints among the original dataset’s attributes,attribute values and privacy budget.This work benefits more than related works,and provides theoretical foundation for algorithm design,algorithm evaluation,and privacy assessment.