Improved Range Searching And Range Emptiness Under FHE Using Copy-And-Recurse

{\em Range counting} is the problem of preprocessing a set $P\subset\RR^d$ of $n$ points, such that given a query range $\gamma$ we can efficiently compute $|P\cap\gamma|$. % It was already shown (Kushnir et al. PETS'24) how to efficiently answer a range searching query under FHE using a technique they called Copy-and-Recurse to traverse partition trees. % In the related {\em Range emptiness} problem the goal is to compute only whether $P\cap\gamma =\emptyset$. This was shown (in plaintext) to be more efficient. % % In this paper we improve and extend the results of Kushnir et al. First, for range searching we reduce the overhead term to the optimal $O(n)$, so for example if the ranges are halfspaces in $\RR^d$ bounded by hyperplanes then range searching can be done with a circuit of size $O(t\cdot n^{1-1/d+\eps}+n)$, where $t$ is the size of the sub-circuit that checks whether a point lies under a hyperplane.

Second, we introduce a variation of copy-and-recurse that we call leveled copy-and-recurse. With this we improve traversal of trees such as 1D partition trees and binary trees. Third, we show how to answer range emptiness queries under FHE.

We implemented our algorithms and show that our techniques for range emptiness yield a solution that is $\times 3.6$ faster than the previous results for a database of $2^{25}$ points.