可證明安全的可變門限代理重簽名方案

楊小東，張 磊， 王彩芬

(西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,甘肅 蘭州 730070)

1 引言

門限代理重簽名利用秘密共享技術(shù)，將重簽名密鑰分割成n個(gè)子密鑰分發(fā)給n個(gè)代理者管理，能有效減少重簽名密鑰泄露所帶來的損失。文獻(xiàn)[1]提出了兩個(gè)門限代理重簽名方案，但雙向門限代理重簽名方案所基于的代理重簽名方案存在安全缺陷。為了彌補(bǔ)該方案存在的安全缺陷，文獻(xiàn)[2]提出了一個(gè)改進(jìn)的雙向門限代理重簽名方案。在現(xiàn)有的門限代理重簽名方案中，門限值幾乎是固定的[1,2]。然而，在許多實(shí)際應(yīng)用場(chǎng)合中，參加重簽名的代理者數(shù)目往往取決于簽名消息的重要性，這就要求簽名方案的門限值k是可變的。例如,專家團(tuán)E去審查某公司的項(xiàng)目M時(shí)，如果M是一個(gè)大型項(xiàng)目，則需要k1(≤k)個(gè)專家成員參與生成項(xiàng)目M的重簽名；如果M是個(gè)中型項(xiàng)目，則需要k2(≤k1)個(gè)專家成員參與生成項(xiàng)目M的重簽名；如果M是一個(gè)小型項(xiàng)目，則需要k3(≤k2)個(gè)專家成員參與生成項(xiàng)目M的重簽名。

雖然代理重簽名的研究已取得了一定的進(jìn)展[3～7]，但門限代理重簽名和可變門限代理重簽名的研究才剛剛起步，關(guān)于可變門限代理重簽名的公開文獻(xiàn)非常少。文獻(xiàn)[8]提出了可變門限代理重簽名的思想，并構(gòu)造了一個(gè)可證明安全的可變門限代理重簽名方案，但該方案對(duì)存儲(chǔ)空間的要求比較高。本文提出一個(gè)具有較短公開參數(shù)和簽名長(zhǎng)度的可變門限代理重簽名方案，并給出了新方案的安全性證明。在門限重簽名密鑰生成算法中，分發(fā)者和每個(gè)代理者之間僅通信一次。根據(jù)可變的門限值，每個(gè)代理者都能非交互地生成相應(yīng)的重簽名子密鑰和驗(yàn)證公鑰。

2 準(zhǔn)備知識(shí)

設(shè)p是一個(gè)大素?cái)?shù)，G是一個(gè)階為p的循環(huán)群，g是G的一個(gè)生成元，群G上的CDH(Computational Diffie-Hellman)問題是：已知(g,ga,gb)∈G3，計(jì)算gab，這里a、b∈Zp。

定義1(CDH假設(shè))如果沒有一個(gè)概率多項(xiàng)式時(shí)間算法在時(shí)間t內(nèi)以至少ε的概率解決群G上的CDH問題，則稱群G上的(t,ε)-CDH假設(shè)成立。

定理1(中國(guó)剩余定理)設(shè)q1、q2、…、qk是兩兩彼此互素的k個(gè)正整數(shù)，Q=q1q2…qk，則一次同余方程組x=ai(modqi)(i=1,2,…,k)，對(duì)模Q有唯一解。

x=(Q1e1a1+Q2e2a2+…+Qkekak)(modQ)

這里Qi=Q/qi，Qiei=1(modqi)(i=1,2,…,k)。

定義2一個(gè)可變門限代理重簽名方案是一個(gè)由概率多項(xiàng)式時(shí)間算法構(gòu)成的七元組(Setup,KeyGen,RekeyShare,Sign,ResignShare,Combine,Ver)。

(1)Setup是系統(tǒng)參數(shù)生成算法：輸入一個(gè)安全參數(shù)1λ，輸出系統(tǒng)參數(shù)cp。

(2)KeyGen、Sign和Ver算法與標(biāo)準(zhǔn)數(shù)字簽名體制中的密鑰生成算法、簽名算法和簽名驗(yàn)證算法相同。

(5)Combine是門限重簽名生成算法：給定k個(gè)誠(chéng)實(shí)代理者對(duì)消息m的部分重簽名σB,i1,…,σB,ik，輸出一個(gè)對(duì)應(yīng)于公鑰pkB的消息m的門限重簽名σB。

