1、第二章 預備知識第二章 預備知識數學理論是現代密碼學建立和發展的基礎，包括復雜性理論、可證明安全理論等，這些理論中的許多概念在設計密碼算法時是必不可少的。本章主要介紹本本文中可能會用到的一些基本概念和結論，并介紹公鑰密碼體制以及代理重加密體制的相關定義。最后，本章討論了密碼系統中存在的密鑰泄露問題。2.1 復雜性理論在計算機中，某一個算法執行的時間是以比特運算的形式來測量的。為完成某一個算法而需要的必要的比特運算數量，稱為這個算法的計算復雜性或簡稱復雜性。它確切定義了求解一個問題是計算“容易”還是“困難”的，并由此對問題和算法的復雜性加以分類。由于算法的計算復雜性是正整數的函數，因此要比較兩個

2、算法的計算復雜性主要是比較當 x 充分大時，它們隨 x 增大而增大的數量級。定義定義 2.1 令函數以及，如果是正整數，且 c 是常數，有時，則將記作，或簡寫為。是對算法復雜性的一個數量級分類，它表示算法所需的比特運算次數的上界，與計算機的操作時間，運行速度等固有的性質無關。在復雜性的分析過程中，我們需要知道執行某個算法的確切的比特運算次數。計算機執行某個算法所需的時間，是和比特元素的數量成正比的。這個比例常數和計算機的性能有關。在執行一個算法的過程中，基本的時間估計是多項式時間的，或簡稱多項式的。一般來說，由于這些算法是最快的算法，因此它們都是可取的，即多項式時間算法是有效的算法。多項式時間

3、算法是對基本的加、減、乘、除運算而言的算法。然而，有些算法的復雜性是，其中，c 為常數且f 是一個關于的多項式，即為指數時間算法，或簡稱為指數的。一個亞指數時間算法是，其中，c 為常數表示滿足的函數。假設輸入算法的最大比特長度為，則，這是指數時間算法。超多項式時間算法的概念為若一個算法的復雜性為，其中 c 為常數，是介于常數和線性函數之間的函數。對現在已知的密碼體制有效的攻擊算法都是超多項式時間算法，但是并沒有證明不存在有效的多項式時間攻擊算法。下面給出關于 的一些性質：假定 f 和 g 是正多項式，則有(1) 若，則有；(2) ；(3) 。證明：（1）若，則有常數和正整數，若，。因此，可得，

4、即。（2）令，則存在和正整數，使得當時，。因此， ，故可得。（3）令，則存在和正整數，使得當時，。因此，即。上述性質中的（1）是（3）在下的特殊情況。同樣，如果，則對任意的，成立。計算復雜性是計算機科學的重要組成部分，同時也是密碼學的理論基礎之一。Shannon 曾指出，設計一個密碼的本質上要尋找一個難解的問題。這一推斷揭示了密碼的安全性與計算復雜性之間的相互依賴關系。公鑰密碼的出現，開拓了直接利用 NPC 問題設計密碼的技術路線。在當今的計算機網絡時代，密碼的編制和分析都利用計算機網絡來進行。在這種情況下，計算復雜性理論的發展將直接影響到密碼的安全，計算復雜性理論作為密碼的一種理論基礎將發揮

5、越來越大的作用。2.2 可證明安全理論本小節將列出本文可能涉及的各類困難問題，如無特殊說明，均假設這些問題是難解的，并稱為對應的困難問題假設。然后，介紹形式化證明方法。2.2.1 困難問題假設群：S 是一個非空集合， 表示異或操作，表示一個群，如果(1) 閉包：；(2) 結合性：；(3) 恒等性：；(4) 反身性：。階：一個群中元素的個數稱為階。第二章 預備知識循環群：令 為階為 q 的群，各不相同，則 稱為循環群，g為群 的生成元。定義定義 2.2 對任意已知元素，有，求整數，即為DL(Discrete Logarithm)難解問題。離散對數假設意味著在群上的離散對數困難問題不能夠被敵手以不

