All known instantiations for fully homomorphic encryption (FHE) produce noisy ciphertexts and rely on a technique called bootstrapping to reduce the noise so as to enable an arbitrary number of homomorphic operations. Bootstrapping is the main performance bottleneck and arguably the biggest obstacle to widespread adoption of FHE. Among the FHE schemes, TFHE and its variations present the appealing property of having a bootstrapping procedure---as well as its extension to programmable bootstrapping---that is relatively light-weight. The essential operations consist of a series of multiplications in (Z/qZ)[X]/(X^N+1). While the NTT is seemingly the natural candidate for evaluating these multiplications in a fast and exact way, it restricts the possible choices for and . To the authors' knowledge, all current implementations of TFHE with a power of two actually employ the FFT over the complex numbers instead. This introduces real numbers to the otherwise purely discrete algorithms, including all the drawbacks of the need to approximate them using finite precision. This work studies the avenues available to apply the NTT in the context of TFHE-like schemes. In particular, it considers various combinations of coefficient rings and quotient polynomials that are compatible with the requirements of the underlying scheme. Importantly, this work provides methods for adapting the (programmable) bootstrapping to quotient polynomials beyond power-of-two cyclotomics. As a side effect, it also demonstrates how this may enhance the programmability of the bootstrapping.

We propose how to homomorphically evaluate arbitrary bivariate integer functions such as division. A prior work proposed by Okada et al.\ (WISTP'18) uses polynomial evaluations such that the scheme is still compatible with the SIMD operations in BFV and BGV, and is implemented with the input domain size \mathbbZ _257 . However, the scheme of Okada et al.\ requires the quadratic number of plaintext-ciphertext multiplications and ciphertext-ciphertext additions in the input domain size, and although these operations are more lightweight than the ciphertext-ciphertext multiplication, the quadratic complexity makes handling larger inputs quite inefficient. In this work, first we improve the prior work and also propose a new approach that exploits the packing method to handle the larger input domain size instead of enabling the SIMD operation, thus making it possible to work with the larger input domain size, e.g., \mathbbZ _2^15 in a reasonably efficient way. In addition, we show how to extend the input domain size to \mathbbZ _2^16 with a relatively moderate overhead. We implement the prior work of Okada et al., our improved scheme of Okada et al., and our new scheme in PALISADE with the input domain size \mathbbZ _2^15 , and confirm that the estimated run-times of the prior work and our improved scheme of the prior work are still about 117 days and 59 days respectively while our new scheme can be computed in 307 seconds.

Decision trees are among the most widespread machine learning models used for data classification, in particular due to their interpretability that makes it easy to explain their prediction. In this paper, we propose a novel protocol for the private classification of a client request in a non-interactive manner. In contrast to existing solutions to this problem, which are either interactive or require evaluating all the branches of the decision tree, our approach only evaluates a single branch of the tree. Our protocol is based on two primitives that we also introduce in this paper and that may be of independent interest : Blind Node Selection and Blind Array Access. Those contributions are based on recent advances in homomorphic cryptography, such as the functional bootstrapping mechanism recently proposed for the Fully Homomorphic Encryption over the Torus scheme TFHE. Our private decision tree evaluation algorithm is highly efficient as it requires only one round of communication and d comparisons, with d being the depth of the tree, while other state-of-the-art non-interactive protocols need 2^d comparisons.

We design and implement a new efficient and accurate fully homomorphic argmin/min or argmax/max comparison operator, which finds its application in numerous real-world use cases as a classifier. In particular we propose two versions of our algorithms using different tools from TFHE's functional bootstrapping toolkit. Our algorithm scales to any number of input data points with linear time complexity and logarithmic noise-propagation. Our algorithm is the fastest on the market for non-parallel comparisons with a high degree of accuracy and precision. For MNIST and SVHN datasets, which work under the PATE framework, using our algorithm, we achieve an accuracy of around 99.95% for both.

More and more data analysis is being outsourced due to the spread of cloud computing. Therefore, protection of the data from privacy violations and information leaks is required. In particular, homomorphic encryption, which allows computation to be performed with encrypted data, is being actively studied as one of the protection method. Ring learning with errors based homomorphic encryption schemes support packing which allows to pack several elements into slots of a plaintext and ciphertext. A trace-type function, which combines shifting slots (rotation) and homomorphic addition to obtain summation of slots, is often used in homomorphic encryption applications and acceleration of the trace-type function is important. In this paper, we further accelerate the trace-type function using Intel AVX512 compared to existing optimized trace-type function with loop unrolling. The results show that our AVX512 version was 1.05-2.30 times speedup compared to the non-AVX512 version.

Fully Homomorphic Encryption (FHE) is a powerful cryptographic primitive that enables performing computations over encrypted data without having access to the secret key. We introduce OpenFHE, a new open-source FHE software library that incorporates selected design ideas from prior FHE projects, such as PALISADE, HElib, and HEAAN, and includes several new design concepts and ideas. The main new design features can be summarized as follows: (1) we assume from the very beginning that all implemented FHE schemes will support bootstrapping and scheme switching; (2) OpenFHE supports multiple hardware acceleration backends using a standard Hardware Abstraction Layer (HAL); (3) OpenFHE includes both user-friendly modes, where all maintenance operations, such as modulus switching, key switching, and bootstrapping, are automatically invoked by the library, and compiler-friendly modes, where an external compiler makes these decisions. This paper focuses on high-level description of OpenFHE design, and the reader is pointed to external OpenFHE references for a more detailed/technical description of the software library.