一種新型基于身份密鑰隔離的簽名方案

劉易+彭長根

【 摘 要 】 密鑰隔離方案能夠在一定程度上解決基于身份的密碼系統中密鑰分發中心權限過于集中的問題。基于支持多外圍設備的身份密鑰隔離簽名方案和Hess簽名方案，提出了一種新的基于身份密鑰隔離數字簽名方案；進一步針對密鑰隔離、強密鑰隔離和密鑰更新的安全性進行了分析；最后，通過與支持多外圍設備的身份密鑰隔離簽名方案和Hess簽名方案進行效率分析與比較，該方案驗算次數少、簽名長度短、速度快，更適用于資源受限的智能手機中。

【 關鍵詞 】 密鑰隔離；數字簽名；密鑰隔離安全性；效率分析

A New Identity- Based Key-Insulated Signature Scheme

Liu Yi 1，2，3 Peng Chang-geng 2，3

[1. College of Computer Science &Technology， Guizhou University GuizhouGuiyang 550025；

2. Guizhou Provincial Key Laboratory of Public Big Data （GuiZhou University）， GuizhouGuiyang 550025；

3. Institute of Cryptography & Data Security， Guizhou University GuizhouGuiyang 550025]

【 Abstract 】 Key-Insulated scheme can solve key distribution center permissions concentration problems based on identity cryptographic system in a way.This paper propose a new Identity-Based Key-Insulated digital signature scheme on the basis of supporting more peripheral Identity-Based Key-Insulated signature scheme and Hess signature scheme； and Key-Insulated，strong Key-Insulated and the key update security were analyzed； Finally， the scheme compared efficiency with supporting more peripheral Identity-Based Key-Insulated signature scheme and Hess signature scheme，the scheme is checking fewer，shorter length of signature，faster，more applicable in resource constrained smart phones.

【 Keywords 】 key-Insulated； digital signature； key-Insulated security； efficiency analysis

1 引言

Diffie和Hellman[1]最早在《New Direction in Cryptography》中提出了數字簽名的概念。1978年，Rivest、Shamir和Adleman[2] 第一個提出了基于大整數分解困難性的RSA數字簽名方案。次年，Shamir又提出了秘密共享方案[3]。基于身份密碼體系的概念和模型于1984年由Shamir首次提出[4]，此時數字簽名被正式分為三類：帶印章的數字簽名、帶影子的數字簽名及使用Hash函數的數字簽名。密鑰隔離機制的思想最早是在Eurocrypt02上由Dodis等 [5]提出的，隨后Dodis等在PKC03上給出了一個構造密鑰隔離數字簽名方案的通用方法，而且提出了一個具體的密鑰隔離數字簽名方案[6]。Hess提出一種高效可證明安全的基于身份數字簽名方案[7]。2014年杜瑞穎等[8]提出了一個無證書密鑰隔離簽名方案，這種方案解決了基于身份密鑰隔離簽名方案中存在的密鑰托管問題。2015年，學者秦志光等[9]對國內外密鑰隔離密碼系統的研究進展進行了綜述，并從方案性能、安全模型及安全性等方面進行了對比分析。2016年尋甜甜[10]提出了一種密鑰隔離的無證書聚合的概念與模型，實現對簽名者密鑰的定時更新。相比于傳統基于證書的密碼體制，基于身份的密碼體制近年來在密碼學中更受關注。在該體制中，任何一對用戶都可以進行安全的通訊，簽名公鑰其實就是用戶的身份信息，如身份、郵件地址等。基于身份的簽名體制是一種特殊的數字簽名體制，其避免了繁雜的證書管理，因此有著廣泛的應用前景。

針對密鑰泄露的問題，本文結合了支持多外圍設備的基于身份的密鑰隔離簽名方案與Hess簽名方案，提出了一種適用于智能手機的基于身份的密鑰隔離數字簽名具體方案，通過其他智能手機的協助來完成用戶的密鑰更新，這在一定程度上提高了系統的密鑰泄露容忍度，且保證了系統的前向與后向安全，同時方案的簽名長度短，由此提高了簽名效率。

