基于二元哈希樹的密鑰隔離代理簽名方案

洪璇

（上海師范大學(xué) 上海 200234）

代理簽名是一種特殊的數(shù)字簽名，它是指當(dāng)某個(gè)簽名人（稱為原始簽名人）由于某種原因不能簽名時(shí)，將簽名權(quán)委托給他人 （稱為代理簽名人）替自己行使簽名權(quán)。1996年，Mambo，Usuda和Okamoto[1-2]首次系統(tǒng)地闡述了代理簽名的概念，并根據(jù)代理授權(quán)對(duì)代理簽名作了分類，即完全代理簽名、部分代理簽名和許可證授權(quán)的代理簽名。部分授權(quán)和許可證授權(quán)比全授權(quán)更安全，部分授權(quán)的優(yōu)點(diǎn)就是他的執(zhí)行速度，許可證授權(quán)非常適用于限制文檔。由于代理的特殊功能，近年來，代理簽名成為一個(gè)活躍的密碼學(xué)研究課題，并在諸如移動(dòng)代理，移動(dòng)通信，分布式系統(tǒng)，網(wǎng)格計(jì)算和電子選舉中被建議廣泛應(yīng)用。在某些應(yīng)用中，原始簽名人希望能控制代理簽名人的代理能力，需要采用密鑰隔離代理簽名方案保護(hù)代理人私鑰。密鑰隔離技術(shù)使得在保持公鑰不變的前提下，對(duì)用戶私鑰采取進(jìn)化的處理方法，在不同的時(shí)間片段內(nèi)使用不同的私鑰，個(gè)別時(shí)間段內(nèi)的密鑰泄漏不會(huì)危害其它時(shí)間片段內(nèi)的安全性，從而大大降低了密鑰泄漏所帶來的危害性。

Dodis等學(xué)者[3]在2002年提出密鑰隔離的概念。密鑰隔離機(jī)制將整個(gè)系統(tǒng)時(shí)間分為若干個(gè)時(shí)間片段，公鑰始終保持不變，而私鑰則在每個(gè)時(shí)間片段都進(jìn)行更新，不同的時(shí)間片段內(nèi)使用不同的臨時(shí)私鑰。用戶私鑰被分成兩部分：一部分為臨時(shí)私鑰，存放在用戶設(shè)備中；另一部分為協(xié)助器密鑰，存放于物理安全的協(xié)助器設(shè)備中。所有密碼操作（如解密、簽名等）均在用戶設(shè)備中進(jìn)行，而協(xié)助器只在每個(gè)時(shí)間片段的開始負(fù)責(zé)與用戶設(shè)備進(jìn)行交互以幫助用戶進(jìn)行臨時(shí)私鑰的更新，并不參與其它任何密碼操作。在某個(gè)時(shí)間片段內(nèi)的簽名操作，只涉及到該時(shí)間片段內(nèi)的臨時(shí)私鑰。因此，某些時(shí)間段發(fā)生臨時(shí)私鑰泄漏并不會(huì)危害其它未發(fā)生密鑰泄漏的時(shí)間片段的安全性。

Dodis等學(xué)者[4]給出了一個(gè)具體的（k，N）密鑰隔離簽名方案，但該方案只支持受限的時(shí)間片段數(shù)目，且公鑰和協(xié)助器密鑰的長(zhǎng)度與參數(shù)k成正比。Galindo等學(xué)者[5]給出了構(gòu)造基于身份密鑰隔離的通用方法：通過對(duì)公鑰基礎(chǔ)設(shè)施下的任意簽名和任意密鑰隔離簽名進(jìn)行巧妙的組合，就可以得到基于身份的密鑰隔離方案。然而所得方案的效率不是很理想，因?yàn)槠浜灻L(zhǎng)度比原來兩個(gè)簽名的長(zhǎng)度之和還要略長(zhǎng)。