3 一個(gè)新的可變門限代理重簽名方案

在Ateniese G等人[3]提出的代理重簽名方案Sbi的基礎(chǔ)上，提出了一個(gè)新的可變門限代理重簽名方案。該方案是雙向的、透明的、多用的和密鑰最優(yōu)的。新方案由受托者、委托者和n個(gè)半可信的代理者(P1,…,Pn)組成。新方案具體描述如下：

(1)Setup：給定一個(gè)安全參數(shù)1λ，選擇一個(gè)大素?cái)?shù)p和兩個(gè)階為p的循環(huán)群G1和G2，定義一個(gè)雙線性映射e:G1×G1→G2。選擇G1的一個(gè)生成元g和一個(gè)安全的密碼學(xué)哈希函數(shù)H:{0,1}*→G1。隨機(jī)選取n個(gè)兩兩互素的正整數(shù)q0

(3)RekeyShare：給定一個(gè)受托者的私鑰skA=α和一個(gè)委托者的私鑰skB=β，該算法執(zhí)行如下操作：

②根據(jù)中國(guó)剩余定理求解同余式組:

可得a0=y(modQ)。

④廣播Aj=gaj/α和Bj=gaj，j=0,…,n-1，其中A0=gβ/α，B0=pkB。

⑤根據(jù)中國(guó)剩余定理求解同余式組:

(4)Sign：給定一個(gè)私鑰sk=α和一個(gè)簽名消息m，輸出m的簽名σ=H(m)α。

(7)Ver：輸入一個(gè)消息m、一個(gè)公鑰pk和一個(gè)待驗(yàn)證的簽名σ，如果e(σ,g)=e(pk,H(m))，輸出1；否則，輸出0。

4 安全性分析與證明

4.1 正確性分析

本方案的正確性可以通過以下方程得到驗(yàn)證。

(1)門限值為k時(shí)的重簽名子密鑰的正確性驗(yàn)證。

(2)門限值為k時(shí)的部分重簽名的正確性驗(yàn)證。

e((H(m)α)fk(i)/α,g)=e(H(m)fk(i),g)=

e(H(m),gfk(i))=e(vkk,i,H(m))

(3)門限值為k時(shí)的門限重簽名的正確性驗(yàn)證。

e(H(m)β,g)=e(pkB,H(m))

4.2 安全性分析

利用文獻(xiàn)[8]可模擬性的安全性證明方法，證明本文提出的新方案的安全性。

定理2門限重簽名密鑰生成算法RekeyShare是可模擬的。

□

定理3門限重簽名生成算法ResignShare是可模擬的。

□

定理4本文提出的新方案是強(qiáng)壯的。

證明對(duì)于任意的門限值k，在RekeyShare算法中至少需要k個(gè)代理者才能重構(gòu)出重簽名密鑰，而最多可容許k-1個(gè)代理者被攻陷。在ResignShare算法中，一旦有惡意的代理者提供了非法的部分重簽名，重簽名合成者便能發(fā)現(xiàn)并確認(rèn)出代理者的身份。即使攻擊者攻陷了k-1個(gè)代理者，只要有k個(gè)誠(chéng)實(shí)的代理者就能產(chǎn)生一個(gè)正確的重簽名。當(dāng)代理者的數(shù)目n≥2k-1時(shí)，惡意的攻擊者無法影響方案的正確執(zhí)行，所以我們提出的可變門限代理重簽名方案滿足強(qiáng)壯性。

□

定理5如果一個(gè)可變門限代理重簽名方案是可模擬的，且關(guān)聯(lián)于該門限方案的代理重簽名方案是安全的，則可變門限代理重簽名方案也是安全的[8]。

定理6在隨機(jī)預(yù)言模型下，代理重簽名方案Sbi在適應(yīng)性選擇消息攻擊下是安全的，其安全性可歸約到CDH假設(shè)[3]。

結(jié)合定理2～定理6，可得如下定理：

定理7在隨機(jī)預(yù)言模型下，本文所提出的可變門限代理重簽名方案在CDH假設(shè)下是安全的；對(duì)于某個(gè)門限值k，如果n≥2k-1，則新方案也是強(qiáng)壯的。

4.3 性能比較