2 相關知識

在這里將介紹基于身份的密鑰隔離簽名方案[11]與標準模型下基于身份的強密鑰隔離簽名方案[12]的定義、困難性假設、非交互的離散對數等式知識證明協議等概念。

定義1：P為強素數，t是正整數，c0，c1，...，ct-1，a1，...，at為常數，假設一個線性反饋移位寄存器序列（Ni），定義為一個t階齊次線性遞歸方程（HLFSR）：

N0 =c0 ，N1 =c1 ，...，Nt-1 =ct-1

Ni+t +a1 Ni+t-1 +...+aiNi =0 其中 i?0（1）

對t階齊次線性遞歸方程（HLFSR），定義一個輔助函數和特征方程，它們分別為：

xt + a1xt-1 +......+at =0，f（x）=xt + a1xt-1 +......+at

定理：假設HLFSR方程（Ni）用（1）定義，輔助函數的根為a1 ，...，al，根的重數分別為m1 ，m2 ，...，ml，m1 +m2 +...+ml =t。Ni =P1（i）α1i +P2（i）α2i +...+Pl（i）αli ，Pi（i）是一個最大次數為ml -1的多項式，當輔助等式只有一個重數是t的根α時，及（x-α）t =0，那么Ni =N（i）αi，N（i）表示為A0+A1i+...+At-1 it-1（2），其中N（i）是一個次數最多為t-1的多項式。

2.1 基于身份的密鑰隔離簽名方案的定義

在基于身份的密鑰隔離簽名方案當中，是由六個算法構成，這六個算法描述如下：IBKIS=（Setup，Extract，HelperUpt，UserUpt，Sign，Verify）：

（1）系統建立算法Setup（k，N）： 當安全參數和時間片段總數的輸入分別為k和N，則算法輸出系統公開參數param和相應的系統主密鑰msk。

（2） 私鑰提取算法Extract（msk，param，ID）：當輸入用戶身份信息ID、系統主密鑰msk及系統公開參數param時，則算法為用戶ID生成初始私鑰TKID，0和協助器密鑰HKID。

（3） 協助器密鑰更新算法HelperUpt（param，t，t'，ID，HKID）：當輸入系統公開參數param、用戶身份信息ID、協助器密鑰HKID及時間片段參數t和t'，則算法生成UIID，t，t'，UIID，t，t'將作為用戶ID的臨時私鑰時間片段t更新到t'所需的更新信息。

（4） 私鑰更新算法UserUpt（param，t，t'，ID，UIID，t，t'，TKID，t）： 當輸入系統公開參數param、時間片段參數t和t'、用戶身份信息ID、臨時私鑰TKID，t、以及更新信息UIID，t，t'，則算法輸出時間片段t'的臨時私鑰TKID，t'，并將TKID，t和UIID，t，t'刪除。

（5） 簽名算法Sign（param，t，M，TKID，t）：當輸入系統公開參數param、消息M、用戶身份信息ID、時間片段參數t和對應的臨時私鑰TKID，t，則算法輸出簽名（t，σ）。

（6） 簽名驗證算法Verify（param，（t，σ），M，ID）：當輸入系統公開參數param、簽名（t，σ）、消息M和身份信息ID，則算法輸出為1（當簽名有效時）或為0（簽名無效時）。

2.2 基于身份的強密鑰隔離簽名方案在標準模型下的定義

（1）Setup：給定一個安全參數k，PKG首先選擇α∈Zq*，g2∈G1且令g1 =gα ，然后選擇u'和m'生成兩個向量、，L1與L2表示為兩個函數，主密鑰msk=g2α ，則公開參數param=（G1，G2，e，q，g，g1，g2，u'，m'，，，H1，H2，L1，L2）。

（2）Extract：給定身份信息ID，PKG隨機選取一個協助器密鑰HKID∈{0，1}k，其中kID，0 =FHK（0 || ID）。如果輸入F的長度小于k，在最前面進行添加0以滿足長度要求；PKG隨機選擇r∈Zq*和初始密鑰TSKID，0。