筆者給出了一個(gè)新的密鑰隔離代理簽名方案。該方案降低了移動(dòng)代理濫用攻擊和密鑰泄漏產(chǎn)生的危害。該方案中的代理簽名仍然由移動(dòng)代理生成，移動(dòng)代理通過協(xié)助器的幫助下更新臨時(shí)密鑰，而公鑰PKPB在整個(gè)生命周期中都保持不變。相比之前的密鑰隔離方案，方案只需要額外的O（TN）次Hash操作和額外的比特存儲(chǔ)量。該方案的代理簽名的密鑰長(zhǎng)度是固定的，與隔離時(shí)間片段無關(guān)。且其代理密鑰是固定的q比特，對(duì)于密鑰長(zhǎng)度沒有任何增加。在隨機(jī)預(yù)言機(jī)模型下，證明方案的安全性基于所用的代理簽名。該方案在隨機(jī)預(yù)言機(jī)模型下是可證明安全的，其安全性證明是基于其所用簽名方案的安全性。從方案的執(zhí)行效率分析和移動(dòng)代理的特點(diǎn)出發(fā)，方案十分有效實(shí)用的，特別適合于能源受限的環(huán)境下的移動(dòng)代理系統(tǒng)。

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

1.1 密鑰隔離簽名安全模型

在2003年，Boldyreva等人[6]給出了代理簽名的形式化定義，相應(yīng)的，給出密鑰隔離代理簽名方案的安全模型。如果對(duì)于概率的多項(xiàng)式時(shí)間攻擊者A，它在查詢了最多q次的密鑰泄漏 Oracle 后，SuccA，KI（k）是可忽略的。 稱方案（G，U，S，V）是一個(gè)安全的（t，TN）密鑰隔離簽名方案。其中 SuccA，KI（k）的定義如下：

其中從來沒用消息（Ti，m）查詢過簽名預(yù)言機(jī)，也從來沒用消息（Ti，m）查詢過密鑰隔離預(yù)言機(jī)。具體來說，可以從如下幾個(gè)方面來衡量一個(gè)密鑰隔離方案的安全性：

（t，TN）密鑰隔離對(duì)于一個(gè)具有TN個(gè)時(shí)間片段的密鑰隔離方案來說，在最多允許t個(gè)時(shí)間片段發(fā)生密鑰泄漏的前提下，若其他時(shí)間片段的安全性仍然能得到保證，則稱該系統(tǒng)是（t，TN）密鑰隔離的。

完備密鑰隔離。若一個(gè)方案是（TN-1，TN）密鑰隔離的，則也稱它為完備密鑰隔離的。該性質(zhì)能夠保證，即使TN-1個(gè)時(shí)間片段的臨時(shí)私鑰都發(fā)生了泄漏，也不會(huì)危害剩下的那些時(shí)間片段的系統(tǒng)安全性。

1.2 二元Hash樹

定義的二元 Hash樹能認(rèn)證 Li（0≤i

對(duì)于每個(gè)樹葉Li=ND，i，都存在相應(yīng)的驗(yàn)證是該節(jié)點(diǎn)的i-兄弟路徑（PN，…，P1），如果該葉子節(jié)點(diǎn)沒有兄弟節(jié)點(diǎn)，Pi=0 那么。 驗(yàn)證公鑰是（D，R），其中 R=L0，0。

如果驗(yàn)證者需要驗(yàn)證Li，只需計(jì)算W0=R，其中WD=Li，和

2 密鑰隔離代理簽名方案

1）代理授權(quán)階段

為了把簽名權(quán)授權(quán)給代理簽名P，原始簽名人O按如下步驟執(zhí)行：

①原始簽名人O首先選擇授權(quán)許可證mw，其中包含時(shí)間片段數(shù)TN。然后O隨機(jī)選取k∈，并計(jì)算：K≡gkmod p和 eB=H（mw||K）。 協(xié)助器密鑰原始簽名人 O 把（eB，SKPB，mw）發(fā)送給代理簽名人 P。

2）代理簽名階段

為了在第Ti個(gè)時(shí)間片產(chǎn)生消息m的密鑰隔離代理簽名，P首先在協(xié)助器的幫助下產(chǎn)生臨時(shí)代理簽名密鑰SKPi=SKPB+li+H（SKPB‖Li）·xpmod q。 然后，P 用 SKPi作為臨時(shí)密鑰簽名消息m。簽名翻案采用DSS簽名方案。隨機(jī)選取ki∈，并計(jì)算：Ki≡gki mod p。代理簽名人Up計(jì)算簽名：

那么在第Ti個(gè)時(shí)間片段，消息m的代理簽名是（σ，Ti，certi）。