6、可忽略的概率解決。定義定義 2.3 令為一個階為 q 循環乘法群，群上的 CDH（Computational Diffie-Hellman）問題是已知二元組（未知） ，求解。設在時間 t 內敵手成功輸出的概率為：，其中是可忽略的。如果 可忽略不計，則 CDH 問題是是難解的。定義定義 2.4 令為一個階為 q 循環群，已知，其中不可知，判斷輸出與是否一致，即為 DDH（Decisional Diffie-Hellman）難解問題。定義定義 2.5 令為一個階為 q 循環群，已知，求解，即 s-CDH（s-Computational Diffie-Hellman）難解問題，其中 是在 中隨機選擇

7、的。特別地，當 s=2 時，稱 s-CDH 問題稱為平方-CDH 問題。定義定義 2.6 令 為一個階為 q 循環群，已知，其中是不可知的，P-CDH 問題意味著計算是困難的。定義定義 2.7 令為一個階為 q 循環群，已知，其中是不可知的，P-DDH 問題意味著判斷是否成立是困難的。定義定義 2.8 如果映射滿足如下性質，則認為該映射是一個雙線性映射（Bilinear Map）：(1)都代表群，且具有相同的素數階 q；(2) 對所有的，等式成立；(3) 該映射是非退化的，即；(4) 映射 e 是高效可計算的。一般地，Weil 對Error! Reference source not foun

8、d.和 Tate 對Error! Reference source not found.可被用于構建雙線性映射 e。定義定義 2.9 令為循環加法群，階為 q，生成元為 P，已知，其中是不可知的，求解，即中的 CDH 問題。定義定義 2.10 令為循環加法群，階為 q，生成元為 P，已知，其中是不可知的，然后判定等式是否滿足，即中的 DDH 問題。定義定義 2.11 令為循環加法群，階為 q，生成元為 P，在 DDH Oracle 的協助下，計算已知元組的 CDH 難題，即 GDH（gap Diffie-Hellman）問題。定義定義 2.12 令為循環加法群，階為 q，生成元為 P，已知，求

9、解，即 q-SDH（q-strong Diffie-Hellman）問題。令、分別是階為 q 的循環加/乘法群，雙線性映射以及群生成元為 P：定義定義 2.13 已知，其中是不可知的，求解，即 BDH（Bilinear Diffie-Hellman）問題。定義定義 2.14 已知，其中是不可知的，判定等式是否成立，即 DBDH（Decisional Bilinear Diffie-Hellman）問題。定義定義 2.15 在 DBDH 預言機的協助下，求解給定的 BDH問題，即 GBDH 問題。2.2.2 形式化證明方法在可證明安全理論中，形式化安全模型被用來評估一個密碼系統的安全性。一個形式

10、化的安全模型包含兩個定義Error! Reference source not found.Error! Reference source not found.：一方面，它必須指出任意概率的敵手如何與密碼系統中的合法用戶進行多項式時間的應答/響應；另一方面，它必須說明該攻擊者要達到哪些目的，才能認定該密碼系統被攻破。一般來說，有兩種方式來描述形式化的安全模型。一種是基于游戲（game-based）的方式。在這種形式化安全模型中，攻擊者需要與一個假定的概率算法（挑戰者）進行交互。挑戰者初始化密碼系統中使用的全部密鑰，可能響應來自攻擊者的詢問。當攻擊者終止時，游戲結束，然后，評估此時的攻擊者是否具

11、備破壞該密碼系統的能力。如果一個密碼系統是安全的，那么我們必須給出說明任意一個攻擊者能夠弱化該密碼系統的可能性都非常小。基于游戲的安全模型已經被廣泛接受，且已被應用于多種類型的密碼系統的安全性證明，包括數字簽名、非對稱加密和對稱加密。本文所描述的形式化安全模型都是基于游戲的安全模型。基于游戲的安全模型的優點是容易理解和實現。然而，Canetti 等Error! Reference source not found.發現基于游戲安全模型下的安全性證明只能獨立的證明密碼系統的安全性，無法說明當該密碼系統部署于復雜環境下時也是可證明安全的。大部分密第二章 預備知識碼方案都不是獨立存在的，而是作為大型

