Year

2014

Degree Name

Doctor of Philosophy

Department

School of Computer Science and Software Engineering

Abstract

Lattice-based cryptography plays an important role in modern cryptography. Apart from being a perfect alternative of classic public key cryptosystems, should the quantum computers become available, the lattice-based cryptography also enables many applications that conventional cryptosystems, such as RSA encryption scheme, can not deliver. One of the most significant aspects from this point of view is the fully homomorphic encryption schemes.

A fully homomorphic encryption scheme allows one to arbitrarily operate on the encrypted messages, without decrypting it. This notion was raised in 1978, and it becomes a "holy grail" for the cryptographers for 30 years until 2009, Craig Gentry presented a framework to construct a fully homomorphic encryption using ideal lattice. The fully homomorphic encryption schemes, although they may be lacking of efficiency at its current stage, enable many important applications, such as secured cloud searching verifiable outsourced computing. Nevertheless, just like other cryptosystems, and perhaps all other inventions at the initial stage, the fully homomorphic encryption is young, prospective, and hence requires more research.

In this thesis, we focus on the security of fully homomorphic encryption schemes. The security of all known fully homomorphic encryption schemes can be reduced to some lattice problems. Therefore, our main tool, not surprisingly, is lattice. Previous work has shown that some of the fully homomorphic encryption schemes can be broken using lattice reduction algorithms. Indeed, there exist several lattice reduction algorithms, such as LLL and L2, that run in polynomial time, that can break a homomorphic encryption scheme. However, the running time, even though it is a polynomial algorithm, is still beyond tolerance. Hence, our first step is to optimize those algorithms. In this thesis, we show three different improvements. To sum up, combining those techniques, we are able to accelerate the reduction form O(d4+εβ2 + d5+εβ) to O(d2+εβ2+ d4+εβ) when the algorithm is dedicated for those cryptosystems, where d is the dimension of the lattice, and β is the maximum bit-length of the norm of input vectors. In practice, those techniques accelerate the reduction for approximately 10 times for moderate lattices, and when it is applied over the fully homomorphic encryption challenge, we can solve the challenge within 15.7 years, while the previous best result was 45 years.

We also analyzed the security of the fully homomorphic encryption scheme using integers under the chosen ciphertext attack model. The chosen ciphertext attack model is one of the classic security models as far as an encryption scheme is concerned. Indeed, we present a chosen ciphertext attack that breaks the security of the scheme. Further, in theory, the chosen ciphertext attack relies on the existence of a decryption oracle that might not always exist in practice. In this thesis, we also show that a decryption oracle can be constructed via a reaction attack for all fully homomorphic encryption schemes that are used in an outsourcing computing environment.

The last component of this thesis is a new fully homomorphic encryption scheme. To construct this scheme, we propose the notion of hidden lattices. We show that several hidden lattice problems, which are to be used in a fully homomorphic encryption scheme, are more difficult than the corresponding problems over a normal lattices. Hence, we base our scheme on a problem that is harder than all problems that existing fully homomorphic encryption schemes are based on. Since our problem is substantially harder to solve, our scheme can operate with smaller parameters, and hence be more efficient, compared to state-of-art ideal lattice based fully homomorphic encryption schemes.

Download

Share

COinS
 

Unless otherwise indicated, the views expressed in this thesis are those of the author and do not necessarily represent the views of the University of Wollongong.