3）代理驗(yàn)證階段

如果驗(yàn)證者 V 需要驗(yàn)證（σ，Ti，certi），V 按如下方式執(zhí)行驗(yàn)證過程：

①首先從公共網(wǎng)上得到公開參數(shù)（mw，PKPB，（D，R））。

②驗(yàn)證消息m是否滿足許可證mw的要求。

③驗(yàn)證certi的有效性。如果需要確認(rèn)代理簽名人P有權(quán)利用SKPi代替O簽名，則要確定W0=R，其中：

如果這些驗(yàn)證都滿足，驗(yàn)證者V認(rèn)為代理簽名（σ，Ti，certi）是合法的。

3 方案性能及安全性分析

本文給出的密鑰隔離代理簽名方案降低了移動(dòng)代理濫用攻擊和密鑰泄漏產(chǎn)生的危害。該方案中代理簽名的長(zhǎng)度只是比簽名的長(zhǎng)度多（|q|+D·s）比特，如果代理簽名人P在公開目錄公開網(wǎng)上公開certi的話，那么該方案中就不存在額外的通信消耗。而且方案中的代理密鑰的長(zhǎng)度只是q比特。為了得到恰當(dāng)?shù)陌踩裕琿根據(jù)采用的簽名方案的安全參數(shù)決定，如Schnorr簽名一般令q=2160。在代理簽名產(chǎn)生階段，二元Hash樹只需要2TN+1次Hash計(jì)算量，且這些值都可以提前計(jì)算。同時(shí)在代理簽名驗(yàn)證階段，只需要額外的驗(yàn)證信息certi。因?yàn)樗恍枰硗狻竘og2TN?次Hash計(jì)算，驗(yàn)證結(jié)果才能接受。相比之前的密鑰隔離方案，該方案只需要額外的O（TN）次Hash操作和|q|比特多余的存儲(chǔ)量。

定理1：如果原始簽名人和代理簽名人都按照方案的規(guī)則執(zhí)行，那么該方案是可驗(yàn)證的。

定理 2：因?yàn)?DSS 簽名方案是選擇消息攻擊下的（ts，ξs）-安全的。假設(shè)H（·）是隨機(jī)預(yù)言機(jī)，該方案在選擇消息/許可證攻擊下是 （t，ξ）-安全的代理簽名方案， 其中 ts=t+（Qd）·exp（Os），εs≥ε-2-k。

定理3：令H（·）是一個(gè)抗碰撞的Hash函數(shù)，所用的簽名算法是安全的簽名算法。那么該方案是（TN-1，TN）完美密鑰隔離安全的。

推論4：密鑰隔離代理簽名方案KIP-SIG是正確的，可驗(yàn)證的，完美密鑰隔離的，且在選擇消息/許可證攻擊下是不可偽造的。

4 結(jié) 論

文中給出一個(gè)新的基于二元Hash樹的密鑰隔離代理簽名方案以降低了移動(dòng)代理濫用攻擊和密鑰泄漏產(chǎn)生的危害。因?yàn)樵摲桨傅拇鎯?chǔ)量和計(jì)算消耗都很少，所以十分適合于移動(dòng)代理。在隨機(jī)預(yù)言機(jī)模型下，證明該方案的安全性基于所用的代理簽名。

[1]Mambo M，Usuda K，Okamoto E.Proxy signature：delegation of the power to sign messages[J].IEICE Trans.Fundamentals，1996（9）：1338-1353.

[2]Mambo M，Usuda K，Okamoto E.Proxy signature for delegating signing operation[C]//ACM CCS 1996：48-57.

[3]Dodis Y，Katz J，Xu S，et al.Key-insulated public-key cryptosystems[C]//Eurocrypt，2002（2332）：65-82.

[4]Dodis Y，Katz J，Xu S，et al.Strong key-insulated signature schemes[C]//PKC 2003， volume 2567 of LNCS：130-144.

[5]GALINDO D，HERRANZ J，KILTZ E.On the generic construction of identity-based signatures with additional properties[C]//Asiacrypt 2006，volume 4284 of LNCS：178-193.

[6]BOLDYREVA A，PALACIO A，WARINSCHI B.Secure proxy signature schemes for delegation of signing rights[J].Journal of Cryptology，2012，25（1）：57-115.