一種公開參數(shù)長(zhǎng)度固定的非零內(nèi)積加密方案*

魏 鐸, 高海英, 趙 建

解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué), 鄭州450001

1 引言

函數(shù)加密[1,2]是一種先進(jìn)的密碼學(xué)模型, 有望極大地提高加密數(shù)據(jù)的可用性.內(nèi)積加密是一類特殊的函數(shù)加密, 與傳統(tǒng)公鑰密碼相比, 內(nèi)積加密能夠?qū)崿F(xiàn)對(duì)密文的細(xì)粒度訪問控制, 在云計(jì)算等新興領(lǐng)域有著廣泛的應(yīng)用.內(nèi)積加密分為零內(nèi)積加密和非零內(nèi)積加密兩類.本文研究的是非零內(nèi)積加密方案, 即在內(nèi)積加密方案中, 密文和密鑰分別與向量x,y相關(guān), 只有x與y滿足xTy=1 時(shí), 才可正確解密.內(nèi)積加密可以看作是基于身份加密的一般化, 它可以作為一種工具來構(gòu)造謂詞加密、屬性基加密和公鑰可搜索加密等密碼方案.

近年來, 一系列內(nèi)積加密方案相繼被提出.2008 年Katz[3]等人提出謂詞加密體制概念, 并構(gòu)造出首個(gè)基于整數(shù)的內(nèi)積加密方案, 比較完美的展現(xiàn)了內(nèi)積加密的本質(zhì).2010 年, Lewko[4]等人利用雙對(duì)偶向量空間(dual pairing vector space)[5,6]技術(shù), 設(shè)計(jì)了第一個(gè)適應(yīng)安全的內(nèi)積加密方案, 雖然方案安全強(qiáng)度比較高, 但方案的公開參數(shù)選取與屬性個(gè)數(shù)呈線性相關(guān).同年, Okamoto[7]等人借鑒文獻(xiàn) [3]的思想, 提出一個(gè)可分層的內(nèi)積加密方案, 并且方案實(shí)現(xiàn)了適應(yīng)安全, 但方案公開參數(shù)規(guī)模較大, 導(dǎo)致方案實(shí)用性不強(qiáng).2012 年, Okamoto[8]等人利用Waters[9]提出的雙系統(tǒng)加密(dual system encryption) 技術(shù)提出了一個(gè)適應(yīng)安全的內(nèi)積加密方案, 雖然該方案較方案 [7]實(shí)現(xiàn)了更強(qiáng)的屬性隱藏, 但方案的公開參數(shù)規(guī)模隨著屬性個(gè)數(shù)的增加而迅速擴(kuò)大, 導(dǎo)致參數(shù)規(guī)模過大, 方案實(shí)現(xiàn)效率比較低.由已有方案可以看出, 設(shè)計(jì)一個(gè)公開參數(shù)長(zhǎng)度固定且具有適應(yīng)安全性的內(nèi)積加密方案是一個(gè)有待解決的問題.

本文基于Chen 等人[10]提出的素?cái)?shù)階雙線性熵?cái)U(kuò)張性質(zhì), 提出了一個(gè)公開參數(shù)長(zhǎng)度固定的非零內(nèi)積加密方案, 方案是基于素?cái)?shù)階群雙線性映射設(shè)計(jì)的, 在方案的密鑰生成算法中, 將每個(gè)屬性與隨機(jī)向量結(jié)合, 為每個(gè)屬性生成私鑰分量; 在加密算法中, 利用隨機(jī)向量與矩陣結(jié)合的方法生成密文.基于素?cái)?shù)階雙線性熵?cái)U(kuò)張引理和MDDHnk,k+1困難假設(shè)證明了該方案具有適應(yīng)安全性, 并且公開參數(shù)規(guī)模明顯較少.

2 預(yù)備知識(shí)

2.1 符號(hào)說明

A,a: 矩陣A, 向量a

span(A): 矩陣A列向量張成的線性空間

spank+1(A): 矩陣A列向量張成的線性空間中的k+1 個(gè)向量模p剩余類環(huán)上m×n維矩陣集合、m維向量集合

(A1|A2|A3):Zp上3 個(gè)矩陣的連接

2.2 雙線性映射

定義 1(非對(duì)稱雙線性映射)[11]設(shè)G1、G2和GT為三個(gè)階為素?cái)?shù)p的乘法循環(huán)群, 且g1,g2分別是G1,G2的生成元.對(duì)于映射e:(G1,G2)→GT稱其為非對(duì)稱雙線性映射, 如果其滿足以下三條性質(zhì):

