δ-privacy: Bounding Privacy Leaks in Privacy Preserving Data Mining

摘要

We propose a new definition for privacy, called δ-privacy, for privacy preserving data mining. The intuition of this work is, after obtaining a result from a data mining method, an adversary has better ability in discovering data providers' privacy; if this improvement is large, the method, which generated the response, is not privacy considerate. δ-privacy requires that no adversary could improve more than δ. This definition can be used to assess the risk of privacy leak in any data mining methods, in particular, we show its relations to differential privacy and data anonymity, the two major evaluation methods. We also provide a quantitative analysis on the tradeoff between privacy and utility, rigorously prove that the information gains of any δ-private methods do not exceed δ. Under the framework of δ-privacy, it is able to design a pricing mechanism for privacy-utility trading system, which is one of our major future works.