12、計算機系統的子程序。在這種情況下，為了確保所使用的密碼算法的安全性，必須要在給定的復雜環境下進行安全性證明。因此，對于基于游戲的安全模型而言，它往往難以更好的表述大型復雜環境的安全需求。另一種是基于仿真(simulation-based)的方式。假設一個密碼系統中一個任意概率的攻擊者能夠與該密碼系統中的每個算法進行多項式時間的交互，并且其它各方也可能多項式時間的訪問密碼系統的算法。我們假設存在一個理想化的密碼系統，該密碼系統永遠都不會被攻破。它不是一個實際的系統，通常會涉及到使用一個抽象的可信第三方來確保數據被安全的傳輸，并且該可信第三方所進行的操作對攻擊者和其它各方而言是透明的。為了判斷一個

13、密碼方案是否安全，攻擊者和其它各方需要分別與真實的密碼系統和理想化的密碼系統進行多項式時間的交互，然后，檢查攻擊者和其它各方的輸出。由于理想化的密碼系統不可能被攻破，如果在真實密碼系統下攻擊者和其它各方的輸出與在理想化密碼系統下的輸出結果大致相同，那么這一真實的密碼系統是可證明安全的。因此，我們認為一個密碼系統是安全的，當且僅當上面兩種輸出是不可區分的或者可區分的概率極小。應該明確，基于仿真的安全模型比基于游戲的安全模型更強。特別地，基于仿真的安全模型提供的安全性證明考慮到了部署于復雜環境下密碼系統，為該密碼系統提供了更可靠的安全保障。目前，一些基于仿真的安全模型被廣泛使用Error! Ref

14、erence source not found.。然而，已被證明，某些密碼函數無法在基于仿真的安全模型下可證明安全Error! Reference source not found.Error! Reference source not found.。顯示一個密碼體制安全的現代方法是可證明安全性。可證明安全性的目的在于證明：如果一個敵手能夠攻破一個密碼體制的某個安全概念，那么就可以利用該敵手解決某個工人的數學困難問題。例如，如果一個敵手能夠在選擇密文攻擊下攻破 RSA 的語義安全性，那么就可以利用該敵手分解大整數；可證明安全的思想就是給定一個算法 A，提出一個新算法 C，C 把 A 作為子程序

15、。輸入給 C 的是希望解決的困難問題，輸入給 A 的是某個密碼算法。然而，如果 A 是一個積極攻擊敵手（選擇密文攻擊敵手或者適應性選擇密文攻擊敵手） ，即 A 可以對輸入公鑰進行解密預言機詢問或簽名預言機詢問。算法 C 要想使用A 作為子程序，就得對 A 的詢問提供回答。算法 C 需要應對以下四個問題：為了回避這個問題，可以使用隨機預言機模型。隨機預言是一個理想的 Hash函數。對于每一個新的詢問，隨機預言產生一個隨機值作為回答，如果問相同的詢問兩次，那么回答仍然相同。在隨機預言機模型中，假設敵手并不使用密碼算法中定義的那個 Hash 函數。也就是所，即使將隨機預言換成真實的 Hash 函數。

16、敵手 A 也是成功的。對于 A 的解密預言詢問或者簽名預言詢問，算法 C 是通過欺騙隨機預言的回答來適合自己的需要的。隨機預言模型為證明密碼體制的安全性提供了一個很好的方法，但是隨機預言模型并不反映真實世界的計算。在隨機預言模型下安全的密碼體制只能說是可能在真實的世界是安全的，不能確保一定在真實的世界是安全的。文獻給出了在隨機預言模型下安全的密碼體制在真實的世界中不安全的例子。許多密碼學研究者開始設計在標準模型（不依賴于隨機預言模型）下安全的密碼體制。移除隨機預言模型是需要代價的，通常需要更強的困難問題假設，而且在標準模型下的密碼體制通常效率較低。 2.3 公鑰密碼體制在對稱密碼體制中，或者與

17、相同，或者可以容易地從中導出。從而，或者的泄露會導致系統的不安全。公鑰密碼體制Error! Reference source not found.（Public Key Cryptography，PKC）的提出在整個密碼學發展歷史中具有里程碑式的意義。在公鑰密碼體制中，可以扎到一個密碼體制，使得由給定的來求是計算不可行的。PKC 的優勢為通信發送發能夠用通信接收方的公鑰加密明文消息并發送給接收方，然后，接收方用其私鑰解密。2.3.1 PKE 定義定義定義 2.16 公鑰加密方案（Public Key Encryption，PKE）. 一個 PKE 方案由概率算法、組成:(1) 密鑰生成算法：輸

