具有短密文的多身份全同態(tài)加密構(gòu)造框架

王學(xué)慶, 王 彪, 薛 銳

1中國(guó)科學(xué)院信息工程研究所信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室 北京 中國(guó) 100093

2中國(guó)科學(xué)院大學(xué)網(wǎng)絡(luò)空間安全學(xué)院 北京 中國(guó) 100049

1 引言

全同態(tài)加密 (Fully Homomorphic Encryption,FHE) 是一個(gè)密碼學(xué)原語(yǔ), 它的功能是允許任何人對(duì)密文進(jìn)行任意計(jì)算, 滿足這樣的實(shí)際需求: 擁有較少資源的用戶, 既能保護(hù)持有數(shù)據(jù)的隱私性, 又能利用擁有較多資源服務(wù)器的強(qiáng)大計(jì)算能力, 適用于安全計(jì)算、隱私數(shù)據(jù)檢索等應(yīng)用場(chǎng)景。同態(tài)加密(Homomorphic Encryption, HE)的思想最早由Rivest,Adleman和Dertouzos在1978年提出[1], 雖然出現(xiàn)了很多HE方案, 如早于同態(tài)思想提出的RSA加密方案[2]、El Gamal加密方案[3]、BGN加密方案[4], 但是這些方案只滿足乘法同態(tài)、加法同態(tài)或較低次數(shù)多項(xiàng)式同態(tài), 直到2009年, Gentry才構(gòu)造出第一個(gè)FHE方案[5]。接下來, 基于不同假設(shè)、具有更多功能、更高效或構(gòu)造思想更自然的 FHE方案[6-14]如雨后春筍般涌現(xiàn)出來。

在 FHE的發(fā)展過程中, 借鑒在傳統(tǒng)公鑰加密基礎(chǔ)上發(fā)展出的密鑰生成與管理更方便的身份加密(Identity-based Encryption, IBE)[15], 2010年, Naccache將如何構(gòu)造身份全同態(tài)加密 (Identity-based Fully Homomorphic Encryption, IBFHE) 方案作為一個(gè)公開問題提出[16]; 2013年, Gentry, Sahai和Waters首次對(duì)這一公開問題作出了正面回答[13], 利用他們基于近似特征向量方法構(gòu)造的、無需計(jì)算密鑰的層次型全同態(tài)加密 (Leveled Fully Homomorphic Encryption,LFHE) 方案(以下簡(jiǎn)稱 GSW), 給出了一個(gè)可將已有基于DLWE假設(shè)的IBE方案, 轉(zhuǎn)換為身份層次型全同態(tài)加密 (Identity-based Leveled Fully Homomorphic Encryption, IBLFHE) 方案的框架; 2014年, Clear和McGoldrick利用不可區(qū)分混淆(Indistinguishability Obfuscation, iO) 方案和可穿孔的偽隨機(jī)函數(shù)(Puncturable Pseudorandom Function, PPRF)[17], 構(gòu)造了一個(gè)可將 FHE方案轉(zhuǎn)換為 IBFHE方案的框架;2015年, Clear和McGoldrick在GSW的基礎(chǔ)上, 給出了可將滿足特殊條件的 IBE方案, 轉(zhuǎn)換為多身份層次型全同態(tài)加密 (Multi-id Identity-based Leveled Fully Homomorphic Encryption, MIBLFHE) 方案[18](以下簡(jiǎn)稱 CM15), 其構(gòu)造方法也可將 GSW 這一LFHE方案轉(zhuǎn)換為多密鑰的層次型全同態(tài)加密(Multi-key Leveled Fully Homomorphic Encryption,MLFHE) 方案, 從而繼López-Alt等人的第一個(gè)基于非標(biāo)準(zhǔn)假設(shè)的 MLFHE方案[19]之后, 得到了第一個(gè)基于DLWE這一標(biāo)準(zhǔn)假設(shè)的方案。雖然CM15利用Gentry, Peikert和Vaikuntannathan的IBE方案[20](以下簡(jiǎn)稱GPV) 構(gòu)造了第一個(gè)單跳①的MIBLFHE方案,但是其安全性只能在隨機(jī)諭言機(jī) (Random Oracle,RO) 模型下得到證明, 且其構(gòu)造方法晦澀復(fù)雜。

在CM15的基礎(chǔ)上, MFHE的研究取得了較大的進(jìn)展, 2016年, Mukherjee和Wichs簡(jiǎn)化了CM15的構(gòu)造方法, 得到了一個(gè)簡(jiǎn)潔自然的、單跳的MLFHE方案 (以下簡(jiǎn)稱MW16)[21]; 同年, Brakerski和Perlman將 MW16中的簡(jiǎn)潔方法用于多密鑰的同態(tài)解密, 得到了一個(gè)短密文的、全動(dòng)態(tài)的 MFHE方案 (以下簡(jiǎn)稱BP方案)[22]; 幾乎同時(shí), Peikert和Shiehian靈活化了 MW16的構(gòu)造方法, 得到了兩個(gè)多跳的 MLFHE方案[23]。