(1) 雙線性性: 對(duì)于 ?a,b∈Zp, 有

(2) 非退化性:e(g1,g2)1,g1,g2均不是單位元.

(3) 可計(jì)算性: ?g∈G1,h∈G2, 均可在多項(xiàng)式時(shí)間內(nèi)計(jì)算出e(g,h).

假設(shè)群生成算法?的輸入安全參數(shù)為 (1λ), 輸出元組為 (p,G1,G2,GT,g1,g2,e), 其中p為素?cái)?shù),g1,g2分別為G1,G2的生成元.對(duì)于[a]1表示 (g1a1,··· ,g1an), [a]2表示(g2a1,··· ,g2an), [a]T表示e(g1,g2)a, 即 [a]T=(e(g1,g2)a1,··· ,e(g1,g2)an).e:G1×G2→GT是一個(gè)非對(duì)稱雙線性映射, 將映射e擴(kuò)展到向量與矩陣上運(yùn)算形式如下:

2.3 困難假設(shè)

2.4 非零內(nèi)積加密方案形式化定義

一個(gè)非零內(nèi)積加密方案由以下四個(gè)多項(xiàng)式時(shí)間算法構(gòu)成:

Setup(1λ,1n): 該概率初始化算法輸入安全參數(shù)(1λ,1n), 輸出系統(tǒng)公開參數(shù)mpk 和主密鑰msk.

Enc(mpk,x,m): 該概率加密算法輸入公開參數(shù)mpk, 向量和明文m, 輸出密文ctx.

KeyGen(mpk,msk,y): 該概率密鑰生成算法輸入主密鑰msk 和向量輸出密鑰sky.

Dec(mpk,sky,ctx): 該確定性解密算法輸入 sky和 ctx, 若P(x,y)=1(即xTy=1), 則可解密密文.

2.5 非零內(nèi)積加密方案的適應(yīng)性安全模型

下面通過挑戰(zhàn)者B和攻擊者A之間的交互游戲給出非零內(nèi)積加密方案的適應(yīng)性安全模型.

Setup: 挑戰(zhàn)者B運(yùn)行方案的初始化算法,將生成的公開參數(shù)mpk 發(fā)送給攻擊者A,保留主密鑰msk.

Phase 1: 攻擊者A自行選擇y′進(jìn)行任意多項(xiàng)式次密鑰查詢.挑戰(zhàn)者B運(yùn)行 KeyGen 算法, 將生成的密鑰發(fā)送給A.

Challenge: 攻擊者A向挑戰(zhàn)者提交兩個(gè)等長(zhǎng)的明文m0和m1, 以及要挑戰(zhàn)的向量x?, (任何詢問y′與要挑戰(zhàn)x?都不滿足 (x?)Ty′= 1), 挑戰(zhàn)者B隨機(jī)選取b∈ {0,1}, 計(jì)算 ctx? = Enc(mpk,x?,mb), 并將ctx?作為挑戰(zhàn)密文返回給攻擊者A.

Phase 2: 與 Phase 1 相同.

Guess: 攻擊者A給出關(guān)于b的猜測(cè)b′.

如果b′=b, 稱攻擊者A贏得了此游戲, 定義A在此游戲中的優(yōu)勢(shì)為

定義4如果對(duì)所有多項(xiàng)式時(shí)間的攻擊者, 贏得上述游戲的優(yōu)勢(shì)都是可忽略的, 則稱該非零內(nèi)積加密方案是適應(yīng)性安全的.

3 方案描述

本文在Chen[10]等人提出的素?cái)?shù)階熵?cái)U(kuò)張引理基礎(chǔ)上, 提出一個(gè)公開參數(shù)長(zhǎng)度固定的非零內(nèi)積加密方案, 下面詳細(xì)介紹方案.

Setup(1λ,1n): 系統(tǒng)初始化階段輸入安全參數(shù)λ和系統(tǒng)屬性個(gè)數(shù)n.選取

方案的解密正確性得證.

4 安全性證明

該非零內(nèi)積加密方案在基于素?cái)?shù)階熵?cái)U(kuò)張引理和 MDDHnk,k+1困難假設(shè)下被證明是適應(yīng)安全的.在方案的證明過程中“·” 表示向量按分維乘, 下面先介紹安全性證明中涉及的相關(guān)概念.

密文分布:

密鑰分布:

標(biāo)準(zhǔn)密鑰: 由密鑰生成算法KeyGen 生成.

熵?cái)U(kuò)張密鑰:

其中dj←span(B).

偽半功能密鑰:

半功能密鑰: 與偽半功能密鑰形式相同, 區(qū)別在于dj←span(B).