18、入，輸出，記為；(2) 加密算法：輸入及，輸出密文 ，記為；(3) 解密算法：輸入 c 以及 sk，輸出 m 或符號 ，表示解密失敗，記為。 對于每一個 n，輸出的每一組密鑰對，以及每一個明文m，等式總是成立。2.3.2 PKE 安全性對于任一公鑰加密方案（KeyGen，Enc，Dec） ，其安全性依賴于攻擊者的能力。針對一個 PKE 方案的主動攻擊有以下三種方式，這些方式被用于分析密碼系第二章 預備知識統的安全性。定義定義 2.17 選擇明文攻擊（）已知一個加密預言機，敵手任意選取消息，并詢問加密預言機，從而產生對應密文。當結束詢問預言機后，敵手的目標是基于已經掌握的明-密文對破壞密碼系統的

19、安全性。定義定義 2.18 選擇密文攻擊（）選擇密文攻擊也稱為午餐時間攻擊，是一種比選擇明文攻擊稍強的攻擊模型。在選擇密文攻擊中，敵手可以訪問一個黑盒，這個黑盒能進行解密。在午餐時間，敵手可以選擇多項式個密文來詢問解密盒，解密盒把解密后的明文發送給敵手。在下午時間，敵手被告知一個目標密文，要求敵手在沒有解密盒的情況下解密目標密文，或者找到關于明文的有用信息。 已知一個解密預言機，敵手任意選取密文，并詢問解密預言機，從而產生對應的明文。敵手的目標是利用已獲得的明-密文對破壞密碼系統的安全性。當敵手結束解密預言機詢問后，如果敵手能夠從給定的目標密文中獲得相應的明文消息，則認為攻擊成功。也就是說，一

20、旦敵手接收到目標密文，攻擊者的解密幫助能力將不可用。定義定義 2.19 適應性選擇密文攻擊（）相比 CCA，CCA2 是一種更強的攻擊模型，且 CCA2 中的敵手能夠一直詢問解密預言機，但不包括對目標密文的詢問。目前普遍認為，任何新提出的公鑰加密算法都應該在適應性選擇密文攻擊下達到多項式安全性。2.4 代理重加密體制1998 年，Blaze 等人Error! Reference source not found.在歐密會上率先提出了代理重加密（Proxy Re-Encryption，PRE）的概念。在代理重加密體制中，一個半可信代理者（Proxy）扮演著密文轉換的角色，它可以將由委托者（Del

21、egator）公鑰加密的密文轉換為被委托者（Delegatee）對同一明文加密的密文，然后被委托者可利用其自身私鑰解密該轉換后的密文。在轉換過程中，代理者必須擁有一個由委托者授權的針對被委托者的密文轉換密鑰（即代理重加密密鑰） ，同時，該代理者無法獲知關于密文中對應明文的任何信息。然而，在文獻Error! Reference source not found.中，Blaze 等人并沒能給出規范的形式化定義，從而導致 PRE 在 19982004 年間發展緩慢Error! Reference source not found.Error! Reference source not found.E

22、rror! Reference source not found.。直到2005 年，Ateniese 等人Error! Reference source not found.在 NDSS05 上第一次對代理重加密進行了形式化定義。此后，代理重加密成為密碼學和信息安全領域的一個研究熱點，積累了大量研究成果。本節將對 PRE 的形式化定義、安全模型以及特性進行簡要描述。2.4.1 形式化定義定義定義 2.20 代理重加密（Proxy Re-Encryption，PRE）. 一個 PRE 方案可由算法、構成： (1)：輸入安全參數，密鑰生成算法為用戶 i 輸出一對公/私鑰；(2)：輸入 Alice

23、 的公/私鑰對和Bob 的公/私鑰對（其中，是可選的） ，代理重加密密鑰生成算法輸出一個代理重加密密鑰。注：此時，Alice 為委托者，Bob 為被委托者；(3)：輸入用戶 i 公鑰和消息，加密算法輸出消息 m 的密文；(4)：輸入一個代理重加密密鑰和 Alice 的密文，代理重加密算法輸出針對 Bob 的重加密密文；(5)：輸入用戶 i 的私鑰和密文 ，解密算法輸出消息 m 或錯誤符號 表明密文 不合法。注：、和與公鑰加密算法Error! Reference source not found.Error! Reference source not found.Error! Reference