關(guān)于MIBFHE的發(fā)展, 2017年, Canetti等人借鑒Brakerski等人構(gòu)造多屬性全同態(tài)加密的方法[24], 給出了一個(gè)構(gòu)造框架[25], 他們利用IBE方案和MFHE方案這兩種構(gòu)件。另外, 為了得到同時(shí)實(shí)現(xiàn)全動(dòng)態(tài)和全同態(tài)的 MIBFHE方案, 我們可以用滿足這兩個(gè)性質(zhì)的BP方案和基于DLWE假設(shè)的IBE方案去實(shí)例化,得到的方案密文規(guī)模為 O （n5lo g5q）,這里n,q是DLWE假設(shè)的參數(shù)。因密文規(guī)模是影響通信效率的關(guān)鍵因素, 故考慮如何構(gòu)造密文規(guī)模更小的 MIBFHE方案, 是一個(gè)具有重要理論意義和實(shí)際價(jià)值的問題。

1 我們的工作

首先, 我們?cè)诘?節(jié)構(gòu)造了一個(gè)可將MFHE方案轉(zhuǎn)換成 MIBFHE方案的框架。經(jīng)過觀察, 我們發(fā)現(xiàn)Canetti等人的框架有兩點(diǎn)不足: (i) 密文規(guī)模較大;(ii) 即使 MFHE的同態(tài)結(jié)果密文規(guī)模不依賴于輸入密文數(shù), MIBFHE的同態(tài)結(jié)果密文規(guī)模也與輸入密文數(shù)成正比, 即 MIBFHE的緊致性比 MFHE的變?nèi)?而導(dǎo)致這兩點(diǎn)不足的原因是: 密文不僅包括用MFHE的公鑰pk對(duì)消息的加密, 還包括pk和IBE的用戶公鑰 (mpk,id) 對(duì)MFHE的私鑰sk的加密。因密文規(guī)模是影響通信效率的關(guān)鍵因素, 從實(shí)際應(yīng)用出發(fā), 我們應(yīng)考慮如何減小密文規(guī)模。為了消除這兩點(diǎn)不足, 我們考慮只在密文中保留對(duì)消息的加密這一部分, 那么就需要用于加密消息的MFHE的pk與id有關(guān), 為了能夠解密, 用MFHE的sk作為skid, 從而需要將id嵌入 (pk,sk) 的生成過程, 一般的方法是將id與生成 (pk,sk) 所用的隨機(jī)串進(jìn)行關(guān)聯(lián), 可用PRF實(shí)現(xiàn)與id相關(guān)的隨機(jī)性, 而為了在證明中劃分挑戰(zhàn)身份id*和解密密鑰查詢的身份集合{idi}, 我們采用PPRF實(shí)現(xiàn), 這樣我們把PPRF的密鑰作為方案的主私鑰, 為了公布與skid配對(duì)的pkid, 可用iO實(shí)現(xiàn), 從而得到了只用MFHE構(gòu)造MIBFHE的框架。

① 同態(tài)計(jì)算的結(jié)果密文不能繼續(xù)參加有新用戶參與的同態(tài)計(jì)算。雖然我們用到了iO這一復(fù)雜度較高的工具, 但因只影響到主公鑰mpk的規(guī)模, 且主公鑰是公共的, 相比于密文規(guī)模, 對(duì)通信效率影響較小。

然后, 我們?cè)诘?節(jié)用BP方案[22]對(duì)第3節(jié)中構(gòu)造的框架進(jìn)行實(shí)例化, 得到了同時(shí)滿足全動(dòng)態(tài)和全同態(tài)性質(zhì)的、密文規(guī)模為O （ nlogq）的MIBFHE方案,且該方案的緊致性比Canneti等人方案的緊致性強(qiáng)。

2 基本概念

在這一章我們將給出本文將要用到的相關(guān)符號(hào)和概念的定義。

本文約定用a←RA表示從集合A中均勻隨機(jī)選取元素 a, 用←(除映射外)表示概率性得出, 用:=表示其左邊的結(jié)果由其右邊確定性計(jì)算得出, 用 PPT(Probabilistic Polynomial Time) 表示概率多項(xiàng)式時(shí)間,用 [n] 表示集合

2.1 帶錯(cuò)學(xué)習(xí)問題(Learning with Errors,LWE)

