陳 宇, 易紅旭, 王煜宇

1.山東大學 網(wǎng)絡(luò)空間安全學院, 青島 266237

2.密碼科學技術(shù)全國重點實驗室, 北京 100878

3.山東大學 密碼技術(shù)與信息安全教育部重點實驗室, 青島 266237

4.電子科技大學, 成都 611731

1 引言

密碼幾乎與文字一樣古老, 發(fā)展歷程大概可以分為以下兩個階段:

? 古典階段: 該階段的密碼內(nèi)涵局限于加密方案.在古典密碼早期, 密碼就已經(jīng)廣泛應(yīng)用于戰(zhàn)爭的機密通信中, 密碼方案的安全性依賴于對其本身的保密, 最為著名的是Caesar 密碼, 其本質(zhì)是將字母循環(huán)后移三位進行簡單的單表代換加密.在古典密碼中期, 密碼的安全性擺脫對于系統(tǒng)保密性的依賴, 轉(zhuǎn)向?qū)γ荑€的保密, 代表性的方案是多表代換加密的Vigènre 密碼, 其不斷重復密鑰并與加密消息進行相加.在古典密碼后期, 人們進一步發(fā)展Caesar、Vigènre 等簡單代換、置換密碼的設(shè)計思想, 設(shè)計出古典密碼的巔峰代表Enigma 密碼, 其代換規(guī)則是動態(tài)的, 每加密一個字母的消息后, 隨著內(nèi)部諸多轉(zhuǎn)子的位置變化, 代換規(guī)則動態(tài)地改變, 從而使得代換、置換關(guān)系更為復雜.總的來說, 古典階段的密碼通常由代換和置換構(gòu)成, 缺少系統(tǒng)的設(shè)計方法論, 一旦加密方案暴露, 容易受到密碼分析而被攻破, 從而陷入了“攻破-修復” 的循環(huán), 密碼的設(shè)計更類似于一種“藝術(shù)”, 而非“科學”[1].

? 現(xiàn)代階段: 現(xiàn)代階段的早期, Shannon 在著名論文《密碼學的數(shù)學理論》[2]首次使用概率論的方法對密碼系統(tǒng)的安全性進行了精準刻畫, 奠定了現(xiàn)代密碼學的基礎(chǔ), 使得密碼學從“藝術(shù)” 走向“科學”.隨著信息化的加速, 密碼也從軍用擴展到商用和民用, Feistel 基于可逆計算的概念設(shè)計了Feistel 密碼體系[3], 該體系在對稱密碼的理論和實踐上都占據(jù)重要地位, 對稱密碼的設(shè)計與分析逐漸形成較為系統(tǒng)的方法, 對稱密碼標準DES (data encryption standard) 應(yīng)運而生; 現(xiàn)代階段的中期, 計算設(shè)備的算力飛速提升、計算環(huán)境由集中式遷移到分布式, 信息技術(shù)的迅猛發(fā)展對密碼學提出了新的挑戰(zhàn).1976 年, Diffie 與Hellman 發(fā)表了著名的論文《密碼學的新方向》[4], 其中蘊含的“不對稱” 思想標志著公鑰密碼學的誕生.Goldwasser 和Micali[5]給出了公鑰加密的合理安全性定義—語義安全, 構(gòu)造出了滿足語義安全的概率公鑰加密方案, 并在此過程中開創(chuàng)了可證明安全的方法, 即借助計算復雜性理論中的歸約技術(shù)將密碼系統(tǒng)的安全性嚴格歸結(jié)為計算困難問題的困難性.此后, 密碼學蓬勃發(fā)展, 內(nèi)涵不斷豐富, 從加密、簽名和密鑰交換擴展到零知識證明[6]、安全多方計算[7]等.2000 年以后至今, 信息化技術(shù)進一步高速發(fā)展, 面對更為多樣的應(yīng)用需求和更強的攻擊手段, 函數(shù)加密、全同態(tài)加密等高功能密碼方案和抗泄漏、抗篡改等高等級安全相繼出現(xiàn)[8].總的來說, 區(qū)別于古典階段密碼設(shè)計的“隨意的藝術(shù)”, 現(xiàn)代密碼學與計算復雜性理論結(jié)合更為緊密, 建立起豐富的歸約網(wǎng)絡(luò)[9], 強調(diào)形式化的定義、準確的計算困難假設(shè)和嚴謹?shù)目勺C明安全的技術(shù)框架.

本文將按照安全性增強和功能性擴展這兩條并行的線索對公鑰加密的發(fā)展歷程和前沿進展做系統(tǒng)綜述.在密碼學的發(fā)展歷程中, 當具有新的功能性或安全性的方案被提出后, 密碼學家通常先給出若干具體方案, 然后隨著研究的深入再抽象出更基本的密碼原語, 進而以它們?yōu)榈讓咏M件給出通用構(gòu)造.通用構(gòu)造不僅能夠總結(jié)一般的方法對既有方案進行分類, 還能凝練關(guān)鍵的思想從而加深對密碼方案本質(zhì)的認識、啟發(fā)新的構(gòu)造, 因此極具價值.為了引領(lǐng)讀者從更高的觀點回顧公鑰加密, 本文注重對通用構(gòu)造的介紹, 其中所涉及的底層密碼原語將有助于讀者拓展知識面、加深理解認知.

2 預備知識

2.1 符號與記號

對于自然數(shù)n ∈N,[n]表示集合{1,2,···,n},Zn表示集合{0,1,···,n?1},Z?n表示集合{x ∈Zn|gcd(x,n) = 1}.對于集合X,|X| 表示其大小; 對于變量x,|x| 表示其二進制表示長度.xR←?X表示對集合X進行隨機采樣, 得到元素x.本文使用λ ∈Z+表示安全參數(shù).如果關(guān)于λ的函數(shù)小于任意關(guān)于λ的多項式的逆, 則稱其是可忽略的(記作negl); 如果一個隨機算法的運行時間由關(guān)于λ的多項式函數(shù)界定, 則稱其是概率多項式時間的(記作PPT).

2.2 公鑰加密的定義與安全性

Diffie 和Hellman[4]在1976 年的劃時代論文中正式提出公鑰加密(public-key encryption, PKE),其與對稱加密的根本差別在于每個用戶自主生成一對密鑰, 公鑰用于加密、私鑰用于解密, 發(fā)送方僅需知曉接收方的公鑰即可向接收方發(fā)送密文.

定義1 (公鑰加密方案) 公鑰加密方案由以下四個PPT 算法組成(如圖1 所示):

圖1 公鑰加密方案示意圖Figure 1 Schematic diagram of public-key encryption scheme

? Setup(1λ): 系統(tǒng)生成算法以安全參數(shù)1λ為輸入, 輸出系統(tǒng)公開參數(shù)pp.pp 通常包含系統(tǒng)中所有用戶可共享的信息, 如公鑰空間PK、私鑰空間SK、明文空間M和密文空間C的描述.1系統(tǒng)公開參數(shù)的內(nèi)容并沒有嚴格規(guī)定, 在一些例子中可能退化為⊥: 如對于RSA 公鑰加密方案, 明文空間和密文空間均與公鑰相關(guān), 所以由算法KeyGen 輸出.該算法由可信第三方運行, 生成的pp 將作為以下所有算法的輸入.當上下文明確時, 常常為了行文簡潔省去pp.

? KeyGen(pp): 密鑰生成算法以系統(tǒng)公開參數(shù)pp 為輸入, 輸出公/私鑰對(pk,sk), 其中公鑰公開,私鑰由用戶秘密保存.

? Encrypt(pk,m;r): 加密算法以公鑰pk∈PK、明文m ∈M和隨機數(shù)r為輸入, 輸出密文c ∈C.

? Decrypt(sk,c): 解密算法以私鑰sk∈SK 和密文c ∈C為輸入, 輸出明文m′∈M或者⊥表示密文非法.解密算法通常為確定性算法.

正確性.該性質(zhì)刻畫公鑰加密的功能性, 確保使用私鑰可以正確恢復出對應(yīng)公鑰加密的密文.正式地,對于任意明文m ∈M, 有:

公式(1)的概率建立在Setup(1λ)→pp、KeyGen(pp)→(pk,sk) 和Encrypt(pk,m)→c的隨機帶上.如果上述概率嚴格等于1, 則稱公鑰加密方案滿足完美正確性.基于數(shù)論假設(shè)的公鑰加密方案通常滿足完美正確性, 而格基方案由于底層困難問題的誤差屬性, 解密算法往往存在誤差.

安全性.令A=(A1,A2) 是攻擊公鑰加密方案安全性的敵手, 定義其優(yōu)勢函數(shù)如下:

在上述定義中,A= (A1,A2) 表示敵手A可劃分為兩個階段, 劃分界線是接收到挑戰(zhàn)密文c?的時候,state 表示A1向A2傳遞的信息, 記錄部分攻擊進展.Odecrypt(·) 表示解密諭言機, 其在接收到密文c的詢問后輸出Decrypt(sk,c).如果任意PPT 敵手在階段1 和階段2 均可自適應(yīng)訪問Odecrypt(·) 的情形下仍僅具有可忽略優(yōu)勢, 則稱公鑰加密方案滿足選擇密文攻擊下的不可區(qū)分(indistinguishability against chosen-ciphertext attack, IND-CCA) 安全, 或者也可稱為IND-CCA2 安全; 如果任意PPT 敵手僅在階段1 可自適應(yīng)訪問Odecrypt(·) 的情形下具有可忽略優(yōu)勢, 則稱公鑰加密方案滿足IND-CCA1 安全.如果任意不可訪問Odecrypt(·) 的PPT 敵手A在上述游戲中的優(yōu)勢函數(shù)均為可忽略函數(shù), 則稱公鑰加密方案滿足選擇明文攻擊下的不可區(qū)分(indistinguishability against chosen-plaintext attack, IND-CPA) 安全.

3 公鑰密碼學發(fā)展的兩條主線

在1976 年Diffie 和Hellman 的開創(chuàng)性論文[4]后, 公鑰密碼學的發(fā)展一日千里、日新月異, 熱潮持續(xù)至今, 孕育了很多新的密碼原語和重要技術(shù).

公鑰密碼的發(fā)展大體有兩條主線: 一條是安全性的增強, 從最初的直覺安全演進到可證明的語義安全,再到不可區(qū)分選擇密文安全和各類超越傳統(tǒng)安全模型的高級安全性, 如選擇打開攻擊安全、抗泄漏安全、抗篡改安全和消息依賴密鑰安全; 另一條是功能性的豐富, 從最初簡單的一對一加解密到可委派身份密鑰的身份加密, 再到支持細粒度訪問控制的屬性加密乃至極致泛化的函數(shù)加密和可對密文進行計算的(全)同態(tài)加密.本文將按照這兩條主線(如圖2 所示) 梳理公鑰密碼學的發(fā)展歷程, 介紹重要的成果.

圖2 公鑰加密發(fā)展主線Figure 2 Development of public-key encryption

4 安全性增強

本文在綜述安全性增強這條發(fā)展主線時, 如果不特意提及, 則約定密碼方案為標準的公鑰加密方案(定義1).

4.1 傳統(tǒng)安全模型

對于密碼方案, 給出恰當?shù)陌踩远x至關(guān)重要, 安全性在必須可達的同時又須足夠強以刻畫現(xiàn)實中存在的攻擊.

隨著應(yīng)用場景的不斷豐富和攻擊手段的不斷增強, 公鑰加密的安全性是從弱到強逐漸提升的, 強安全的公鑰加密方案往往基于弱安全的公鑰加密方案構(gòu)造.

1976 年, Diffie 和Hellman[4]首次提出了公鑰加密的概念但并沒有給出具體方案構(gòu)造.1978 年,Rivest 等[10]基于數(shù)論問題構(gòu)造出了首個公鑰加密方案—RSA 加密.在這一階段, 公鑰加密的安全性僅具備符合直覺的單向性, 即在平均意義下從密文中恢復出明文是計算困難的.到上世紀80 年代, 密碼學家們逐漸認識到單向性并不足以滿足現(xiàn)實的隱私保護需求.具體來說, 對于單向安全的公鑰加密方案, 敵手盡管無法從密文中恢復出明文的全部信息, 但有可能恢復出明文的部分信息.而在應(yīng)用中, 由于數(shù)據(jù)來源的多樣性和不確定性,明文的每一比特都可能包含關(guān)鍵的機密信息(比如股票交易指令中的“買”或“賣”).

1982 年, Goldwasser 和Micali[5]發(fā)展了可證明安全的技術(shù)框架: 建立安全模型以準確刻畫敵手的攻擊行為和攻擊效果, 將密碼方案的安全性歸約到計算困難問題的困難性上.此外, Goldwasser 和Micali還指出單向安全的不足, 提出了公鑰加密的合理定義—語義安全(semantic security).語義安全的直觀含義是密文不泄漏關(guān)于明文額外的有效知識, 因此密文對敵手求解明文沒有幫助.嚴格定義頗為精妙, 定義的形式是基于模擬的, 即掌握密文的敵手的視角可以由一個不掌握密文的PPT 模擬器在計算意義下模擬出來.語義安全性可以看做Shannon 完美安全在計算意義的對應(yīng), 然而在論證的時候稍顯繁瑣笨重.

