Compressed Oblivious Encoding for Homomorphically Encrypted Search
Compressed Oblivious Encoding for Homomorphically Encrypted Search
复制标题
DOI：
10.1145/3460120.3484792
复制
发表时间：
2021-09
期刊：
影响因子：
--
通讯作者：
Seung Geol Choi;Dana Dachman-Soled;S. D. Gordon;Linsheng Liu;Arkady Yerukhimovich
中科院分区：
文献类型：
--
作者：
Seung Geol Choi;Dana Dachman-Soled;S. D. Gordon;Linsheng Liu;Arkady Yerukhimovich
全同态加密（FHE）为安全搜索提供了一个简单而有吸引力的框架。与其他安全搜索系统相比，不需要昂贵的设置过程;客户端只需将加密的数据库上传到服务器就足够了。提供机密性是因为服务器只对加密的查询和记录进行操作。而搜索功能由加密方案的完全同态来实现。因此，这一问题越来越受到研究者的关注。自从Akavia等人（CCS 2018）提出了一个在FHE加密数据上进行安全搜索的框架，并给出了一个名为SPiRiT的工作实现以来，已经提出了几种更有效的实现。在本文中，我们确定了这个框架的主要瓶颈，并展示了如何显着提高性能的FHE为基础的安全搜索。特别是，为了检索l个匹配项，现有框架需要顺序地重复协议l次。在我们的新框架中，所有匹配项都在单个协议执行中并行检索。Wren等人的最新工作（CCS 2020）需要O（n）乘法来计算第一个匹配索引。我们的解决方案不需要同态乘法，而是只使用加法和标量乘法来编码所有匹配的索引。我们的实现和实验表明，获取16个匹配的记录，我们的系统提供了一个1800倍的速度比最先进的在获取查询结果，导致在一个26倍的速度为完整的搜索功能。
Fully homomorphic encryption (FHE) enables a simple, attractive framework for secure search. Compared to other secure search systems, no costly setup procedure is necessary; it is sufficient for the client merely to upload the encrypted database to the server. Confidentiality is provided because the server works only on the encrypted query and records. While the search functionality is enabled by the full homomorphism of the encryption scheme. For this reason, researchers have been paying increasing attention to this problem. Since Akavia et al. (CCS 2018) presented a framework for secure search on FHE encrypted data and gave a working implementation called SPiRiT, several more efficient realizations have been proposed. In this paper, we identify the main bottlenecks of this framework and show how to significantly improve the performance of FHE-base secure search. In particular, To retrieve l matching items, the existing framework needs to repeat the protocol l times sequentially. In our new framework, all matching items are retrieved in parallel in a single protocol execution. The most recent work by Wren et al. (CCS 2020) requires O(n) multiplications to compute the first matching index. Our solution requires no homomorphic multiplication, instead using only additions and scalar multiplications to encode all matching indices. Our implementation and experiments show that to fetch 16 matching records, our system gives an 1800X speed-up over the state of the art in fetching the query results resulting in a 26X speed-up for the full search functionality.