LWE問題是帶噪聲校驗(yàn)位學(xué)習(xí) (Learning Parity with Noise, LPN) 問題的一個(gè)擴(kuò)展, 最初由Regev提出[26], 有搜索性和判定性兩種形式, 通過設(shè)置合適的參數(shù), 搜索性 LWE與判定性 LWE (Decisional LWE, DLWE) 問題的困難性等價(jià), 下面只給出判定性LWE問題的定義:

定義1. 對(duì)于任意安全參數(shù)λ,設(shè)兩個(gè)整數(shù)n= n (λ),q = q (λ)≥ 2 ,一 個(gè) 支 撐 集 為 ? 的 分 布χ=χ( λ),用DLWEn,q,χ表示的 DLWE問題是指區(qū)這兩個(gè)分布。DLWEn,q,χ假設(shè)是指不存在求解 D LWEn,q,χ問題的PPT算法。

目前已知 Regev在2005年[26]、Peikert在 2009年[27]分別給出了從格上的近似最短向量問題到DLWEn,q,χ問題的量子歸約和經(jīng)典歸約, 由于目前尚無求解格上近似最短向量問題的多項(xiàng)式時(shí)間量子算法, 因此也沒有求解 D LWEn,q,χ問題的多項(xiàng)式時(shí)間量子算法, 進(jìn)而公認(rèn)基于 D LWEn,q,χ問題的密碼學(xué)方案是抗量子攻擊的。另外, 這些歸約中用到的χ都是高斯分布, 而高斯分布與取值恰當(dāng)?shù)腂χ有界分布統(tǒng)計(jì)不可區(qū)分[11], 因此為了簡(jiǎn)便, 本文方案中的噪聲分布都用Bχ有界分布。

下面給出Bχ有界分布的定義[11,13]。

定義 2. 設(shè)整數(shù)集?上的一個(gè)概率分布總體｛χn｝n∈?, 對(duì) 于 任 意 常 數(shù) Bχ＞ 0 ,若成立, 則稱該概率分布總體是Bχ有界的。

2.2 多身份全同態(tài)加密(Multi-id Identitybased Fully Homomorphic Encryption,MIBFHE)

若一個(gè)IBFHE方案能同態(tài)計(jì)算用不同身份加密得到的密文, 則稱它是多身份的?；诎踩钥紤],MIBFHE要求只有聯(lián)合參與同態(tài)計(jì)算的所有用戶,才能對(duì)結(jié)果密文進(jìn)行正確解密。

一個(gè)MIBFHE方案由以下五個(gè)多項(xiàng)式時(shí)間算法構(gòu)成:

-Setup（1λ）→ （ m pk , m sk）:概率性的系統(tǒng)參數(shù)生成算法 Setup以安全參數(shù)1λ為輸入, 生成公共參數(shù)mpk和主私鑰 m sk.

-KeyGen（ms k , i d ）→skid:概率性或確定性的解密密鑰生成算法KeyGen以主私鑰msk和身份標(biāo)識(shí)id為輸入, 生成id對(duì)應(yīng)的解密密鑰 s kid.

-Enc（mp k , i d ,μ ）→cid:概率性的加密算法Enc以公共參數(shù) m pk , 身份標(biāo)識(shí)id和消息μ為輸入, 生成只能用 s kid解密的密文 cid.

-Eval（mpk, f ,（ c1,… ,ct））→?:概率性或確定性的同態(tài)計(jì)算算法 Eval以公共參數(shù) m pk,電路f和與其輸入數(shù)相同個(gè)數(shù)的一組密文 c1,… ,ct為輸入, 這些密文可能對(duì)應(yīng)不同的身份標(biāo)識(shí) i d , 生成結(jié)果密文

-Dec（（skid1,… ,s kidN）,? ）→ μ:確 定 性的 解 密算 法Dec以密文c?和與其對(duì)應(yīng)所有身份標(biāo)識(shí)的解密密鑰（skid1,… ,s kidN）為輸入, 聯(lián)合解密得出消息μ。

一個(gè)MIBFHE方案的一些性質(zhì)定義如下:-全動(dòng)態(tài)性。設(shè) N = N(λ),t = t (λ),對(duì)任一可同態(tài)計(jì)算的電路 f ,任意 （id1, … ,i dN）和 （c?1,… ,c ?t）,滿足(m pk, m sk)←Setup(1λ),對(duì)于所有的i∈[N],

skidi←KeyGen(msk,idi),若Pr[D ec （ （sk1, … ,skN）,E val（mpk,f, (c?1, … ,c?t)））≠f(μ1, … ,μt) ] = negl(λ)成立, 則稱MIBFHE方案具有全動(dòng)態(tài)性; 否則, Setup算法以N作為輸入, 即預(yù)先給定可參與同態(tài)計(jì)算的最大用戶數(shù)。注意, 這里隱含了方案正確性的定義。