Goldwasser 等[5,11]給出了另一個等價的定義(等價性證明參見Dodis 和Ruhl 的短文[12]), 即選擇明文攻擊下的不可區(qū)分性(indistinguishability against chosen-plaintext attack, IND-CPA).IND-CPA安全定義的直覺是密文在計算意義下不泄漏明文的任意一比特信息, 即任意兩個明文對應(yīng)的密文分布是計算不可區(qū)分的, 其中選擇明文攻擊刻畫了公鑰公開特性使得任意敵手均可通過自行加密獲得任意明文對應(yīng)密文這一事實.使用IND-CPA 安全進行安全論證相比語義安全要便捷很多, 因此被廣為采用.

選擇密文安全.IND-CPA 安全僅考慮被動敵手, 即敵手只竊聽信道上的密文.1990 年, Naor 和Yung[13]指出敵手有能力發(fā)起一系列主動攻擊, 比如重放密文、修改密文等, 進而提出選擇密文攻擊(chosen-ciphertext attack, CCA) 刻畫這一系列主動攻擊行為, 允許敵手自適應(yīng)地獲取指定密文對應(yīng)的明文; 所對應(yīng)的安全性稱為選擇密文攻擊下的不可區(qū)分性(indistinguishability against chosen-ciphertext attack, IND-CCA), 即IND-CCA 安全.Naor 和Yung 考慮了兩種選擇密文攻擊, 一種是弱化版本, 稱為午餐時間攻擊(lunch-time attack), 含義是敵手只能在極短的時間窗口(收到挑戰(zhàn)密文之前) 進行選擇密文攻擊, 該攻擊類型對應(yīng)IND-CCA1 安全; 另一種是標準版本, 敵手可在長時間窗口(收到挑戰(zhàn)密文前后)進行選擇密文攻擊, 該攻擊類型對應(yīng)IND-CCA2 安全, 或簡稱為IND-CCA 安全.

1998 年, Bleichenbacher[14]展示了針對PKCS#1 標準中公鑰加密方案的有效選擇密文攻擊, 從而實證了關(guān)于IND-CCA 安全的研究并非杞人憂天, 而是具有重要的實際意義.從此, IND-CCA 安全成為了公鑰加密方案的事實標準.根據(jù)模型劃分, 構(gòu)造IND-CCA 安全的公鑰加密方案有以下主流的方法技術(shù):

? 隨機諭言機模型下:

– OAEP (optimal asymmetric encryption padding) 轉(zhuǎn)換.Bellare 等[15]提出了隨機諭言機模型(random oracle, RO), 而后在文獻[16] 提出了一種基于陷門置換構(gòu)造IND-CCA 安全PKE方案的通用轉(zhuǎn)換, 即OAEP 轉(zhuǎn)換.Shoup[17]指出OAEP 轉(zhuǎn)換并不是對所有的陷門置換成立.Fujisaki 等[18]則進一步指出了OAEP 轉(zhuǎn)換應(yīng)該滿足的條件, 并提出了基于RSA 類型陷門置換的RSA-OAEP 方案.

– Fujisaki-Okamoto (FO) 類提升安全性的通用轉(zhuǎn)換.Fujisaki 和Okamoto[19]首先提出了在RO 模型下利用混合加密將IND-CPA 安全的PKE 方案提升為IND-CCA 安全的PKE 方案的通用轉(zhuǎn)換, 其核心思想是引入哈希函數(shù)綁定密文的各部分使得密文不可延展.Fujisaki 和Okamoto 在同年[20]將底層PKE 方案的安全性從IND-CPA 安全弱化為單向安全, 這一通用轉(zhuǎn)換稱為FO 轉(zhuǎn)換[20,21].類似的通用轉(zhuǎn)換還有許多, 但其核心思想均與FO 轉(zhuǎn)換相似, 如Pointcheval[22]在RO 模型下將單向陷門函數(shù)轉(zhuǎn)換為IND-CCA 安全的PKE 方案, 又如Okamoto 和Pointcheval[23]提出的REACT 通用轉(zhuǎn)換.

– FO 類通用轉(zhuǎn)換的改進.由于FO 轉(zhuǎn)換思想簡潔、轉(zhuǎn)換高效, 近期的工作主要是在FO 轉(zhuǎn)換的基礎(chǔ)上進行改進.Hofheinz 等[24]將FO 轉(zhuǎn)換分為去隨機化重加密和哈希映射兩個部分進行模式化分析, 將類似于FO 轉(zhuǎn)換的通用轉(zhuǎn)換, 例如REACT[23]、GEM[25]等統(tǒng)一在一起, 闡明了底層PKE 方案的性質(zhì)、密文結(jié)構(gòu)的不同對FO 轉(zhuǎn)換后得到的PKE 方案安全性的影響, 并推廣FO 轉(zhuǎn)換到量子RO 模型下.后續(xù)的工作則集中在提升文獻[24] 中的歸約效率[26]或者降低密文開銷[27,28].

? 標準模型下:

– 使用非交互零知識證明將任意IND-CPA 安全的PKE 強化為IND-CCA 安全.Naor 和Yung[13]首次提出雙密鑰加密策略結(jié)合非交互零知識證明(non-interactive zero-knowledge proof, NIZK) 將任意IND-CPA 安全的PKE 方案轉(zhuǎn)換為IND-CCA1 安全; Dolev 等[29]設(shè)計出矩陣式加密結(jié)構(gòu), 結(jié)合一次性不可偽造簽名(one-time signature, OTS) 和NIZK 將任意IND-CPA 安全的PKE 方案提升至IND-CCA 安全; 受上述兩個工作啟發(fā), Sahai[30]展示如何用OTS 將普通NIZK 強化為模擬穩(wěn)固(simulation soundness, SS) 的NIZK, 以此為工具應(yīng)用Naor-Yung 雙重加密范式, 將任意IND-CPA 安全的PKE 方案強化為IND-CCA 安全.Biagioni 等[31]和Cramer 等[32]分別給出了Naor-Yung 雙重加密范式的兩個變體, 前者對加密隨機數(shù)進行了安全的重用, 后者使用了新的加密重復策略和消息一致性證明方法.

– 基于弱化的非交互式零知識證明構(gòu)造IND-CCA 安全的PKE.Cramer 和Shoup[33]提出了一種特殊的指定驗證者非交互式零知識證明(designated-verifier NIZK, DV-NIZK)—哈希證明系統(tǒng)(hash proof system, HPS), 并基于HPS 給出了一類基于判定性困難問題的IND-CCA安全的PKE 方案的通用構(gòu)造.Wee[34]提出了一種特殊的指定驗證者非交互式零知識的知識證明—可提取哈希證明系統(tǒng)(extractable HPS, EHPS), 并基于EHPS 給出了一類基于搜索性困難問題的IND-CCA 安全的PKE 方案的通用構(gòu)造, 該構(gòu)造不僅解釋了已有的方案[35–37], 還啟發(fā)了基于CDH 假設(shè)的新PKE 方案的設(shè)計.

– 以結(jié)構(gòu)更豐富的加密方案為起點構(gòu)造IND-CCA 安全的PKE.Boneh 等[38]以身份加密(identity-based encryption, IBE) 為底層方案, 結(jié)合OTS 或消息驗證碼(message authentication code, MAC) 構(gòu)造出IND-CCA 安全的PKE 方案.Kiltz[39]將IBE 弱化為基于標簽的加密(tag-based encryption, TBE), 結(jié)合OTS 構(gòu)造出IND-CCA 安全的PKE 方案.

– 基于更強的單向陷門函數(shù).Kiltz 等[40]提出了自適應(yīng)單向陷門函數(shù)(adaptive trapdoor functions, ATDF), 并基于此給出了IND-CCA 安全的PKE 方案的通用構(gòu)造.該構(gòu)造簡潔優(yōu)雅, 并且涵蓋了基于有損陷門函數(shù)[41]和相關(guān)積單向函數(shù)[42]的構(gòu)造.最近的突破性結(jié)果是Hohenberger 等[43]展示了如何僅基于單射陷門函數(shù)構(gòu)造IND-CCA 安全的PKE.

– 基于不可區(qū)分混淆的編譯器.Sahai 和Waters[44]引入可穿孔偽隨機函數(shù), 借助不可區(qū)分混淆(indistinguishability obfuscation,iO) 構(gòu)造出IND-CCA 安全的PKE 方案.該構(gòu)造實現(xiàn)了Diffie 和Hellman 自20 世紀70 年代起的愿景, 展示了如何將對稱加密編譯為公鑰加密.

– Chen 等[45]提出了可公開求值偽隨機函數(shù), 并基于此給出了PKE 方案的通用構(gòu)造.該構(gòu)造不僅從更抽象的層次闡釋了經(jīng)典的GM 加密方案[5]和ElGamal 加密方案[46]的設(shè)計思想, 還統(tǒng)一了基于(可提取) 哈希證明系統(tǒng)、單向陷門函數(shù)、可穿孔偽隨機函數(shù)與iO的構(gòu)造.

選擇打開安全.IND-CPA 安全模型和IND-CCA 安全模型主要考慮一對一的兩方通信場景, 但是PKE 方案常常被應(yīng)用到多對多的分布式協(xié)議當中.例如考慮如下場景,n ?1 個發(fā)送者用某用戶的公鑰對某輪協(xié)議中(相關(guān)聯(lián)) 的消息進行加密, 并發(fā)送給該用戶.此時存在一個強力的敵手, 其腐化了該輪協(xié)議一部分消息發(fā)送方的計算機, 不僅獲得了他們密文對應(yīng)的明文, 還獲得了加密用的隨機數(shù).類似于兩方通信下PKE 方案的語義安全, 在多方的環(huán)境下, 仍然希望敵手不會獲得除了條件分布以外關(guān)于未腐化用戶的明文的有效知識.Bellare 等[47]首先考慮了上述的情景, 將這樣的安全性稱為選擇打開(selective opening, SO) 安全, 并從模擬和不可區(qū)分兩個角度分別給出了SO 安全的SIM-SO 和IND-SO 兩種形式化定義.同時, 他們也提出了有損加密(lossy encryption) 這一新概念.簡單來說, 有損加密有兩種加密模式, 單射模式下利用私鑰可以解密密文得到明文, 而有損模式下則是多個密文對應(yīng)到一個明文, 從而無法正確解密, 他們證明了有損加密方案本身為IND-SO-CPA 安全的, 而具有某種高效打開算法的有損加密方案本身為SIM-SO-CPA 安全的.但是上述的場景—多用戶根據(jù)同一個公鑰加密消息發(fā)送給某一用戶(敵手腐化發(fā)送方取得明文與加密隨機數(shù)) 與真實的多方協(xié)議相去甚遠.因此, Bellare 等[48]提出了一個新的場景—某一用戶根據(jù)多個用戶不同的公鑰加密發(fā)送不同的加密消息給不同的用戶(敵手腐化接收方取得私鑰).為了區(qū)分, 他們稱第一種場景下的安全性為發(fā)送者SO (sender SO, SSO) 安全, 第二種場景下的安全性為接受者SO (receiver SO, RSO) 安全.SO 安全的主要研究工作集中在如何構(gòu)造SSO 安全和RSO 安全的PKE 方案上.

? SSO 安全的PKE 的構(gòu)造: Bellare 等[47]利用有損加密給出了SSO 安全的PKE 方案的構(gòu)造, 后續(xù)一系列研究延續(xù)Bellare 等的路線, 圍繞著有損加密方案的構(gòu)造展開.Hemenway 等[49]從多種密碼原語出發(fā)(例如同態(tài)加密、哈希證明系統(tǒng)等) 給出了有損加密的多種構(gòu)造方法, 結(jié)合All-But-N有損陷門函數(shù)進一步構(gòu)造出了IND-SSO-CCA 安全的PKE 方案.Hofheinz[50]將All-But-N有損陷門函數(shù)拓展為All-But-Many 有損陷門函數(shù), 構(gòu)造出了SIM-SSO-CCA 安全的PKE 方案.Fehr 等[51]則采取了另外一條有別于Bellare 的路徑.他們先證明了發(fā)送者模糊性(sender equivocable, NC) CCA 安全蘊含了SIM-SSO-CCA 安全, 然后給出一種基于哈希證明系統(tǒng)和交叉驗證碼構(gòu)造NC-CCA 安全的PKE 方案的通用方法, 進而構(gòu)造出SIM-SSO-CCA 安全的PKE方案.Huang 等[52]指出了Fehr 等[51]的證明中的問題, 并給出了一個可行的修正方法—將交叉驗證碼的性質(zhì)加強.格上SSO 安全的PKE 方案的構(gòu)造主要是從All-But-Many 有損陷門函數(shù)[53,54] 出發(fā).

? RSO 安全的PKE 的構(gòu)造: Hazay 等[55]首先利用接受者非承諾加密(non-committing encryption for receiver, NCER) 構(gòu)造了SIM-RSO-CPA 安全的PKE 方案, 并用NCER 的變體構(gòu)造了INDRSO-CPA 的PKE 方案.Jia 等[56]基于Naor-Yung 雙重加密范式給出了IND-RSO-CCA 安全的PKE 的通用構(gòu)造.該構(gòu)造將IND-RSO-CPA 安全的PKE 方案和CCA 安全的PKE 方案相結(jié)合, 并通過NIZK 轉(zhuǎn)換為IND-RSO-CCA 安全的PKE 方案.Hara 等[57]將類似的方法推廣到了SIM-RSO-CCA 安全的PKE 方案的構(gòu)造中, 并額外基于DDH 假設(shè)給出了一個效率較高的具體構(gòu)造.

