公鑰密碼體制的研究(2)

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

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

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

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

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

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

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

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

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

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

11、備破壞該密碼系統(tǒng)的能力。如果一個(gè)密碼系統(tǒng)是安全的，那么我們必須給出說明任意一個(gè)攻擊者能夠弱化該密碼系統(tǒng)的可能性都非常小?；谟螒虻陌踩Ｐ鸵呀?jīng)被廣泛接受，且已被應(yīng)用于多種類型的密碼系統(tǒng)的安全性證明，包括數(shù)字簽名、非對(duì)稱加密和對(duì)稱加密。本文所描述的形式化安全模型都是基于游戲的安全模型?；谟螒虻陌踩Ｐ偷膬?yōu)點(diǎn)是容易理解和實(shí)現(xiàn)。然而，Canetti 等Error! Reference source not found.發(fā)現(xiàn)基于游戲安全模型下的安全性證明只能獨(dú)立的證明密碼系統(tǒng)的安全性，無法說明當(dāng)該密碼系統(tǒng)部署于復(fù)雜環(huán)境下時(shí)也是可證明安全的。大部分密第二章 預(yù)備知識(shí)碼方案都不是獨(dú)立存在的，而是作為大型

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

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

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

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

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

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

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

19、安全性。定義定義 2.18 選擇密文攻擊（）選擇密文攻擊也稱為午餐時(shí)間攻擊，是一種比選擇明文攻擊稍強(qiáng)的攻擊模型。在選擇密文攻擊中，敵手可以訪問一個(gè)黑盒，這個(gè)黑盒能進(jìn)行解密。在午餐時(shí)間，敵手可以選擇多項(xiàng)式個(gè)密文來詢問解密盒，解密盒把解密后的明文發(fā)送給敵手。在下午時(shí)間，敵手被告知一個(gè)目標(biāo)密文，要求敵手在沒有解密盒的情況下解密目標(biāo)密文，或者找到關(guān)于明文的有用信息。 已知一個(gè)解密預(yù)言機(jī)，敵手任意選取密文，并詢問解密預(yù)言機(jī)，從而產(chǎn)生對(duì)應(yīng)的明文。敵手的目標(biāo)是利用已獲得的明-密文對(duì)破壞密碼系統(tǒng)的安全性。當(dāng)敵手結(jié)束解密預(yù)言機(jī)詢問后，如果敵手能夠從給定的目標(biāo)密文中獲得相應(yīng)的明文消息，則認(rèn)為攻擊成功。也就是說，一

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

21、egator）公鑰加密的密文轉(zhuǎn)換為被委托者（Delegatee）對(duì)同一明文加密的密文，然后被委托者可利用其自身私鑰解密該轉(zhuǎn)換后的密文。在轉(zhuǎn)換過程中，代理者必須擁有一個(gè)由委托者授權(quán)的針對(duì)被委托者的密文轉(zhuǎn)換密鑰（即代理重加密密鑰） ，同時(shí)，該代理者無法獲知關(guān)于密文中對(duì)應(yīng)明文的任何信息。然而，在文獻(xiàn)Error! Reference source not found.中，Blaze 等人并沒能給出規(guī)范的形式化定義，從而導(dǎo)致 PRE 在 19982004 年間發(fā)展緩慢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 上第一次對(duì)代理重加密進(jìn)行了形式化定義。此后，代理重加密成為密碼學(xué)和信息安全領(lǐng)域的一個(gè)研究熱點(diǎn)，積累了大量研究成果。本節(jié)將對(duì) PRE 的形式化定義、安全模型以及特性進(jìn)行簡要描述。2.4.1 形式化定義定義定義 2.20 代理重加密（Proxy Re-Encryption，PRE）. 一個(gè) PRE 方案可由算法、構(gòu)成： (1)：輸入安全參數(shù)，密鑰生成算法為用戶 i 輸出一對(duì)公/私鑰；(2)：輸入 Alice

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

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

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

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

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

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

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

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

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

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

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

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

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

36、的代理重加密方案進(jìn)行對(duì)比分析。表 2-1 中列舉了當(dāng)前具有代表性的代理重加密方案。表 2-1 代理重加密方案的特性對(duì)比方案123456789Error! Reference source not found.NoYesYesYesYesNoNoNoNoError! YesNoYesYesYesYesYesNoYes第二章 預(yù)備知識(shí)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第二章 預(yù)備知識(shí)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 中，我們可以直觀地發(fā)現(xiàn)，目前還沒有一個(gè)代理重加密方案能夠同時(shí)滿足這 9 個(gè)特性。但隨著研究的深入，方案能夠滿足的特性也越來越多。其中，復(fù)用性可以提高方案執(zhí)行效率，暫時(shí)性可以增強(qiáng)方案的靈活性和實(shí)用性。然而，表 1 中僅有 4 個(gè)方案滿足復(fù)用性，3 個(gè)方案滿足暫時(shí)性。因此，對(duì)于這兩個(gè)特性還需要進(jìn)一步關(guān)注。(2) 性能對(duì)比 本節(jié)從計(jì)算開

40、銷、存儲(chǔ)開銷和安全性質(zhì)三個(gè)方面比較、分析了表 2-1 中各個(gè)PRE 方案的性能，如表 2-2 與表 2-3 所示。在本節(jié)性能對(duì)比中，我們忽略了 hash運(yùn)算、異或操作以及循環(huán)群上的乘法、加法運(yùn)算，因?yàn)樗鼈兊挠?jì)算開銷遠(yuǎn)比指數(shù)運(yùn)算和對(duì)運(yùn)算要小。表中涉及的符號(hào)解釋如下，p、e 和 ep：分別表示一個(gè)雙線性對(duì)運(yùn)算、一個(gè)指數(shù)運(yùn)算以及一個(gè)上的指數(shù)運(yùn)算的運(yùn)行時(shí)間；s和 v：分別表示一次簽名和一次簽名驗(yàn)證所需的時(shí)間；S.enc 和 S.dec：分別表示執(zhí)行一次對(duì)稱加密和解密所需的時(shí)間；k、和：分別表示一個(gè)安全參數(shù)以及和的比特長度；、和：分別表示、以及中元素的長度； |s|和|：分別表示一次簽名密鑰和一次簽名的

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

42、度適中。在標(biāo)準(zhǔn)模型下，所有方案都是利用雙線性對(duì)構(gòu)造的，其中 Canetti 等人 Error! Reference source not found.構(gòu)造的代理重加密方案性能較好，與其它幾個(gè)方案相比，它的密鑰和密文更短，計(jì)算效率更高。表 2-2 代理重加密方案的計(jì)算開銷對(duì)比計(jì)算開銷方案加密解密重加密重加密密文解密無雙線性對(duì)Error! Reference source not 2e1e1e1e第二章 預(yù)備知識(shí)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第二章 預(yù)備知識(shí)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 代理重加密方案的計(jì)算開銷對(duì)比密鑰長度密文長度方案公鑰私鑰重加密密鑰原密文重加

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第二章 預(yù)備知識(shí)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第二章 預(yù)備知識(shí)nce source not found.Error! Reference source not found.322CCA, STM, 6-AmDBDH2.5 密鑰泄露2.5.1 問題描述對(duì)于密碼系統(tǒng)而言，密鑰泄露攻擊被認(rèn)為是

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