-緊致性。對(duì)于任意的同態(tài)計(jì)算結(jié)果密文c? ← Eval（mpk,f,｛ci｝）,存在一個(gè)多項(xiàng)式poly(.),使得 |c ?|≤ poly(λ),其中poly(.)獨(dú)立于電路f的規(guī)模、深度、輸入密文數(shù)或不同用戶數(shù)①因本文用于實(shí)例化的BP方案只關(guān)于電路的規(guī)模和輸入數(shù)具有緊致性, 故我們得到的MIBFHE方案也只關(guān)于電路的規(guī)模和輸入數(shù)具有緊致性, 即這里的poly只獨(dú)立于電路規(guī)模和輸入數(shù), 是關(guān)于安全參數(shù)、電路深度和不同用戶數(shù)的函數(shù)。。

-全同態(tài)性。若f是任意多項(xiàng)式深度的電路, 即方案可用于同態(tài)計(jì)算任意多項(xiàng)式深度的電路, 則該方案被稱為全同態(tài)加密方案; 否則, 若Setup算法以L作為輸入, 即預(yù)先給定可同態(tài)計(jì)算電路的最大深度,則稱該方案是層次型全同態(tài)加密方案 (Leveled Fully Homomorphic Encryption, LFHE).

-安全性。 MIBFHE方案的安全性定義與 IBE的相同, 一般考慮 IND-aID-CPA (又稱適應(yīng)安全性) 和IND-sID-CPA (又稱選擇安全性) 這兩種安全性, 下面給出IND-sID-CPA安全性的形式化定義。

IND-sID-CPA安全性實(shí)驗(yàn)由挑戰(zhàn)者C與敵手A交互執(zhí)行:

初始化階段: A向C提交將要挑戰(zhàn)的身份標(biāo)識(shí)id*;

參數(shù)生成階段: C根據(jù)方案生成mpk和msk, 并將mpk發(fā)送給A;

解密密鑰查詢階段(挑戰(zhàn)前): A選擇除 id*以外的任意身份標(biāo)識(shí)id對(duì)解密密鑰oracle進(jìn)行多項(xiàng)式次詢問,C充當(dāng)解密密鑰oracle, 回答與id對(duì)應(yīng)的解密密鑰;挑戰(zhàn)階段: A向C提交 (μ0, μ1), 要求μ0與μ1等長(zhǎng),C隨機(jī)選擇b∈{0,1}, 調(diào)用加密算法生成μb的密文cid*發(fā)送給A;

解密密鑰查詢階段(挑戰(zhàn)后): A可以繼續(xù)選擇除id*以外的任意身份標(biāo)識(shí)id對(duì)解密密鑰oracle進(jìn)行多項(xiàng)式次詢問, C按照挑戰(zhàn)前的方式進(jìn)行回答;

猜測(cè)階段: A向C提交對(duì)b的猜測(cè)b′, 若b′=b, 則輸出1, 否則輸出0.

IND-aID-CPA安全性定義與IND-sID-CPA安全性定義的區(qū)別是: 敵手 A在挑戰(zhàn)階段與消息一起選擇并提交挑戰(zhàn)身份id*.

注: 因MIBFHE方案是對(duì)IBE, FHE, MFHE方案的擴(kuò)展, 由 MIBFHE的定義易得出后三種方案的定義, 故在此只給出MIBFHE的定義。

2.3 不可區(qū)分混淆 (Indistinguishability Obfuscation, iO)

iO作為對(duì)虛擬黑盒 (Virtual Black Box, VBB)混淆的一種弱化方案, 最初由 Barak等人[28]在 2001年提出, 它用來保證任意兩個(gè)功能相同的電路混淆后計(jì)算不可區(qū)分。

定義 3. 設(shè)iO為一致的 PPT算法, 若對(duì)于一個(gè)電路分布簇｛Cλ｝, 若iO滿足以下兩個(gè)條件:

-正確性。對(duì)于任一安全參數(shù)λ∈N, 任一電路C∈Cλ,任一輸入x, 都有

-不可區(qū)分性。對(duì)任意 PPT 敵手(S amp, D ) ,(C0,C1, τ) ← S amp(1λ), 都存在一個(gè)關(guān)于λ的可忽略函數(shù) εiO, 使得如果Pr［C0(x) =C1(x) for ?x］ ＞1 - εiO,≤ εiO.則稱iO為不可區(qū)分混淆方案。

2.4 可穿孔的偽隨機(jī)函數(shù)(Puncturable Pseudorandom Function, PPRF)