孤立的SSO 安全或者是RSO 安全仍然與現(xiàn)實多對多分布式協(xié)議的安全性要求并不十分吻合, 后續(xù)有些研究開始考慮更為廣泛意義下的SO 安全性.例如, Lai 等[58]首次在一個模型下同時考慮SSO 和RSO 兩種安全性, 形式化提出了基于模擬的SIM-(w)Bi-SO-CCA 安全性, 并基于密鑰模糊性哈希證明系統(tǒng)這一新的密碼原語給出了SIM-wBi-SO-CCA 安全的PKE 方案的通用構(gòu)造.這些研究成果使得SO 安全的PKE 方案可以有效保障多對多分布式協(xié)議的安全.

另外, 除了關(guān)于SO 安全的PKE 方案具體構(gòu)造的研究外, SO 安全性與其他安全性間的強弱聯(lián)系等理論問題也得到了深入的研究.例如, Bellare 等[47,59]證明了SIM-SSO-CPA 安全性在黑盒意義上蘊涵IND-SSO-CPA 安全性; Bellare 等[48]證明了標準的IND-CPA 安全性不蘊涵SIM-SSO-CPA 安全性等.

消息依賴安全.IND-CPA 安全模型下敵手可以獲得消息對應(yīng)的密文, 而IND-CCA 安全模型下敵手還可以額外獲得選定密文對應(yīng)的明文, 除此之外, 敵手不能獲得其他與sk 有關(guān)的信息, 這通常無法契合復雜的現(xiàn)實應(yīng)用場景.以Windows 操作系統(tǒng)下最為知名的文件加密程序BitLocker[60]為例, 其不僅將保密文件經(jīng)過加密放在硬盤上, 還將相應(yīng)的密鑰對加密存儲在硬盤上, 那么對于惡意的敵手而言, 他不僅獲得了機密文件對應(yīng)的密文, 還獲得了私鑰的密文, 此類攻擊行為顯然無法被IND-CPA 安全和CCA 安全所刻畫, 類似的場景還有匿名證書系統(tǒng)[61]等.為了刻畫敵手可以獲得加密的私鑰的能力, Black 等[62]首先定義了消息依賴密鑰(key-dependent message, KDM) 安全, 其含義簡單來說就是, 即使敵手看到了與密鑰相關(guān)的密文, 密碼系統(tǒng)仍然可以保證通信的機密性.非正式地說, 假定n組密鑰對為{(ski,pki)}i∈[n],F為密鑰相關(guān)函數(shù)集, 如果PKE 方案的敵手在看到f(sk1,sk2,···,skn)(任何一個f ∈F下) 在所有pki下加密的密文后, 其他消息的機密性對于敵手而言仍然保持, 那么就稱該PKE 方案為F-KDM 安全的.顯然, 密鑰函數(shù)集F越大, 對應(yīng)的F-KDM 安全性越強, 而關(guān)于消息依賴密鑰安全研究的一個核心問題就在于如何擴大密鑰函數(shù)集F.

Boneh 等[60]基于DDH 假設(shè)構(gòu)造出首個KDM-CPA 安全的PKE 方案, 其支持的密鑰相關(guān)函數(shù)集為仿射函數(shù)Faff.Applebaum 等[63]基于LWE 假設(shè)構(gòu)造出另一個Faff-KDM-CPA 安全的PKE 方案.之后, Malkin 等[64]基于DCR 假設(shè)給出了一個相關(guān)密鑰函數(shù)集為次數(shù)有界多項式Fpoly的KDM-CPA安全的PKE 方案.Wee[65]基于同態(tài)的哈希證明系統(tǒng)給出了一個通用的KDM-CPA 安全的PKE 方案設(shè)計框架, 統(tǒng)一了諸多已有的具體構(gòu)造[60,66].

后續(xù)工作致力于構(gòu)造更強的KDM-CCA 安全的PKE 方案.Camenisch 等[67]指出Naor-Yung 雙重加密范式可將F-KDM-CPA 安全的PKE 方案強化為F-KDM-CCA 安全的PKE 方案.然而該通用方法的效率不高, 需要使用NIZK, 且密文尺寸為O(λ) 數(shù)量級.之后, Hofheinz[68]針對KDM 安全的一個特例—循環(huán)安全(circular security), 基于DCR、DDH 和DLIN 假設(shè)構(gòu)造了密文緊致(尺寸為O(1))的PKE 方案, 但是密文仍然包含50 個以上的群元素.Han 等[69]延續(xù)文獻[70] 的技術(shù)框架, 提出了一個密文緊致的Faff-KDM-CCA 安全的PKE 方案, 并進一步拓展為Fpoly-KDM-CCA 安全的PKE 方案.Kitagawa 等[71]基于DDH 假設(shè)構(gòu)造出了F-KDM-CCA 安全的PKE 方案, 密文尺寸為O(λ) 數(shù)量級.Kitagawa 等[72]提出對稱密鑰封裝這一新型密碼原語改進之前的方案, 得到了更為高效Faff-KDM-CCA安全的PKE 方案, 密文相較于Han 等[69]的Faff-KDM-CCA 安全的PKE 方案進一步減少了10 個以上的群元素, 而其Fpoly-KDM-CCA 安全的PKE 方案的密文長度相較于Han 等[69]的Fpoly-KDM-CCA安全的PKE 方案實現(xiàn)了數(shù)量級上的縮減, 當多項式次數(shù)的上界為d, 密文長度為O(d), 而Han 等[69]方案的密文長度為O(d9).

類似于SO 安全的研究,對KDM 安全的研究除了關(guān)于KDM 安全的PKE 方案的具體構(gòu)造,KDM 安全性與其他安全性間的強弱聯(lián)系等理論問題也得到了深入的研究.例如, Kitagawa 等[73]證明了KDMCPA 安全和KDM-CCA 安全在黑盒意義上是等價的; Waters 等[74]證明了對于PKE 方案而言, 單密鑰循環(huán)安全在黑盒意義上蘊含了支持相關(guān)函數(shù)集為任意有限深度電路的KDM 安全等.

4.2 超越傳統(tǒng)安全模型

IND-CPA 與IND-CCA 仍然屬于傳統(tǒng)安全模型范疇.傳統(tǒng)安全模型的一個基本假設(shè)是完美黑盒, 即密碼算法的軟硬件實現(xiàn)可以完美防護內(nèi)部秘密信息(如私鑰、隨機數(shù)), 敵手僅能以黑盒的方式通過預定義的接口收集信息以分析密碼算法, 而無法篡改或通過其他方式獲取內(nèi)部秘密信息.

完美黑盒假設(shè)可以細分為抗泄漏、抗篡改假設(shè):

? 抗泄漏: 敵手無法通過預定義接口以外的信道獲取秘密信息.

? 抗篡改: 敵手無法篡改密碼算法軟硬件實現(xiàn)及其中的秘密信息.

長久以來, 傳統(tǒng)安全模型的“完美黑盒” 假設(shè)被認為是合理穩(wěn)固的.然而, 自上世紀90 年代起, 密碼分析技術(shù)的飛速發(fā)展表明密碼算法的軟硬件實現(xiàn)難以達到真正的黑盒, 上述兩大假設(shè)均不成立.攻擊者既可以通過分析算法運行時間[75]、監(jiān)測能耗水平[76]、分析電磁輻射[77]、冷啟動讀取內(nèi)存[78]等多種側(cè)信道攻擊獲取安全模型既定接口之外的秘密信息, 也可以通過故障植入[79,80]、截斷線路、加熱冷凍、射線照射等多種手段對密碼算法的軟硬件實現(xiàn)及其中的秘密信息實施篡改.這些低成本的有效攻擊導致許多在傳統(tǒng)安全模型中可證明安全的密碼方案在實際應(yīng)用中并不安全.為了防御上述攻擊, 工業(yè)界一般采用屏蔽、混淆等硬件層次的防御方法, 但大多只針對具體攻擊和具體方案有效, 通用性不足, 難以應(yīng)付層出不窮的泄漏、篡改攻擊.密碼學界從2004 年起致力于從源頭上給出抗側(cè)信道攻擊的通用解決方法, 即在經(jīng)典安全模型的基礎(chǔ)上建立泄漏安全模型以刻畫絕大多數(shù)已知甚至未知的側(cè)信道攻擊(刻畫方式通常是將攻擊者通過側(cè)信道可能獲得的秘密狀態(tài)信息表達為關(guān)于秘密狀態(tài)的多項式可計算的函數(shù)), 奠定了獲得可證明抗側(cè)信道攻擊的理論基礎(chǔ).

抗泄漏安全.2004 年, Micali 和Reyzin[81]提出了物理可觀測安全密碼學, 拉開了從理論上防御泄漏攻擊的研究序幕.2008 年, Dziembowski 和Pietrzak[82]正式提出了抗泄漏密碼學, 在傳統(tǒng)安全模型之上, 通過允許敵手訪問泄漏函數(shù)建立了更強的泄漏安全模型.在泄漏安全模型下可證明安全的密碼方案能夠抵御一系列已知或未知的側(cè)信道攻擊, 適用于各種復雜未知的應(yīng)用環(huán)境.

總體而言, 泄漏模型通過增加泄漏諭言機Oleak(·) 強化傳統(tǒng)安全模型.敵手可以自適應(yīng)地向泄漏諭言機發(fā)起一系列泄漏詢問fi: sk0,1}?i并獲得相應(yīng)的結(jié)果, 其中fi是關(guān)于私鑰的函數(shù), 稱為泄漏函數(shù).不同的泄漏模型通過對泄漏函數(shù)施加不同的限制獲得.Micali 和Reyzin[81]首先給出唯計算泄漏模型, 即要求泄漏函數(shù)的輸入只能是私鑰參與計算的部分.然而冷啟動攻擊表明該模型無法全面刻畫現(xiàn)實攻擊, 未參與計算的存儲單元同樣可能發(fā)生泄漏.之后出現(xiàn)的模型對發(fā)生泄漏的存儲單元不再加以限制, 即所有的存儲單元均可能存在泄漏.其又可進一步分為相對泄漏模型(relative memory leakage model) 和連續(xù)泄漏模型(continual memory leakage model), 前者對密碼系統(tǒng)在整個生命周期內(nèi)的泄漏量存在一定限制;后者考慮密碼系統(tǒng)可進行連續(xù)更新, 只對狀態(tài)更新之間的泄漏量存在一定限制, 而對整個生命周期內(nèi)的泄漏量沒有限制.

? 相對泄漏模型中, 攻擊者能夠通過訪問泄漏函數(shù)獲取關(guān)于私鑰的信息.對泄漏函數(shù)施加的細粒度限制進一步細分了此類模型.Akavia 等[83]提出的有界泄漏模型(bounded leakage model) 的限制是其中?i為敵手自適應(yīng)選擇的泄漏詢問fi的輸出長度,?為泄漏量上界, 泄漏率被定義為比值?/|sk|, 用于衡量泄漏量的多少.Akavia 等在有界泄漏模型下基于LWE 假設(shè)給出了抗泄漏安全的公鑰加密方案和身份加密方案.隨后Naor 和Segev[84]基于哈希證明系統(tǒng)給出了有界泄漏模型下抗泄漏公鑰加密的通用構(gòu)造, 并給出多個實例化方案, 特別地, 基于Cramer-Shoup加密方案的變體給出了泄漏率為1/6?o(1) 的選擇密文安全構(gòu)造.此外, Naor 和Segev[84]還將有界泄漏模型放寬為噪聲泄漏模型(noisy leakage model), 該模型不再對泄漏函數(shù)輸出長度總和進行限制, 僅要求泄漏后私鑰的最小熵仍大于預設(shè)的下界.后續(xù)的工作致力于提升抗泄漏選擇密文安全公鑰加密方案的泄漏率.Liu 等[85]基于Cramer-Shoup 加密方案的新變體給出了泄漏率為1/4?o(1) 的構(gòu)造.Dodis 等[86]猜測完全基于哈希證明系統(tǒng)的選擇密文安全構(gòu)造泄漏率不可能大于1/2?o(1).Qin 等[87]等結(jié)合哈希證明系統(tǒng)和一次性有損過濾器(one-time lossy filter)給出了選擇密文安全公鑰加密的新構(gòu)造, 并在文獻[88] 中通過精心的實例化達到了最優(yōu)泄漏率1?o(1).Chen 等[89]對有損陷門函數(shù)[41]進行弱化, 提出正則有損函數(shù)(regular lossy function, RLF), 并展示了其在抗泄漏領(lǐng)域的強力應(yīng)用: 一方面正則有損函數(shù)蘊含了最優(yōu)泄漏率的單向函數(shù)和消息驗證碼, 另一方面與哈希證明系統(tǒng)結(jié)合則可構(gòu)造出具有最優(yōu)泄漏率的選擇密文公鑰加密方案.由于代數(shù)友好的哈希證明系統(tǒng)蘊含正則有損函數(shù), 因此該結(jié)果否證了Dodis 等人[86]的猜想.Chen等[90]綜合不可區(qū)分混淆(iO)、可穿孔(公開求值) 偽隨機函數(shù)和有損函數(shù)給出了構(gòu)造抗泄漏公鑰加密的非黑盒新路線, 方法的核心是利用iO將可穿孔(公開求值) 偽隨機函數(shù)編譯為抗泄漏版本, 并借助有損函數(shù)達到最優(yōu)泄漏率.