（3） UpdH：給定身份信息ID、兩個時間片段t1和t2、協助器生成kID，t和kID，t、則通過返回協助器更新私鑰UKID，t，t。

（4）UpdS ：給定時間片段t1、協助器更新私鑰UKID，t，t、這兩個時間片段內的臨時私鑰TSKID，t和TSKID，t，得到時間片段t內的臨時私鑰TSKID，t。

（5）Sign ：在時間片段t內，通過簽名者ID對應的臨時簽名私鑰TSKID，t，為消息m生成簽名σ。

（6）Verify ：簽名σ、身份信息ID與消息m，驗證者是否接受此簽名取決于σ=（t，g2α ·L1（U'ID）r ·L1（U'ID，t ） ·L2（Mm ），g，g，g）是否成立。

2.3 困難性假設

假設G是一個加法群，則有：

（1） 離散對數困難問題：給定兩個P，Q∈G，要找出一個正整數n∈Zq*，使之滿足Q=nP是困難的。

（2）CDH問題：對于a，b∈Zq*，P∈G，給定（P，aP，bP），計算abP是困難的。

2.4 非交互的離散對數等式知識證明協議

設G是q階乘法群，g與h是它的兩個生成元，證明者P利用α∈Zq*來滿足α=log gG =log hH，證明者P要讓驗證者V相信他確實知道秘密信息α，但不泄露α的值。

3 一種新型基于身份的密鑰隔離數字簽名方案實現

本節首先通過形式化定義一些系統參數，然后設計一個新型基于身份密鑰隔離數字具體簽名方案。

3.1 形式化定義

參數設置：1n表示系統安全參數、t和t'表示任意兩個不同的時間片段、n表示智能手機的個數、簽名者的身份信息用ID表示，SPKi表示第i（i=1，2，...，n）個智能手機的密鑰、UKID，t表示身份信息為ID的簽名者在第t個時間片段內的簽名私鑰、MID表示第i（i=1，2，...，n）個智能手機的密鑰演化信息，這n個中任意k個智能手機均由差值多項式計算出系統的密鑰演化信息MIDID，t，t'，且協助簽名者實現臨時簽名私鑰的更新。

一中新型基于身份的密鑰隔離數字簽名方案由六個多項式算法組成，這些算法分別表示為（Setup，Extract，HelperUpt，UserUpt，Sign，Verify），以下對這些算法進行詳細描述。

（1） 系統初始建立算法Setup（1n）：輸入系統安全參數1n，輸出系統公開參數param和主密鑰mask。

（2） 初始私鑰生成算法Extract（mask，param，ID）：輸入系統公開參數param、主密鑰mask以及簽名者的身份信息ID，輸出簽名者的初始簽名私鑰UKID，0及智能手機的密鑰SPK。

（3） 智能手機密鑰更新算法HelperUpt（param，t，t'，ID，SPK）： 輸入系統公開參數param、任意兩個時間片段t和t'、簽名者的身份信息ID及智能手機密鑰SPK，輸出密鑰演化信息MIDID，t，t'，該密鑰演化信息MIDID，t，t'協助簽名者將其臨時簽名私鑰由時間片段t更新到時間片段t'。

（4） 臨時簽名私鑰更新算法UserUpt（param，t，t'，ID，MIDID，t，t'，UKID，t）：輸入系統公開參數param，任意兩個時間片段t和t'、簽名者的身份信息ID、時間片段t內的臨時簽名私鑰UKID，t及密鑰演化信息MIDID，t，t'，輸出時間片段t'內的臨時簽名私鑰UKID，t'，然后把UKID，t和MIDID，t，t'刪除。

（5） 簽名算法Sign（param，t，M，UKID，t）：輸入系統公開參數param、時間片段t、消息M及時間片段t內的簽名者臨時簽名私鑰UKID，t，輸出簽名者在時間片段t內對消息M的簽名（t，ID，U，V）。