PPRF作為一類簡(jiǎn)單的受限 PRF, 最初由 Sahai和Waters在2014年提出[29], 它允許PPT敵手首先給定一個(gè)多項(xiàng)式規(guī)模的輸入集合, 即使給敵手一個(gè)計(jì)算密鑰, 該密鑰可用來計(jì)算除此集合之外所有輸入的函數(shù)值, 它也難以區(qū)分一個(gè)值是此集合中輸入的函數(shù)值還是一個(gè)等長(zhǎng)的隨機(jī)元素。

定義 4. 一個(gè)可穿孔的偽隨機(jī)函數(shù)F:K × { 0,1}k→{0,1}m有兩個(gè)算法(Key, Puncture),滿足以下兩個(gè)條件:

-穿孔外的功能不變性。對(duì)于任意 PPT敵手 A,{0,1}k(λ)?S←A ( 1λ),對(duì) 于 所 有 不 在S中 的x ∈ { 0,1}k(λ),Pr[F ( K, x) = F ( K( S ) ,x) :K ← Key (1λ),K(S) ← Puncture(K,S)]=1成立。

-穿孔處的偽隨機(jī)性。對(duì)于任意PPT敵手 ( A1, A2),有

2.5 Brakerski和Perlman的全動(dòng)態(tài)多密鑰全同態(tài)加密方案

Brakerski和Perlman在CRYPTO 2016給出的方案[22]是目前已知的唯一一個(gè)全動(dòng)態(tài)→ M FHE方案, 其中用到一個(gè)特殊矩陣G: =I?gT,這里 I 表示

n+1n+1

-BP. S etup ( 1λ) :生成 D LWE假設(shè)成立的參數(shù)n,q,χq, n, m,χ,Bχ,其 中q是 模 數(shù), n是 維 數(shù),m = ( n + 1 )?q, Bχ-有界的分布 χ是噪聲分布,

令 B it(s k)表示sk的比特分解→

對(duì)于i∈ [m] ,Ri←R{0,1}m×m[ i] := ARi+ B it(s k )[ i].G

對(duì)于

輸出

-BP. E nc( p k,μ ∈ { 0,1}):隨 機(jī) 選 取

2.6 Canetti等人的多身份全同態(tài)加密構(gòu)造框架

設(shè)(M FHE.Setup, M FHE.KeyGen, M FHE.Enc,Eval, MFHE.Dec)是一個(gè) MFHE方案, (IBE.Setup, IBE.KeyGen, I BE.Enc, IBE.Dec)是一個(gè)IBE方案, Canetti等人[24]利用這兩類方案構(gòu)造了多身份的身份全同態(tài)加密方案, 其主要思想是將身份標(biāo)識(shí)到加密密鑰的映射與密文計(jì)算分開, 即利用 IBE方案的從身份標(biāo)識(shí)到加密密鑰的映射, 和 MFHE方案的同態(tài)計(jì)算能力, 既避免了僅利用 IBE存在密文擴(kuò)展問題所導(dǎo)致的無法利用已有的適應(yīng)性安全方案問題, 又解決了僅利用 MFHE方案存在的身份標(biāo)識(shí)到加密密鑰的映射問題。該思想與Brakerski等人[25]利用屬性加密和多密鑰全同態(tài)加密構(gòu)造多屬性全同態(tài)加密的思想相同。

-Setup ( 1λ) :PPMFHE←MFHE. S etup (1λ),(mpkIBE,mskIBE) ← IBE. S etup (1λ)

輸出 m pk : =(P PMFHE, m pkIBE) , msk : = mskIBE.-KeyGen(m sk, i d ):

輸出 s kid←IBE. K eyGen(m skIBE,i d ).-Enc ( m pk, i d ,μ):將mpk分解為

(PPMFHE,mpkIBE),

(pkMFHE,skMFHE) ← MFHE. K eyGen(PPMFHE),

c1←MFHE. E nc(pk,μ),

idMFHE

c2←IBE. E nc (mpk,id,sk),

idIBEMFHE

-Eval(f, (c1, … ,ct)):

假設(shè) c1,…,ct對(duì)應(yīng)不同的身份下標(biāo)集合I1,… ,It,

且滿足 {idi}i∈I1∪… ∪ {idi}i∈It={id1,… ,idN}

對(duì)于所有的i∈[t],將ci分解為

首先將c{idi}i∈[N]分解為

觀察以上構(gòu)造, 我們發(fā)現(xiàn)其新鮮密文不僅包括對(duì)消息的加密, 還包括MFHE的公鑰pk和IBE對(duì)MFHE的私鑰sk的加密, 另外, 其同態(tài)計(jì)算中的結(jié)果密文不得不包括所有輸入密文中 MFHE私鑰sk的密文的級(jí)聯(lián), 因此即使 MFHE緊致性較強(qiáng) (如同態(tài)結(jié)果密文規(guī)模僅與不同id數(shù)有關(guān), 而與輸入密文數(shù)無關(guān)), MIBFHE的同態(tài)結(jié)果密文規(guī)模也與輸入密文數(shù)成正比。

