On the efficiency of checking perfect privacy
On the efficiency of checking perfect privacy
复制标题
论完美隐私检查的效率
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
J. Gehrke
中科院分区：
文献类型：
--
作者：
Ashwin Machanavajjhala;J. Gehrke
隐私保护的查询应答系统回答查询，同时可证明地保证敏感信息保密。隐私的一个非常有吸引力的概念是完全隐私-秘密通过查询QS来表示，并且只有当查询QV没有公开关于秘密查询QS的信息时才回答查询QV。然而，如果QS和QV是任意的合取查询，检查QV是否透露任何有关QS的信息的问题是已知的，在本文中，我们表明，对于大型有趣的子类别的合取查询执行完美的隐私是易于处理的。而不是给不同的参数不同的复杂性的查询类，我们完美的隐私和检查查询包含的问题之间的连接。然后，我们使用这种连接的复杂性，实施完美的隐私的复杂性，查询包容。
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 QS, and a query QV is answered only if it discloses no information about the secret query QS. However, if QS and QV are arbitrary conjunctive queries, the problem of checking whether QV discloses any information about QS is known to be Πp2-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 to the complexity of query containment.