{\em Range searching} is the problem of preprocessing a set of points , such that given a query range we can efficiently compute some function . For example, in a 1 dimensional {\em range counting} query, is a set of numbers, is a segment and we need to count how many numbers of are in .
In higher dimensions, is a set of dimensional points and the query range is some volume in . In general, we want to compute more than just counting, for example, the average of .
Range searching has applications in databases where some SELECT queries can be translated to range queries.
It had received a lot of attention in computational geometry where a data structure called {\em partition tree} was shown to solve range queries in time sub-linear in using space only linear in .
In this paper we consider partition trees under FHE 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 operations, where , is the number of operations needed to compare to and is a parameter. As far as we know, this is the first non-trivial bound on range searching under FHE and it improves over the na\"ive solution that needs 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 and , our algorithms run and (respectively) faster than the na\"ive algorithm.
The improvement of our algorithm comes from a method we call copy-and-recurse. With it we efficiently traverse a -ary tree (where each inner node has children) that also has the property that at most 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.
@misc{cryptoeprint:2023/983,
author = {Eyal Kushnir and Guy Moshkowich and Hayim Shaul},
title = {Secure Range-Searching Using Copy-And-Recurse},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/983},
year = {2023},
url = {https://eprint.iacr.org/2023/983}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.