為了從以上構(gòu)造中得到全動(dòng)態(tài)的多身份全同態(tài)加密方案, 目前我們可以用基于 D LWEn,q,χ假設(shè)的IBE方案和 BP方案去實(shí)例化, 因已有的基于DLWEn,q,χ假設(shè)的 IBE方案[20,31-32]的密文空間最小為 ?m,根據(jù)2.5節(jié), 我們知道BP方案的公鑰空間為q故實(shí)例化得到的多身份全同態(tài)加密方案的密文規(guī)模為 O （n5lo g5q）.

3 具有較短密文和較強(qiáng)緊致性的多身份全同態(tài)加密構(gòu)造框架

如前所述, 我們僅利用 MFHE這一個(gè)構(gòu)件去構(gòu)造MIBFHE, 具體地, 將id與生成MFHE的 (pk, sk)的隨機(jī)串關(guān)聯(lián), 嵌入到其生成算法KeyGen中, 因已有MFHE方案KeyGen算法中的隨機(jī)元素是從?q或?中, 根據(jù)均勻分布或高斯分布選取出的向量或矩陣, 我們不是簡(jiǎn)單地利用一個(gè) PPRF, 而是針對(duì)每一類隨機(jī)元素, 增加概率抽樣算法, 作為PPRF生成的隨機(jī)串與 KeyGen算法所用隨機(jī)元素之間的橋梁,也就是將 PPRF生成的隨機(jī)串作為概率抽樣算法的隨機(jī)串, 概率抽樣算法的輸出作為 KeyGen算法的隨機(jī)元素, 從而使得PPRF的輸入id決定KeyGen算法的輸出（pkid,skid）,

設(shè)(M FHE.Setup, M FHE.KeyGen, MFHE.Enc, MFHE.Eval, MFHE.Dec)是一個(gè)MFHE方案,構(gòu)造的MIBFHE方案的身份標(biāo)識(shí)空間為{0,1}k,噪聲分布為Bχ-有界分布χ,iO是一個(gè)不可區(qū)分混淆方其 中 ?SampleU, ?SampleE分 別 是 概 率 算 法SampleU, SampleE的隨機(jī)數(shù)空間, 這里SampleU(A1,U)是指從集合 A1中按照均勻分布U隨機(jī)抽取出一個(gè)元素, S ampleE( A2,χ)是指從集合 A2中按照噪聲分布χ隨機(jī)抽取出一個(gè)元素。

-MIBFHE. S etup ( 1λ):P P←MFHE. S etup (1λ),K←F. K ey (1λ),令H為程序 FMapPK(見圖 1)的一個(gè)混 淆 iO(1λ,FMapPK), 輸 出mpk: = (PP,H),msk: =(PP,K).

(pkid,skid):= MFHE. K eyGen (PP; (Rid,Eid)),輸出skid.注意, 這里的集合 A1, A2由 M FHE. KeyGen算法決定。

-MIBFHE. E nc (mpk,id∈{0,1}k,μ):pk:= H(id),

id輸出 cid←MFHE. E nc(p kid,μ).

-MIBFHE. E val (mpk,f, (c1, … ,ct)):假 設(shè)c1,…,ct對(duì)應(yīng)于不同的身份下標(biāo)集合為 I1,… ,It,且滿足I1∪…∪It={id1,… ,idN},對(duì) 于 任 意i∈[N],pkidN),f,(c1,… ,ct)).

