  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.
