We propose how to homomorphically evaluate arbitrary univariate and 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 schemes, and is implemented with the input domain ℤ257. However, the scheme of Okada et al. requires the quadratic numbers 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., ℤ215 in a reasonably efficient way. In addition, we show how to slightly extend the input domain size to ℤ216 with a relatively moderate overhead. Further we show another approach to handling the larger input domain size by using two ciphertexts to encrypt one integer plaintext and applying our techniques for uni/bivariate function evaluation. We implement the prior work of Okada et al., our improved version of Okada et al., and our new scheme in PALISADE with the input domain ℤ215, and confirm that the estimated run-times of the prior work and our improved version of the prior work are still about 117 days and 59 days respectively while our new scheme can be computed in 307 seconds.

Fully homomorphic encryption (FHE) enables secret computations. Users can perform computation using data encrypted with FHE without decryption. Uploading private data without encryption to a public cloud has the risk of data leakage, which makes many users hesitant to utilize a public cloud. Uploading data encrypted with FHE avoids this risk, while still providing the computing power of the public cloud. In many cases, data are stored in HDDs because the data size increases significantly when FHE is used. One important data analysis is Apriori data mining. In this application, two files are accessed alternately, and this causes long-distance seeking on its HDD and low performance. In this paper, we propose a new striping layout with reservations for write areas. This method intentionally fragments files and arranges blocks to reduce the distance between blocks in a file and another file. It reserves the area for intermediate files of FHE Apriori. The performance of the proposed method was evaluated based on the I/O processing of a large FHE Apriori, and the results showed that the proposed method could improve performance by up to approximately 28%.

In this paper, we propose the first private decision tree evaluation (PDTE) schemes which are suitable for use in Machine Learning as a Service (MLaaS) scenarios. In our schemes, a user and a model owner send the ciphertexts of a sample and a decision tree model, respectively, and a single server classifies the sample without knowing the sample nor the decision tree. Although many PDTE schemes have been proposed so far, most of them require to reveal the decision tree to the server. This is undesirable because the classification model is the intellectual property of the model owner, and/or it may include sensitive information used to train the model, and therefore the model also should be hidden from the server. In other PDTE schemes, multiple servers jointly conduct the classification process and the decision tree is kept secret from the servers under the assumption they do not collude. Unfortunately, this assumption may not hold because MLaaS is usually provided by a single company. In contrast, our schemes do not have such problems. In principle, fully homomorphic encryption allows us to classify an encrypted sample based on an encrypted decision tree, and in fact, the existing non-interactive PDTE scheme can be modified so that the server classifies only handling ciphertexts. However, the resulting scheme is less efficient than ours. We also show the experimental results for our schemes.

A fully homomorphic encryption (FHE) would be the important cryptosystem as the basic scheme for the cloud computing. Since Gentry discovered in 2009 the first fully homomorphic encryption scheme, some fully homomorphic encryption schemes were proposed. In the systems proposed until now the bootstrapping process is the main bottleneck and the large complexity for computing the ciphertext is required. In 2011 Zvika Brakerski et al. proposed a leveled FHE without bootstrapping. But circuit of arbitrary level cannot be evaluated in their scheme while in our scheme circuit of any level can be evaluated. The existence of an efficient fully homomorphic cryptosystem would have great practical implications in the outsourcing of private computations, for instance, in the field of the cloud computing. In this paper, IND-CCA1secure FHE based on the difficulty of prime factorization is proposed which does not need the bootstrapping and it is thought that our scheme is more efficient than the previous schemes. In particular the computational overhead for homomorphic evaluation is O(1).

In this paper, we propose the decomposition ring homomorphic encryption scheme, that is a homomorphic encryption scheme built on the decomposition ring, which is a subring of cyclotomic ring. By using the decomposition ring the structure of plaintext slot becomes ℤpl, instead of GF(pd) in conventional schemes on the cyclotomic ring. For homomorphic multiplication of integers, one can use the full of ℤpl slots using the proposed scheme, although in conventional schemes one can use only one-dimensional subspace GF(p) in each GF(pd) slot. This allows us to realize fast and compact homomorphic encryption for integer plaintexts. In fact, our benchmark results indicate that our decomposition ring homomorphic encryption schemes are several times faster than HElib for integer plaintexts due to its higher parallel computation.

With the flourish of applications based on the Internet of Things (IoT), privacy issues have been attracting a lot of attentions. Although the concept of privacy homomorphism was proposed along with the birth of the well-known RSA cryptosystems, cryptographers over the world have spent about three decades for finding the first implementation of the so-called fully homomorphic encryption (FHE). Despite of, currently known FHE schemes, including the original Gentry's scheme and many subsequent improvements as well as the other alternatives, are not appropriate for IoT-oriented applications because most of them suffer from the problems of inefficient key size and noisy restraining. In addition, for providing fully support to IoT-oriented applications, symmetric fully homomorphic encryptions are also highly desirable. This survey presents an analysis on the challenges of designing secure and practical FHE for IoT, from the perspectives of lightweight requirements as well as the security requirements. In particular, some issues about designing noise-free FHE schemes would be addressed.

In this paper, we present a faster (wall-clock time) sorting method for numerical data subjected to fully homomorphic encryption (FHE). Owing to circuit-based construction and the FHE security property, most existing sorting methods cannot be applied to encrypted data without significantly compromising efficiency. The proposed algorithm utilizes the cryptographic single-instruction multiple-data (SIMD) operation, which is supported by most existing FHE algorithms, to reduce the computational overhead. We conducted a careful analysis of the number of required recryption operations, which are the computationally dominant operations in FHE. Accordingly, we verified that the proposed SIMD-based sorting algorithm completes the given task more quickly than existing sorting methods if the number of data items and (or) the maximum bit length of each data item exceed specific thresholds.

We construct the first fully homomorphic encryption (FHE) scheme that encrypts matrices and supports homomorphic matrix addition and multiplication. This is a natural extension of packed FHE and thus supports more complicated homomorphic operations. We optimize the bootstrapping procedure of Alperin-Sheriff and Peikert (CRYPTO 2014) by applying our scheme. Our optimization decreases the lattice approximation factor from Õ(n3) to Õ(n2.5). By taking a lattice dimension as a larger polynomial in a security parameter, we can also obtain the same approximation factor as the best known one of standard lattice-based public-key encryption without successive dimension-modulus reduction, which was essential for achieving the best factor in prior works on bootstrapping of standard lattice-based FHE.