基于身份的可審計多重截取簽名方案*

何啟芝，曹素珍，王彩芬,2，盧彥霏，方子旋，閆俊鑒

(1.西北師范大學計算機科學與工程學院，甘肅 蘭州 730070；2.深圳技術大學大數據與互聯網學院，廣東 深圳 518118)

1 引言

傳統數字簽名技術可以保證數據在傳輸過程中的完整性和不可抵賴性。然而，在一些特定的應用環境中，傳統數字簽名技術并不能完全滿足安全需求。如圖1所示，總公司文件處理部門簽署一份重要的電子文件后，為最大程度地減少對公司敏感信息的泄露，要求各子公司文件處理者根據工作需要截取一部分內容并轉發給下屬各部門，各部門能在不與總公司文件處理者交互的情況下，確認收到的文件是合法有效的。

Figure 1 Example of an application scenario 圖1 應用場景實例

為滿足上述應用環境對簽名文件的安全要求，必須對傳統簽名根據特定規則按需截取，確保截取后的簽名合法有效且不存在二義性。內容可截取簽名CES(Content Extraction Signature)[1]的提出解決了上述問題，且能保證各公司、各部門收到的文件是不可偽造的，同時保證總公司可以完全控制對原文件的截取方式。

具有可刪改性質的內容可截取簽名CES于2001年由Steinfeld等人提出，內容可截取簽名允許用戶根據需要，在不與原始簽名人交互的情況下，對已簽名數據進行截取，并且得到一個可驗證的截取簽名，實現了保護數據隱私的功能。藍才會等人[2]在2007年提出了一個基于身份的內容可截取簽名方案，該方案結合了可截取簽名體制和批簽名的思想，不需要對消息的每個子消息進行簽名，但是由于該方案使用了雙線性對技術，因此整個方案的效率比較低。曹素珍等人[3]在2013年提出了一個基于離散對數DLP(Discrete Logarithm Problem)[4]問題的內容可截取簽名方案，進一步提高了計算效率。但是，文獻[2，3]不能實現對簽名的可審計性，不支持對數據發布者和簽名者身份的追溯，不能解決惡意修訂(即不按照修訂控制規則修訂或截取)的問題。2002年Johnson等人[5]提出的可修訂簽名方案RSS(Redactable Signature Scheme)是具有同態性質的數字簽名，可實現修訂人不與簽名人交互就能刪除已簽名消息的部分數據，同時為修訂后的消息生成新的簽名，并能驗證該簽名是具有同態性質的簽名，具有很廣闊的應用前景，但是仍無法解決惡意修訂問題。2015年Pohls等人[6]提出了一個可審計的可修訂簽名ARS(Accountable Redactable Signature)方案，該方案解決了當出現數據責任糾紛時，允許一個任意的仲裁第三方針對糾紛數據的簽名是否有效來判定責任，且該簽名人無法抵賴責任。2020年，馬金花等人[7]提出了一個公開可審計的可修訂簽名方案的通用框架，該框架可以利用傳統的數字簽名方案將任意的可修訂簽名方案轉化為公開可審計的可修訂簽名方案，從而實現簽名人和修訂人的公開可審計性。與文獻[6]中的方案相比，該方案更適用于對開放環境中的數據進行修訂，并且計算開銷更小。當數據內容產生糾紛時，由于該方案只能證明數據的來源(來自簽名者或修訂者)，并不能有效阻止惡意修訂情況的發生，因此其可用性并不強。

多重簽名[8]可以實現多個人對同一個消息分別進行簽名。根據簽名有無順序，多重簽名分為有序多重簽名[9]和廣播多重簽名。Wu等人[10]提出了基于身份的多重簽名方案，隨著多重簽名的不斷發展，研究人員已經基于多重簽名的安全性、機密性和實用性提出了許多擴展應用方案[11 - 14]。此后，Gentry等人[15]提出了一個基于Weil 對的基于身份的廣播多重簽名方案，該方案基于計算DH CDH(Computational Diffie-Hellman) 困難問題[16]，并證明了在隨機預言模型下是安全的。

