October 27, 2021


Dedicated Forum to help removing adware, malware, spyware, ransomware, trojans, viruses and more!

Compressed Oblivious Encoding for Homomorphically Encrypted Search, by Seung Geol Choi and Dana Dachman-Soled and S. Dov Gordon and Linsheng Liu and Arkady Yerukhimovich

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

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.