方案的安全性證明是基于一系列Game 之間不可區(qū)分, 假設(shè)攻擊者A在一次Game 中最多可進(jìn)行Q次密鑰查詢, 用Advxx(λ) 表示攻擊者A在Gamexx的優(yōu)勢(shì).基于描述的密文、密鑰分布, 下面我們?cè)敿?xì)描述Game 序列, 并在表1 給出了 Game 序列的對(duì)比.

Game0: 查詢得到標(biāo)準(zhǔn)密鑰, 挑戰(zhàn)密文是標(biāo)準(zhǔn)密文.

Game0′: 查詢得到熵?cái)U(kuò)張密鑰, 挑戰(zhàn)密文是熵?cái)U(kuò)張密文.

Gamei: 查詢前i?1 次是半功能密鑰、最后Q?i+1 次是熵?cái)U(kuò)張密鑰, 挑戰(zhàn)密文是熵?cái)U(kuò)張密文.

Gamei,1: 查詢前i?1 次是半功能密鑰、最后Q?i次是熵?cái)U(kuò)張密鑰、第i次是偽標(biāo)準(zhǔn)密鑰, 挑戰(zhàn)密文是熵?cái)U(kuò)張密文.

Gamei,2: 查詢前i?1 次是半功能密鑰、最后Q?i次是熵?cái)U(kuò)張密鑰、第i次是偽半功能密鑰, 挑戰(zhàn)密文是熵?cái)U(kuò)張密文.

Gamei,3: 查詢前i?1 次是半功能密鑰、最后Q?i次是熵?cái)U(kuò)張密鑰、第i次是半功能密鑰, 挑戰(zhàn)密文是熵?cái)U(kuò)張密文.

GameFinal: 查詢得到半功能密鑰, 挑戰(zhàn)密文是對(duì)隨機(jī)數(shù)加密的熵?cái)U(kuò)張密文.

表1 Game 序列Table 1 Game sequence

引理 1如果存在一個(gè)攻擊者A在 Game0和 Game0′的攻擊優(yōu)勢(shì)滿足 |Adv0(λ)?Adv0′(λ)|>ε, 那么可構(gòu)造一個(gè)算法B0以不可忽略的優(yōu)勢(shì)區(qū)分素?cái)?shù)階熵?cái)U(kuò)張引理中的左右分布, 且Time(B0)≈Time(A).

證明:挑戰(zhàn)者B0得到分布:

B0需區(qū)分該分布是熵?cái)U(kuò)張引理的左分布, 還是右分布.

Phase 1: 攻擊者A申請(qǐng)向量對(duì)應(yīng)的私鑰, 挑戰(zhàn)者B0模擬密鑰生成算法, 在隨機(jī)選取向量生成向量y′對(duì)應(yīng)的密鑰

Challenge: 攻擊者A選擇兩個(gè)等長(zhǎng)的消息m0和m1, 以及要挑戰(zhàn)的向量Phase 1中的向量y′與要挑戰(zhàn)x?向量都不滿足 (x?)Ty′=1) 發(fā)送給挑戰(zhàn)者B0, 挑戰(zhàn)者B0隨機(jī)選取b∈{0,1},利用向量k以及得到的分布生成挑戰(zhàn)密文

Phase 2: 與 Phase 1 相同.

Guess: 攻擊者A給出b的猜測(cè)b′.

如果挑戰(zhàn)者B0得到的是左分布, 那么A詢問到標(biāo)準(zhǔn)密鑰與得到標(biāo)準(zhǔn)挑戰(zhàn)密文, 如果挑戰(zhàn)者B0得到的是右分布, 那么A詢問到熵?cái)U(kuò)張密鑰與得到熵?cái)U(kuò)張?zhí)魬?zhàn)密文.

如果攻擊者A的攻擊優(yōu)勢(shì)滿足 |Adv0(λ)?Adv0′(λ)|>ε, 那么挑戰(zhàn)者B0同樣以不可忽略的優(yōu)勢(shì)區(qū)分素?cái)?shù)階熵?cái)U(kuò)張引理的左右分布.

引理 2由表1, 可以得到 Game0′≡Game1.

引理 3如果存在一個(gè)攻擊者A在 Gamei和 Gamei,1的優(yōu)勢(shì)滿足 |Advi(λ)?Advi,1(λ)|>ε, 那么可以構(gòu)造一個(gè)算法B1以不可忽略的優(yōu)勢(shì)解決問題, 并且Time(B1)≈Time(A).

Phase 1,2: 設(shè)將攻擊者A對(duì)挑戰(zhàn)者B1進(jìn)行第κ次密鑰詢問, 對(duì)應(yīng)的向量是我們分三種情況討論:

Case 1:κ

發(fā)送給攻擊者A.

Case 2:κ>i, 挑戰(zhàn)者B1利用得到的分布隨機(jī)選取 [dj]2←span([B]2), 并且利用向量k和攻擊者A詢問的向量生成熵?cái)U(kuò)張密鑰sky′

發(fā)送給攻擊者A.

Case 3:κ=i, 挑戰(zhàn)者B1針對(duì)攻擊者A詢問的向量并且利用向量k、{[tj]2}j∈[n]和攻擊者A詢問的向量生成密鑰 sky′

發(fā)送給攻擊者A.

Challenge: 攻擊者A選擇兩個(gè)等長(zhǎng)的消息m0和m1, 以及要挑戰(zhàn)的向量(Phase 1 中的向量y′與要挑戰(zhàn)x?向量都不滿足(x?)Ty′=1)發(fā)送給挑戰(zhàn)者B1, 挑戰(zhàn)者B1隨機(jī)選取b∈{0,1},隨機(jī)選取生成挑戰(zhàn)密文

Guess: 攻擊者A給出b的猜測(cè)b.

如果 [t1,··· ,tn]=BS, 那么第i次詢問的密鑰是熵?cái)U(kuò)張密鑰, 上述游戲?qū)?yīng)的是 Gamei, 如果[t1,··· ,tn]=Z, 那么第i次詢問的密鑰是偽標(biāo)準(zhǔn)密鑰, 對(duì)應(yīng)的是 Gamei,1.

如果攻擊者A使 |Advi(λ)?Advi,1(λ)| >ε不可忽視, 那么挑戰(zhàn)者B1同樣以不可忽略的優(yōu)勢(shì)區(qū)分[t1,··· ,tn]=BS和 [t1,··· ,tn]=Z.

引理 4對(duì)于任意攻擊者A, 在 Gamei,1和 Gamei,2的優(yōu)勢(shì)滿足 |Advi,1(λ)?Advi,2(λ)|=0.

證明:Gamei,1和 Gamei,2不同之處僅在于第i次密鑰詢問, 挑戰(zhàn)者在 Gamei,1中用向量k生成偽標(biāo)準(zhǔn)密鑰, 在Gamei,2中用生成偽半功能密鑰.下面說明這兩個(gè)游戲無法區(qū)分.

Setup: 同引理 3 中的 Setup, 在這里挑戰(zhàn)者隨機(jī)選取輸出公開參數(shù)

Phase 1,2: Gamei,1中挑戰(zhàn)者B針對(duì)攻擊者A的第i次密鑰詢問的向量隨機(jī)選取向量生成y′密鑰

在 Gamei,2中, 挑戰(zhàn)者隨機(jī)選取生成密鑰

可以觀察到兩個(gè)游戲的第i次私鑰查詢差別僅在于這一分量, 分析這兩個(gè)分量

由于隨機(jī)值α以及隨機(jī)向量的參與,同分布, 故從攻擊者角度來看這兩種密鑰無法區(qū)分.

Challenge: 由于這兩個(gè)游戲輸出的都是熵?cái)U(kuò)張?zhí)魬?zhàn)密文, 同分布.

由上分析得到 |Advi,1(λ)?Advi,2(λ)|=0.

引理 5如果存在一個(gè)攻擊者A在 Gamei,2和 Gamei,3的優(yōu)勢(shì)滿足 |Advi,2(λ)?Advi,3(λ)|>ε, 那么可以構(gòu)造一個(gè)算法B2以不可忽略的優(yōu)勢(shì)解決問題, 并且Time(B2)≈Time(A).

證明:與引理 3 證明相似, 只是在密鑰查詢的時(shí)候: 第i次查詢用的向量k換成向量針對(duì)攻擊者A詢問的向量挑戰(zhàn)者B2利用向量和{[tj]2}j∈[n]生成密鑰發(fā)送給攻擊者A.

如果 [t1,··· ,tn]=Z, 那么第i次詢問的密鑰是偽半功能密鑰, 上述游戲?qū)?yīng)的是 Gamei,2, 如果[t1,··· ,tn]=BS, 那么第i次詢問的密鑰是半功能密鑰, 對(duì)應(yīng)的是 Gamei,3.所以如果攻擊者A使|Advi,2(λ) ? Advi,3(λ)| >ε不可忽視, 那么挑戰(zhàn)者同樣以不可忽略的優(yōu)勢(shì)區(qū)分 [t1,··· ,tn]=BS和[t1,··· ,tn]=Z.

