Efficient Privacy Preserving Range Query Using Segment Tree

The range query is a problem to compute a function on a subset of a given data and is used in various real-world setting such that the user inputs a range, and the server computes the function on the range. For many cases using a sensitive data such as a location data, privacy protection is necessary for both query and data. In this study, we propose a secure range query search protocol based on 2-out-of-2 secret sharing. The key idea of our protocol is to generate the input data’s segment tree, which enables the search in O(log N) time and deploy the encrypted tree on the server. By using the encrypted tree, our method enables computing a range query in O(log N) time, communication size, and round of communication after the input of query. We implemented our protocol and a baseline protocol and compared their performances on two network environments. We observed that the search time of our method after the query input is two orders of magnitude faster than the baseline method when the database length is 104, and the time, the communication size, and the round of communication of our method are well concordant with theoretical complexities.