密碼學(xué)基礎(chǔ)

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