Research On Related Algorithms Of Fully Homomorphic Encryption

With the development of network technology, cloud computing and delegating computing have been widely used in our life. These computing models greatly enhance the data processing capabilities, and effectively reducing the customer’s investment in the information infrastructure. To complete the data processing tasks, individuals should delegate their own data to the cloud service provider/server. In addition to storage, the cloud is expected to manipulate and process the data per the user’s requests, since local processing on the end user’s device is infeasible. This allows for great flexibility in the use of data, but also means new challenges for data privacy. To answer these challenges, we need to construct new tools to our cryptographic toolbox.As an effective solution to protect the privacy of the data, fully homomorphic encryption has become a hotspot field in cryptography research. Roughly speaking, fully homomorphic encryption is an encryption scheme, in which, a party can efficiently receive ciphertexts and perform arbitrary operations on this data. Although the ciphertexts remain encrypted throughout, the operations can be done without having to know the decryption key. Such a scheme is of advantages, especially in ensuring the privacy of data that is sent to a entrust party. Fully homomorphic encryption is a natural solution to ensure the security of cloud computing and delegating computing. Unfortunately, existing schemes are not truly practical due to their high computational complexity and huge key size. How to construct the efficient fully homomorphic encryption scheme with short key size is an interesting problem excepting to solve.In this thesis, the authors present three results that push the state of the art for fully homomorphic encryption in the face of practical challenges. The main contributions of this thesis are described as follows:1. Improved key generation algorithm. First, in previous Gentry-style fully homomorphic encryption, the key generation algorithm should be repeated until the scheme can handle the desired bound of the evaluation circuit depth. Furthermore, it is note that the complexity of selecting a suitable module is too high. In Chapter 3, the authors address this problem by proposing an improved key generation algorithm. Based on Gershgorin circle theorem, the proposed strategy for solving the problem is to take a basis where the size of the eigenvalues for which are ensured instead of selecting randomly a module, and then construct a primary basis with the selected eigenvalues. Compared with previous works, the proposed key generation algorithm enables us to create a more practical somewhat homomorphic encryption scheme. Furthermore, the SVP is one of the two challenges underlying the security of Gentry-style fully homomorphic encryption scheme. In the security analysis of their scheme, the authors informally described the known complexity bound for the approximate SVP in lattices, but without any in-depth analysis of the security issues. The authors give a more aggressive security analysis of the approximate SVP against lattice attacks, compared to the roughly analysis given in previous work. The new analysis of SVP takes into account the complexity of approximate SVP in detail. In the end, the authors describe an implementation of Gentry-style somewhat homomorphic encryption scheme.2. In charpter 4, the authors propose an efficent somewhat homomorphic encryption scheme whose security is based solely on the hardness of learning divisor with noise (LDN). The construction proceeds by three steps:firstly, the authors describe a private key somewhat homomorphic encryption scheme; Secondly, the authos propose a technique that can refresh the rough ciphertext and gets a new ciphertext with smaller noise. Thirdly, the private key homomorphic encryption scheme is transferred to its public key version. Compared with previous works, the construction only use elementary modular arithmetic over the integers rather than working with ideal lattices. And it is simpler in pedagogical and theoretical.The main contributions of proposed scheme are the small key size and ciphertext size.3. Coron et al. proposed a batch homomorphic encryption scheme, i.e. a scheme that supports encrypting and homomorphically evaluating several plaintext bits as a single ciphertext. Based on china remainder theorem, the authors propose a multi-integer somewhat homomorphic encryption scheme. It can be regarded as a generalization of Coron’s scheme (CLT13 scheme) with larger message space. Furthermore, the authors put forward a new hardness problem, which is called the random approximation greatest common divisor (RAGCD). The authors prove that RAGCD problem is a stronger version of approximation greatest common divisor (AGCD) problem. Our variant remains semantically secure under RAGCD problem. The estimates are backed up with experiment data. It is expected that, the proposed scheme makes the encrypted data processing practical for suitable applications.