Title Page
Abstract
Contents
Chapter 1. Introduction 10
1.1. Contributions and Results 13
1.2. Included Publications 16
Chapter 2. Preliminaries 17
2.1. Notations and Terminologies 17
2.2. Factorization of Cyclotomic Polynomials 18
2.2.1. Factorization of ΦM(x) in Zₚₖ[x][이미지참조] 18
2.2.2. Irreducibility of Φ₂ₘ(x) in Z₂ₖ[x] 19
2.3. RMFE 20
Chapter 3. Definitions and Basic Concepts 22
3.1. Homomorphic Packing 22
3.2. Properties of Homomorphic Packing 25
3.2.1. Packing Density 25
3.2.2. Level-Consistency 26
3.2.3. Surjectivity 27
3.3. Decomposition Lemmas 28
Chapter 4. Constructions 33
4.1. Previous Constructions 33
4.1.1. HElib Packing 33
4.1.2. Overdrive2k Packing 34
4.1.3. Notes on Overdrive2k Packing 35
4.2. New Packing Method for Z₂ₖ-Messages 37
4.2.1. Tweaked Interpolation 38
4.2.2. Packing Method from Tweaked Interpolation 38
4.3. Analysis and Comparison 41
Chapter 5. Application to MPC over Z₂ₖ 44
5.1. Background on MPC and SPDZ₂ₖ 44
5.2. Overview of Our Protocol 46
5.3. Authenticated Triple Generation 50
5.4. Reshare for Level-dependent Packings 51
Chapter 6. Limitations 54
6.1. Packing Density 54
6.1.1. Algebraic Background 55
6.1.2. Packing Density of Zₚₖ-Message Packings 55
6.1.3. Packing Density of Fₚₖ-Message Packings 60
6.1.4. Proof of Prop. 6.1.1 66
6.2. Level-consistency 67
6.2.1. Idempotents and Nilpotents 67
6.2.2. Level-consistency in Zₚₖ-Message Packings 69
6.2.3. Level-consistency in Fₚₖ-Message Packings 73
6.2.4. Proof of Thm. 6.2.13 75
6.3. Surjectivity 78
6.3.1. Zero-Set Ideal 79
6.3.2. Surjectivity in Zₚₖ-Message Packings 79
6.3.3. Surjectivity in Fₚₖ-Message Packings 82
6.3.4. Proof of Thm. 6.3.2 84
6.3.5. Proof of Thm. 6.3.10 87
Bibliography 91
국문초록 102