Homomorphic Encryption for Approximate Arithmetic
근사계산을 위한 동형암호 구축에 관한 연구

DC Field Value Language
dc.description학위논문 (박사)-- 서울대학교 대학원 : 자연과학대학 수리과학부, 2018. 2. 천정희.-
dc.description.abstractHomomorphic encryption is a cryptosystem which allows us to perform an arithmetic of encrypted data. The technology of homomorphic encryption has a tremendous possibilities in real world applications based on secure outsourcing of computation on public server. However, previous schemes had a common limitation in approximate arithmetic such as real number operations.

In this paper we suggest a method to construct a homomorphic encryption scheme for approximate arithmetic. It supports an approximate addition and multiplication of encrypted messages, together with a new rescaling procedure for managing the magnitude of plaintext.
The main idea is to add a noise following significant figures which contain a main message. This noise is originally added to the plaintext for security, but considered to be a part of error occurring during approximate computations that is reduced along with plaintext by rescaling. Consequently, the bit size of ciphertext modulus grows linearly with the depth of the circuit being evaluated due to rescaling procedure, compared to an exponentially large size of previous works. We also propose a new batching technique for a RLWE-based construction. A plaintext polynomial will be mapped to a vector of complex numbers via complex canonical embedding map, which is an isometric ring homomorphism. We show that our scheme can be applied to the efficient evaluation of circuits of approximate numbers including transcendental functions such as multiplicative inverse, exponential function, logistic function and discrete Fourier transform.

We extend the leveled homomorphic encryption scheme into a fully homomorphic encryption. Namely, we propose a new technique to refresh low-level ciphertexts based on Gentry's bootstrapping process. The bootstrapping procedure is required to evaluate the decryption formula homomorphically using arithmetic operations over the integers, and the modular reduction becomes the main bottleneck in bootstrapping. We exploit a scaled sine function as an approximation of the modular reduction circuit and present an efficient strategy to evaluate trigonometric functions recursively. Our method requires only two homomorphic multiplications at each iteration and the computation cost grows linearly with the depth of the decryption formula. We also show how to bootstrap packed ciphertexts on RLWE construction with a proof of concept implementation.

We prove the efficiency of our scheme by applying it to real-world applications. Specifically we use our open source homomorphic encryption library to learn a model of logistic regression using biomedical data. We show that our scheme can evaluate the gradient descent method with 20~25 iterations in a few hours.
dc.description.tableofcontents1 Introduction 1
1.1 Homomorphic Encryption for Approximate Arithmetic 3
1.1.1 Packed Ciphertext 4
1.1.2 Evaluation of Circuits 5
1.1.3 Library 5
1.2 Bootstrapping 6
1.2.1 Decryption Formula 6
1.2.2 Results 8
1.2.3 Implications of our bootstrapping method 9
1.3 Machine Learning 10
1.4 List of Papers 11
2 Preliminaries 13
2.1 Notation 13
2.2 The Cyclotomic Ring 13
2.3 Ring Learining with Errors 14
3 Homomorphic Encryption for Arithmetic of Approximate
Numbers 16
3.1 Main Idea 17
3.2 Packing Method 18
3.3 Scheme 20
3.3.1 Description 21
3.3.2 Security 23
3.3.3 Modulus Reduction 23
3.4 Key Switching Technique 24
3.4.1 Rotation 24
3.4.2 Conjugation 25
3.5 Correctness and Analysis 25
3.5.1 Distributions 25
3.5.2 Noise Estimation 26
3.5.3 Tagged Information 28
3.5.4 Relative Error 28
4 Evaluation of Circuits 30
4.1 Polynomial Functions 30
4.2 Approximate Polynomials and Multiplicative Inverse 33
4.3 Fast Fourier Transform 36
4.4 Implementation 38
5 Bootstrapping 43
5.1 Decryption Formula over the Integers 44
5.1.1 Approximation to a Trigonometric Function 44
5.1.2 Evaluation Strategy 46
5.2 Bootstrapping for HEAAN 49
5.2.1 Linear Transformations on Packed Ciphertexts 49
5.2.2 An Overview of Recryption Procedure 50
5.2.3 Estimation of Noise and Complexity 53
5.3 Implementation 55
5.3.1 Optimized Matrix Multiplication 55
5.3.2 Recryption with Sparsely Packed Ciphertexts 56
5.3.3 Experimental Results 57
6 Privacy-Preserving Logistic Regression 60
6.1 Background 61
6.2 Privacy-Preserving Logistic Regression 62
6.2.1 Polynomial Approximation 63
6.2.2 Homomorphic Evaluation of GD Algorithm 64
6.3 Implementation 68
6.3.1 Parameter Setting 68
6.3.2 Technical Details 69
7 Conclusions 73
Abstract (in Korean) 84
dc.format.extent3903487 bytes-
dc.publisher서울대학교 대학원-
dc.subjectApproximate Arithmetic-
dc.subjectLogistic Regression-
dc.subjectHomomorphic Encryption-
dc.titleHomomorphic Encryption for Approximate Arithmetic-
dc.title.alternative근사계산을 위한 동형암호 구축에 관한 연구-
dc.contributor.AlternativeAuthorYongsoo Song-
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.