You are looking at a specific version 20210917:091553 of this paper. See the latest version.

Paper 2021/1199

Compressed Oblivious Encoding for Homomorphically Encrypted Search

Seung Geol Choi and Dana Dachman-Soled and S. Dov Gordon and Linsheng Liu and Arkady Yerukhimovich

Abstract

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, 1. To retrieve $\ell$ matching items, the existing framework needs to repeat the protocol $\ell$ times sequentially. In our new framework, all matching items are retrieved in parallel in a single protocol execution. 2. 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. 3. 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. ACM CCS2021
Keywords
secure searchencrypted databasefully homomorphic encryption
Contact author(s)
arkady @ gwu edu
History
2021-09-17: received
Short URL
https://ia.cr/2021/1199
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.