抗量子計算密碼

本書系統地介紹了抗量子計算密碼的基本原理、代表性成果和發展趨勢。全書共有6篇。第1篇：抗量子計算密碼導論；第2篇：量子計算；第3篇：基於Hash函式的數字簽名方案；第4篇：基於糾錯碼的密碼；第5篇：基於格的密碼；第6篇：多變數公鑰密碼學。

本書內容豐富，較完整地給出了抗量子計算密碼領域的全貌，不僅介紹現有成果，而且給出了今後的發展趨勢,有較高的參考價值。本書可作為信息安全、計算機等相關專業高年級本科生和研究生的教材或參考資料，也可供從事信息安全、計算機、通信、數學、量子科學等領域的科技人員參考。

基本介紹

• 書名：抗量子計算密碼  
• 作者：Daniel J. Bernstein，Johannes Buchmann，Erik Dahmen  
• 譯者：張煥國、王后珍、楊昌 等 
• ISBN：9787302363514 
• 定價：29.5元 
• 出版社：清華大學出版社 
• 出版時間：2015-2-1 
• 裝幀：平裝 

前言

21世紀是信息的時代，除了電子信息科學技術繼續高速發展之外，量子和生物等新型信息科學正在建立和發展。量子信息科學的研究和發展催生了量子計算機、量子通信和量子密碼的出現。

由於量子信息的奇妙特性，使得量子計算具有天然的並行性。例如，當量子計算機對一個n量子比特的數據進行處理時，量子計算機實際上是同時對2n個數據狀態進行了處理。正是這種並行性使得原來在電子計算機環境下的一些困難問題，在量子計算機環境下卻成為容易計算的。量子計算機的這種超強計算能力，使得基於計算複雜性的現有公鑰密碼的安全受到挑戰。

目前可用於密碼破譯的量子計算算法主要有Grover算法和Shor算法。對於密碼破譯來說，Grover算法的作用相當於把密碼的密鑰長度減少一半。而Shor算法則可以對目前廣泛使用的RSA、EIGamal、ECC公鑰密碼和DH密鑰協商協定進行有效攻擊。這說明在量子計算環境下，RSA、EIGamal、ECC公鑰密碼和DH密鑰協商協定將不再安全。

早在2001年IBM公司就研製出7個量子位的示例型量子計算機，向世界宣告了量子計算機原理的可行性。2011年9月2日，美國加州大學聖芭芭拉分校的科學家宣布，研製出具有馮·諾依曼計算機結構的量子計算機，並成功地進行了小合數的因子分解試驗。2012年3月1日IBM宣布找到了一種可以大規模提升量子計算機量子位數的關鍵技術。

除了美國之外，加拿大的量子計算機取得了長足的發展。2007年2月加拿大D-Wave System公司宣布研製出世界上第一台商用16量子位的量子計算機。2008年5月提高到48量子位。2011年5月30日又提高到128量子位，並開始公開出售，1000萬美元一台。美國著名軍火製造商洛克希德·馬丁公司購買了這種量子計算機，用於新式武器的研製。2013年初又大幅度地提高到512量子位，價格也上升為1500萬美元一台。著名信息服務商谷歌公司購買了這種量子計算機，用於提高信息搜尋效率和研究量子人工智慧。

由上可知，量子計算機的發展大大超出了人們原來的預想。

必須指出的是，目前加拿大的量子計算機屬於專用型量子計算機，它能夠執行Grover算法，尚不能執行Shor算法。美國加州大學聖芭芭拉分校的量子計算機可以執行Shor算法，但量子位數太少。也就是說，目前的量子計算機尚不能對現有密碼構成實際的威脅。但是，隨著量子計算技術的發展，總有一天會對現有密碼構成實際威脅。

在量子計算環境下我們仍然需要確保信息安全，仍然需要使用密碼，但是我們使用什麼密碼呢？這是擺在我們面前的一個重大戰略問題。

抗量子計算密碼出版說明根據哲學的基本原理，任何事物有優點，必然也有缺點。據此量子計算機有優勢，必然也有劣勢。有其擅長計算的問題，必然也有其不擅長計算的問題。

