Abstract Fully homomorphic encryption (FHE) allows to compute any function on encrypted values. However, in practice, there is no universal FHE scheme that is effi-cient in all possible use cases. In this work, we show that FHE schemes suitable for arithmetic circuits (e.g. BGV or BFV) have a similar performance as FHE schemes for non-arithmetic circuits (TFHE) in basic comparison tasks such as less-than, maximum and minimum operations. Our implementation of the less-than function in the HElib library is up to 3 times faster than the prior work based on BGV/BFV. It allows to compare a pair of 64-bit integers in 11 milliseconds, sort 64 32-bit integers in 19 seconds and find the minimum of 64 32-bit integers in 9.5 seconds on an average laptop without multi-threading.

State-of-the-art implementations of homomorphic encryption exploit the Fan and Vercauteren (FV) scheme and the Residue Number System (RNS). While the RNS breaks down large integer arithmetic into smaller independent channels, its non-positional nature makes operations such as division and rounding hard to implement, and makes the representation of small values inefficient. In this work, we propose the application of the Hybrid Position-Residues Number System representation to the FV scheme. This is a positional representation of large radix where the digits are represented in RNS. It inherits the benefits from RNS and allows to accelerate the critical division and rounding operations while also making the representation of smaller values more compact. This directly benefits the decryption and the homomorphic multiplication procedures, reducing their asymptotic complexity, in dimension n, from O(n2log n) to O(n log n) and from O(n3log n) to O(n3), respectively and has resulted in noticeable speedups when experimentally compared to related art RNS implementations.

In an ever more data-centric economy, machine learning models have risen in importance. With the large amounts of data companies collect, they are able to develop highly accurate models to predict the behaviours of their customers. It is thus important to safeguard the data used to build these models to prevent competitors from mimicking their services. In addition, as this type of techniques finds its way into areas that need to deal with more sensitive information, like the medical industry, the privacy of the data that needs to be classified also has to be ensured. Herein, this topic is addressed by homomorphically evaluating Support Vector Machine (SVM) models, in a way that guarantees that a client learns nothing about the model except for the classification of his data, and that the service provider learns nothing about the data. Whereas, previously, Fully Homomorphic Encryption (FHE) has mostly focused on either bit-wise or value-wise computations, SVMs present an additional challenge since they combine both: during an initial phase a kernel function is evaluated that makes use of real arithmetic, and during a second phase the sign bit has to be extracted. Novel techniques are herein proposed that allow for speedups of up to 2.7 and 6.6 for the evaluation of polynomials and the determination of sign, respectively, in comparison to the state of the art. Finally, it is shown that the proposed techniques do not deteriorate the classification accuracy of the SVM models.