-MIBFHE. D ec ( (skid1,… ,skidN),:輸出 μ:= MFHE.

圖1 程序 F MapPKFigure 1 ProgramFMapPK

定理1. 若方案MFHE是IND-CPA安全的, iO是一個(gè)計(jì)算不可區(qū)分混淆方案和F是一個(gè)可穿孔的偽隨機(jī)函數(shù), 則方案MIBFHE是IND-sID-CPA安全的。

證明. 假設(shè)存在一個(gè) PPT的敵手A,攻擊MIBFHE方案 IND-sID-CPA安全性的優(yōu)勢(shì)為εMIBFHE(λ) , 我們將采用實(shí)驗(yàn)序列的方式證明εMIBFHE(λ)可忽略, 其中每個(gè)實(shí)驗(yàn)都由挑戰(zhàn)者C與敵手A交互執(zhí)行:

Game 0. 這是定義IND-sID-CPA安全性的原始實(shí)驗(yàn),首先敵手A向挑戰(zhàn)者提交將要挑戰(zhàn)的身份標(biāo)識(shí)id*,然后在參數(shù)生成階段, C調(diào)用(mpk,msk)←MIBFHE. S etup ( 1λ),并將mpk發(fā)送給 A .在解密查詢階段, 當(dāng)A對(duì)idi進(jìn)行查詢時(shí), C檢查idi是否等于id*,若是, 則拒絕回答, 否則調(diào)用skidi←MIBFHE. K eyGen (msk,idi),將skidi發(fā)送給A,這樣的查詢可執(zhí)行關(guān)于λ的任意多項(xiàng)式次。在挑戰(zhàn)階段, 當(dāng)收到A發(fā)送的一對(duì)等長(zhǎng)消息（μ0, μ1）時(shí),C從{0,1}中 隨機(jī) 選 擇 b, 調(diào) 用c←MIBFHE. E nc (mpk,id*,μ ),將c發(fā)送給

id*bid*A.在挑戰(zhàn)后的解密查詢階段, 對(duì)于A的詢問, C像挑戰(zhàn)前一樣處理。在猜測(cè)階段, A發(fā)送b′給C,若b′=b,C輸出1, 否則輸出0.

Game 1. 在參數(shù)生成階段, C生成 K ←F. K ey (1λ)后, 調(diào)用 K ( {i d*} ) ← F. P uncture(K , {i d*}),在挑戰(zhàn)前后的解密密鑰查詢階段, C利用K( {id*})而不是K回答A的解密查詢, 其他與Game 0中相同。

Game 2. C不在挑戰(zhàn)階段利用H生成 p kid*,而是在參數(shù)生成階段如下生成: 生成 K ←F. K ey (1λ)后,

圖 2 程序MapPKFigure 2 ProgramMapPK

Game 5. C不先選取 Rid*和 Eid*,而是直接調(diào)用MFHE. K eyGen(P P)生成 (pkid*,ski*d),其他與Game 4中相同。

接下來對(duì)以上實(shí)驗(yàn)進(jìn)行分析, 令Si表示敵手 A在Gamei(0 ≤i≤5)中取得成功這一事件。

因Game 0是IND-sID-CPA安全性的原始實(shí)驗(yàn), 故

Game 1與Game 0的唯一不同是在解密密鑰查詢階段, Game 0中C用K回答A對(duì) idi的查詢, 而Game 1中用的是 K ( {i d*}),根據(jù)PPRF穿孔外的功能不變性, 可得對(duì)于任意idi≠id*, F(K,idi)=即這兩個(gè)實(shí)驗(yàn)中的從而分別用作為隨機(jī)串選取的 Ridi和 Eidi相等, 用 Ridi和 Eidi作為 M FHE. KeyGen的隨機(jī)串生成的skidi相等, 故

Game 2與Game 1的不同有: (i)pkid*的生成位置和生成方式不同; (ii) 用來生成混淆方案H的程序不同。(i) Game 1中C在挑戰(zhàn)階段利用H生成pkid*,而Game 2中C在參數(shù)生成階段直接利用 K , 因Game 1中生成H的程序 FMapPK是直接用K生成任意id對(duì)應(yīng)的 p kid,根據(jù)不可區(qū)分混淆方案iO的正確性, 得對(duì)于 PPT敵手A,這兩個(gè)實(shí)驗(yàn)中生成的pkid*相同, 且pkid*的生成位置不同對(duì) A的猜測(cè)不會(huì)有任何影響;(ii) 根據(jù)PPRF穿孔外的功能不變性, 可得對(duì)于任意輸入 id , FMapPK與MapPK的輸出相同, 從而根據(jù)不可區(qū)分混淆方案iO的不可區(qū)分性, 得 A成功區(qū)分H ← iO ( 1λ,F )與H ← iO ( 1λ,)的概率可MapPK MapPK忽略, 設(shè)其概率為 εiO(λ),故

引理 1. 假設(shè)方案MFHE是 IND-CPA安全的,則敵手A在Game 5中的成功優(yōu)勢(shì)可忽略。

證明. 利用A構(gòu)造攻擊MFHE方案IND-CPA安全性的敵手 B : B收到自己的挑戰(zhàn)者所發(fā)送的(PP, pk)和A提交的 i d*,令pkid*:=pk,調(diào)用利用PP,pkid*和K( {id*})作為參數(shù)構(gòu)造程序FMapPK,將 m pk:= H 發(fā)送給 A .在解密查詢階段, B利用 K ( {i d*})生成解密密鑰對(duì)A進(jìn)行回答。在挑戰(zhàn)階段, 收到A發(fā)送的一對(duì)等長(zhǎng)消息（μ0, μ1）,B將其轉(zhuǎn)發(fā)給自己的挑戰(zhàn)者, 得到密文作為cid*發(fā)送給 A .在猜測(cè)階段, 收到A發(fā)送的猜測(cè)b′,B將其作為自己的猜測(cè)發(fā)送給挑戰(zhàn)者。

由MFHE方案的IND-CPA安全性, 得 εMFHE(λ)可忽略, 故A在Game 5中的成功優(yōu)勢(shì)可忽略。

綜合式(1)-(7), 可得

4 全動(dòng)態(tài)的多身份全同態(tài)加密方案

目前只有Brakerski和Perlman給出了全動(dòng)態(tài)的MF HE方案[22], 現(xiàn)用該方案對(duì)第3節(jié)中的MIBFHE框架進(jìn)行實(shí)例化, 因在此實(shí)例化中, 只有MIBFHE. Setup和 M IBFHE. KeyGen與框架中的相應(yīng)算法不同, 故下面只給出這兩個(gè)算法的描述。

設(shè)(B P.Setup, B P.KeyGen, B P.Enc, B P.Eval,BP.Dec)是Brakerski和Perlman的全動(dòng)態(tài)MFHE方案, F :K × { 0,1}k→? ×?,

11SampleU1SampleE

F:K × { 0,1}k× [ (n + 1 )?] → ?,

22qSampleU2

F:K ×{0,1}k×[m2(n+1)? ]→ ? 是三個(gè)PPRF,

33qSampleU3

?SampleU1,?SampleE, ?SampleU2,?SampleU3分別是概率算法SampleU1, S ampleE, S ampleU2, SampleU3的隨機(jī)數(shù)空間。

-MIBFHE. S etup(1λ):

(q,n,m, χ,Bχ,B) ← BP. S etup(1λ),

K←F. K ey ( 1λ), K ←F. K ey(1λ),

1 1 2 2

K←F. K ey (1λ),令H為程序 F (見圖3)的一個(gè)混

33PK

淆 iO (1λ,FPK),輸出mpk:=H,

msk : =(A, K1,K2, K3),其中 m pk, msk中都隱含參數(shù)q, n, m,χ,Bχ.

-MIBFHE. K eyGen (msk,id∈{0,1}k):

(r1,1,r1,2):= F(K,id),

idid1 1

對(duì)于任意i∈ [ (n+ 1 )? ],r2,i:= F(K,id,i),

qid22對(duì)于任意

j∈ [m2(n+ 1 )? ],r3,j:= F(K,id,j),

qid3 3

:=SampleU1( ?n,U;r1),e→ : = SampleE(?m,χ;r2),

qidid對(duì)任意

i∈[(n+1)? ],R:= SampleU2( {0,1}m×m,U;r2,i),對(duì)

q1,iid任意

j∈ [m2],R:= SampleU3( {0,1}m×m, U ; r3,(i-1)m2+j),

2,i,jid

(p kid,s kid):=

輸出 s kid.

因該方案的密文空間就是 BP方案的密文空間?n+1,故本方案的密文規(guī)模 O （nl o gq）遠(yuǎn)遠(yuǎn)小于 Canneti等人實(shí)例化方案的密文規(guī)模 O （n5lo g5q）.

定理2. 若方案BP是IND-CPA安全的, iO是一個(gè)計(jì)算不可區(qū)分混淆方案, F是一個(gè)可穿孔的偽隨機(jī)函數(shù), 則方案MIBFHE是IND-sID-CPA安全的。

證明. 根據(jù)文獻(xiàn)[22]中Lemma 4.1的證明和定理1的證明, 可得出該定理的證明。

圖3 程序 F P K#Figure 3 Program FPK

5 總結(jié)

觀察到Canetti等人的MIBFHE構(gòu)造框架的不足:密文規(guī)模大和緊致性弱, 本文構(gòu)造了密文規(guī)模較小和緊致性較強(qiáng)的 MIBFHE框架, 相比于前者用到MFHE和 IBE兩種構(gòu)件, 本文中的構(gòu)造僅需 MFHE一個(gè)構(gòu)件。若用Brakerski和Perlman的MFHE方案去實(shí)例化這兩個(gè)框架 (Canetti等人的框架還需用基于DLWE假設(shè)的IBE方案), 可得Canetti等人實(shí)例化方案的密文規(guī)模為 O (n5log5q),而實(shí)例化我們框架所得方案的密文規(guī)模為 O ( n l ogq). 然而, 我們的方案只能實(shí)現(xiàn)選擇安全性, 且用到了iO這一目前復(fù)雜性較高的工具, 故如何構(gòu)造更高效的、密文規(guī)模較小的、適應(yīng)性安全的 MIBFHE方案, 是我們將來要研究的問題。