有界泄漏模型和噪聲泄漏模型的泄漏容忍上界正比于私鑰長度, 泄漏上界的提升將導致密碼系統(tǒng)私鑰長度的增加和運行效率的下降.為了在泄漏上界極大(如O(2λ)) 的情況下盡可能實現(xiàn)優(yōu)良的運行效率, Alwen 等[91]提出有界獲取模型(bounded retrieval model).該模型允許敵手獲取關(guān)于私鑰高達?=O(2λ) 比特量級的信息, 同時要求密碼算法運行時間與泄漏量?無關(guān), 仍為關(guān)于安全參數(shù)λ的多項式.Alwen 等[92]利用身份哈希證明系統(tǒng)基于不同困難假設(shè)構(gòu)造了一系列有界獲取模型下抗泄漏的身份加密方案.Dodis 等[93,94]觀察到上述相對泄漏模型的共同點是要求泄漏后私鑰仍有一定的統(tǒng)計意義下的最小熵.于是, 他們將統(tǒng)計意義進一步放寬到計算意義, 得到了更具一般性的輔助輸入模型, 并在該模型下構(gòu)造了抗泄漏的公鑰加密方案.

? 持續(xù)泄漏模型: 該類模型中針對密鑰具有連續(xù)更新機制的密碼系統(tǒng)定義.攻擊者每個更新周期內(nèi)都可以獲得任意內(nèi)存單元的泄漏.在該模型下, Brakerski 等[95]利用線性代數(shù)的技巧, 基于雙線性群中的線性假設(shè)構(gòu)造出抗泄漏的PKE 方案和IBE 方案.Lewko 等[96]利用雙系統(tǒng)加密技術(shù),給出了更強意義下的抗泄漏的(H)IBE 方案和屬性加密方案, 其中泄漏不僅可以針對一個身份/屬性的多個私鑰發(fā)生, 還可針對主私鑰發(fā)生.Lewko 等[97]基于合數(shù)階群中的判定性假設(shè), 給出抗泄漏的公鑰加密方案, 且允許更新過程中的泄漏量超過指數(shù)級別.Yuen 等[98]將連續(xù)內(nèi)存泄漏模型和輔助輸入模型結(jié)合, 利用雙系統(tǒng)加密技術(shù)給出了抗泄漏的(H)IBE 方案.以上持續(xù)泄漏模型的局限是僅允許泄漏發(fā)生在每個私鑰生命周期中, 不允許在私鑰更新過程中發(fā)生泄漏.Dachman-Soled等[99]利用不可區(qū)分混淆構(gòu)造了一個編譯器, 可對持續(xù)泄漏模型下的公鑰加密方案進行強化, 進一步容忍私鑰更新過程中的泄漏.

主流的泄漏安全模型聚焦私鑰的泄漏, 但是, 在真實的泄漏場景中, 不僅僅是存儲私鑰的存儲單元可能存在泄漏, 參與計算的存儲單元甚至所有的存儲單元都可能存在泄漏.那么在一定的程度上來說, 只考慮私鑰的泄漏是不合理的, 更強的抗泄漏模型還應(yīng)考慮密碼算法執(zhí)行中各類存儲單元的泄漏, 例如使用的隨機數(shù)的泄漏.針對廣泛情形下的泄漏, 一條可行的技術(shù)路線是研究抗泄漏的存儲編碼技術(shù), 抗泄漏的存儲編碼技術(shù)保證敵手即使獲得了部分消息編碼后的信息, 仍然無法獲得原始消息的有效知識.如此, 如果算法本身將隨機數(shù)進行抗泄漏編碼后存儲, 則可以滿足抗隨機數(shù)泄漏的性質(zhì).但正如Goldwasser 和Rothblum[100]指出的, 安全模型不進一步限制敵手行為, 則難以抵御任意存儲單元的泄漏攻擊, 故存儲編碼方案的構(gòu)造通常還需要其他對敵手限制的假設(shè).Davì 等[101]提出了抗泄漏存儲的存儲編碼技術(shù), 其在存儲泄漏相互獨立的假設(shè)和泄漏函數(shù)低復雜度的假設(shè)要求下, 利用雙源提取器等技術(shù)得到了兩種抗泄漏存儲編碼方案.Dziembowski 等[102]仍基于存儲泄漏相互獨立等假設(shè), 推廣[101] 到持續(xù)泄漏模型下, 可容忍更高程度的泄漏, 但也需要動態(tài)地存儲更新的過程.Dodis 等[103]則進一步基于文獻[97] 中的技術(shù)去除了存儲更新過程中對不同存儲間同步通信的要求, 使得存儲編碼方案更加方便快捷, 契合現(xiàn)實使用要求.除了上述的存儲編碼技術(shù)外, 另外一條技術(shù)路線是研究抗不同類型泄漏的通用編譯器, 它們能將非抗泄漏的密碼方案轉(zhuǎn)換為抗泄漏的密碼方案.在不同類型的泄漏下, 抗泄漏的通用編譯器也得到了充分的研究[100,104,105].

抗篡改安全.同在2004 年, Gennaro 等[106]提出了抗篡改密碼學, 在傳統(tǒng)安全模型之上, 通過允許敵手訪問篡改函數(shù)獲取秘密狀態(tài)的額外信息.例如, 具體到公鑰加密, 敵手可以詢問解密諭言機(?,c) 以獲得c在密鑰?(sk) 下的解密值.可見, 區(qū)別于泄漏攻擊敵手的被動性, 篡改攻擊的敵手具有主動性.因此, 篡改攻擊的威力極強, Boneh 等[107]曾指出, 一個隨機性的錯誤足夠攻擊基于RSA 的簽名, 從而, 研究抗篡改安全的公鑰密碼是非常重要的.

就最廣泛的意義而言, 擁有篡改能力的敵手可以同時篡改算法對應(yīng)的電路C和內(nèi)部秘密狀態(tài)st (例如包含私鑰sk), 具體來說, 敵手可以對(C,st) 實施任何的篡改函數(shù)得到(C′,st′) =f(C,st), 這被稱為計算篡改(tampering with computation) 模型.若不具有篡改能力的敵手能訪問某個密碼算法諭言機C(st,·),那么具有篡改能力的敵手就能訪問篡改后的密碼算法諭言機C′(st′,·).顯然, 如果不給f施加限制, 那么可使篡改后的密碼算法對應(yīng)的電路C′直接輸出內(nèi)部狀態(tài)st, 而內(nèi)部狀態(tài)st 往往包含sk, 從而敵手可直接從密碼算法諭言機中獲得sk 從而實現(xiàn)任意的解密.為了避免類似的平凡攻擊, 在討論抗篡改安全模型時,通常均會限制f從某個篡改函數(shù)集Φ 中選擇.篡改安全模型的強弱取決于篡改函數(shù)集Φ 的大小, 因此如何擴大可容忍的篡改函數(shù)集是抗篡改密碼學的核心問題.Ishai 等[108]在計算篡改模型下研究了這個問題, 他們采取的方法是構(gòu)造通用的電路編譯器, 將不抗篡改攻擊的密碼電路編譯為具有篡改性質(zhì)的.但是,他們只能在非常受限的篡改函數(shù)集Φ 上得到一般的通用電路編譯器.后續(xù)一系列研究[109–111]致力于擴展文獻[108] 中篡改函數(shù)集的限制, 但是效果比較有限, 與實際可行的篡改函數(shù)集相比仍存在較大差距.

與最廣泛的計算篡改模型相比, 目前在唯內(nèi)存篡改(memory-only tampering) 模型取得的進展更多.在唯內(nèi)存篡改的模型下, 敵手只能對內(nèi)部秘密狀態(tài)st 進行篡改, 而不能對電路本身進行篡改.內(nèi)部秘密狀態(tài)主要可分為密鑰sk 和隨機數(shù), 但是文獻[112] 指出即使篡改少量的隨機數(shù), 對整個密碼系統(tǒng)的影響都是毀滅性的, 故目前關(guān)于抗唯內(nèi)存篡改的研究通常假設(shè)篡改攻擊的敵手僅能篡改私鑰sk, 即實施相關(guān)密鑰攻擊(related-key attack, RKA).具體地, 如果密碼算法可以抗篡改函數(shù)集為Φ 的篡改攻擊, 則稱該密碼算法為Φ-RKA 安全.而關(guān)于RKA 安全的密碼方案的研究主要可分為三類, 一類研究的著重點在于構(gòu)造具體的方案, 而另外一類研究的著重點則在于構(gòu)造通用的強化方法, 此外, 亦有一些關(guān)于不可能結(jié)果的理論研究.

? 具體方案: Bellare 等[113]首次提出了針對密碼算法的RKA 安全的理論模型, 并展開了對PRF、PRP 的RKA 安全的研究.早期RKA 安全的研究主要集中在PRF、PRP 這類的密碼原語上[114–116].Bellare 等[115]首次將RKA 安全的理論模型推廣到PKE 和IBE 上, 并且證明了可利用BCHK 轉(zhuǎn)換[38]將Φ-RKA 安全的IBE 轉(zhuǎn)換為Φ-RKA 安全的PKE.Wee[117]基于適應(yīng)性陷門關(guān)系給出了RKA-CCA 的通用構(gòu)造, 并分別基于BDDH、LWE 等假設(shè)得到了相應(yīng)的實例化, 但是Wee 的構(gòu)造篡改函數(shù)集Φ 限制在仿射函數(shù)集Φaff.Bellare 等[118]則延續(xù)文獻[115] 的研究方法, 從RKA 安全的IBE 入手, 基于非標準d-EDBDH 假設(shè)給出了篡改函數(shù)集為d次多項式Φpoly的IBE 方案, 從而得到了Φpoly-RKA-CCA 安全的PKE 方案.為了基于標準假設(shè)構(gòu)造RKA-CCA 安全的PKE 方案, Qin 等[119]將文獻[120] 中提出的不可延展密鑰導出函數(shù)(nonmalleable key derivation functions, NM-KDF) 擴展為連續(xù)不可延展密鑰導出函數(shù)(cNM-KDF),并以此為工具將一系列密碼方案(包括公鑰加密) 提升為對函數(shù)集Φhoeiocr(高輸出熵且輸入-輸出抗碰撞的函數(shù)集, 該函數(shù)集包含次數(shù)有上界的多項式函數(shù)) 的Φhoeiocr-RKA 安全的方案.Chen 等[121]首次提出不可延展函數(shù)(non-malleable function, NMF) 的概念, 建立起其與單向函數(shù)之間的全面聯(lián)系, 并展示了NMF 在抗篡改安全領(lǐng)域中的強力應(yīng)用, 具體地, 將cNM-KDF 強化為RKA 安全的可認證密鑰導出函數(shù), 并基于NMF 給出簡潔的黑盒構(gòu)造.該構(gòu)造凝練了Qin 等cNM-KDF 的本質(zhì)思想, 并且擴大了可容許的篡改函數(shù)集, 從而提高了提升轉(zhuǎn)換的編譯效果.Fujisaki 等[122]則基于DBDH 假設(shè)進一步將篡改函數(shù)集推廣到ΦaInv(有效可逆函數(shù)構(gòu)成的函數(shù)集).為了得到更為廣泛的篡改函數(shù)集, 同時繞過Gennaro 等[106]給出的不可能結(jié)果—針對sk 無限制的篡改函數(shù)集實現(xiàn)RKA 安全是不可能的, Damg?rd 等[123]提出了有界篡改模型.有界篡改模型雖然不限制篡改函數(shù)集,但是限制敵手的篡改次數(shù),衡量其安全強度的一個重要指標是篡改率ρ(λ):=τ(λ)/s(λ)(其中τ(λ) 為篡改的次數(shù)上界,s(λ) 為sk 的比特長度).Damg?rd 等[123]基于雙線性映射得到了第一個ρ(λ)=O(1/λ) 的RKA 安全的PKE 方案.Faonio 等[124]基于哈希證明系統(tǒng)得到了不基于雙線性映射的ρ(λ)=O(1/λ) 的RKA 安全的PKE 方案.

? 通用的強化方法: 與具體方案不同, 這條路線主要考慮如何采用通用的方式將不具有RKA 安全性的密碼方案轉(zhuǎn)換為具有RKA 安全性的密碼方案, 而這也正是Gennaro 等[106]最初構(gòu)造RKA 安全密碼方案的主要著手點.Dziembowski 等[125]提出了不可延展編碼(non-malleable code) 這一新的密碼原語, 并基于該原語構(gòu)造了一個能將不具有RKA 安全的密碼方案編譯為具有RKA 安全的密碼方案的通用編譯器, 但是他們只證明了該編碼的存在性, 而沒有給出在較強安全模型下該編碼的構(gòu)造.后續(xù)的工作主要圍繞不可延展編碼的構(gòu)造展開, 而其核心問題仍然是如何擴大篡改函數(shù)集的大小, 例如Faust 等[126]考慮了空間有界的篡改函數(shù)集, Brian 等[127]考慮了多項式深度電路對應(yīng)的篡改函數(shù)集等.

? 不可能結(jié)果: Wang 等[128]證明了在有界篡改模型下, 即使敵手的篡改次數(shù)被限制為一次, 也無法通過黑盒歸約基于任意的計算困難問題證明多種具有唯一性的密碼原語的RKA 安全性.具體包括: 可驗證隨機函數(shù)、單射單向函數(shù)、具有唯一性的簽名和具有唯一消息性的加密, 涵蓋了Cramer-Shoup 加密[33]、RSA 簽名[10]、Waters 簽名[129]等方案.

4.3 緊歸約安全

