Title Page
Abstract
Contents
Chapter 1. Introduction 11
1.1. Fully Homomorphic Encryption 11
1.2. Problem Definition 14
1.2.1. Homomorphic Encryption 15
1.2.2. Boolean Circuit and Multiplicative Depth 17
1.2.3. Problem 18
1.3. Search-based Optimization Method 19
1.3.1. Program Synthesis 19
1.3.2. Term Rewriting and Equality Saturation 20
1.4. Contributions 22
Chapter 2. Informal Description 24
Chapter 3. Algorithm 30
3.1. Preliminaries 30
3.2. Learning Rewrite Rules 33
3.2.1. The Overall Algorithm 33
3.2.2. Region Selection 35
3.2.3. Synthesizing Replacement 36
3.2.4. Collecting and Simplifying Rewrite Rules 36
3.3. Optimization without Backtracking 37
3.3.1. Our Term Rewriting System 38
3.3.2. Optimizations 41
3.4. Optimization with Backtracking Based on Equality Saturation 44
3.4.1. E-graph Structure 44
3.4.2. Equality Saturation Process 46
3.4.3. Tradeoff between Optimality and Cost 48
Chapter 4. Evaluation 50
4.1. Experimental Setup 51
4.2. Effectiveness of Lobster 54
4.3. Comparison to the Baseline 59
4.4. Efficacy of Reusing Pre-Learned Rewrite Rules 60
4.5. Efficacy of Equality Saturation 63
4.6. Efficacy of Equational Rewriting 65
4.7. Sensitivity to Changes in a Time Limit 66
4.8. Sensitivity to Changes in a Training Set 67
Chapter 5. Related Work 69
Chapter 6. Conculsion 74
Bibliography 75
Appendices 85
요약 125
Table 3.1. Rules for C-matching 43
Table 4.1. Characteristics of benchmarks from {medical [14], sorting [17], bit-vector evaluation [38,64], circuit [1]} algorithm. ×Depth denotes the multi-... 53
Table 4.2. Detailed main results (comparison to Carpov etl al. [15]). The timeout for optimization is set to 12 hours. #AND ↑ shows the ratio between the... 56
Table 4.3. Detailed comparison results of single-path rewriting and saturation-based rewriting. The timeout for optimization is set to 12 hours. #AND ↑... 63
Figure 1.1. Secure third-party computation with private data. 11
Figure 1.2. Optimizing synthesis for homomorphic evaluation circuit 20
Figure 1.3. Semantic equivalence between E-graph and context-free-grammar. 22
Figure 1.4. Overview of the system. 23
Figure 2.1. (a) The circuit cex of depth 5. (b) A circuit that hasdepth 3 and the same semantics as cex.[이미지참조] 28
Figure 3.1. Simple example of E-graph. Each box means enode, and dotted box means eclass. 45
Figure 3.2. Change of E-graph during a single iteration. Dotted box means eclass. (a) ematch result for root enode. (b) add subcircuit c₁ and c₂ to E-graph.... 47
Figure 3.3. Change of E-graph during iterations. Dotted box means eclass. (a) initial E-graph. (b) after 1 iteration. (c) after 2 iterations. (d) saturated E-graph. 48
Figure 4.1. Main results comparing the optimization performance of LOBSTER and Carpov et al. [15] - Speedups in overall homomorphic evaluation time (left)... 55
Figure 4.2. Correlation plot of multiplicative depth and homomorphic evaluation time 55
Figure 4.3. distribution of rule sizes and how often they were used during optimization 58
Figure 4.4. Comparison between on-the-fly synthesis and equality saturation with learned rules 61
Figure 4.5. Impact of changing rewrite rules 62
Figure 4.6. Efficacy of Equality Saturation 64
Figure 4.7. Efficacy of equational rewriting 65
Figure 4.8. Comparison between the optimization results with 1h and 12h of time limit. 66
Figure 4.9. Comparison between the optimization results with two-fold cross validation and leave-one-out cross validation. 68