24、 source not found.一致。正確性：對任意明文空間中的消息和任意兩對公/私鑰，上述的正確性必須滿足如下兩個條件：，。如圖 2.1 所示，在上述代理重加密定義中，一個擁有代理重加密密鑰的半可信代理者能夠將 Alice 公鑰下的密文重加密為 Bob 公鑰下針對同一明文的密文。然后，Bob 能夠解密并獲得消息，同時，該代理者無法獲得任何信息（如：，和 m） 。圖 2.1 代理重加密系統模型 在上述 PRE 定義的算法中，被委托者 Bob 的私鑰是可選的。一般地，Apk當 Bob 的私鑰不參與代理重加密密鑰生成時，該代理重加密方案具有單向性和非交互性；相反地，算法輸出一個雙向代理重加密密

25、鑰，且該 PRE 方案具有交互性。此外，算法和算法輸出的密文空間分別為和，當Error! Reference source not 第二章 預備知識found.Error! Reference source not found.時，算法和算法的輸出具有相同的密文空間，只需一個解密算法就可以同時解密上述兩種算法輸出的密文；而當Error! Reference source not found.時，針對和算法，則需要兩個不同的算法。2.4.2 特性在文獻 Error! Reference source not found.Error! Reference source not found.中，At

26、eniese 等人描述了一些一個 PRE 方案應該具備的特性，下面將依據上述代理重加密的定義對 PRE 的 9 個重要特性進行介紹：(1) 單向性（Unidirectional）：在一個單向 PRE 方案中，代理重加密密鑰是單向的，即代理者可以利用一個單向代理重加密密鑰將 Alice 的密文轉換為 Bob 的密文，而不能將 Bob 的密文轉換為 Alice 的密文；相反地，雙向（Bidirectional）PRE 不僅允許代理者將 Alice 的密文轉換為Bob 的密文，而且反之亦然；(2) 復用性（Multi-use）：在一個復用 PRE 方案中，算法和算法的輸出結果都可以再次作為算法的輸入

27、；反之，單用（Single-use）PRE 只允許加密算法的輸出作為算法的輸入；(3) 秘密代理（Private-proxy）：在一個秘密代理重加密中，代理者是誠實的且能夠確保代理重加密密鑰的隱私性，即攻擊者無法從密文轉換過程中獲取代理重加密密鑰；反之，在公開代理（Public-proxy）PRE 中，攻擊者可以通過觀察代理者的輸入與輸出計算出代理重加密密鑰；(4) 透明性（Transparent）：在一個具有透明性的 PRE 方案中，代理者是透明的，即由算法輸出的密文與由算法輸出的密文在計算上是不可區分的；(5) 密鑰優化（Key-optimal）：在密鑰優化的 PRE 方案中，不論存在多少

28、委托者或被委托者，用戶只需保護和存儲的少量的秘密數據；(6) 非交互性（Non-interactive）：在非交互性的 PRE 方案中，代理重加密密鑰由委托者的公/私鑰對和被委托者的公鑰產生，即被委托者不參與代理重加密密鑰的授權過程；(7) 非傳遞性（Non-transitive）：在非傳遞性 PRE 方案中，代理重加密密鑰具有非傳遞性，即給定的代理重加密密鑰和的代理重加密密鑰，代理者無法通過計算得到的代理重加密密鑰；(8) 暫時性（Temporary）：在暫時性的 PRE 方案中，代理重加密密鑰是可撤銷的，即委托者有權收回委托出去的解密授權；(9) 抗合謀攻擊（Collusion-resis

29、tant）：在抗合謀攻擊的 PRE 方案中，代理重加密密鑰能夠抵抗合謀攻擊，即當被委托者與代理者合謀時，二者無法揭露委托者的私鑰和明文信息。2.4.3 安全模型Canetti 和 HohenbergerError! Reference source not found.給出了針對雙向、多用代理重加密的適應性選擇密文攻擊安全模型（CCA2） 。在該安全模型中，他們提出了挑戰后繼（Derivatives of the Challenge）的概念，即所有與挑戰相關聯的都是的后繼，這一概念影響著安全模型中隨機預言機的限制條件的定義。由于代理重加密存在和兩種加密算法，所以挑戰密文后繼在代理重加密的安全模

