Sub-linear Queries Statistical Databases: Privacy with Power

摘要

We consider a statistical database in which a trusted administrator introduces noise to the query responses with the goal of maintaining privacy of individual database entries. In such a database, a query consists of a pair (5, f) where S is a set of rows in the database and f is a function mapping database rows to {0,1}. The true response is ∑_(r∈S) f(DB_r), a noisy version of which is released. Results in show that a strong form of privacy can be maintained using a surprisingly small amount of noise, provided the total number of queries is sublin-ear in the number n of database rows. We call this a sub-linear queries (SuLQ) database. The assumption of sublinearity becomes reasonable as databases grow increasingly large. The SuLQ primitive - query and noisy reply - gives rise to a calculus of noisy computation. After reviewing some results of on multi-attribute SuLQ, we illustrate the power of the SuLQ primitive with three examples: principal component analysis, k means clustering, and learning in the statistical queries learning model.