鑒于此，本文在文獻[2]的基礎上借鑒多重簽名的思想，提出了一個基于身份的可審計多重截取簽名方案。方案首先構造了一個M叉樹模型，通過該模型來實現廣播多重簽名，即從根節點向子節點實現分層廣播簽名。由于層級劃分明確，當出現糾紛時可從下往上進行逆向追蹤，從而實現對截取簽名的可審計性，保證簽名的合法性。其次，在隨機預言模型下，基于離散對數困難問題證明了方案可抵抗適應性選擇消息攻擊下的存在性偽造。與文獻[2，3]中的方案相比，本文構造的可截取簽名方案具有更高的簽名效率。

2 預備知識

2.1 符號說明

本文方案中使用的部分符號說明如表1所示。

Table 1 Symbol description表1 符號說明

假設一個消息m由n個更小的子消息組成，即m={m1,m2,…,mn}。截取的子消息可表示為m′={m′1,m′2,…,m′n}，CI(m′)是由m′中所包含的子消息段的編號構成的集合。消息m根據CI(m′)所指定的m′進行截取。CEAS是內容截取訪問結構，簽名者通過CEAS來構造截取子集CI(m′)，用來指定提取哪些子消息的有效簽名。

2.2 相關困難問題

設群G是階為q的乘法循環群，G的生成元為g。

2.3 內容可截取簽名

內容可截取簽名過程由如下4個核心算法構成：

(1)密鑰生成。輸入系統安全參數λ，生成一個公/私鑰對(pk,sk)；

(2)簽名。該算法由簽名者運行，輸入簽名者私鑰sk、內容截取訪問結構CEAS和簽名數據m，輸出一個數據/簽名對(m,σ)。

(3)截取簽名。該算法由截取者運行，輸入簽名者公鑰pk、截取者私鑰sk、截取子集CI(m′)和數據/簽名對(m,σ)，輸出截取后的數據m′和截取簽名(m′,σ′)。

(4)驗證簽名。輸入簽名者公鑰pk、截取后的數據m′和截取簽名(m′,σ′)，若簽名有效，輸出True；否則，簽名無效，輸出False。

假如原始消息是m={m1,m2,m3}，截取子集CI(m′)={1,3}，則對應的截取子消息是m′={m1,?,m3}，用“？”表示沒有被截取的子消息段。需要注意的是，根據m′的定義，截取子集和截取的子消息段要一一對應，其順序也要和原消息中的子消息段順序保持一致，如截取子集CI(m′)={1,3}，則截取子消息m′={m1,m2,?}是非法的，因為截取子消息沒有和截取子集CI(m′)對應起來；截取子消息{?,m1,m3}和{m1,m3,?}也都是非法的，因為沒有與原消息中的順序保持一一對應。

3 方案描述

3.1 形式化定義

可截取簽名方案主要包括簽名者、截取者和驗證者，而且截取者和驗證者可以是同一人，簽名者完成對原始消息的全局簽名，截取者首先完成對消息正確性的驗證，接著完成對消息的截取簽名。該方案由以下5個算法構成：

(1)系統建立Setup(λ)。

選取一個安全參數λ，PKG生成系統主密鑰和系統參數par，保密主密鑰，將系統參數公開。

(2)密鑰生成KeyGen(par)。

輸入安全參數k，為簽名者生成一個公/私鑰對(pk,sk)。

(3)簽名生成Sign(sk,m,CEAS)。

簽名者為根節點生成簽名(普通簽名)，輸入簽名者的私鑰sk、消息m、內容截取訪問結構CEAS，輸出一個可截取的全局簽名(m,σF)。

(4)截取簽名生成Extract(pk,(m,σ),CI(m′))。

①首先驗證上一級的簽名是否有效，若簽名有效，繼續執行下面的算法；否則，終止算法。

②輸入簽名人的公鑰pk、簽名(m,σ)和截取子集CI(m′)，該算法輸出截取后的簽名(m′,σE)。

(5)驗證Verify(pk,m′,σE)。