30、型中意義重大。定義定義 2.21 挑戰密文后繼（Derivatives of the Challenge Ciphertext）. (1)是其自身的一個后繼；(2) 如果存在是的一個后繼，而又是的一個后繼，那么是的一個后繼；(3) 如果敵手已經發送一個詢問請求到重加密預言機，并且得到了詢問結果 ，那么是的一個后繼；(4) 如果敵手已經發送一個詢問請求到重加密密鑰生成預言機，并且，那么是所有的一個后繼。下面通過一個敵手和挑戰者 之間的安全游戲 Unidirectional-PRE-CCA2 來定義單向代理重加密方案語義安全于適應性選擇密文攻擊（IND-CCA2） 。安全游戲分為如下幾個階段：階段

31、階段 1 1：敵手可以適應性地向挑戰者 提出一系列詢問請求，其中，某個 的詢問過程如下： 公鑰生成預言機：敵手輸入索引 i，挑戰者 執行 KeyGen 算法，輸入安全參數，輸出一對公/私鑰。然后， 發送到，并將記錄到表中。 私鑰生成預言機：敵手輸入一個公鑰，挑戰者 在表中查找并將其對應的私鑰返回給。這里通過公鑰查詢預言機得到。 代理重加密密鑰生成預言機：敵手以作為輸入，挑戰者第二章 預備知識首先查找表中對應的私鑰，然后執行 ReKey 算法，并將一個代理重加密密鑰返回給。這里和都是的輸出。 代理重加密預言機：敵手以作為輸入，挑戰者 執行ReKey 和 ReEncrypt 算法，并返回一個重加密

32、密文到。這里和都是的輸出，是對應的私鑰。 解密查詢預言機：敵手以作為輸入，挑戰者 首先查找表中對應的私鑰，然后執行 Decrypt 算法，并返回到。這里是的輸出。敵手的上述詢問是適應性的，即對第 i 次詢問的回答可以依賴于前 i-1 次iq的詢問。挑戰階段挑戰階段：一旦敵手決定結束階段階段 1，將從明文空間中選擇兩個等長的明文消息，和一個公鑰為的挑戰用戶。挑戰者 選擇一個隨機比特C C并計算，然后 返回 到。此外，對于的選擇將有如下限制：(1) 在階段階段 1 中，敵手不曾將挑戰用戶的公鑰作為私鑰查詢預言機的輸入；(2) 敵手不允許選擇可以導致間接平凡解密下密文的挑戰用戶（例如，敵手可能通過多

33、次和查詢將下的密文轉換成查詢過的某個公鑰下的密文，從而使解密操作很容易實現，此類是不被允許的） 。階段階段 2：敵手適應性地向挑戰者 提出更多的詢問，其中，某個 詢問過程如下：挑戰者 的回答與階段階段 1 一致；：敵手輸入一個公鑰，如果且和分別不曾作為和的輸入，那么，挑戰者 的回答與階段階段 1 一致。這里是的后繼；：敵手以作為輸入，如果，則挑戰者 拒絕回答；否則， 的回答與階段階段 1 一致；：敵手以作為輸入，若是的一個后繼，則挑戰者 拒絕回答；否則， 的回答與階段階段 1 一致；：敵手以作為輸入，若不是的一個后繼，挑戰者 的回答與階段階段 1 一致。猜測階段猜測階段：敵手返回一個猜測結果，

34、若，則敵手在Unidirectional-PRE-CCA2 游戲中獲勝。將上述安全游戲中的敵手定義為一個 Unidirectional-PRE-CCA2 敵手，則敵手攻破安全參數為的單向代理重加密的優勢為定義定義 2.22 （Unidirectional-PRE-CCA2 安全）.一個單向代理重加密方案是語義安全于適應性選擇密文攻擊的（Unidirectional-PRE-CCA2 安全） ，當且僅當不存在任意一個多項式時間的 Unidirectional-PRE-CCA2 敵手能夠以不可忽略的優勢攻破一個單向 PRE 方案。定義定義 2.23 （Unidirectional-PRE-CA 安

