Welcome to the resource topic for 2025/751
Title:
Improved Range Searching And Range Emptiness Under FHE Using Copy-And-Recurse
Authors: Eyal Kushnir, Hayim Shaul
Abstract:Range counting is the problem of preprocessing a set P\subset R^d of n points, such that given a query range \gamma we can efficiently compute |P\cap\gamma|. In the more general range searching problem the goal is to compute f(P\cap\gamma), for some function f.
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 Range emptiness problem the goal is to compute only whether P\cap\gamma =\emptyset. This was shown (in plaintext) to be done more efficiently.
Range emptiness is interesting on its own and also used as a building block in other algorithms.
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 R^d bounded by hyperplanes then range searching can be done with a circuit of size O(t\cdot n^{1-1/d+\varepsilon}+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 variation we improve range searching in the 1-dimensional case as well as traversal of other trees (e.g., binary trees and B-trees).
Third, we show how to answer range emptiness queries under FHE more efficiently than range counting.
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.
ePrint: https://eprint.iacr.org/2025/751
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .