密碼學基礎

第1章  緒論 1                  
 1.1  密碼學：概述 1                  
 1.1.1  加密機制 2                  
 1.1.2  偽隨機序列發(fā)生器 3                  
 1.1.3  數(shù)字簽名 3                  
 1.1.4  容錯協(xié)議和零知識證明 4                  
 1.2  概率論基礎知識 6                  
 1.2.1  符號約定 6                  
 1.2.2  3個不等式 7                  
 1.3  計算模型 9                  
 1.3.1  P, NP與NP-完全 9                  
 1.3.2  概率多項式時間算法 10                  
 1.3.3  非均勻多項式時間算法 12                  
 1.3.4  難處理假設 14                  
 1.3.5  預言機（Oracle Machine） 15                  
 1.4  嚴密處理的目的 15                  
 1.4.1  嚴密處理的需要 16                  
 1.4.2  嚴密處理的實際結果 17                  
 1.4.3  保守傾向 18                  
 1.5  其他 19                  
 1.5.1  歷史記錄 19                  
 1.5.2  關于進一步閱讀的建議 20                  
 1.5.3  未決問題 21                  
 1.5.4  習題 21                  
 第2章  計算復雜性 23                  
 2.1  單向函數(shù)：動機(單向函數(shù)的意義) 24                  
 2.2  單向函數(shù)的定義 25                  
 2.2.1  強單向函數(shù) 25                  
 2.2.2  弱單向函數(shù) 27                  
 2.2.3  兩個有用的長度協(xié)議 27                  
 2.2.4  單向函數(shù)的候選形式 31                  
 2.2.5  非均勻單向函數(shù) 32                  
 2.3  弱單向函數(shù)隱含強單向函數(shù) 33                  
 2.3.1  定理2.3.2的證明 34                  
 2.3.2  一個有趣的例子 37                  
 2.3.3  討論 38                  
 2.4  單向函數(shù)的多樣性 39                  
 2.4.1*  通用單向函數(shù) 40                  
 2.4.2  單向函數(shù)類 41                  
 2.4.3  單向函數(shù)類的實例 42                  
 2.4.4  陷門單向置換 44                  
 2.4.5*  無爪（claw-free）函數(shù) 46                  
 2.4.6*  關于推薦候選式 48                  
 2.5  核心斷言（Hard-Core Predicates） 49                  
 2.5.1  定義 49                  
 2.5.2  任意單向函數(shù)的核心斷言 50                  
 2.5.3*  核心函數(shù) 56                  
 2.6*  單向函數(shù)的有效放大 59                  
 2.6.1  構造 60                  
 2.6.2  分析 62                  
 2.7  其他 67                  
 2.7.1  歷史記錄 67                  
 2.7.2  關于進一步閱讀的建議 68                  
 2.7.3  未決問題 69                  
 2.7.4  習題 70                  
 第3章  偽隨機發(fā)生器 77                  
 3.1  啟發(fā)性討論 78                  
 3.1.1  隨機性的計算逼近 78                  
 3.1.2  偽隨機發(fā)生器的一個嚴格逼近 78                  
 3.2  計算不可分辨性 79                  
 3.2.1  定義 79                  
 3.2.2  統(tǒng)計相關性 80                  
 3.2.3  重復實驗不可分辨性 81                  
 3.2.4*  電路族不可分辨性 84                  
 3.2.5  偽隨機總體 85                  
 3.3  偽隨機序列發(fā)生器定義 85                  
 3.3.1  偽隨機發(fā)生器的標準定義 85                  
 3.3.2  增加擴展因子 86                  
 3.3.3*  不定長輸出的偽隨機發(fā)生器 90                  
 3.3.4  偽隨機發(fā)生器的適用性 90                  
 3.3.5  偽隨機性和不可預測性 91                  
 3.3.6  偽隨機發(fā)生器隱含著單向函數(shù) 94                  
 3.4  基于單向置換的構造 94                  
 3.4.1  基于單一置換的構造 95                  
 3.4.2  基于置換集合的構造 100                  
 3.4.3*  應用核心函數(shù)而不是核心斷言 102                  
 3.5*  基于單向函數(shù)的構造 103                  
 3.5.1  利用1-1單向函數(shù) 103                  
 3.5.2  利用正則單向函數(shù) 107                  
 3.5.3  在正則單向函數(shù)之后的討論 112                  
 3.6  偽隨機函數(shù) 113                  
 3.6.1  定義 113                  
 3.6.2  構造 115                  
 3.6.3  應用程序：一個一般的方法論 119                  
 3.6.4*  一般化(普遍化) 120                  
 3.7*  偽隨機置換 124                  
 3.7.1  一些定義 125                  
 3.7.2  構造 126                  
 3.8  其他 128                  
 3.8.1  歷史記錄 128                  
 3.8.2  關于進一步閱讀的建議 129                  
 3.8.3  未決問題 130                  
 3.8.4  習題 130                  
 第4章  零知識證明系統(tǒng) 140                  
 4.1  零知識證明：動機 141                  
 4.1.1  證明的概念 142                  
 4.1.2  獲得知識 144                  
 4.2  交互證明系統(tǒng) 145                  
 4.2.1  定義 145                  
 4.2.2  一個實例(IP中的圖非同構問題) 148                  
 4.2.3*  IP類的結構 151                  
 4.2.4  模型的擴展 152                  
 4.3  零知識證明：定義 152                  
 4.3.1  完備零知識和計算零知識 153                  
 4.3.2  一個例子(PZK中的圖同構) 157                  
 4.3.3  關于輔助輸入的零知識 162                  
 4.3.4  零知識證明的順序合成 164                  
 4.4  NP零知識證明 169                  
 4.4.1  承諾方案 170                  
 4.4.2  圖著色的零知識證明 173                  
 4.4.3  普遍結論和一些應用 182                  
 4.4.4  二級考慮 185                  
 4.5*  否定結果 187                  
 4.5.1  交互和隨機性的重要性 187                  
 4.5.2  無條件結果的限制 188                  
 4.5.3  統(tǒng)計零知識證明的限制 190                  
 4.5.4  零知識和并行合成 190                  
 4.6*  證據(jù)不可分辨性和隱藏性 192                  
 4.6.1  定義 193                  
 4.6.2  并行合成 195                  
 4.6.3  構造 196                  
 4.6.4  應用 198                  
 4.7*  知識證明 198                  
 4.7.1  定義 198                  
 4.7.2  減少知識誤差 202                  
 4.7.3  NP知識的零知識證明 203                  
 4.7.4  應用 203                  
 4.7.5  身份證明(身份認證機制) 204                  
 4.7.6  強知識證明 207                  
 4.8*  計算合理性證明(參數(shù)) 209                  
 4.8.1  定義 210                  
 4.8.2  完備隱藏承諾方案 210                  
 4.8.3  NP完備零知識理論 215                  
 4.8.4  多項式對數(shù)效率的討論 216                  
 4.9*  常數(shù)輪零知識證明 217                  
 4.9.1  使用完全保密的承諾機制 218                  
 4.9.2  限定欺騙證明者的能力 222                  
 4.10*  非交互零知識證明 225                  
 4.10.1  基本定義 225                  
 4.10.2  構造 226                  
 4.10.3  擴展 230                  
 4.11*  多證明者零知識證明 234                  
 4.11.1  定義 234                  
 4.11.2  兩發(fā)送者的承諾方案 236                  
 4.11.3  NP完備零知識 239                  
 4.11.4  應用 240                  
 4.12  其他 241                  
 4.12.1  歷史記錄 241                  
 4.12.2  關于進一步閱讀的建議 242                  
 4.12.3  未決問題 243                  
 4.12.4  習題 244                  
 附錄A  計算數(shù)論背景 250                  
 A.1  素數(shù) 250                  
 A.1.1  素數(shù)求模的二次剩余 250                  
 A.1.2  在素數(shù)求模運算中開方 250                  
 A.1.3  素性檢測器 251                  
 A.1.4  素數(shù)的均勻選擇 252                  
 A.2  合數(shù) 252                  
 A.2.1  合數(shù)求模的二次剩余 253                  
 A.2.2  合數(shù)求模的開方運算 253                  
 A.2.3  勒讓德和雅克比符號 254                  
 A.2.4  布盧姆整數(shù)和它們的二次剩余結構 254                  
 附錄B  第2卷摘要 256                  
 B.1  加密：摘要 256                  
 B.1.1  定義 256                  
 B.1.2  構造 257                  
 B.1.3  防竊聽安全性 259                  
 B.1.4  一些建議 261                  
 B.2  簽名：摘要 261                  
 B.2.1  定義 262                  
 B.2.2  構造 262                  
 B.2.3  一些建議 264                  
 B.3  密碼學協(xié)議：摘要 265                  
 B.3.1  定義 265                  
 B.3.2  構造 266                  
 B.3.3  一些建議 267                  
 參考文獻 268