將本文提出的新方案與文獻(xiàn)[1,2,8]的雙向門限代理重簽名方案進(jìn)行計(jì)算開銷和帶寬效率方面的比較，結(jié)果如表1所示。但是，文獻(xiàn)[1,2]所提出的雙向門限代理重簽名方案的門限值是固定的，僅有文獻(xiàn)[8]提出的雙向門限代理重簽名方案的門限值是可變的。為了便于描述，令E表示G上的指數(shù)運(yùn)算，P表示雙線性對(duì)運(yùn)算，|G|表示G中一個(gè)元素的長(zhǎng)度，n表示代理者的總數(shù)，nm表示文獻(xiàn)[1,2,8]方案中待簽名消息的長(zhǎng)度。

Table 1 Comparison of bidirectional threshold proxy re-signature schemes表1 雙向門限代理重方案的比較

從表1可知，在本文提出的新方案中簽名算法Sign需要一次指數(shù)運(yùn)算，部分重簽名生成算法ResignShare需要一次指數(shù)運(yùn)算和兩次雙線性對(duì)運(yùn)算，簽名和重簽名僅為G中的一個(gè)元素。因此，新方案的計(jì)算開銷和帶寬效率高于文獻(xiàn)[8]的雙向可變門限代理重簽名方案。

5 結(jié)束語

本文基于代理重簽名方案Sbi，提出了一個(gè)可變門限代理重簽名方案，并給出了該方案的安全性證明。根據(jù)消息的重要性，能靈活地選擇不同的門限值進(jìn)行相應(yīng)的門限重簽名。在該方案中，分發(fā)者和代理者之間僅通信一次；代理者得到初始重簽名子密鑰后，根據(jù)可變的門限值能靈活地生成相應(yīng)的重簽名子密鑰和驗(yàn)證公鑰。與已有的同類方案相比，具有更短的公開參數(shù)和簽名長(zhǎng)度。如何在標(biāo)準(zhǔn)模型[9]下構(gòu)造安全高效的可變門限代理重簽名方案，將是我們下一步研究的工作方向。

[1] Yang Pi-yi,Cao Zhen-fu,Dong Xiao-lei.Threshold proxy re-signature[C]∥Proc of IPCCC’08, 2008:450-455.

[2] Yang Xiao-dong, Wang Cai-fen. Threshold proxy re-signature schemes in the standard model[J]. Chinese Journal of Electronics, 2010, 19(2E):345-350.

[3] Ateniese G, Hohenberger S. Proxy re-signatures:New definitions, algorithms, and applications[C]∥Proc of the 12th ACM CCS, 2005:310-319.

[4] Shao Jun, Wei Gui-yi, Ling Yun, et al. Unidirectional identity-based proxy re-signature[C]∥Proc of 2011 IEEE ICC, 2011:1-5.

[5] Guo Dun-tao, Wei Ping, Yu Dan, et al. A certificateless proxy re-signature scheme[C]∥Proc of IEEE ICCSIT’10, 2010:157-161.

[6] Yang Xiao-dong,Wang Cai-fen.Efficient on-line/off-line proxy re-signature schemes[J]. Journal of Electronics & Information Technology, 2011, 33(12):2916-2921.(in Chinese)

[7] Hong Xuan, Chen Ke-fei, Wan Zhong-mei. Simplified universally composable proxy re-signature[J]. Journal of Software, 2010, 21(8):2079-2088. (in Chinese)

[8] Yang Xiao-dong, Wang Cai-fen, Lan Cai-hui, et al. Flexible threshold proxy re-signature schemes[J]. Chinese Journal of Electronics, 2011, 20(4E):691-696.

[9] Sun Hua, Zhong Luo, Wang Ai-min. Provably secure identity-based threshold ring signature in the standard model[J]. Computer Engineering & Science, 2013, 35(3):92-96.(in Chinese)

附中文參考文獻(xiàn)：

[6] 楊小東，王彩芬.高效的在線/離線代理重簽名方案[J].電子與信息學(xué)報(bào)，2011,33(12):2916-2921.

[7] 洪璇，陳克非，萬中美.簡(jiǎn)單的通用可組合代理重簽名方案[J].軟件學(xué)報(bào)，2010,21(8):2079-2088.

[9] 孫華, 鐘珞, 王愛民. 標(biāo)準(zhǔn)模型下可證安全的基于身份門限環(huán)簽名[J]. 計(jì)算機(jī)工程與科學(xué), 2013, 35(3):92-96.