On the efficiency of checking perfect privacy

摘要

Privacy-preserving query-answering systems answer queries while provably guaranteeing that sensitive information is kept secret. One very attractive notion of privacy is perfect privacy-a secret is expressed through a query Q_S, and a query Q_V is answered only if it discloses no information about the secret query Q_S. However, if Q_S and Q_V are arbitrary conjunctive queries, the problem of checking whether Q_V discloses any information about Q_S is known to be Π^p₂-complete.In this paper, we show that for large interesting subclasses of conjunctive queries enforcing perfect privacy is tractable. Instead of giving different arguments for query classes of varying complexity, we make a connection between perfect privacy and the problem of checking query containment. We then use this connection to relate the complexity of enforcing perfect privacy tothe complexity of query containment.