密碼學中的緊歸約安全研究始于偽隨機函數(shù)[130].具體來說, 假定安全性證明中包含歸約R, 其將高效的敵手A轉(zhuǎn)換為歸約算法RA解決底層某個計算困難問題,記敵手A和歸約算法RA的運行時間分別為tA(λ)和tRA(λ), 優(yōu)勢分別為?A(λ)和?RA(λ), 且有tRA(λ)/?RA(λ)=?(λ)·tA(λ)/?A(λ), 那么?(λ)即可作為衡量歸約損失的度量,?(λ) 越大, 則歸約損失越大, 歸約越低效.在密碼背景下, 歸約算法和敵手的運行時間通常均為多項式級別, 因此密碼學歸約更關(guān)注比值L(λ) =?A(λ)/?RA(λ), 如果L(λ) =O(1)(或者L(λ) =O(λ)), 則稱對應(yīng)的密碼方案為(幾乎) 緊歸約安全的.通常來說, 如果采用一般的混合論證技術(shù)(hybrid argument),L(λ) 往往與敵手控制的參數(shù)相關(guān), 例如用戶的數(shù)量n、加密查詢的次數(shù)Qe、解密查詢的次數(shù)Qd等.一般來說,n、Qe和Qd的數(shù)量級在230以上[131,132], 這對歸約效率影響極大.密碼方案若安全歸約低效, 則需增大安全參數(shù)以保證方案的安全性, 進而會影響方案效率, 而具有緊歸約安全的密碼方案無須調(diào)整安全參數(shù).綜上, 對密碼方案緊歸約安全的研究不僅具有理論價值, 也具有實際意義.

公鑰密碼的緊歸約安全的研究發(fā)源于文獻[133] 中對多挑戰(zhàn)多用戶模型下歸約效率的討論, 但其并沒有得到O(λ) 或者是O(1) 的緊歸約CCA 安全的PKE 方案.而后, 密碼學家對如何在標準模型下構(gòu)造多挑戰(zhàn)多用戶的緊歸約CCA 安全的PKE 方案這一問題展開了廣泛且深入的研究.總的來說, 目前在多挑戰(zhàn)多用戶的設(shè)定下設(shè)計緊歸約CCA 安全的PKE 方案主要有兩種方式, 第一種基于Naor-Yung 雙重加密范式, 第二種基于哈希證明系統(tǒng).

? 基于Naor-Yung 雙重加密范式: 由于Naor-Yung 雙重加密范式的轉(zhuǎn)換是緊的, 即在緊歸約安全的NIZK 下, 緊歸約CPA 安全的PKE 方案可轉(zhuǎn)換為緊歸約CCA 安全的PKE 方案, 而且緊歸約CPA 安全的PKE 方案很容易構(gòu)造[133], 所以基于雙重加密范式的緊歸約的CCA 安全的公鑰加密方案主要集中在如何構(gòu)造緊歸約安全的NIZK 上.Hofheinz 和Jager[134]設(shè)計了第一個緊歸約安全的結(jié)構(gòu)保持的簽名方案(structure-preserving signature, SPS), 并利用Groth-Sahai 證明[135]得到了第一個緊歸約安全的無界模擬穩(wěn)固(unbounded simulation sound, USS) 的NIZK,從而得到第一個基于標準假設(shè)的緊歸約CCA 安全的公鑰加密方案.但是該方案開銷過大, 后續(xù)的工作主要集中在如何保證緊歸約的同時使NIZK 更為高效.Abe 等[136]通過構(gòu)造緊歸約安全的帶標簽的單次簽名得到了更為高效的緊歸約安全的SPS, 使用文獻[134] 中的轉(zhuǎn)換框架得到了高效的緊歸約USS 的NIZK; Libert 等[137,138]則更進一步, 他們注意到在Naor-Yung 雙重加密范式下, 利用更弱的NIZK 即可得到CCA 安全的PKE 方案, 他們將NIZK 弱化為準適應(yīng)性NIZK (quasi-adaptive NIZK, QANIZK), 并利用線性同態(tài)性結(jié)構(gòu)保持簽名(linear homomorphic SPS, LHSPS) 構(gòu)造了高效的緊歸約USS 的QANIZK; Gay 等[139]利用適應(yīng)性劃分(adaptive partition) 技術(shù)構(gòu)造了一個緊歸約安全且非常高效的MAC, 并借助Bellare-Goldwasser 轉(zhuǎn)換[140]得到一個非常高效的SPS, 使用文獻[134] 中的轉(zhuǎn)換框架也就得到了高效的緊歸約USS 的NIZK;目前在標準模型、標準假設(shè)下最好結(jié)果是Abe 等[141]構(gòu)造的緊歸約USS 的QANIZK 與SPS,其QANIZK 的證明部分只需要14 個群元素的開銷且公共參數(shù)串的長度與安全參數(shù)無關(guān), 其SPS的簽名部分只需要11 個群元素的開銷且其驗證算法只使用7 個配對積方程.

? 基于哈希證明系統(tǒng): 傳統(tǒng)HPS[33,142]的固有結(jié)構(gòu)難以實現(xiàn)緊歸約CCA 安全, 故相關(guān)工作主要集中在如何設(shè)計HPS 的變體, 并基于此來設(shè)計緊歸約CCA 安全的PKE 方案.Gay 等[143]根據(jù)標簽的比特位來線性組合多個HPS 的私鑰, 并基于標簽對挑戰(zhàn)密文、解密諭言機詢問進行劃分, 以O(shè)(λ) 的損失引入了指數(shù)量級的熵, 得到了第一個不基于雙線性映射的緊歸約CCA 安全的PKE方案; 但是文獻[143] 中由于私鑰和公鑰的數(shù)量與安全參數(shù)成線性關(guān)系而開銷過大, 文獻[144] 則進一步改造HPS 為合法證明系統(tǒng)(qualified proof system, QPS), 借助于或證明(OR proof) 的技術(shù)將私鑰、公鑰的數(shù)量縮減到常數(shù), 得到了非常高效的緊歸約CCA 安全的PKE 方案.后續(xù)的工作主要圍繞這二者進一步展開, 并將類似技術(shù)推廣到更強的安全模型下[132,145,146].

除此之外, 還有許多基于未充分研究的假設(shè)的緊歸約工作, 其主要可以分為基于非標準的q類(qtype) 假設(shè)[50], 以及基于合數(shù)階群上的計算困難假設(shè)[147,148], 這里不一一闡述, 關(guān)于這方面更進一步的介紹請參閱文獻[149].

5 功能性豐富

本文在綜述功能性豐富這條發(fā)展主線時, 如果不特意提及, 則約定將密碼方案的安全模型限定為對應(yīng)功能性下基本的安全模型.

5.1 身份加密

通常, 傳統(tǒng)公鑰加密的密鑰產(chǎn)生算法得到的公鑰不具備語義特性, 因此公鑰與用戶的身份信息必須通過可信第三方簽發(fā)的證書進行綁定, 在實際應(yīng)用中, 公鑰必須通過PKI 體系的認證才能使用.為了擺脫對PKI 體系的依賴, Shamir[150]提出了身份加密(identity-based encryption, IBE) 這一新概念.相比于傳統(tǒng)公鑰加密, 身份加密增加了密鑰派生算法, 即可以通過主私鑰msk 派生出針對身份id 的身份密鑰skid.其中, id 允許用戶使用任意字符串(如手機號碼、Email、地址) 作為公鑰.IBE 規(guī)避了復雜的證書管理與公鑰分發(fā)驗證過程, 不再依賴PKI.不過, IBE 亦有一些缺點, 例如, IBE 方案的用戶私鑰由可信的PKG生成, 密鑰托管(key escrow) 的問題難以避免.

Shamir 最初的工作只給出了IBE 的概念, 并沒有給出具體方案.直到2001 年前后, 三組密碼科學家?guī)缀跬瑫r獨立地給出了IBE 的具體構(gòu)造, 分別是Sakai 等[151]基于雙線性Diffie-Hellman 逆假設(shè)、Boneh 等[152]基于判定性雙線性Diffie-Hellman(DBDH)假設(shè)和Cocks[153]基于二次剩余假設(shè).Gentry等[154]與Horwitz 等[155]提出了層級身份加密(hierarchical IBE, HIBE).以上方案均在隨機諭言機模型下可證明安全.為了在標準模型下構(gòu)造安全的IBE 方案, Canetti 等[156]提出了較弱的選擇身份模型(selective-identity model), 即敵手必須在游戲的開始階段承諾挑戰(zhàn)身份id?, 而非自適應(yīng)選擇.Boneh 和Boyen[157]在選擇身份模型下基于DBDH 假設(shè)給出了不依賴隨機諭言機的IBE 方案.隨后, Boneh 和Boyen[158]展示了如何使用可容許哈希函數(shù)(admissible hash function) 實例化隨機諭言機, 得到標準模型下的IBE 方案, 然而該方案效率低下無法應(yīng)用于實際.Waters[129]通過巧妙的設(shè)計身份到群元素的映射實例化隨機諭言機, 基于DBDH 假設(shè)得到了首個標準模型下高效的IBE 方案.Hohenberger 等[159]給出了基于不可區(qū)分程序混淆和可容許哈希函數(shù)實例化全域哈希類范式中隨機諭言機的方法, 應(yīng)用該方法可將Boneh-Franklin IBE[152]的安全性從隨機諭言機模型提升到標準模型.上述所有IBE 方案在證明中均采用的是分割策略(partition strategy), 即歸約算法將身份空間I切分為I0和I1, 期望敵手選擇I0中的身份進行私鑰詢問, 選擇I1中的身份作為挑戰(zhàn).分割策略成功的概率決定了歸約的松緊.Katz 和Wang[160]指出當IBE 的私鑰生成算法符合全域哈希簽名形式時(如Boneh-Franklin IBE), 可以使用雙私鑰的技術(shù)收緊歸約.然而這種技術(shù)應(yīng)用范圍僅局限于隨機諭言機模型下的部分方案, 不適用于標準模型下的IBE 方案.Gentry[161]基于判定性可增雙線性Diffie-Hellman 指數(shù)(DABDHE) 假設(shè)給出了標準模型下緊歸約的高效IBE 方案.此外, Gentry 在該工作中還首次為IBE 引入了匿名性.Gentry 的工作是IBE 發(fā)展的一個里程碑, 后續(xù)的研究方向轉(zhuǎn)向如何基于格基假設(shè)設(shè)計IBE.

基于格的IBE 與基于雙線性映射的IBE 演進路線基本一致.Gentry 等[162]首先構(gòu)造出對偶的Regev PKE 方案, 再利用隨機諭言機將其升級為IBE 方案.Agrawal 等[163]設(shè)計了格基采樣算法, 以此在選擇身份模型下設(shè)計出首個不依賴隨機諭言機的IBE 方案.Cash 等[164]設(shè)計了格基代理算法, 設(shè)計出首個完全安全的標準模型下的IBE 方案.雖然文獻[164] 達到了適應(yīng)性安全, 但是由于其格基代理算法的固有結(jié)構(gòu)使得其公鑰、私鑰、密文長度都是O(λ) 的, 其效率遠不及文獻[163] 中選擇身份模型下安全的公私鑰、密文開銷僅為O(1) 的IBE 方案, 故后續(xù)的工作主要集中在如何兼顧完全的適應(yīng)性安全以及較高的效率[165–171].其中, Yamada[170]設(shè)計了新的劃分技術(shù), 給出了兼顧安全性和效率的優(yōu)良結(jié)果, 其公鑰長度為O(log2λ), 私鑰和密文長度均為O(1) 常數(shù)量級.目前為止, 最優(yōu)的結(jié)果由文獻[172] 給出, 其進一步改進了Yamada[170]中的劃分技術(shù), 在保持安全性和私鑰、密文長度開銷幾乎不變的情況下, 將公鑰長度降低到了ω(1) 超常數(shù), 具體的方案下可為O(log logλ).

在IBE 的各種具體構(gòu)造百花齊放后, 密碼學者開始探索構(gòu)造的不可能結(jié)果.Boneh 等[173]指出IBE無法以黑盒的方式由陷門置換或CCA 安全的PKE 構(gòu)造得出.Papakonstantinou 等[174]指出IBE 無法以黑盒的方式基于DDH 假設(shè)構(gòu)造得出.D?ttling 和Garg[175]使用基于混淆電路(garbled circuits) 的非黑盒技術(shù)繞過上述不可能結(jié)果, 首次基于計算性Diffie-Hellman 假設(shè)或大整數(shù)分解假設(shè)構(gòu)造出IBE.

在通用構(gòu)造方面, D?ttling 和Garg[176]展示了如何基于任意選擇安全的IBE 構(gòu)造完全安全的IBE.Hofheinz 和Kiltz[177]抽象出離散對數(shù)群上的可編程哈希函數(shù)(programmable hash function, PHF), 以此解釋了一類標準模型下基于分割證明策略的IBE 方案.Zhang 等[171]提出并設(shè)計出格基可編程函數(shù),以此為工具設(shè)計出高效的IBE 方案.Alwen 等[92]和Chen 等[178]提出了身份哈希證明系統(tǒng), 闡釋了一系列基于判定性假設(shè)的IBE 方案的設(shè)計思想[161,162,179,180].Chen 等[181]提出了身份可提取哈希證明系統(tǒng), 闡釋了一系列基于搜索性假設(shè)的IBE 方案的設(shè)計思想[35,182–185].

