International Association
for Cryptologic Research

Range searching is the problem of preprocessing a set of points $P$, such that given a query range $\gamma$ we can efficiently compute some function $f(P\cap\gamma)$. For example, in a 1 dimensional range counting query, $P$ is a set of numbers, $\gamma$ is a segment and we need to count how many numbers in $P$ are in $\gamma$. In higher dimensions, $P$ is a set of $d$ dimensional points and the query range is some volume in $R^d$. In general, we want to compute more than just counting, for example, the average of $P\cap\gamma$. Range searching has applications in databases where some SELECT queries can be translated to range searches. It had received a lot of attention in computational geometry where a data structure called partition tree was shown to solve range searching in time sub-linear in $|P|$ using only space linear in $|P|$.

In this paper we consider partition trees in a secure setting where we answer range queries without learning the value of the points or the parameters of the range. We show how partition trees can be securely traversed with $O(n^{1+\epsilon} + t \cdot n^{1-\frac{1}{d}+\epsilon})$ operations, where $n=|P|$, $t$ is the number of operations needed to compare to $\gamma$ and $\epsilon>0$ is a parameter. As far as we know, this is the first non-trivial bound on range searching and it improves over the na\"ive solution that needs $O(t\cdot n)$ operations.

Our algorithms are independent of the encryption scheme but as an example we implemented them using the CKKS FHE scheme. Our experiments show that for databases of sizes $2^{23}$ and $2^{25}$, our algorithms run $\times 2.8$ and $\times 4.7$ (respectively) faster than the naive algorithm.

The improvement of our algorithm comes from a method we call copy-and-recurse. With it we efficiently traverse a $r$-ary tree (where each inner node has $r$ children) that also has the property that at most $\xi$ of them need to be recursed into when traversing the tree. We believe this method is interesting in its own and can be used to improve traversals in other tree-like structures.