實際上，量子計算機能夠有效攻擊許多現有密碼，但並不能有效攻擊所有的現有密碼。基於量子計算機不擅長計算的那些問題構造密碼，就可以抵抗量子計算的攻擊。我們稱能夠抵抗量子計算機攻擊的密碼為抗量子計算密碼。

出於對抗量子計算密碼需求的緊迫性，國際上從2006年開始舉辦"抗量子計算密碼學術會議（PostQuantum Cryptography）"，每兩年舉行一次，至今已舉辦了4屆。已經產生了一批重要的研究成果，讓人們看到了抗量子計算密碼的新曙光。

為了使我國廣大讀者能夠了解抗量子計算密碼的發展，促進我國抗量子計算密碼的科學研究和技術進步，清華大學出版社組織我們翻譯出版了《抗量子計算密碼》一書。

本書由12位作者供稿，並由其中的3位作者進行編著而成，這些作者都是抗量子計算密碼領域各個分支的著名專家。本書系統地介紹了抗量子計算密碼的基本原理、代表性成果和發展趨勢。全書共分6篇，第1篇為抗量子計算密碼導論。首先介紹量子計算機對現有密碼的威脅，然後簡單介紹現有抗量子計算密碼的概貌，使讀者對此領域有一個整體的了解。第2篇為量子計算。講述了量子算法的工作原理及其最新進展，使讀者能夠對量子算法及其攻擊密碼的能力有一個了解。第3篇為基於Hash函式的數字簽名方案。基於Hash函式的數字簽名方案為抗量子計算密碼提供了一種有趣的候選。本篇介紹了基於Hash函式的數字簽名技術的發展，給出了幾種代表性的方案。第4篇為基於糾錯碼的密碼。糾錯碼是一種有效的容錯技術，基於糾錯碼可以構造密碼，而且具有抗量子計算攻擊的能力。本篇介紹了基於糾錯碼的主要密碼類型，並分析指出了它們的優缺點。第5篇為格密碼。首先介紹了格的困難問題，然後介紹了幾種有代表性的格密碼。當前，格密碼已成為學術界的研究熱點。第6篇為多變數公鑰密碼學。多變數公鑰密碼被認為是能抵抗量子計算機攻擊的公鑰密碼體制之一。本篇介紹了多變數公鑰密碼過去二十多年的發展和主要成果，並具體分析了每一種方案的優缺點。

本書內容豐富，較完整地給出了這一領域的全貌，不僅介紹現有成果，而且給出了今後的發展趨勢。因此本書是一本很有參考價值的好書。本書可作為研究生和高年級本科生的教材或參考書，也可供從事信息安全、計算機、通信、數學、量子信息科學等領域的科技人員作為參考書。

本書的第1篇和第4篇由張煥國翻譯，第2篇由楊昌翻譯，第3篇由吳萬青翻譯，第5篇由毛少武翻譯，第6篇由王后珍翻譯。

本書的翻譯採取了分工翻譯，集體討論修訂的方法。博士研究生胡國香、王亞輝、劉金會、賈建衛等參與了翻譯書稿的討論修訂和譯稿整理工作。

由於譯者的專業知識和外語水平有限，書中錯誤在所難免，敬請讀者指正，譯者在此先致感謝之意。

目錄

第1篇抗量子計算密碼導論

1密碼學完蛋了嗎1

2抗量子計算密碼的初步體驗4

2.1基於Hash函式的公鑰簽名體制5

2.2基於糾錯碼的公鑰加密體制6

2.3多變數二次多項式公鑰簽名體制7

3抗量子計算密碼面臨的挑戰9

3.1效率9

3.2信任10

3.3可用性10

4與量子密碼的比較11

第2篇量子計算

1經典密碼學與量子計算13

1.1量子計算機下密碼體系的脆弱性14

1.2其他密碼學原語15

2計算模型16

3量子傅立葉變換18

4隱藏子群問題19

4.1阿貝爾HSP21

4.2非阿貝爾HSP22

5搜尋算法23

6展望25

參考文獻25

