In this paper, we propose a new protocol for secure integer comparison which consists of parties having each a private integer. The goal of the computation is to compare both integers securely and reveal to the parties a single bit that tells which integer is larger. Nothing more should be revealed. To achieve a low communication overhead, this can be done by using homomorphic encryption (HE). Our protocol relies on binary decision trees that is a special case of branching programs and can be implemented using HE. We assume a client-server setting where each party holds one of the integers, the client also holds the private key of a homomorphic encryption scheme and the evaluation is done by the server. In this setting, our protocol outperforms the original DGK protocol of Damgård et al. and reduces the running time by at least 45%. In the case where both inputs are encrypted, our scheme reduces the running time of a variant of DGK by 63%.

Order-preserving encryption (OPE) allows encrypting data, while still enabling efficient range queries on the encrypted data. Moreover, it does not require any change to the database management system, which makes OPE schemes very suitable for data outsourcing with threats from weak adversaries. However, all OPE schemes are necessarily symmetric limiting the use case to one client and one server. Imagine a scenario where a Data Owner (DO) outsources encrypted data to the Cloud Service Provider (CSP) and a Data Analyst (DA) wants to execute private range queries on this data. Then either the DO must reveal its encryption key or the DA must reveal the private queries. In this paper, we overcome this limitation by allowing the equivalent of a public-key OPE. We present a secure multiparty protocol that enables secure range queries for multiple users. In this scheme, the DA cooperates with the DO and the CSP in order to order-preserving encrypt the private range queries without revealing any other information to the parties. The basic idea of our scheme is to replace encryption with a secure, interactive protocol. In this protocol, we combine OPE based on binary search trees with homomorphic encryption and garbled circuits (GC) achieving security against passive adversaries with sublinear communication and computation complexity. We apply our construction to different OPE schemes including frequency-hiding OPE and OPE based on an efficiently searchable encrypted data structure which can withstand many of the popularized attacks on OPE. We implemented our scheme and observed that if the database size of the DO has 1 million entries it takes only about 0.3 s on average via a loopback interface (1.3 s via a LAN and 15.6 s via a WAN with about 200 ms round-trip time) to encrypt an input of the DA. Moreover, while the related work has an overhead of 10 to 100 seconds compared to a plaintext MySQL range query on a database with 10 million entries, our scheme has an overhead of only 360 milliseconds.

Abstract Decision trees are widespread machine learning models used for data classification and have many applications in areas such as healthcare, remote diagnostics, spam filtering, etc. In this paper, we address the problem of privately evaluating a decision tree on private data. In this scenario, the server holds a private decision tree model and the client wants to classify its private attribute vector using the server’s private model. The goal is to obtain the classification while preserving the privacy of both – the decision tree and the client input. After the computation, only the classification result is revealed to the client, while nothing is revealed to the server. Many existing protocols require a constant number of rounds. However, some of these protocols perform as many comparisons as there are decision nodes in the entire tree and others transform the whole plaintext decision tree into an oblivious program, resulting in higher communication costs. The main idea of our novel solution is to represent the tree as an array. Then we execute only d – the depth of the tree – comparisons. Each comparison is performed using a small garbled circuit, which output secret-shares of the index of the next node. We get the inputs to the comparison by obliviously indexing the tree and the attribute vector. We implement oblivious array indexing using either garbled circuits, Oblivious Transfer or Oblivious RAM (ORAM). Using ORAM, this results in the first protocol with sub-linear cost in the size of the tree. We implemented and evaluated our solution using the different array indexing procedures mentioned above. As a result, we are not only able to provide the first protocol with sublinear cost for large trees, but also reduce the communication cost for the large real-world data set “Spambase” from 18 MB to 1 [triangleright] 2 MB and the computation time from 17 seconds to less than 1 second in a LAN setting, compared to the best related work.