An Information-Theoretic Approach to Inference Attacks on Random Data Perturbation and a Related Privacy Measure

Random data perturbation (RDP) has been in use for several years in statistical databases and public surveys as a means of providing privacy to individuals while collecting information on groups, and has recently gained popularity as a privacy technique in data mining. This correspondence provides an information-theoretic framework for all inference attacks on RDP. The framework is used to demonstrate the existence of a tight asymptotic lower bound on the number of queries required per bit of entropy for all inference attacks with zero asymptotic error and bounded average power in the query sequence. A privacy measure based on security against inference attacks is proposed.