第3篇基於Hash函式的數字簽名方案

1基於Hash函式的一次性簽名方案30

1.1LamportDiffie一次性簽名方案30

1.2Winternitz一次性簽名方案312Merkle樹認證方案33

2.1MSS密鑰對生成34

2.2高效的根計算34

2.3MSS簽名生成35

2.4MSS簽名驗證35

3利用偽隨機數產生器產生一次性密鑰對36

3.1利用偽隨機數產生器產生MSS密鑰對36

3.2利用PRNG產生MSS簽名37

3.3前向安全37

4認證路徑的計算37

4.1經典的遍歷38

4.2分形Merkle樹遍歷39

4.3log時空的Merkle樹遍歷45

4.4漸進最優結果47

4.5LOG遍歷算法的改進49

5樹型連結方案55

5.1思路55

5.2CMSS密鑰對生成56

5.3CMSS簽名生成57

5.4CMSS驗證57

6分散式簽名產生57

6.1思路58

6.2分散式根簽名58

6.3分散式根計算59

6.4分散式認證路徑計算60

6.5GMSS密鑰對生成61

6.6GMSS簽名生成62

6.7GMSS簽名驗證63

7Merkle簽名方案的安全性63

7.1概念和定義63

7.2LamportDiffie一次性簽名方案的安全性65

7.3Merkle簽名方案的安全性66

7.4MSS的安全級別68

參考文獻71

第4篇基於糾錯碼的密碼

1引言74

2密碼體制75

2.1McEliece公鑰密碼體制75

2.2CFS簽名79

2.3Stern身份識別方案79

2.4基於伴隨式單向函式的密碼體制81

3把計算伴隨式作為單向函式的安全性83

3.1基礎知識83

3.2解碼問題84

3.3解碼算法85

3.4對FSB和CFS的碰撞攻擊87

3.5量子計算機的衝擊89

4編碼和結構90

4.1碼的等價91

4.2支撐集合分裂算法92

4.3識別碼的結構94

5實際情況100

5.1McEliece公鑰密碼體制的快速加解密100

5.2節省存儲的需求104

5.3McEliece密碼方案的語義安全性105

6附錄108

6.1代數編碼理論108

6.2GRS碼和Goppa碼109

6.3秩距離111

參考文獻111

第5篇基於格的密碼

1簡介116

1.1格問題和算法117

1.2格密碼118

1.3量子和格118

1.4本章結構119

2預備知識119

2.1q模格120

2.2格問題120

3在隨機q格中找短向量120

3.1格基規約方法121

3.2組合方法122

4Hash函式123

4.1Ajtai的構造和進一步改善123

4.2基於循環格和理想格的高效Hash函式125

5公鑰加密方案129

5.1GGH/HNF公鑰密碼體制130

5.2NTRU密碼體制131

5.3AjtaiDwork密碼體制和後續工作133

5.4基於LWE的密碼體制134

6數字簽名方案140

6.1GGH和NTRUSign簽名方案141

6.2基於原像抽樣陷門函式的方案142

6.3基於抗碰撞Hash函式的方案142

7其他密碼類型143

7.1CCA安全的密碼體制143

7.2IBE143

7.3OT協定144

7.4零知識證明和ID方案144

8開放問題144

致謝144

參考文獻145

第6篇多變數公鑰密碼學

1引言150

2多變數公鑰密碼的基本結構151

2.1標準(雙極)結構和符號151

2.2其他結構153

3多變數公鑰密碼實例154

3.1Rainbow(28，18,12,12)簽名方案155

3.2PMI+(136，6,18,8)，一個擾動的MatsumotoImai加方案155

3.3Quartz或HFEv(2,129,103,3,4)簽名方案156

3.4MPKC一些計算方面的技巧156

4基本結構及其變種158

4.1MPKCs的構造歷史158

4.2三角形結構158

4.3大域結構類: MatsumotoImai(C)和HFE159

4.4不平衡油醋方案及其衍生方案160

4.5加減變種方案162

4.6TTM及其相關方案: “鎖”和多重三角形163

4.7中等域: MFE和