35、全）. 若對于任意一個多項式時間的敵手，如下概率都是可以忽略的，則聲明一個單向代理重加密方案是抗合謀攻擊安全的（Unidirectional-PRE-CA 安全） 。.定義定義 2.24 （Unidirectional-PRE-Full 安全）. 若一個代理重加密方案同時具備 Unidirectional-PRE-CCA 安全和 Unidirectional-PRE-CA 安全，則聲明該單向代理重加密方案是完全安全的（Unidirectional-PRE-Full 安全） 。2.4.4 PRE 方案對比(1) 特性對比本文在本章 2.4.2 節中描述了代理重加密的 9 個特性，本節將據此對現有

36、的代理重加密方案進行對比分析。表 2-1 中列舉了當前具有代表性的代理重加密方案。表 2-1 代理重加密方案的特性對比方案123456789Error! Reference source not found.NoYesYesYesYesNoNoNoNoError! YesNoYesYesYesYesYesNoYes第二章 預備知識Reference source not found.-1Error! Reference source not found.-2YesNoYesYesYesYesYesNoYesError! Reference source not found. YesNoYesY

37、esYesYesYesYesYesError! Reference source not found.-1NoYesNoYesYesNoNoNoNoError! Reference source not found.-2NoYesNoYesYesNoNoNoNoError! Reference source not found.-1YesNoYesNoYesYesNoNoYesError! Reference source not found.-2YesNoYesNoYesYesNoYesYesError! Reference source not found.NoNoYesNoYesNoNo

38、NoNoError! Reference source not found.-1YesNoYesYesNoYesYesNoYesError! Reference source not found.-YesNoYesYesNoYesYesYesYes第二章 預備知識2Error! Reference source not found.YesNoYesYesYesYesYesNoYesError! Reference source not found.YesNoYesYesYesYesYesNoYesError! Reference source not found.YesYesYesNoYesY

39、esYesNoYesError! Reference source not found.YesNoYesYesYesYesYesNoYesError! Reference source not found.YesNoYesNoYesYesYesNoYes從表 2-1 中，我們可以直觀地發現，目前還沒有一個代理重加密方案能夠同時滿足這 9 個特性。但隨著研究的深入，方案能夠滿足的特性也越來越多。其中，復用性可以提高方案執行效率，暫時性可以增強方案的靈活性和實用性。然而，表 1 中僅有 4 個方案滿足復用性，3 個方案滿足暫時性。因此，對于這兩個特性還需要進一步關注。(2) 性能對比 本節從計算開

40、銷、存儲開銷和安全性質三個方面比較、分析了表 2-1 中各個PRE 方案的性能，如表 2-2 與表 2-3 所示。在本節性能對比中，我們忽略了 hash運算、異或操作以及循環群上的乘法、加法運算，因為它們的計算開銷遠比指數運算和對運算要小。表中涉及的符號解釋如下，p、e 和 ep：分別表示一個雙線性對運算、一個指數運算以及一個上的指數運算的運行時間；s和 v：分別表示一次簽名和一次簽名驗證所需的時間；S.enc 和 S.dec：分別表示執行一次對稱加密和解密所需的時間；k、和：分別表示一個安全參數以及和的比特長度；、和：分別表示、以及中元素的長度； |s|和|：分別表示一次簽名密鑰和一次簽名的

41、長度； |T|：時間戳的長度；：消息 m 的長度；|S.enc|：一次對稱加密密文的長度；、和：分別表示安全素數模量的長度；ROM 和 STM：分別表示隨機預言機模型和標準模型。通過觀察表 2-2 和表 2-3，相比基于雙線性對的代理重加密方案，那些不依靠這一計算昂貴的數學工具構造的代理重加密方案無論在計算開銷還是存儲開銷方面都要高效很多。另外，在隨機預言機模型下，文獻Error! Reference source not found.Error! Reference source not found.中的代理重加密方案性能要優于其它方案，其滿足 CCA 安全性，加解密效率較高，且密鑰與密文長

