全同態(tài)加密：從理論到實踐

第1章全同態(tài)加密入門1
1.1全同態(tài)加密引言1
1.1.1為什么需要全同態(tài)加密1
1.1.2第一個全同態(tài)加密的誕生3
1.1.3為什么采用電路模型4
1.1.4全同態(tài)加密的構(gòu)造框架5
1.2全同態(tài)加密入門7
1.2.1全同態(tài)加密的4部分8
1.2.2同態(tài)解密控制噪聲10
1.2.3LWE上的全同態(tài)加密12
1.3詳解同態(tài)解密思想16
1.3.1一個簡化的整數(shù)上的加密算法16
1.3.2可怕的噪聲17
1.3.3同態(tài)解密： 一個生硬的思路18
1.3.4解密電路的復雜度19
1.3.5壓縮解密電路21
1.3.6實現(xiàn)算法24
1.4格密碼學介紹25
第2章格密碼理論基礎(chǔ)27
2.1格密碼在后量子密碼中的優(yōu)勢27
2.2數(shù)學基礎(chǔ)知識31
2.2.1向量空間簡介31
2.2.2矩陣和行列式的一些重要概念33
2.3格理論基礎(chǔ)33
2.3.1格的定義及性質(zhì)33
2.3.2格上的計算問題35
2.4構(gòu)建格公鑰密碼系統(tǒng)的方法38
2.4.1陷門單向函數(shù)38
2.4.2隨機格39全同態(tài)加密——從理論到實踐目錄2.4.3構(gòu)造單向哈希函數(shù)39
2.4.4構(gòu)造陷門單向函數(shù)40
2.4.5格公鑰密碼系統(tǒng)的框架42
2.5LWE問題43
2.5.1LWE搜索問題43
2.5.2LWE判定問題44
2.5.3構(gòu)造LWE單向哈希函數(shù)46
2.5.4構(gòu)造LWE陷門單向函數(shù)46
2.5.5LWE問題的困難性48
2.5.6高斯分布49
2.6LWE私鑰加密算法50
2.7LWE上公鑰加密算法52
2.7.1LWE上Regev公鑰加密算法 52
2.7.2LWE上Regev公鑰加密變形53
2.7.3LWE上多位Regev公鑰加密算法53
2.8環(huán)LWE問題54
2.9基于環(huán)LWE的公鑰加密56
2.9.1環(huán)LWE上公鑰加密算法  56
2.9.2環(huán)LWE上公鑰加密算法變形56
2.9.3環(huán)LWE上的NTRU加密算法57
2.10最壞情況下的困難問題58
第3章全同態(tài)加密的噪聲依賴分析與安全參數(shù)分析60
3.1全同態(tài)加密61
3.1.1全同態(tài)加密定義61
3.1.2全同態(tài)加密分類61
3.2全同態(tài)加密關(guān)鍵技術(shù)62
3.2.1同態(tài)解密技術(shù)62
3.2.2模交換技術(shù)  62
3.2.3位展開技術(shù)63
3.2.4密鑰交換  64
3.3基于噪聲依賴分析的全同態(tài)加密算法研究66
3.3.1噪聲依賴分析方法66
3.3.2噪聲增長依賴于密文中噪聲的全同態(tài)加密算法: BGV算法67
3.3.3噪聲增長依賴于密鑰的全同態(tài)加密算法: Bra12算法70
3.3.4噪聲增長依賴于密文的全同態(tài)加密算法： GSW13算法75
3.3.5算法參數(shù)尺寸與噪聲增長分析比較77
3.4全同態(tài)加密具體安全參數(shù)分析78
3.4.1具體的安全參數(shù)分析方法79
3.4.2Bra12算法和GSW13算法的具體安全參數(shù)80
第4章使用提升維數(shù)法設(shè)計NTRU型無須密鑰交換的全同態(tài)加密83
4.1問題的提出83
4.2解決問題的主要思想84
4.3提升維數(shù)法85
4.4環(huán)LWE上NTRU基本加密方案與擴展加密方案87
4.4.1判定小多項式比問題87
4.4.2NTRU基本加密方案87
4.4.3NTRU擴展加密方案88
4.5同態(tài)屬性89
4.5.1NTRU基本加密方案的同態(tài)性89
4.5.2擴展加密方案的乘法同態(tài)性89
4.5.3擴展加密方案的加法同態(tài)性90
4.6密文同態(tài)計算的噪聲分析90
4.6.1加法噪聲分析90
4.6.2乘法噪聲分析91
4.6.3乘法計算優(yōu)化91
4.7層次型全同態(tài)加密91
4.8選擇具體安全參數(shù)92
4.8.1方案的參數(shù)屬性92
4.8.2具體參數(shù)93
4.9總結(jié)94
第5章使用提升維數(shù)法設(shè)計環(huán)LWE上的無須密鑰交換的全同態(tài)加密96
5.1問題的提出96
5.2解決問題的主要思想97
5.3提升維數(shù)法98
5.4密文是矩陣的環(huán)LWE上的加密方案99
5.5環(huán)LWE上的擴展加密方案100
5.6環(huán)LWE上擴展加密方案的同態(tài)性101
5.6.1加法同態(tài)性101
5.6.2乘法同態(tài)性101
5.7密文同態(tài)計算的噪聲分析102
5.7.1加法噪聲分析102
5.7.2乘法噪聲分析102
5.8環(huán)LWE上擴展加密方案上的層次型全同態(tài)加密方案102
5.9密文是矩陣的LWE上加密方案103
5.10LWE上的擴展加密方案104
5.11LWE上擴展加密方案的同態(tài)性106
5.11.1加法同態(tài)性106
5.11.2乘法同態(tài)性106
5.12密文同態(tài)計算的噪聲分析107
5.12.1加法噪聲分析107
5.12.2乘法噪聲分析107
5.13LWE上擴展加密方案上的層次全同態(tài)加密方案107
5.14選擇具體的安全參數(shù)108
5.14.1方案的參數(shù)屬性108
5.14.2具體參數(shù)109
5.15總結(jié)111
第6章一個基于BinaryLWE的全同態(tài)加密方案113
6.1問題的提出113
6.2解決問題的主要思路114
6.3BinaryLWE問題114
6.4改進的基本加密方案115
6.5方案的同態(tài)性116
6.5.1加法同態(tài)性116
6.5.2乘法同態(tài)性117
6.5.3密鑰交換117
6.6層次型全同態(tài)加密方案118
6.7密文同態(tài)計算的噪聲分析119
6.7.1加法噪聲分析119
6.7.2乘法噪聲分析119
6.8選擇具體安全參數(shù)120
6.8.1方案的參數(shù)屬性120
6.8.2具體參數(shù)121
6.9總結(jié)122
第7章基于BinaryLWE噪聲控制優(yōu)化的全同態(tài)加密方案改進123
7.1問題的提出123
7.2解決問題的主要思路123
7.3改進的基本加密方案124
7.4方案的同態(tài)性125
7.4.1加法同態(tài)性126
7.4.2乘法同態(tài)性126
7.4.3密鑰交換127
7.5層次型全同態(tài)加密方案127
7.6密文同態(tài)計算的噪聲分析128
7.6.1加法噪聲分析128
7.6.2乘法噪聲分析128
7.7選擇具體安全參數(shù)129
7.7.1方案的參數(shù)屬性129
7.7.2具體參數(shù)130
7.8總結(jié)131
第8章一個LWE上的短公鑰多位全同態(tài)加密132
8.1一個多位的LWE加密方案132
8.2方案的同態(tài)性134
8.2.1加法同態(tài)性134
8.2.2乘法同態(tài)性134
8.3密鑰交換135
8.4層次型全同態(tài)加密方案136
8.5噪聲分析137
8.6具體安全參數(shù)138
第9章基于抽象解密結(jié)構(gòu)的全同態(tài)加密構(gòu)造方法分析141
9.1解密結(jié)構(gòu)與同態(tài)性141
9.1.1抽象解密結(jié)構(gòu)142
9.1.2密文乘法期盼解密結(jié)構(gòu)的構(gòu)造143
9.1.3解密結(jié)構(gòu)與噪聲增長依賴主要項144
9.1.4最終解密結(jié)構(gòu)145
9.2密文矩陣的解密結(jié)構(gòu)146
9.2.1密文矩陣的解密結(jié)構(gòu)147
9.2.2密文矩陣的最終解密結(jié)構(gòu)147
9.3密文堆疊的加密形式148
9.3.1密文矩陣的零次同態(tài)加密形式148
9.3.2密文矩陣的全同態(tài)加密形式149
9.4通用構(gòu)造方法150
9.4.1構(gòu)造思想150
9.4.2通用構(gòu)造方法介紹150
9.5全同態(tài)加密的形式比較151
9.5.1解密結(jié)構(gòu)151
9.5.2密文乘法同態(tài)計算形式152
9.5.3噪聲控制153
9.5.4最終解密結(jié)構(gòu)153
第10章浮點數(shù)上的全同態(tài)加密算法CKKS155
10.1浮點數(shù)同態(tài)計算的重要性與挑戰(zhàn)155
10.2近似同態(tài)計算例子158
10.3分圓多項式159
10.4編碼與解碼161
10.4.1?瘙綇［X］/(XN 1)→?瘙綇N的編碼與解碼161
10.4.2?瘙綄［X］/XN 1→?瘙綇N/2的編碼與解碼162
10.5再縮減技術(shù)163
10.6CKKS算法164
第11章SEAL全同態(tài)加密庫的使用166
11.1設(shè)置參數(shù)166
11.2密鑰生成與加密解密168
11.3示例169
11.4批處理編碼172
11.5模交換鏈174
11.6CKKS算法的使用175
11.7密文中的向量旋轉(zhuǎn)176
參考文獻178
附錄A注釋表187
附錄B如何學習全同態(tài)加密188