輸入m′,σE,pk驗證整個簽名，若通過驗證，表示截取簽名有效；否則，截取簽名無效。

3.2 安全模型

引理1若存在敵手F在概率多項式時間內贏得以下游戲的優勢是可忽略的，則稱本文所提的可審計多重可截取簽名方案在適應性選擇消息攻擊下滿足不可偽造性。

證明挑戰者C和敵手F之間的交互游戲定義如下：

(1)初始階段(Setup)。挑戰者C執行密鑰生成算法，生成公/私鑰對(pk,sk)，然后將公鑰pk發送給敵手F，保密私鑰sk。

(2)詢問(Qureies)。敵手F能夠向挑戰者C自適應地進行一系列不同的詢問，具體如下：

①密鑰提取詢問。敵手F能獲取任何身份u所對應的私鑰，挑戰者C執行密鑰生成算法，輸出身份u所對應的私鑰Su并返回給F。

③H2詢問。假設mi是m的子消息，F向C發出H2詢問，C運行Sign算法，計算H2(mi‖CEAS)發送給F。

‖H2(m3‖CEAS)‖…‖H2(mi‖CEAS))

發送給F。

⑥簽名詢問。假設mi是m的子消息，F向C發出簽名詢問，C運行Sign算法，計算σi并返回給F，F最后構造出原消息的全局簽名σF。

⑦簽名截取詢問。F收到消息m的全局簽名σF后，根據C發送的CEAS構造出CI(m′)，C運行Extract算法，計算消息m截取后的子消息m′的簽名σ′并驗證該簽名是否有效。

(3)偽造(Forgery)。經過多項式次詢問后，敵手F輸出偽造身份u*對消息m*的截取簽名σ*，并使以下3個條件成立，則說明攻擊成功：

①敵手F沒有發起過對身份u*的密鑰提取詢問；

②敵手F沒有發起過對(u*,m*)的簽名詢問；

③通過驗證算法可以驗證σ*是身份u*對于消息m*的有效簽名。

定義1如果敵手F的運行時間最多為t，密鑰提取詢問最多發起qe次，H1詢問最多發起qH1次，H2詢問最多發起qH2次，H3詢問最多發起qH3次，H4詢問最多發起qH4次，簽名詢問最多發起qs次，簽名截取詢問最多發起qSE次，以不小于ε的概率贏得上述游戲，則稱敵手F是基于身份的可截取簽名方案的(t,ε,qe,qH1,qH2,qH3,qH4,qs,qSE)-偽造者。如果在該方案中不存在(t,ε,qe,qH1,qH2,qH3,qH4,qs,qSE)-偽造者，則稱方案是(t,ε,qe,qH1,qH2,qH3,qH4,qs,qSE)-安全的。

3.3 方案構造

本文方案需要構建一棵M叉樹，具體構建方法如圖2所示。

Figure 2 M-tree model圖2 M叉樹模型

從圖2可以看出，M叉樹在根節點處進行原始簽名，分支節點(虛線框中的節點)在圖中只表示出了1層，但是在具體方案中可能有很多層。第2層虛線框的內部線條是虛線，表示分支節點可以有很多層。

根據圖2所示的模型構建M叉樹的方法，遵從樹形結構中從根節點到葉子節點的順序，整個過程是一個分級廣播多重簽名的過程。首先在根節點處，將該簽名分成若干子消息后進行根簽名；在第2層，首先進行判斷，根據內容截取訪問結構CEAS判斷每個子消息是否需要進行截取簽名，若需要進行截取簽名，則繼續同樣的步驟。在每一層，分別進行廣播多重簽名，即不分簽名的先后順序分別進行截取簽名，這樣便得到了一棵M叉樹，同時還實現了分級廣播多重簽名。構建M叉樹的算法如算法1所示：

算法1構建M叉樹

輸入：消息m，CEAS。

輸出：一棵M叉樹。

步驟1Getm={m1,m2,…,mn}fromthesigner；

步驟2ComputeσF={m,CEAS}；

rootNode←σF；

步驟3 fori=1 tondo