最近關(guān)于IBE 的工作主要是集中在如何增強IBE 的功能性和安全性, 構(gòu)造IBE 的變體以應(yīng)對更為豐富的實際場景、更加契合實際使用要求.在功能性上, 一個重要問題是如何使得PKG 擁有類似于PKI的密鑰撤銷(key revocation) 的功能.事實上, 早在文獻[152] 中就提出過一種樸素的撤銷思路, 即PKG每隔一定時間段內(nèi)為誠實用戶更新關(guān)于(id,t) 的功能密鑰, 但是通信開銷與用戶成正比而顯得過于笨重.Boldyreva 等[186]第一次形式化了可撤銷IBE (revocable IBE, RIBE) 的安全模型, 利用二叉樹構(gòu)造了通信開銷為對數(shù)量級的RIBE.Seo 等[187]討論了文獻[186] 中RIBE 安全模型的缺陷并加以修正, 后續(xù)關(guān)于RIBE 的工作[188–190]的安全模型均基于此修正增強后的安全模型.除了對于密鑰撤銷這一功能性的考量, IBE 的計算效率、身份匹配模式等性能性、靈活性的主題也都得到了廣泛且深入的研究[191–193].

5.2 屬性加密

如果把身份加密看作一種訪問控制的策略, 那么IBE 只有當解密者擁有加密者所期望的身份才能進行正確解密, 這屬于一對一的簡單訪問控制結(jié)構(gòu), 但是對于現(xiàn)實應(yīng)用而言, 通常希望一個加密的文件對于擁有某種權(quán)限的人都能解密, 即實現(xiàn)一對多的訪問控制結(jié)構(gòu), 從而IBE 這種簡單的訪問控制結(jié)構(gòu)是遠遠不夠的, 需要新的密碼原語以提供更強大的訪問控制結(jié)構(gòu).Sahai 和Waters[194]拓展了IBE 的內(nèi)涵, 結(jié)合秘密共享方案, 提出第一個基于門限訪問控制的屬性加密(attribute-based encryption, ABE) 方案, 具體來說, 他們將身份加密下的身份看作由不同的屬性構(gòu)成, 這種ABE 只要解密者的屬性密鑰與加密者所期望的屬性集合足夠相似即可以進行正確解密.相比于身份加密下實現(xiàn)的一對一的訪問控制結(jié)構(gòu), ABE 的主要優(yōu)點是支持更為豐富、強大的控制策略, 具有一對多的訪問控制結(jié)構(gòu), 更加靈活、更加細粒度.

Goyal 等在文獻[195] 中正式給出了ABE 的語義, 他們考慮到密文和密鑰在控制與被控制關(guān)系上的對稱性, 將ABE 進一步劃分為密鑰策略的ABE (key-policy ABE, KP-ABE) 以及密文策略的ABE(ciphertext-policy ABE, CP-ABE) 以適用于不同的應(yīng)用場景, 顧名思義, KP-ABE 就是將控制策略與委派的屬性密鑰相綁定, 而將屬性集與密文相綁定, 能夠正確解密當且僅當密文的屬性集符合密鑰的控制策略, CP-ABE 亦作類似解釋, 除此之外, 他們利用雙線性映射、秘密共享, 給出了第一個選擇屬性模型下的單調(diào)訪問控制結(jié)構(gòu)(即與門和或門構(gòu)成的布爾電路) 的KP-ABE 方案, 但需要注意的是, 不同于秘密共享, 他們定義的ABE 還需要額外滿足抗合謀性.但是也正是為了滿足抗合謀性, CP-ABE 的構(gòu)造顯得較為困難, Bethencourt 等[196]在一般群模型(generic group model, GGM) 下通過給不同的屬性密鑰引入隨機數(shù)以防止其重組與合謀實現(xiàn)了第一個支持單調(diào)訪問控制結(jié)構(gòu)的CP-ABE.利用類似的思想, Cheung和Newport[197]在標準模型下構(gòu)造了只支持與門構(gòu)成的訪問控制結(jié)構(gòu)的CP-ABE.Waters[198]則開發(fā)了新的證明技術(shù), 其通過將線性秘密共享嵌入到公開參數(shù)中, 實現(xiàn)了在標準模型和標準假設(shè)下的支持單調(diào)訪問控制結(jié)構(gòu)的CP-ABE, 并且密文大小僅與訪問控制結(jié)構(gòu)對應(yīng)的單調(diào)電路大小成線性相關(guān).另一方面,由于單調(diào)訪問控制結(jié)構(gòu)對應(yīng)的布爾電路僅包含與門和或門, 并不完備, Ostrovsky 等[199]利用Naor 等在文獻[200] 中運用的技術(shù), 將KP-ABE 推廣到了非單調(diào)訪問控制結(jié)構(gòu).Okamoto 和Takashima[201]則進一步將CP-ABE 也推廣到了非單調(diào)訪問控制結(jié)構(gòu).

在安全性方面, 上面論述的早期ABE 方案一般都只能達到選擇模型下的安全性, 如果簡單使用IBE中的分割策略, 當屬性空間較大時, 安全歸約將指數(shù)級地松弛, 從而失效.Lewko 等[202]以合數(shù)階群的雙線性映射為代數(shù)工具, 結(jié)合雙系統(tǒng)加密技術(shù)[203]構(gòu)造出首個適應(yīng)性安全的ABE.Okamoto 等[201]則引入對偶配對向量空間, 進而利用素數(shù)階群的雙線性映射模擬合數(shù)階群的雙線性映射, 同樣結(jié)合雙系統(tǒng)加密技術(shù)構(gòu)造除了適應(yīng)性安全的ABE.

格上的構(gòu)造與群上構(gòu)造的發(fā)展路線幾乎一致.Agrawal 等[191]利用類似于文獻[194] 中的技術(shù), 構(gòu)造出了格上第一個基于LWE 問題的門限訪問控制結(jié)構(gòu)的屬性加密.同年, Zhang 等[204]將類似的結(jié)果推廣到了CP-ABE 下.Boyen[205]基于LWE 假設(shè)構(gòu)造了支持單調(diào)訪問控制結(jié)構(gòu)的KP-ABE, 大大擴大了格上構(gòu)造的ABE 的控制策略的表達能力.Gorbunov 等[206]則更進一步, 基于LWE 假設(shè), 將格上KP-ABE 的構(gòu)造推廣到了全電路(即任意多項式深度), 其密鑰大小和電路大小有關(guān), 密文大小則與電路的深度成線性相關(guān).Boneh 等[207]結(jié)合同態(tài)加密[208]的思想, 構(gòu)造了支持訪問控制結(jié)構(gòu)為全電路的KP-ABE, 相較于文獻[206], 其最大的效率提升在于密鑰的大小僅與電路的深度有關(guān).Brakerski 等[209]則提出了支持訪問控制結(jié)構(gòu)為全電路的CP-ABE, 且其密文的大小僅與電路的深度有關(guān), 但是該方案的安全性只停留在密碼分析上, 沒有給出安全性證明.Datta 等[210]基于LWE 假設(shè)給出了一個支持訪問控制為NC1電路的CP-ABE 方案.

但是, ABE 的諸多構(gòu)造主要強調(diào)的是加密消息的語義安全, 即具有載荷隱藏(payload-hiding) 的性質(zhì), 而屬性集是公開的, 但在一些場合下, 屬性集也希望對外保密, 即希望ABE 方案具有屬性隱藏(attribute-hiding) 的性質(zhì).為了達到這樣的安全要求, Katz 等[211]首先正式提出了謂詞加密(predicate encryption) 的概念, 其安全模型在不可區(qū)分實驗下精準刻畫了屬性隱藏的含義, 他們基于合數(shù)階群的雙線性映射構(gòu)造了選擇性安全的內(nèi)積謂詞加密, 并基于內(nèi)積謂詞加密, 給出了針對多項式、析取邏輯等謂詞族的謂詞加密.與ABE 的研究路線相同, 謂詞加密研究的主要問題在于如何兼顧安全性的同時擴大謂詞族.Lewko 等[202]利用對偶配對向量空間技術(shù), 在素數(shù)階群上基于n-eDDH 假設(shè)構(gòu)造了適應(yīng)性弱屬性隱藏安全的內(nèi)積謂詞加密.Okamoto 等[201]利用對偶配對向量空間技術(shù), 在素數(shù)階群上基于DLIN 假設(shè)亦構(gòu)造出適應(yīng)性弱屬性隱藏安全的內(nèi)積謂詞加密.Okamoto 等[212]開發(fā)了對偶配對向量空間下的新技術(shù)—索引(indexing) 和隨機性放大(randomness amplification), 利用這些新的技術(shù), 他們基于DLIN 假設(shè)構(gòu)造了第一個適應(yīng)性屬性隱藏安全的內(nèi)積謂詞加密, 并且將該結(jié)果進一步推廣到無界(unbounded) 內(nèi)積謂詞加密.Gorbunov 等[213]延續(xù)文獻[214] 中的思想方法, 將ABE 與同態(tài)加密相結(jié)合, 基于LWE 假設(shè)構(gòu)造了選擇性安全但謂詞族為有限深度布爾電路族的謂詞加密.一個自然的問題是能否構(gòu)造謂詞加密方案, 其在滿足較強適應(yīng)性安全的同時亦可支持謂詞族為更為廣泛的電路族(如NC1) 的謂詞加密? Bitansky 和Vaikuntanathan[215]指出適應(yīng)性安全且支持的謂詞族為廣泛的電路族的謂詞加密將直接蘊含不可區(qū)分混淆(indistinguishability obfuscation,iO).Wee[216]為了避開上述結(jié)果, 提出了部分屬性隱藏這一新的安全性質(zhì), 構(gòu)造了半適應(yīng)性(semi-adaptive) 部分屬性隱藏安全的謂詞加密方案, 其在公開屬性上支持的謂詞族為算術(shù)分叉程序(arithmetic branching program, ABP), 在私有屬性上支持的謂詞族為內(nèi)積函數(shù), 首次得到了“雙贏” 的謂詞加密構(gòu)造.Datta 等[217]利用對偶配對向量空間的方法進一步將上述結(jié)果推廣到適應(yīng)性安全下.

其他關(guān)于屬性加密的研究主要集中在如何進一步增強屬性加密功能的多樣性, 以便適用于更廣泛的應(yīng)用場景, 例如, 類似于IBE, 如果只有一個權(quán)威可信方分發(fā)屬性密鑰, 那么可信方勢必要對大量的用戶進行服務(wù)而造成性能瓶頸, IBE 為了應(yīng)對這樣的場景而拓展為HIBE, 對應(yīng)地, 分層次的ABE (hierarchy ABE, HABE) 也被Wang 等[218]提出, 他們將HIBE 和CP-ABE 相結(jié)合給出了HABE 的通用構(gòu)造, 后續(xù)關(guān)于HABE 的工作則是如何增強HABE 的安全性[219–221].除此之外, 還有關(guān)于ABE 各種變體的研究, 比如多權(quán)威ABE[210,222,223]、注冊化ABE [224,225] 等.

5.3 函數(shù)加密

自1978 年公鑰加密體制問世以來, 其被廣泛應(yīng)用于保障機密數(shù)據(jù)的傳輸和存儲安全.然而在經(jīng)典的公鑰加密體制中, 解密為完全或無(all or nothing) 的方式, 即擁有私鑰能夠恢復全部信息, 否則得不到任何信息.隨著云計算時代的到來和隱私保護技術(shù)的發(fā)展, 要求公鑰加密體制支持任意細粒度訪問控制機制的需求愈發(fā)迫切.考察如下的應(yīng)用場景: Alice 想通過社交網(wǎng)站與好友們分享合照, 希望每個好友只能看到合照中的他本人和Alice, 看不到其他人, 為了保護隱私信息, Alice 計劃將合照加密后上傳.顯然, 經(jīng)典的公鑰加密體制無法滿足這一需求.在此背景下, O’Neill[226]和Boneh 等[227]分別獨立提出函數(shù)加密(functional encryption, FE) 的概念.簡單來說, 函數(shù)加密相較于傳統(tǒng)的公鑰加密增加了函數(shù)密鑰委派算法, 其可以針對函數(shù)族中的合法f(例如某個訪問控制策略) 委派出函數(shù)密鑰skf, 函數(shù)密鑰skf的擁有方可以調(diào)用函數(shù)加密方案的解密算法從密文中計算出f(m), 而不一定是數(shù)據(jù)m本身, 從而超越了傳統(tǒng)密碼的完全或無的加解密方式.針對上述分享合照實際場景, Alice 可以作為函數(shù)加密方案的主私鑰持有方, 并且根據(jù)一定的委派策略為不同好友分享不同的函數(shù)密鑰skfi, 這樣不同的好友僅能從加密的照片中計算出fi(m), 即為他本人和Alice 的合照.函數(shù)加密極大拓寬了公鑰加密的內(nèi)涵, 是傳統(tǒng)公鑰加密(PKE)、身份加密(IBE)[150,152]、可搜索公鑰加密(public-key encryption with keyword searching, PEKS)[228]、模糊身份加密[194]、屬性加密(ABE)[195,202]、謂詞加密(predicate encryption, PE)[211,229]逐步升華泛化的結(jié)果.函數(shù)加密的強大功能性使其不僅具有重要的理論研究意義, 更使其在互聯(lián)網(wǎng)、物聯(lián)網(wǎng)、云計算中的自主訪問控制、密文搜索、隱私保護、外包計算等領(lǐng)域有著廣泛的應(yīng)用.