引理 6由表1, 可以得到 Gamei≡Gamei?1,3.

引理7對(duì)于任意一個(gè)攻擊者A,在GameQ+1和GameFinal的優(yōu)勢(shì)滿足|AdvQ+1(λ)?AdvFinal(λ)|=0.

證明:這兩個(gè)游戲的差別在于 GameQ+1挑戰(zhàn)密文是消息mb的熵?cái)U(kuò)張密文, GameFinal挑戰(zhàn)密文是隨機(jī)數(shù)的熵?cái)U(kuò)張密文.下面來說明這兩個(gè)游戲不可區(qū)分.

Phase: 挑戰(zhàn)者B3針對(duì)攻擊者A申請(qǐng)?jiān)L問的向量隨機(jī)選取dj←span(B),生成半功能密鑰:

Challenge: 攻擊者A選擇兩個(gè)等長(zhǎng)的消息m0和m1,以及要挑戰(zhàn)的向量x?=(x?1,··· ,x?n)(Phase 1中的向量y′與要挑戰(zhàn)x?向量都不滿足 (x?)Ty′=1) 發(fā)送給挑戰(zhàn)者B3, 挑戰(zhàn)者B3隨機(jī)選取b∈{0,1},隨機(jī)選取向量c,cj,cj′←span(A1,a2), 生成挑戰(zhàn)密文

Phase 2: 與 Phase 1 相同.

Guess: 攻擊者A給出b的猜測(cè)b.

由以上分析得到 |AdvQ+1(λ)?AdvFinal(λ)|=0.

定理 1在素?cái)?shù)階熵?cái)U(kuò)張引理和困難假設(shè)成立的條件下, 本文提出的非零內(nèi)積加密方案是適應(yīng)性安全的, 并且max{Time(B0),Time(B1),Time(B2)}≈Time(A).

證明:在適應(yīng)性安全模型下, 攻擊者A對(duì)本文給出的非零內(nèi)積方案的攻擊優(yōu)勢(shì)就是對(duì)Game0的攻擊優(yōu)勢(shì), 由安全性證明中給出的Game 序列之間的關(guān)系, 可得:

由引理 1 知 |Adv0(λ)? Adv0′(λ)|<ε.由引理 2 知 |Adv0′(λ)? Adv1(λ)|=0.

Gamei到 Gamei+1的逼近可理解為:

由引理 3–6 知:

由引理 7 知 |AdvQ+1(λ)? AdvFinal(λ)|=0, 攻擊者A在 GameFinal中的優(yōu)勢(shì) AdvFinal(λ)=0.綜上分析, 得到攻擊者A在 Game0中的優(yōu)勢(shì) Adv0(λ)≤ (2Q+1)ε.

5 性能對(duì)比

本文基于素?cái)?shù)階群上的雙線性映射, 設(shè)計(jì)了一個(gè)公開參數(shù)長(zhǎng)度固定且適應(yīng)安全的非零內(nèi)積加密方案,本文與文獻(xiàn) [4,7,8]相比, 雖然在密鑰長(zhǎng)度與密文長(zhǎng)度有所增加, 但是在公開參數(shù)長(zhǎng)度方面具有絕對(duì)的優(yōu)勢(shì), 并且隨著屬性個(gè)數(shù)的增加, 文獻(xiàn) [4,7,8]公開參數(shù)長(zhǎng)度增長(zhǎng)程度遠(yuǎn)大于本文方案.下面給出當(dāng)k= 1時(shí), 本方案與現(xiàn)有內(nèi)積加密方案的數(shù)據(jù)長(zhǎng)度對(duì)比, 見表2.其中n表示系統(tǒng)屬性的個(gè)數(shù), |G1|,|G2|,|GT| 分別表示G1,G2,GT中群元素的長(zhǎng)度.

表2 與現(xiàn)有內(nèi)積加密方案的數(shù)據(jù)長(zhǎng)度比較Table 2 Parameter scale comparison with existing inner product encryption schemes

6 結(jié)束語

本文借鑒 Chen[10]等人提出的素?cái)?shù)階熵?cái)U(kuò)張引理, 基于素?cái)?shù)階群雙線性映射, 提出了一個(gè)公開參數(shù)長(zhǎng)度固定的非零內(nèi)積加密方案, 并在素?cái)?shù)階熵?cái)U(kuò)張引理和困難假設(shè)的基礎(chǔ)上證明了該方案是適應(yīng)安全的.與現(xiàn)有內(nèi)積方案相比, 本文方案的系統(tǒng)公開參數(shù)規(guī)模大大縮小, 方案操作性和實(shí)用性較強(qiáng).