Computeσmi=(mi,CEAS)；

endfor

步驟4 ifmi+1∈CI(m′)then

childNodemi←σmi+1；

else

siblingmi←σmi+1；

endif

方案具體構造如下：

(1)Setup(λ)。

(2)KeyGen(par)。

假設ID表示簽名者的唯一可識別的身份，PKG對簽名者進行鑒定，確信ID具有唯一性。

②PKG計算QID=H1(ID)作為簽名者的公鑰，任何人都可通過系統的公開參數計算得到簽名者的公鑰。

③PKG計算SID=sQID，將它作為簽名者的私鑰并安全地發送給簽名者。

(3)Sign(sk,m,CEAS)。

假設被簽名的消息為m，根據需要m被劃分為x個部分，mk表示m中的子消息段，k為子消息段在消息m中的編號，k∈{1,2,…,n}，m′表示截取后的子消息。

假如m={m1,m2,m3}，則

H2(m3‖CEAS))

(4)Extract(pk,(m,σ),CI(m′))。

①根據CEAS構造CI(m′)；

②用m′={m′1,m′2,…,m′n}代替m={m1,m2,…,mn}:

(5)Verify(pk,m′,σE)。

①判斷者首先驗證CI(m′)∈CEAS是否成立，若成立，則繼續；否則，終止算法；

4 方案分析

4.1 正確性分析

在截取簽名算法中，替換各子消息段的方法如式(1)所示：

(1)

(2)

從式(1)和式(2)可以得知，驗證時每個子消息段和簽名中的子消息段是一致的，均為H2(mi‖CEAS)。

本文方案具有可審計性，可以追蹤到惡意修訂的敵手。由于分支節點需要先驗證簽名，再截取簽名，因此審計和追蹤是在父節點與子節點之間完成的。構造的一個攻擊場景模型圖如圖3所示，F為敵手，其子節點A既是節點F的簽名驗證者同時也是截取簽名者，若A未能通過截取簽名驗證，則A還可作為一名審計者進行逆向追溯(如圖3中虛線框所示)，且將追溯結果反饋至敵手的父節點，從而追蹤到敵手F，以便制止敵手F的惡意修訂行為。

Figure 3 Model of attack scenario圖3 攻擊場景模型圖

由以上分析得知，本文方案是正確的。

4.2 安全性證明

挑戰者C還有一個身份，就是DLP問題的攻擊者。假定已知(g,b=ga)，要求挑戰者C計算出a的值。

定理1在隨機預言模型下，若存在一個敵手F能夠以不可忽略的優勢在概率多項式時間內贏得引理1中的游戲，則挑戰者C就能夠以一定的優勢解出離散對數困難問題。

證明挑戰者C運行系統建立算法，設b=ga，然后生成系統公開參數par={G1,G2,g,b,q,H1,H2,H3,H4}，并將系統公開參數發送給敵手F，挑戰者C與敵手F執行以下模擬算法。

敵手F選擇一個身份ID，能夠模仿一般用戶進行自適應地詢問，密鑰提取詢問最多發起qe次，H1詢問最多發起qH1次，H2詢問最多發起qH2次，H3詢問最多發起qH3次，H4詢問最多發起qH4次，簽名詢問最多發起qs次，簽名截取詢問最多發起qSE次，詢問如下：

(1)密鑰提取詢問：挑戰者C維護初始值為空的表Lk，表中記錄(ID,QID,SID,R)，敵手F詢問身份IDu的密鑰，挑戰者C執行以下操作：

①若表Lk中存在ID對應的四元組，則將所對應的值返回給敵手F；

(2)H1詢問：挑戰者C維護初始值為空的二元組列表L1，表中記錄(ID,QID)，敵手F詢問，挑戰者C執行以下操作：

①若表L1中存在ID對應的二元組，則將所對應的值返回給敵手F；

②若表L1中不存在ID對應的二元組，則計算QID=H1(ID)，將其加入列表L1中并返回給敵手F；

(3)H2詢問：挑戰者C維護初始值為空的二元組列表L2，表中記錄(mi,CEAS)，敵手F詢問，挑戰者C執行以下操作：