就研究的函數(shù)族而言, 函數(shù)加密主要可以劃分為兩大類, 一類主要研究針對通用的函數(shù)族的函數(shù)加密方案, 其針對的函數(shù)族可為多項式深度布爾電路對應(yīng)的函數(shù)族等, 這類研究雖然得到的密碼方案功能性強大, 但往往會依賴于較沉重的密碼學組件, 例如不可區(qū)分混淆(indistinguishability obfuscation,iO) 等,通常其理論意義大于現(xiàn)實意義.另外一類則主要研究針對特定且常用的函數(shù)族的函數(shù)加密方案, 例如內(nèi)積函數(shù)、二次函數(shù)等, 其不像第一類研究中針對通用函數(shù)族的函數(shù)加密方案那樣有強大的功能性, 但其構(gòu)造的方案的效率、安全性卻有大幅提升, 具有更大的現(xiàn)實意義.

? 針對通用函數(shù)族的函數(shù)加密方案: 由于抗無界(unbounded) 函數(shù)密鑰腐化攻擊的通用FE 難以直接構(gòu)造, 早期的研究主要是在有界函數(shù)密鑰腐化模型下進行考慮, Sahai 和Seyalioglu[230]首次在單次函數(shù)密鑰腐化模型下, 利用混淆電路和PKE 作為基本組件構(gòu)造出了針對全電路的FE.但是其密鑰大小與表示函數(shù)密鑰的電路大小相關(guān), Goldwasser 等[214]以ABE 和全同態(tài)加密作為組件解決了這一問題, 使得密文大小與函數(shù)密鑰對應(yīng)的電路大小無關(guān).另外一方面, 文獻[231,232] 也將上述在單次函數(shù)密鑰腐化模型下的構(gòu)造提升到有界函數(shù)密鑰腐化模型下.通用FE 構(gòu)造的一個重要突破是Garg 等[233]在無界函數(shù)密鑰腐化模型下, 基于iO構(gòu)造的選擇性安全的通用FE 方案.Boyle 等[234]則進一步基于推廣的差分輸入iO構(gòu)造了適應(yīng)性安全的通用FE 方案.而差分輸入iO的構(gòu)造可分別由iO[235]或多線性映射[236]給出.針對于iO的構(gòu)造, 密碼學界也展開了大量的研究[237–242], 其中文獻[241] 指出iO可以由三線性映射或者簡潔三次函數(shù)加密構(gòu)造, 而最新的里程碑成果[238]中, Jain 等從四個標準假設(shè)的亞指數(shù)困難性出發(fā)構(gòu)造出了亞指數(shù)安全的iO.

? 針對特定函數(shù)族的函數(shù)加密方案: Abdalla 等[243]首先研究了針對較為簡單的內(nèi)積函數(shù)的函數(shù)加密方案, 他們利用類似于并行ElGamal 加密的結(jié)構(gòu)基于DDH 假設(shè)構(gòu)造了選擇性安全的內(nèi)積函數(shù)加密方案, 利用類似的結(jié)構(gòu), 他們也得到了基于LWE 假設(shè)的選擇性安全的內(nèi)積函數(shù)加密方案.Agrawal 等[244]將文獻[243] 中的密文結(jié)構(gòu)改為類似于HPS 的密文結(jié)構(gòu), 并分別基于DDH、DCR、LWE 假設(shè)給出了適應(yīng)性安全的內(nèi)積函數(shù)加密方案.Agrawal 等[245]進一步改造文獻[244]中的內(nèi)積函數(shù)加密方案, 將其IND-CPA 安全性提升為SIM-CPA 安全性.理論上, 從內(nèi)積函數(shù)加密出發(fā)可以樸素地構(gòu)造出任意次數(shù)多項式的函數(shù)加密, 但是這種樸素構(gòu)造開銷過大, 比如二次函數(shù)的構(gòu)造至少是平方的密文開銷.另一方面, 受限于目前的密碼組件多是線性, 模擬二(高) 次多項式時常會出現(xiàn)交叉項而難以處理, 從而二次函數(shù)加密的構(gòu)造更顯得困難.Baltico 等[246]利用雙線性映射處理交叉項, 首次以線性的密文開銷實現(xiàn)了選擇性IND-CPA 的二次函數(shù)加密.Gay[247]提出了部分函數(shù)隱藏的內(nèi)積函數(shù)加密這一新的密碼原語, 并基于此給出了內(nèi)積函數(shù)加密方案向二次函數(shù)加密方案的通用轉(zhuǎn)換, 實現(xiàn)了半適應(yīng)性SIM-CPA 和半適應(yīng)SIM-CCA 安全的二次函數(shù)加密方案.Gong 和Qian[248]將底層線性組件模擬二次函數(shù)出現(xiàn)的交叉項用另一套內(nèi)積函數(shù)加密方案進行封裝加密, 得到了比文獻[247] 開銷更小的二次函數(shù)加密方案.Wee[249]則重新考慮了使用底層線性組件模擬二次函數(shù)的方式, 進一步得到了開銷更小的二次函數(shù).但是, 到目前為止, 能否在密文為線性的開銷下實現(xiàn)適應(yīng)性安全的二次函數(shù)加密仍然是一個長期的公開問題.

其他關(guān)于函數(shù)加密的研究主要集中在如何進一步增強函數(shù)加密方案功能的多樣性, 以便適用于更廣泛的應(yīng)用場景, 例如Goldwasser 等[250]為了實現(xiàn)n個輸入源下n個不同輸入源索引的消息mi(i ∈[n])的獨立加密以及協(xié)同的函數(shù)解密, 提出了多輸入函數(shù)加密這一新的密碼概念, 而多輸入函數(shù)加密在內(nèi)積函數(shù)[251–253]、二次函數(shù)[254,255]上均有深入的研究成果; 又例如一般的內(nèi)積函數(shù)或者是二次函數(shù)加密方案都會在最開始固定消息向量的維度, 這并不適宜于云計算背景中的應(yīng)用, 因為云服務(wù)器上存儲的密文是非常大的, 但是實際上云服務(wù)器只需要對其中的一部分進行函數(shù)計算, 從而如果函數(shù)解密算法作用于整體密文, 則云服務(wù)器計算開銷高昂.為了應(yīng)對此種場景, Datta 等[256]提出了無界(unbounded) 內(nèi)積函數(shù)加密, Tomida 和Takashima[257]基于對偶配對向量空間的方法給出了其在IND-CPA 安全性下的構(gòu)造,Tomida[258]也進一步把無界性推廣到二次函數(shù)加密的語境下, 并基于RO 給出了高效的構(gòu)造.除此之外,函數(shù)加密還有諸如多權(quán)威[259]、去中心化[260,261]、多層次[262]等更豐富功能性下的擴展變體.

5.4 可搜索加密

函數(shù)加密強大的功能性使得函數(shù)密鑰的擁有方能夠做指定的函數(shù)運算以知道消息的函數(shù)值, 其安全性則保證了函數(shù)密鑰的擁有方除了消息的函數(shù)值外一無所知.這樣的特點使得函數(shù)加密這一密碼原語擁有廣泛的應(yīng)用場景, 例如, 考慮如下云存儲的場景: 醫(yī)療機構(gòu)將巨量加密后的病歷及其對應(yīng)的關(guān)鍵詞索引等數(shù)據(jù)存儲在云服務(wù)器上, 除此之外, 醫(yī)療機構(gòu)也希望能夠通過與云服務(wù)器交互, 在加密的數(shù)據(jù)上檢索任何一位病人的病歷數(shù)據(jù), 且不會泄漏關(guān)于病例數(shù)據(jù)的明文的任何有效知識給云服務(wù)器和第三方.顯然,理論上來說, 針對全電路/圖靈機的函數(shù)加密可以完美地實現(xiàn)上述場景, 但是由于其存在性依賴于沉重的密碼組件, 極大的計算開銷和查詢復雜度使得其很難應(yīng)用到現(xiàn)實生產(chǎn)環(huán)境中.另一方面, 在加密數(shù)據(jù)上進行檢索又是現(xiàn)實中非常普遍的、亟需解決的問題, Song 等[263]針對這樣的場景, 首次提出了可搜索加密(searchable encryption, SE) 的概念, 并利用對稱加密構(gòu)造了非常高效的可搜索加密方案.從此之后, 可搜索加密飛速發(fā)展, 其上研究主要可以分為基于對稱加密的對稱可搜索加密(symmetric searchable encryption, SSE), 以及基于公鑰加密的非對稱可搜索加密(asymmetric searchable encryption, ASE), 下面將主要介紹ASE 方面的研究成果.

Boneh 等[228]首次將可搜索加密引入了公鑰密碼學的領(lǐng)域, 為其建立了基本的語義和形式化的安全模型, 并分別基于雙線性映射和陷門置換函數(shù)構(gòu)造了第一個基于公鑰加密的關(guān)鍵詞可搜索方案(publickey encryption with keyword searching, PEKS).Abdalla 等[264]則注意到身份加密中的身份和搜索關(guān)鍵詞的關(guān)聯(lián)性, 給出了匿名IBE 方案到PEKS 方案的通用轉(zhuǎn)換.但是以上關(guān)于ASE 的工作都是針對單關(guān)鍵詞的可搜索加密, 現(xiàn)實中的搜索應(yīng)該支持更為豐富的高級搜索選項, 例如多個關(guān)鍵詞、區(qū)間搜索、模糊搜索等.Golle 等[265]重新定義了基于公鑰加密下的可搜索加密的語義, 將其推廣到了支持多個關(guān)鍵詞的搜索, 并基于DDH 假設(shè)構(gòu)造了通信復雜度與數(shù)據(jù)庫中的數(shù)據(jù)量成線性關(guān)系的可搜索加密方案.Boneh等[229]提出隱藏向量加密(hidden vector encryption, HVE) 這一新的密碼原語, 并基于該原語分別給出了支持多關(guān)鍵詞、區(qū)間搜索、子集檢索的高效簡潔的可搜索加密方案的通用構(gòu)造框架.在安全模型上,Baek 等[266]注意到一般在討論可搜索加密的時候[228,264]都是單獨考慮關(guān)鍵詞域的安全性, 他們認為這樣安全模型并不完整, 因此將關(guān)鍵詞域部分的PEKS 和對應(yīng)的數(shù)據(jù)域部分的PKE 作為一個整體, 同時考慮其安全性, 定義了PKE-PEKS 的安全模型.Zhang 等[267]則注意到Baek 定義的PKE-PEKS 的安全模型忽略了關(guān)鍵詞域部分的安全性, 重新定義了PKE-PEKS 的安全模型.Bellare 等[268]進一步注意到在CCA 安全下不僅僅需要考慮PKE 解密諭言機的信息泄漏, 還需要額外考慮PEKS 的關(guān)鍵詞匹配諭言機的額外信息泄漏, 從而再度增強了PKE-PEKS 安全模型, 并利用基于標簽的CCA 安全的PKE 方案和PEKS 方案給出了滿足增強安全性后的PKE-PEKS 方案.Chen 等[269]則是改進了Bellare 等[268]的構(gòu)造, 給出了從匿名HIBE 到PKE-PEKS 的通用構(gòu)造, 其密鑰大小約為文獻[268] 中的一半.后續(xù)的工作則是進一步細化關(guān)鍵詞的搜索匹配模式, 比如針對于不同度量距離(如漢明距離、編輯距離等) 下的模糊搜索[270–273], 除此之外, 還有一系列工作是將可搜索加密推廣到更廣泛的使用場景下(例如多用戶等) [274,275].

以上構(gòu)造可搜索加密的底層公鑰加密方案幾乎都是概率性加密算法, 雖然得到的安全性較高, 但是云存儲服務(wù)器的查詢復雜度一般都與數(shù)據(jù)庫中的數(shù)據(jù)量成線性關(guān)系, 針對存儲著大量加密數(shù)據(jù)的云服務(wù)器, 這樣的查詢復雜度是無法接受的.另外一條實現(xiàn)可搜索加密的路徑是使用確定性加密(deterministic encryption) 方案.Bellare 等[276]提出了確定性公鑰加密, 形式化了其PRIV 安全模型, 并利用“以哈希值作為加密隨機數(shù)(encrypt with hash)” 的技術(shù)構(gòu)造了PRIV 安全的確定性公鑰加密.除此之外, 他們利用PRIV 安全的確定性加密方案給出了高效可搜索方案的通用構(gòu)造, 其思想極簡潔: 對關(guān)鍵字域做哈希運算得到關(guān)鍵字的短標簽, 然后將關(guān)鍵字用上述技術(shù)進行確定性加密就可以得到高效的可搜索加密(存儲相應(yīng)的短標簽和關(guān)鍵字的密文可以采用樹狀數(shù)據(jù)結(jié)構(gòu)).接收者若要查詢相應(yīng)的關(guān)鍵字, 可以直接計算關(guān)鍵字的哈希值得到其短標簽, 云存儲服務(wù)器根據(jù)短標簽的值可以采用類似于二分查找的方法快速定位相應(yīng)的關(guān)鍵字, 其查詢復雜度僅為數(shù)據(jù)量的對數(shù)級別.最開始滿足PRIV 安全性的確定性加密方案是在隨機諭言機(RO) 下進行構(gòu)造的, 而Boldyreva 等[277]利用文獻[41] 中的技術(shù)在較弱的PRIV1 安全模型下給出了標準模型和標準假設(shè)下的構(gòu)造.Bellare 等[278]進一步詳細討論了確定性加密不同安全性的等價關(guān)系,給出了更多的構(gòu)造.事實上, 如果關(guān)鍵字域的最小熵較小, 那么基于確定性加密的可搜索加密會遭受暴力遍歷攻擊, 并且Bellare[276]定義的安全模型是選擇性的模型, 而非適應(yīng)性的模型, 所以如何為確定性加密定義更強的安全模型并給出相應(yīng)的構(gòu)造是后續(xù)研究的主要關(guān)注點, 一系列的工作均圍繞此展開[279–284].

