Secure Computation via Homomorphic Encryption

Abstract

(Fully) Homomorphic encryption (FHE, HE) is one of the natural and powerful tools for ensuring privacy of sensitive data since it enables to handle ciphertexts without decryption and thus allow complicated computations on the encrypted data. Due to this property, homomorphic encryption can be applied to many scenarios in the real life, especially, databases. Until now, most of homomorphic encryption schemes restrict a plaintext space as an integer and thus numeric data should be represented by integers. However, there are many applications working in the real number system that operate on very sensitive information, for example, user's location information and patient's medical information. Usually, these information can be represented by the real numbers and thus it should be encoded into the integers. The general decimal representation requires \emph{quite large} plaintext space and a polynomial representation also requires a \emph{higher degree} of polynomials, which has a bad influence to the performance of FHE scheme.

In this thesis, we employ continued fraction to represent real numbers and to alleviate this inefficiency. With continued fraction, real numbers can be represented by a set of \emph{quite small} integers and it makes performance improvement than other encoding techniques. Moreover, we can develop a set of algorithms and circuits using continued fraction for the following operations: homomorphic integer division, equality circuit and comparison circuits over the real numbers.

First, we suggest an algorithm for homomorphic integer division using continued fraction and restoring division algorithm. Since the integer is not closed under the division, the most of homomorphic encryption schemes cannot support the division, however, we suggest a transformation from rational numbers to continued fractions being encrypted and it allows to divide two encrypted integers. Further, we can evaluate a polynomial whose coefficients are in the rational numbers.

Second, we describe comparison circuits over the encrypted real numbers including equality circuits. Since comparing two continued fraction is also easy as much as comparing two decimal numbers, we can build \emph{more efficient} comparison circuits while maintaining the small message space utilizing the homomorphic comparison circuits over the integers. With our efficient comparison circuits, we can apply to the real-type database which indicates each numeric data is represented by the real numbers and our circuits enable to sorting and private database queries such as retrieval queries and aggregate queries, which makes database useful.

Finally, we present a proof of correct decryption in a single party homomorphic encryption. Although a server evaluates some polynomial being encrypted, the server cannot know any information about the result. Thus, if a server is interested in the result, a data owner returns the decryption result. The problem is that the server should believe the data owner at this time because the data owner can manipulate the decryption result and the server cannot recognize it. We prevent this situation by utilizing one-time message authentication code. Moreover, this technique can be applied to many scenarios, especially, a protocol for authentication of biometrics.