①若表L2中存在IDi對應的二元組，則將所對應的值返回給敵手F；

②若表L2中不存在IDi對應的二元組，則計算H2(mi‖CEAS)，將其加入列表L2中并返回給敵手F；

①若表L3中存在IDi對應的三元組，則將所對應的值返回給敵手F；

H2(m3‖CEAS)‖…‖H2(mi‖CEAS))，將其加入列表L3中并返回給敵手F；

①若表L4中存在IDi對應的三元組，則將所對應的值返回給敵手F；

(6)簽名詢問：挑戰者C維護初始值為空的四元組列表Ls，表中記錄(ID,m,CEAS,σ)，敵手F詢問，挑戰者C執行以下操作：

①若表Ls中存在ID對應的四元組，則將所對應的值返回給敵手F；

(7)簽名截取詢問：挑戰者C維護初始值為空的四元組列表Lr，表中記錄(ID,m′,CEAS,σ′)，敵手F詢問，挑戰者C執行以下操作：

①若表Lr中存在ID對應的四元組，則將所對應的值返回給敵手F；

由上述分析可得，本文基于身份的可審計多重截取簽名方案在適應性選擇消息攻擊下具有不可偽造性。

4.3 性能分析

本節將文獻[2,3]方案與本文方案的計算效率進行比較。常用的密碼操作有par、exp和has，其中，par表示雙線性對運算，exp表示指數運算，has表示哈希運算。文獻[2，3]中的方案與本文方案所采用的運算次數如表2所示。

Table 2 Number of different operations used in the scheme 表2 方案采用的不同運算次數

如表2所示，文獻[2]方案在簽名和驗證階段都采用了雙線性對運算，文獻[3]方案采用的指數運算也要多于本文方案的，實驗運行環境是Intel(R) Core(TM) i5-7200U CPU@2.50 GHz處理器、12 GB內存、Windows 10操作系統，基于JPBC(Java Pairing-Based Cryptography)庫用Java語言實現。通過實驗可以得到不同方案的運算時間，如表3所示。

Table 3 Computing time of different schemes表3 不同方案的運算時間 ms

為了更直觀地展現本文方案在計算效率方面的優勢，文獻[2,3]方案和本文方案的實驗結果如圖4和圖5所示。

Figure 4 Computational overhead of signature and extraction phases圖4 簽名及截取階段的計算開銷

Figure 5 Computational overhead of signature verification phase圖5 驗證簽名階段的計算開銷

圖4是在簽名及截取階段對不同方案進行比較，隨著截取子消息的不斷增加，3個方案的運算時間也在不斷增加，由于文獻[2]方案在該階段采用了雙線性對運算，因此該方案的計算開銷最大，文獻[3]方案在該階段未采用雙線性對技術，但是由于指數運算較多，計算開銷也高于本文方案的，可以看出本文方案的計算開銷優于文獻[2，3]方案的。在驗證簽名階段，由于文獻[2]方案在該階段采用了雙線性對運算，導致該方案的計算開銷明顯高于文獻[3]方案和本文方案的，雖然本文方案和文獻[3]方案的計算開銷差別不是很大，但是隨著驗證簽名中截取子消息的增加，本文方案的計算開銷始終低于文獻[3]方案的計算開銷。

由以上分析可以得出，在簽名及截取階段和驗證簽名階段，本文方案的計算開銷都要比文獻[2,3]方案的計算開銷小。

5 結束語

本文提出的可審計多重截取簽名方案，利用M叉樹模型實現了多重截取簽名，通過對M叉樹中節點的逆向追溯，可實現對惡意修訂者的審計追蹤。實驗結果表明，本文方案沒有采用對運算，僅采用了少量指數運算和哈希運算，與同類簽名方案相比，計算成本降低了很多，更適用于電子商務、電子政務及網絡電子投票等應用場景。下一步考慮如何實現不同需求下的消息截取，然后將特定的截取消息發送給相應的驗證者，實現簽名的多樣性。