Fully Homomorphic Encryption (FHE) is a promising solution to enable privacy-preserving inference and training of machine learning models over encrypted data. Among the machine learning methods used in practice, Extreme Gradient Boosting (XGBoost) is one technique that shines in many applications. While previous works have tackled the problem of training tree-based models over FHE, these works either rely on interaction with the client, which adds the extra burden of communication, or consume a typically unreasonable amount of time to train a large model. In this work, we present an efficient system for a non-interactive XGBoost training over FHE that achieves up to 360 imes speedup compared to the state of the art. The argmax operation is a basic building block invoked repeatedly during the XGBoost training as well as other machine learning algorithms, but computing it over FHE is time consuming. When utilizing the Single Instruction Multiple Data (SIMD) parallelism capability offered by most FHE schemes and using a configuration with s slots, the state of the art methods compute argmax on n <= s values using either O(log_2 n) SIMD-comparisons in tournament-style comparison or ceil{n^2 /s} SIMD-comparisons using all pairs comparison. As a second contribution of this work, we propose an efficient argmax algorithm that is based on a novel technique to maximize SIMD-utilization, and computes the argmax of n <= s values using only O(log_2(log_2(n)) SIMD-comparisons. The method extends to n > s with complexity O(n/s) + log_2(log_2(s)), compared to O(n/s) + log_2(s) for state of the art methods. We conduct empirical experiments to compare our method with other existing argmax methods, and show that when using the HEaaN FHE scheme with a configuration of s=2^15 to compute the argmax of n=s values, our implementation is about 1.6 times faster than the state of the art.

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 of 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 queries. It had received a lot of attention in computational geometry where a data structure called partition tree was shown to solve range queries in time sub-linear in |P| using space only linear in |P|. 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 O(t n^{1-1/d+epsilon} + n^{1+epsilon}) operations, where n=|P|, t is the number of operations needed to compare to gamma and epsilon>0 is a parameter. When the ranges are axis-parallel hyper-boxes the running time is O(t n^epsilon + n log^{d-1} n). As far as we know, this is the first non-trivial bound on range searching under FHE and it improves over the naive solution that needs O(t 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 x2.8 and x4.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.

Computation delegation to untrusted third-party while maintaining data confidentiality is possible with homomorphic encryption (HE). However, in many cases, the data was encrypted using another cryptographic scheme such as AES-GCM. Hybrid encryption (a.k.a Transciphering) is a technique that allows moving between cryptosystems, which currently has two main drawbacks: 1) lack of standardization or bad performance of symmetric decryption under FHE; 2) lack of input data integrity.