LEAF: A Faster Secure Search Algorithm via Localization, Extraction, and Reconstruction
LEAF: A Faster Secure Search Algorithm via Localization, Extraction, and Reconstruction
复制标题
DOI：
10.1145/3372297.3417237
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Rui Wen;Yu Yu-Yu;Xiang Xie;Yang Zhang
中科院分区：
文献类型：
--
作者：
Rui Wen;Yu Yu-Yu;Xiang Xie;Yang Zhang
安全搜索从（可能是云托管的）加密数据库中查找和检索记录，同时确保查询的机密性。近年来，由于人们对数据库隐私的日益关注，安全搜索越来越受到研究人员的关注。然而，安全搜索中的同态运算（特别是乘法运算）效率低下，阻碍了其在实际中的应用。为了解决这个问题，Akavia等人[CCS 2018，PETS 2019]提出了新的协议，将搜索算法中的乘法次数从O（n2）降低到O（n log 2 n），然后降低到O（n log n），其中n是数据库的大小。在本文中，我们提出了第一个安全的搜索协议-- LEAF及其变体LEAF+ --它只需要$O（n）$乘法。具体来说，在LEAF的核心是我们提出的三种新方法，称为定位，提取和重建。此外，LEAF具有低通信复杂度，仅需要客户端执行解密，这增加了其在弱功率设备（如移动的电话）上部署的优势。
Secure search looks for and retrieves records from a (possibly cloud-hosted) encrypted database while ensuring the confidentiality of the queries. Researchers are paying increasing attention to secure search in recent years due to the growing concerns about database privacy. However, the low efficiency of (especially multiplicative) homomorphic operations in secure search has hindered its deployment in practice. To address this issue, Akavia et al. [CCS 2018, PETS 2019] proposed new protocols that bring down the number of multiplications in the search algorithm from O(n2) to O(n log2 n), and then to O(n log n), where n is the size of the database. In this paper, we present the first secure search protocol -- LEAF and its variant LEAF+ -- which only requires $O(n)$ multiplications. Specifically, at the core of LEAF are three novel methods we propose, referred to as Localization, Extraction, and Reconstruction. In addition, LEAF enjoys low communication complexity and only requires the client to perform decryption, which adds its advantage in deployment on weak-power devices such as mobile phones.