（6） 對應簽名的驗證算法Verify（param，（t，ID，U，V）M，ID）：輸入系統公開參數param、簽名（t，ID，U，V）、消息M及簽名者的身份信息ID，如果簽名（t，ID，U，V）是簽名者在時間片段t內對消息M的有效簽名，則算法最終輸出1，否則算法輸出0。

3.2 具體方案

3.2.1系統初始建立算法

算法通過執行如下步驟生成系統公開參數param以及系統主密鑰mask，參數param是公開，而系統主密鑰mask由PKG秘密保存。

（1） 設一個加法群G和一個乘法群GT ，而且它們的階都是素數p，同時設群G的兩個生成元分別為P與P'及一個雙線性映射e：G×G→GT 。

（2） 選取四個單向的哈希函數：H1：{0，1}*→G，H2：{0，1}*→G，H3：{0，1}*×GT →Zp*，H：{0，1}*→G。

（3） 隨機選取一個整數s∈Zp* ，并令系統公鑰Ppub=s·P，用戶公鑰Upub=s-1·UKID，t 。

（4） 算法輸出系統主密鑰及系統公開參數：系統主密鑰為mask=s，而系統公開參數為param=（G，GT，e，p，P，P'，Ppub ，H1，H2，H3）。

3.2.2 私鑰生成算法

輸入系統主密鑰mask，簽名者身份信息ID∈（0，1）*及系統公開參數param，PKG為簽名者生成初始私鑰和智能手機密鑰的步驟有幾個。

（1） 隨機選取一個SPK∈Zp*，然后構造一個齊次線性遞歸序列，選擇兩個強素數m、n，使得N=mn，選擇一個與φ（N）互素的整數c，計算d，使得cd=1modφ（N），計算I0 =gd modN并公布（c，N）。n個參與者選擇自己的秘密Si，計算Ii =gSi modN后發送給PKG，PKG計算SPKi=IidmodN，SPKi≠SPKj，且當i≠j時。

（2）N0 =SPK1 ，N1 =SPK2 ，...，Nt-1 =SPKt

Ni+t +a1 Ni+t-1 +...+aiNi =0mod P，其中i?0。計算Ni（t?i?n+1），計算Yi=Ii-Ni （t?i?n）和r=SPK-Nn+1，公開（I0 ，I1 ，...，In ，r，Yt+1 ，...，Yn ）。第j個參與者對第i個參與者進行驗證，第i個子密鑰為SPKi =I0Si modN，假設第i個參與者提供的份額為SPKi'，則第j個參與者計算（SPKi' ）c modN=Ii'。如果Ii'=Ii，則沒有欺騙，否則有欺騙。

（3） 由LID=SPK·H（ID）·P和QID，0 =s·H1（ID）+SPK·H（ID）·H2（ID，LID，0）計算出LID和QID，t ；同時令初始私鑰UKID，0 =（QID，0 ，LID ）。

（4）該算法最終將會輸出簽名者的初始私鑰UKID，0以及第i個智能手機的密鑰SPKi =（SPK（i）·H（ID），LID），同時算法還會向所有的智能手機廣播一個對SPKi的承諾hi =SPK（i）·H（ID）·P'以驗證密鑰的正確性。

3.2.3 第i個智能手機的密鑰更新算法

當智能手機在收到簽名者的私鑰更新請求之后，第i個智能手機就會執行這個密鑰更新算法，得到自己持有的部分密鑰更新信息。輸入系統公開參數param，時間片t和t'及第i個智能手機的密鑰SPKi ，算法最終將會輸出第i個智能手機持有的部分密鑰更新信息MID=SPKi ·H（ID）·（H2（ID，LID，t'）-H2（ID，LID，t））。

3.2.4 簽名者執行的臨時簽名私鑰更新算法

在某個特定的時間片段內，簽名者執行的臨時簽名私鑰更新算法為五個步驟，執行完畢后，簽名者的臨時簽名私鑰將會從時間片段更新到時間片段t'。