42、度適中。在標準模型下，所有方案都是利用雙線性對構造的，其中 Canetti 等人 Error! Reference source not found.構造的代理重加密方案性能較好，與其它幾個方案相比，它的密鑰和密文更短，計算效率更高。表 2-2 代理重加密方案的計算開銷對比計算開銷方案加密解密重加密重加密密文解密無雙線性對Error! Reference source not 2e1e1e1e第二章 預備知識found.Error! Reference source not found.-11p+1e+2ep1p+1ep1p1epError! Reference source not foun

43、d.-21p+1e+2ep1p+1ep1p1epError! Reference source not found. 1p+1e+2ep1p+1ep1p1epError! Reference source not found.-11p+3e+1ep+1s5p+1e +1v4p+1e +1v5p+1e +1vError! Reference source not 1p+3e+1ep+1s5p+1e +1v4p+1e +1v5p+1e +1vfound.-2Error! Reference source not found.-11p+5e+1ep+1s3p+1e+1ep+1v2p+4e +1v5p

44、+1e+1ep+1vError! Reference source not found.-21p+5e+1ep+1s3p+1e+1ep+1v2p+4e +1v5p+1e+1ep+1vError! Reference source not found.3e4e3e2eError! Reference source not found.-15e5e4e4eError! Reference source 5e5e4e4e第二章 預備知識not found.-2Error! Reference source not found.3e4e3e4eError! Reference source not f

45、ound.7e+1s7e4e+1v7eError! Reference source not found.1p+2e+2ep+1s3p+3e+1ep+1v6p+6e+3ep+1s+1v9p+7e+3ep+3vError! Reference source not found.kp+2e+2ep+1s3p+4e+1ep7p+5e3p+2e+2epError! Reference source not found.1p+7e+1S.enc5p+1e+1ep4p+5e+1S.enc8p+3e+1ep+1S.dec表 2-3 代理重加密方案的計算開銷對比密鑰長度密文長度方案公鑰私鑰重加密密鑰原密文重加

46、密密文安全性Error! Reference source not found.2CPA, ROM, CDHError! Reference source not found.-12CPA, ROM, q-DBDHIError! Reference source not found.-222CPA, ROM, e-DBDHError! Reference source not found. 222CPA, ROM, DBDHError! Refere33CCA, ROM, m-DBDH第二章 預備知識nce source not found.-1Error! Reference source

47、not found.-233CCA, STM, DBDHError! Reference source not found.-144RCCA, STM, 3-QDBDHError! Reference source not found.-244RCCA, STM, 4-QDBDHError! Reference source not found.2CCA, ROM, CDHError! 32CCA, ROM, Reference source not found.-1+2kDDHError! Reference source not found.-232+2kCCA, ROM, DDHErro

48、r! Reference source not found.2222CCA, ROM, CDHError! Reference source not found.222CCA, ROM, CDHError! Reference source not found.CCA, STM, 2-ABDHEError! RefereCCA, STM, 3-wDBDHI第二章 預備知識nce source not found.Error! Reference source not found.322CCA, STM, 6-AmDBDH2.5 密鑰泄露2.5.1 問題描述對于密碼系統而言，密鑰泄露攻擊被認為是

49、危害性最大的一類攻擊，因為密碼算法（如：加密、解密和簽名生成等）通常被放到一個相對不安全的設備（如：移動設備或者聯網設備）上來執行，而由此類設備維護的密鑰將不可避免的發生泄露。因此，密鑰泄露問題可能是密碼學在實際應用中存在的最大威脅：相對于解決密碼系統中的困難性問題，攻擊者很容易從單純、不設防的用戶那里獲得密鑰。當今社會，隨著越來越多的用戶使用移動互聯設備，密鑰泄露問題的威脅也隨之增加。2.5.2 解決方法針對公鑰密碼體制存在的密鑰泄露問題，通常存在三種解決方法：1、 在線密鑰生成中心：在線密鑰生成中心是一個協助用戶實現密鑰更新的可信機構。然而，當系統中的用戶量不斷增加時，密鑰生成中心將承受巨大的計算、通信開銷負荷，嚴重將導致系統癱瘓。此外，用戶與 PKG交互時也會犧牲大量的通信開銷。2、 分布式密鑰存儲技術：下面介紹了基于分布式存儲技術的三種抗密鑰泄露方法，(1) 秘密共享（Secret Sharing）技術Error! Reference