5.5 (全) 同態(tài)加密

身份加密、屬性加密、函數(shù)加密、可搜索加密的解密過程可以統(tǒng)一理解為用私鑰對密文進行秘密計算, 計算的結(jié)果為明文.從而, 即使是極致泛化的函數(shù)加密也無法對密文進行有意義的計算(在不擁有函數(shù)密鑰的情況下), 也就很難將數(shù)據(jù)的計算外包給半誠實或者惡意的云服務(wù)器.事實上, Rivest 等[285]就提出一個問題—“能否在保護數(shù)據(jù)隱私的同時實現(xiàn)數(shù)據(jù)的外包計算？” 這樣的問題在現(xiàn)實應(yīng)用中是非常普遍的, 比如, 某個醫(yī)療機構(gòu)想要對內(nèi)部采集的保密且巨量的基因數(shù)據(jù)進行分析, 顯然分析帶來的巨大計算開銷是普通機構(gòu)無法承受的, 這時, 在保證數(shù)據(jù)不泄漏的情況下實現(xiàn)相應(yīng)的計算任務(wù)就顯得極為重要.圍繞(全) 同態(tài)加密的研究正是為了能解決這樣的問題, 并且是以更省、更快、更普遍的方式加以解決.

根據(jù)可計算的函數(shù)類型, 同態(tài)加密的方案可分為部分同態(tài)加密和全同態(tài)加密(fully homomorphic encryption, FHE), 其中全同態(tài)的加密方案支持任意深度的電路, 而部分同態(tài)的加密方案僅支持非常受限類型的電路.事實上, 部分同態(tài)的PKE 方案很早就存在, 例如Goldwasser 等[286]的GM 加密方案即支持模2 上的無限制次數(shù)的加法運算, 又例如Rivest 等[10]的RSA 加密方案即支持Z?N上無限制次數(shù)的乘法運算.后續(xù)有很多方案在部分同態(tài)上走得更遠, 例如Boneh 等[287]的基于雙線性映射的PKE 方案可以支持有限域上無限制次數(shù)的加法和僅一次乘法, Sander 等[288]的PKE 方案可以支持對數(shù)深度的電路(即NC1).部分同態(tài)的加密方案要么存在著密文隨著同態(tài)運算次數(shù)的增多而快速膨脹的問題, 要么存在著僅能支持一種運算、或者有限次運算的問題.2009 年Gentry[289]基于理想格提出了真正意義上的全同態(tài)加密, 這是全同態(tài)加密領(lǐng)域的一個里程碑式的研究成果, 此后, 各種全同態(tài)加密方案被陸續(xù)提出, 下面按照四個世代對其展開闡述.

? 第一代全同態(tài)加密: Gentry[289]提出了第一個全同態(tài)加密方案, 其中的關(guān)鍵為自舉(bootstrapping) 技術(shù), 該技術(shù)可以在保證不損壞同態(tài)性的同時減少噪聲從而使得密文合法, 即可以正確解密,該技術(shù)可以將某些具有自舉性質(zhì)的部分同態(tài)的加密算法轉(zhuǎn)換為全同態(tài)加密算法, Gentry 基于理想格上的困難問題構(gòu)造了滿足自舉性質(zhì)的部分同態(tài)加密方案, 然后將其自舉, 得到了全同態(tài)加密方案.Gentry 的全同態(tài)加密方案雖然是理論上的一大突破, 但是實際運行效率并不高, 每比特運算需要耗時30 分鐘[290].Van Dijk 等[291]將文獻[289] 底層的基于理想格的部分同態(tài)加密方案換為基于整數(shù)的部分同態(tài)加密方案, 并沿用Gentry 的技術(shù)路線, 得到了第二個全同態(tài)加密方案.

? 第二代全同態(tài)加密: Brakerski 和Vaikuntanathan[292,293]革命性地改進了自舉技術(shù), 在標準格上基于(R)LWE 假設(shè)以及循環(huán)安全假設(shè)(circular security assumption) 構(gòu)造了兩個新的全同態(tài)加密方案, 他們引入了兩個非常重要的技術(shù), 即重線性化技術(shù)(re-linearization) 與模縮減(modulus reduction) 技術(shù).重線性化技術(shù)可以壓縮密文的大小, 防止其過度膨脹, ?？s減則可以將部分同態(tài)的密碼方案轉(zhuǎn)換為全同態(tài)的密碼方案, 該技術(shù)將較大模下的密文轉(zhuǎn)換為較小模下的另一密文, 引入的噪聲更小, 也不需要利用稀疏子集困難問題進一步壓縮電路, 更加高效.Brakerski 等[294]則進一步提出支持有限深度電路的層次化的全同態(tài)加密的概念, 使得全同態(tài)加密在一定程度上擺脫了計算開銷較大的自舉技術(shù), 大幅提高了效率.后續(xù)的工作則進一步通過引入并行化、打包、批處理[295,296]等優(yōu)化技術(shù), 使得效率進一步提高.而近期相關(guān)的研究則是僅基于RLWE 假設(shè), 在多項式環(huán)上實現(xiàn)上述BGV 方案[294]的變體, 效率更優(yōu)[297,298].

? 第三代全同態(tài)加密: Gentry 等[208]利用新的技術(shù)—近似特征向量方法(approximate eigenvector method), 避免了重線性化給乘法帶來的較大噪聲.Brakerski 和Vaikuntanathan[299]則注意到對于特殊的電路, GSW 方案[208]的噪聲增長速度更慢, 從而給出了更高效和更安全的實現(xiàn), 該全同態(tài)加密方案基于多項式近似的GapSVP 假設(shè).Alperin-Sheriff 和Peikert[300]進一步基于此觀察, 同時結(jié)合FFT (fast Fourier transform) 算法等優(yōu)化方法, 得到了具有高效的自舉過程的全同態(tài)加密方案.Chillotti 等[301]基于文獻[300] 的思想, 利用另外一種自舉方式[302]得到了極其高效的實現(xiàn), 其自舉一個比特僅需要12 ms.

? 第四代全同態(tài)加密: Cheon 等[303]提出了可以支持某些浮點運算的分層次全同態(tài)加密方案, 而浮點運算是諸多工業(yè)應(yīng)用(例如訓練神經(jīng)網(wǎng)絡(luò)) 所需要的, 這使得分層次全同態(tài)加密具備了落地實用的可能.次年, 他們[304]又將類似結(jié)果推廣到了全同態(tài)加密下.后續(xù)的工作則進一步研究了CKKS 方案的更優(yōu)化的實現(xiàn)[305,306], 例如支持打包等操作.Li 和Micciancio[307]討論了CKKS方案[303]在被動攻擊下的安全性, 他們指出在部分場景下, IND-CPA 安全性可能并不足夠, 并給出了一些具體的攻擊.關(guān)于Li 和Micciancio[307]的攻擊, 一些修補方法也陸續(xù)被提出[308].

總的來說, 自從Gentry[289]在2009 年提出第一個全同態(tài)加密方案后, 全同態(tài)加密的研究主要是對自舉技術(shù)不斷改進, 將自舉開銷從分鐘量級[290]最終降低到毫秒量級[309], Rivest 等[285]的愿景終于成為現(xiàn)實.

6 前沿進展與新方向

6.1 公鑰加密選擇密文安全的復雜度下界

公鑰加密中一個重要的公開問題是: CPA 安全的PKE 是否在黑盒意義下蘊含CCA 安全的PKE?近年的一系列前沿工作正式圍繞這一問題展開.Koppula 和Waters[310]提出了hinting PRG (帶提示的偽隨機數(shù)生成器), 并以此為工具給出了CPA 安全PKE 到CCA 安全PKE 的黑盒轉(zhuǎn)換.該結(jié)果并未解決公開問題, 因為目前已知的hinting PRG 構(gòu)造仍需依賴CDH 假設(shè)、大整數(shù)分解假設(shè)或LWE 假設(shè).根據(jù)已知的結(jié)果, 標準的單射單向陷門函數(shù)蘊含CPA 安全的PKE, 具有豐富性質(zhì)的單向陷門函數(shù)(如信息有損、相關(guān)積安全) 可以蘊含CCA 安全的PKE.Hohenberger 等[43]向著公開問題邁出了重要的一步,證明了標準的單射單向陷門函數(shù)即可蘊含CCA 安全的PKE.此后, 只需證明CPA 安全的PKE 蘊含單射單向陷門函數(shù)即可徹底解決公開問題.Garg 等[311]展示了結(jié)合具有偽隨機密文性質(zhì)的CPA 安全加密和hinting PRG 即可構(gòu)造出單向陷門函數(shù).因此, 我們認為今后研究的焦點將圍繞探尋構(gòu)造hinting PRG所需最弱假設(shè)展開.

6.2 細粒度模型下的公鑰加密

傳統(tǒng)密碼學中, 幾乎所有私鑰密碼方案的安全性都至少依賴單向函數(shù)的存在性, 而公鑰加密等公鑰密碼方案則依賴輸入同態(tài)弱不可預測函數(shù)等更強的密碼原語或者整數(shù)分解類、Diffie-Hellman 類等具體的結(jié)構(gòu)化數(shù)學假設(shè).然而, 至今單向函數(shù)是否存在仍是密碼學領(lǐng)域乃至整個計算復雜性領(lǐng)域中一個懸而未決的問題, 更遑論公鑰加密方案.隨著密碼分析技術(shù)的發(fā)展, 更強的密碼原語或結(jié)構(gòu)化數(shù)學假設(shè)一旦被攻破, 現(xiàn)有的公鑰加密大廈恐將瞬間坍塌.

為緩解上述威脅, Merkle[312]于1978 年開啟了關(guān)于細粒度模型下的密碼學(fine-grained cryptography) 的研究.細粒度模型下的密碼學旨在根據(jù)實際情況針對(如計算量、存儲量或算法回路深度等) 運算資源相對受限的攻擊者進行更精細的劃分和定義, 并要求: (1) 只基于非常弱的假設(shè)甚至不基于任何假設(shè)針對精細定義的攻擊者設(shè)計安全的密碼方案; (2) 用戶運行方案時所消耗的資源不超過攻擊者所消耗的資源, 以保證密碼方案能高效運行.一般情況下, 運行該類密碼方案所消耗的資源遠少于傳統(tǒng)密碼方案, 因此, 雖只考慮資源有限的攻擊者, 該模型下的密碼仍具有廣泛的實用價值.例如, 細粒度模型下的簽名能保證攻擊者偽造簽名須消耗一定時長, 因此能在降低成本的同時通過拒絕簽名超時的用戶來過濾攻擊者; 而細粒度模型下的加密能以極低的成本加密具有實效性的信息.此外, 通過利用雙層加密等手段將細粒度模型下的密碼方案與傳統(tǒng)密碼方案相結(jié)合, 可立即得到在強假設(shè)下能抵御任意的多項式攻擊者且在弱假設(shè)下能抵御資源相對受限的攻擊者的混合密碼方案.下面將重點介紹細粒度模型下公鑰加密領(lǐng)域的代表性成果.

Merkle[312]在隨機諭言機模型下提出了非交互密鑰交換協(xié)議, 其運行的時間復雜度為O(n) 并能抵御時間復雜度為O(n2) 的攻擊; Biham 等[313]則基于強單向函數(shù)實現(xiàn)了同樣的方案; LaVigne 等[314]基于zerok-clique 實現(xiàn)的私鑰交換協(xié)議可抵御復雜度為O(n1.5) 的攻擊者.這些方案都可被轉(zhuǎn)換為細粒度模型下的公鑰加密.Degwekar 等[315]基于被廣泛認可的最壞復雜假設(shè)NC1?⊕L/poly 針對NC1(即深度為O(logn) 且由多項式個扇入2 的與、或、非門組成的回路集合) 的攻擊者構(gòu)造了一個滿足INDCPA 安全性且能在AC0[2] (即常數(shù)深度且由多項式個無限扇入與、或、非、異或門組成的回路集合, 注:AC0[2] ?NC1) 中運行的公鑰加密方案.在同樣的細粒度模型下, Campanelli 和Gennaro[316]提出了準同態(tài)公鑰加密方案; Egashira 等[317]提出了細粒度模型下的單向陷門函數(shù)與滿足IND-CCA 安全性的公鑰加密方案, 并進一步提出了該模型下的全域單向陷門函數(shù)[317]; Wang 等[318]提出了該模型下的屬性基加密方案以及QA-NIZK, 前者可被實力化為針對多種謂詞函數(shù)的屬性基加密、廣播加密、身份加密以及模糊身份加密, 后者可用于實現(xiàn)帶有公開驗證機制的細粒度IND-CCA 加密; Wang 和Pan[319]則提出了該模型下的全同態(tài)公鑰加密方案.研究如何基于不同的弱假設(shè)使密碼原語抵御更大范圍的攻擊者以及如何在實現(xiàn)相同安全性的前提進一步弱化假設(shè)會是細粒度模型下的重要課題.

除了以上提及的兩個前沿方向外, 抗量子攻擊的公鑰加密方案是學術(shù)界和產(chǎn)業(yè)界共同關(guān)注的熱點與焦點, 關(guān)于這方面的前沿進展請參閱文獻[320].