（1） 首先將時間片段t內的臨時簽名私鑰UKID，t按照UKID，t =（QID，t ，LID ）進行分解。

（2） 使用非交互的離散對數等式知識證明協議，第i個智能手機向簽名者驗證自己所提供的部分密鑰更新信息MID是正確的。由3.2.2與3.2.3可以知道，第i個智能手機知道一個對SPKi的承諾hi =SPK（i）·H（ID）·P'以及部分密鑰更新信息MID=SPKi ·H（ID）·（H2（ID，LID，t'）-H2（ID，LID，t））。由離散對數的零知識證明可知，第i個智能手機在知道SPK（i）的前提下，很容易就能夠計算出下列等式成立log=log，所以也就可以驗證第i個智能手機輸出的部分密鑰更新信息MID為正確。

（3）n個智能手機中任意k個均可插值得到完整的密鑰演化信息MID，且完整的密鑰演化信息MID=C（x）·Smod p；其中，n個智能手機中任意k個智能手機組成的一個群體用B表示，插值系數多項式為C（x）=mod p，Si =MID。

（4） 計算QID，t' =QID，t +MID，并將時間片段t'的簽名者臨時私鑰更新為UKID，t' =（QID，t' ，LID ）。

（5） 輸出時間片段t'的臨時私鑰UKID，t' ，并將UKID，t和MID刪除。

3.2.5 簽名算法

在時間片段t內，簽名者利用該時間片段內簽名者的臨時私鑰UKID，t，按如下步驟對消息M進行簽名。

（1） 隨機選取k∈Zq*，計算r=e（P，P'）k；

（2） 計算V=H3（M，r）；

（3） 計算U=kP'+V·UKID，t，則對消息M的簽名是（t，ID，U，V），且簽名屬于GT ×Zq*。

3.2.6 對應簽名的驗證算法

輸入系統公開參數param、簽名（t，ID，U，V）、簽名者身份信息ID及消息M，驗證者按如下步驟驗證簽名的有效性。

（1） 用戶的公鑰Upub =s-1·UKID，t；

（2） 計算r=e（U，P）e（Upub ，Ppub ）V，驗證：當且僅當V=H3（M，r）時驗證者認為此簽名正確。

4 新型的基于身份的密鑰隔離簽名方案分析

本節對所設計方案的安全性和效率分別進行分析。

4.1 安全分析

一個良好的方案滿足三個安全性。

（1）（k，N）密鑰隔離安全性：在群G上的CDH問題是難解的，從而所有智能手機的部分密鑰都是在安全的前提下，當攻擊者沒有截取到超過k個時間片段內用戶的簽名私鑰，攻擊者將不能偽造用戶的簽名。在這種情形下，該方案滿足了密鑰隔離安全性。

（2） 強密鑰隔離安全性：在本方案中，用戶簽名私鑰是由時間片段t時的臨時簽名私鑰及其他智能手機的密鑰共同參與計算得到的，即使攻擊者是截取到其他智能手機的密鑰或者時間片段t內的臨時簽名私鑰中的任意一個，都不能偽造用戶在時間片段t'內的簽名私鑰。通過多重保護，該方案具有強密鑰隔離安全性。

（3） 安全密鑰更新：如果簽名者在將臨時私鑰從UKID，t更新到UKID，t'時，攻擊者截獲了時間片段t內的臨時私鑰UKID，t及密鑰更新信息MID，那么除時間片段t及t'之外的時間片段系統還是安全的，從而系統密鑰更新足夠安全。

正確性：e（U，P）=e（kP'+V·UKID，t ，P）

=e（kP'，P）e（V·UKID，t ，P）

=e（P，P'）k e（UKID，t ，P）V

=r·e（sUpub ，P）V

=r·e（Upub ，Ppub ）V

則可驗證：r=e（U，P）e（Upub ，-Ppub ）V

=r·e（Upub ，Ppub ）V·e（Upub ，-Ppub ）V=r

4.2 效率分析

