Efficient Fully Homomorphic Encryption over the Integers
효율적인 정수 기반 동형 암호

DC Field Value Language
dc.description학위논문 (박사)-- 서울대학교 대학원 : 수리과학부, 2015. 2. 천정희.-
dc.description.abstractFully homomorphic encryption allows a worker to perform additions and multiplications on encrypted plaintext values without decryption. The first construction of a fully homomorphic scheme (FHE) based on ideal lattices was described by Gentry in 2009. Since Gentry's breakthrough result, many improvements have been made, introducing new variants, improving efficiency, and providing new features.

The most FHE schemes still have very large ciphertexts (millions of bits for a single ciphertext). This presents a considerable bottleneck in practical deployments.
To improve the efficiency of FHE schemes, especially ciphertext size, we can consider the following two observations. One is to improve the ratio of plaintext and ciphertext by packing many messages in one ciphertext and the other is to reduce the size of FHE-ciphertext by combining FHE with existing public-key encryption.

In the dissertation, we study on construction of efficient FHE over the integers.
First, we propose a new variant DGHV fully homomorphic encryption to extend message space. Using Chinese remainder theorem, our scheme reduces the overheads (ratio of ciphertext computation and plaintext computation) from $\tilde{O}(\lambda^4)$ to $\tilde{O}(\lambda)$. We reduce the security of our Somewhat Homomorphic Encryption scheme to a decisional version of Approximate GCD problem (DACD).

To reduce the ciphertext size, we propose a hybrid scheme that combines public key encryption (PKE) and somewhat homomorphic encryption (SHE). In this model, messages are encrypted with a PKE and computations on encrypted data are carried out using SHE or FHE after homomorphic decryption. Our approach is suitable for cloud computing environments since it has small bandwidth, low storage requirement, and supports efficient computing on encrypted data.

We also give alternative approach to reduce the FHE ciphertext size.
Some of recent SHE schemes possess two properties, the public key compression and the key switching. By combining them, we propose a hybrid encryption scheme in which a block of messages is encrypted by symmetric version of the SHE and its secret key is encrypted by the (asymmetric) SHE. The ciphertext under the symmetric key encryption is compressed by using the public key compression technique and we convert the ciphertext into asymmetric encryption to enable homomorphic computations using key switching technique.
1 Introduction 1
1.1 A Brief Overview of this Thesis 3
2 CRT-based FHE over the Integers 8
2.1 Preliminaries 12
2.2 Our Somewhat Homomorphic Encryption Scheme 14
2.2.1 Parameters 14
2.2.2 The Construction 15
2.2.3 Correctness 17
2.3 Security 19
2.4 FullyHomomorphicEncryption 27
2.4.1 BitMessageSpace 28
2.4.2 LargeMessageSpace 29
2.5 Discussion 35
2.5.1 SecureLargeIntegerArithmetic 35
2.5.2 Public key compression 35
3 A Hybrid Scheme of PKE and SHE 37
3.1 Preliminaries 39
3.1.1 HardProblems 40
3.1.2 Homomorphic Encryption Schemes 41
3.2 Encrypt with PKE and Compute with SHE 43
3.2.1 A Hybrid Scheme of PKE and SHE 44
3.2.2 Additive Homomorphic Encryptions for PKE in the HybridScheme 48
3.2.3 Multiplicative Homomorphic Encryptions for PKE in theHybridScheme 51
3.3 Homomorphic Evaluation of Exponentiation 56
3.3.1 Improved Exponentiation using Vector Decomposition 56
3.3.2 Improve the Bootstrapping without Squashing 59
3.4 Discussions 62
3.4.1 ApplicationModel 62
3.4.2 Advantages 63
3.5 Generic Conversion of SHE from Private-Key to Public-Key 68
4 A Hybrid Asymmetric Homomorphic Encryption 70
4.1 Preliminaries 72
4.2 A Hybrid Approach to Asymmetric FHE with Compressed Ciphertext 73
4.2.1 MainTools 73
4.2.2 Hybrid Encryption with Compressed Ciphertexts 76
4.3 ConcreteHybridConstructions 77
4.3.1 Hybrid Encryptions based on DGHV and Its Variants 77
4.3.2 Hybrid Encryptions based on LWE 87
4.4 Discussion 93
4.4.1 Comparison to Other Approaches 93
4.4.2 Other Fully Homomorphic Encryptions 94
5 Conclusion 95
Abstract (in Korean) 105
Acknowledgement (in Korean) 106
dc.format.extent3745621 bytes-
dc.publisher서울대학교 대학원-
dc.subjectfully homomorphic encryption-
dc.subjectsomewhat homomorphic encryption-
dc.subjecthybrid scheme-
dc.subjectapproximate GCD problem-
dc.titleEfficient Fully Homomorphic Encryption over the Integers-
dc.title.alternative효율적인 정수 기반 동형 암호-
dc.contributor.AlternativeAuthorJinsu Kim-
dc.contributor.affiliation자연과학대학 수리과학부-
Appears in Collections:
College of Natural Sciences (자연과학대학)Dept. of Mathematical Sciences (수리과학부)Theses (Ph.D. / Sc.D._수리과학부)
Files in This Item:
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.