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

洪璇

（上海師范大學 上海 200234）

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

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

Dodis等學者[4]給出了一個具體的（k，N）密鑰隔離簽名方案，但該方案只支持受限的時間片段數目，且公鑰和協助器密鑰的長度與參數k成正比。Galindo等學者[5]給出了構造基于身份密鑰隔離的通用方法：通過對公鑰基礎設施下的任意簽名和任意密鑰隔離簽名進行巧妙的組合，就可以得到基于身份的密鑰隔離方案。然而所得方案的效率不是很理想，因為其簽名長度比原來兩個簽名的長度之和還要略長。

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

1 預備知識

1.1 密鑰隔離簽名安全模型

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

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

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

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

1.2 二元Hash樹

定義的二元 Hash樹能認證 Li（0≤i

對于每個樹葉Li=ND，i，都存在相應的驗證是該節點的i-兄弟路徑（PN，…，P1），如果該葉子節點沒有兄弟節點，Pi=0 那么。 驗證公鑰是（D，R），其中 R=L0，0。

如果驗證者需要驗證Li，只需計算W0=R，其中WD=Li，和

2 密鑰隔離代理簽名方案

1）代理授權階段

為了把簽名權授權給代理簽名P，原始簽名人O按如下步驟執行：

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

2）代理簽名階段

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

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

3）代理驗證階段

如果驗證者 V 需要驗證（σ，Ti，certi），V 按如下方式執行驗證過程：

①首先從公共網上得到公開參數（mw，PKPB，（D，R））。

②驗證消息m是否滿足許可證mw的要求。

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

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

3 方案性能及安全性分析

本文給出的密鑰隔離代理簽名方案降低了移動代理濫用攻擊和密鑰泄漏產生的危害。該方案中代理簽名的長度只是比簽名的長度多（|q|+D·s）比特，如果代理簽名人P在公開目錄公開網上公開certi的話，那么該方案中就不存在額外的通信消耗。而且方案中的代理密鑰的長度只是q比特。為了得到恰當的安全性，q根據采用的簽名方案的安全參數決定，如Schnorr簽名一般令q=2160。在代理簽名產生階段，二元Hash樹只需要2TN+1次Hash計算量，且這些值都可以提前計算。同時在代理簽名驗證階段，只需要額外的驗證信息certi。因為它只需要另外「log2TN?次Hash計算，驗證結果才能接受。相比之前的密鑰隔離方案，該方案只需要額外的O（TN）次Hash操作和|q|比特多余的存儲量。

定理1：如果原始簽名人和代理簽名人都按照方案的規則執行，那么該方案是可驗證的。

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

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

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

4 結 論

文中給出一個新的基于二元Hash樹的密鑰隔離代理簽名方案以降低了移動代理濫用攻擊和密鑰泄漏產生的危害。因為該方案的存儲量和計算消耗都很少，所以十分適合于移動代理。在隨機預言機模型下，證明該方案的安全性基于所用的代理簽名。

[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.