在效率分析當中，我們從強密鑰隔離、安全密鑰更新、時間片段數目及是否滿足前向后向安全的性能上將本方案與其他簽名方案進行具體對比分析，結果如表1所示。

我們還從簽名、驗證、可證明安全及簽名長度這四方面將本方案與其他簽名方案進行具體對比分析，結果如表2所示。

5 結束語

數字簽名作為信息安全的一項重要技術，已經在許多領域得到運用。而隨著越來越多的密碼算法被應用到不安全的環境密鑰泄露在所難免。本文提出了一個基于身份的密鑰隔離簽名方案，該方案通過多個智能手機的協助，簽名者的簽名私鑰做到隨時間變化，保證了簽名的前向和向后安全性，使得攻擊者偽造簽名者簽名的機會大大減少，從而降低了應用于安全較低的設備中基于身份密碼系統密鑰泄露風險，提高了系統對密鑰泄露所造成危害的容忍度。同時該方案采用高效的簽名算法，能夠滿足于簽名者在智能手機端的頻繁更新私鑰后進行簽名的要求，一定程度上解決了密鑰泄露與密鑰管理的問題，并且方案在保證前向與后向安全的前提下，只需要很少的計算資源、存儲資源和通信資源，因此適用于智能手機等資源受限的環境中。

參考文獻

[1] Diffie W and Hellman M. New Direction in Cryptography[J]. IEEE Transactions on Information Theory.1976，IT-22（6）： 644-654.

[2] Rivest R， Shamir A and Adleman L. A method for obtaining digital signatures and public key cryptosystems[J]. Communications of ACM，1978，21（2）： 120-126.

[3] SHAMIR A. How to share a secret[J]. Communications of ACM，1979，22（11）： 612-613.

[4] Shamir A. Identity-Based Cryptosystems and Signature Schemes[J]. Lecture Notes in Computer Science，1995，21（2）：47-53.

[5] Dodis Y， Katz，Xu and Yung M. key-insulated public-key cryptosystems[C].In Advances in Cryptology-Eurocrypt 02， LNCS 2332，Springer-Verlag，2002，pp. 65-82.

[6] Yevgeniy Dodis， Jonathan Katz， Shouhuai Xu. Strong Key-Insulated Signature Schemes[J]. Lecture Notes in Computer Science，2002，2567（2567）：130-144.

[7] Hess F.Efficient Identity Based Signature Schemes Based on Pairings[J].Selected Areas in Cryptography. Springer Berlin Heidelberg，2003：310-324.

[8] 杜瑞穎， 劉亞斌， 劉建東， 等. 無證書密鑰隔離簽名方案[J]. 山東大學學報，2014，49（9）： 24-28.

[9] 秦志光， 劉京京， 趙洋， 等. 密鑰隔離密碼系統研究現狀[J].計算機學報， 2015，38（4）： 759-774.

[10] 尋甜甜，于佳，楊光洋，等.密鑰隔離的無證書聚合簽名[J]. 電子學報，2016，44（5）： 1111-1116.

[11] 元振楊，陳建華，吳黎兵.具有后向安全的認證密鑰協商協議[J]. 小型微型計算機系統，2016，37（7）： 1398-1401.

[12] 翁健， 陳克非，劉勝利，等. 標準模型下基于身份的強密鑰隔離簽名[J]. 軟件學報，2008，19（6）： 1555-1564.

基金項目：

1. 國家自然科學基金（61662009，61262073，61363068）；

2. 貴州省教育廳青年科技人才成長項目（黔教合KY字[2016]169）；

3. 貴州省科技基金計劃項目（黔科合基礎[2016]1023）。

作者簡介：

劉易（1991-），女，漢族，貴州貴陽人，畢業于貴州大學，碩士學位；主要研究方向和關注領域：密碼學、信息安全、大數據隱私保護。

彭長根（1963-），男，漢族，貴州錦屏人，畢業于貴州大學，博士學位，教授，博士生導師；主要研究方向和關注領域：密碼學、信息安全、大數據隱私保護。