Leakage Inversion: Towards Quantifying Privacy in Searchable Encryption
Leakage Inversion: Towards Quantifying Privacy in Searchable Encryption
复制标题
泄漏反演：量化可搜索加密中的隐私
DOI：
10.1145/3548606.3560593
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Psomas, Alexandros
中科院分区：
文献类型：
--
作者：
Kornaropoulos, Evgenios M.;Moyer, Nathaniel;Papamanthou, Charalampos;Psomas, Alexandros
可搜索加密（SE）提供密码保证，用户可以有效地搜索加密数据，同时仅公开有关数据的模式，也称为泄漏。最近，社区开发了泄漏滥用攻击，揭示了攻击者可以使用上述泄漏推断潜在的敏感信息。在这项工作中，一个明显的缺失是缺乏一个系统的和严格的方法，量化的隐私保证SE。在这项工作中，我们提出了泄漏反转的概念，量化的隐私SE。我们的见解是，泄漏是一个函数，因此，可以定义其逆，对应于数据库的集合，揭示结构上等同于原始明文数据库的模式。我们把这个数据库集合称为重建空间，并严格研究了它的性质，这些性质会影响SE方案的隐私，例如重建空间的熵及其成员与原始明文数据库的距离。泄漏反演允许一个基本的算法分析所提供的隐私SE，我们证明了这一点，通过定义封闭形式的表达式和下/上界的重建空间的属性为基础的关键字和范围的数据库。我们在三种情况下使用泄漏反转：（i）我们量化了辅助信息（一个典型的密码分析假设）对整体隐私的影响，（ii）我们量化了在限制范围方案以响应有限数量的查询的情况下隐私如何受到影响，以及（iii）我们研究了效率与隐私权衡所提出的填充防御。我们在这三种情况下都使用了真实世界的数据库，并从理论上对泄漏、攻击、防御和效率之间的相互作用提出了新的见解。
Searchable encryption (SE) provides cryptographic guarantees that a user can efficiently search over encrypted data while only disclosing patterns about the data, also known as leakage. Recently, the community has developed leakage-abuse attacks that shed light on what an attacker can infer about the underlying sensitive information using the aforementioned leakage. A glaring missing piece in this effort is the absence of a systematic and rigorous method that quantifies the privacy guarantees of SE.In this work, we put forth the notion of leakage inversion that quantifies privacy in SE. Our insight is that the leakage is a function and, thus, one can define its inverse which corresponds to the collection of databases that reveal structurally equivalent patterns to the original plaintext database. We call this collection of databases the reconstruction space and we rigorously study its properties that impact the privacy of an SE scheme such as the entropy of the reconstruction space and the distance of its members from the original plaintext database. Leakage inversion allows for a foundational algorithmic analysis of the privacy offered by SE and we demonstrate this by defining closed-form expressions and lower/upper bounds on the properties of the reconstruction space for both keyword-based and range-based databases. We use leakage inversion in three scenarios: (i) we quantify the impact that auxiliary information, a typical cryptanalytic assumption, has to the overall privacy, (ii) we quantify how privacy is affected in case of restricting range schemes to respond to a limited number of queries, and (iii) we study the efficiency vs. privacy trade-off offered by proposed padding defenses. We use real-world databases in all three scenarios and we draw theoretically-grounded new insights about the interplay between leakage, attacks, defenses, and efficiency.
登录
查看更多内容
影响因子：
--
作者：
A. Boldyreva;Tianxin Tang
通讯作者：
A. Boldyreva;Tianxin Tang
DOI：
--
发表时间：
2021
期刊：
International Conference on the Theory and Application of Cryptographic Techniques
影响因子：
--
作者：
Marilyn George;S. Kamara;Tarik Moataz
通讯作者：
Tarik Moataz
SSE 和 SSD：页面高效可搜索对称加密
DOI：
--
发表时间：
2021
期刊：
IACR Cryptology ePrint Archive
影响因子：
--
作者：
Angèle Bossuat;Raphael Bost;Pierre;Brice Minaud;Michael Reichle
通讯作者：
Michael Reichle
DOI：
10.1145/3035918.3035948
发表时间：
2017-05
期刊：
Proceedings of the 2017 ACM International Conference on Management of Data
影响因子：
--
作者：
Caleb Horst;Ryo Kikuchi;Keita Xagawa
通讯作者：
Caleb Horst;Ryo Kikuchi;Keita Xagawa
DOI：
10.1007/978-3-319-96131-6
发表时间：
2020
期刊：
The Science of Quantitative Information Flow
影响因子：
--
作者：
M. Alvim;K. Chatzikokolakis;Annabelle McIver;Carroll Morgan;C. Palamidessi;Geoffrey Smith
通讯作者：
Geoffrey Smith