可修訂數字簽名研究綜述

馬金花 劉江華 伍 瑋 黃欣沂

1(福建師范大學數學與信息學院 福州 350007) 2(福建省網絡安全與密碼技術重點實驗室(福建師范大學) 福州 350007) 3(澳大利亞迪肯大學信息技術學院 澳大利亞墨爾本 3125) (jinhuama55@hotmail．com)

2017-09-01；

2017-09-05

國家自然科學基金項目(61402110,61472083,61771140)；福建師范大學校創新團隊基金項目(IRTL1207)；福建省杰出青年科學基金項目(2016J06013) This work was supported by the National Natural Science Foundation of China (61402110, 61472083, 61771140), the Innovation Team of Fujian Normal University (IRTL1207), and the Distinguished Young Scholars Fund of Fujian Province (2016J06013).

伍瑋(weiwu@fjnu.edu.cn)

可修訂數字簽名研究綜述

馬金花1,2劉江華3伍 瑋1,2黃欣沂1,2

1(福建師范大學數學與信息學院 福州 350007)2(福建省網絡安全與密碼技術重點實驗室(福建師范大學) 福州 350007)3(澳大利亞迪肯大學信息技術學院 澳大利亞墨爾本 3125) (jinhuama55@hotmail．com)

數據的安全問題已成為關系國家經濟、政治、國防、文化安全的重大問題.數字簽名可驗證數據內容的完整性和數據源的真實性，是保障數據安全的核心技術之一.數字簽名的傳統安全要求為在自適應選擇消息攻擊下滿足存在不可偽造性.雖然數字簽名的傳統安全目標能滿足數據認證的基本要求，但也阻礙了對已簽名數據的合理操作，不能滿足很多實際應用的需求.可修訂簽名是一類支持編輯操作的具有同態性質的數字簽名.在不與簽名人交互的情況下，簽名持有人(修訂者)可刪除已簽名數據中的敏感子數據，并計算修訂后數據的有效簽名.自2001年可修訂數字簽名被正式提出以來，就一直是應用密碼學領域的研究熱點.近年來許多國內外的學者從形式化安全定義、修訂規則、計算效率、通信效率等多個方面對其進行探索研究，相繼取得了一批有意義的研究成果.網絡技術及其應用的快速發展在不斷地對可修訂數字簽名提出新的要求，將從其核心算法定義、安全模型以及現有的代表性方案等方面對可修訂數字簽名進行概括和分析，并探討值得進一步研究的問題.

可修訂簽名；同態簽名；數字簽名；數據認證；安全模型

隨著社會的日益數字化，人類社會已經進入數據時代，數據的價值得到越來越廣泛的認同，數據的安全問題已成為關系國家經濟、政治、國防、文化安全的重大問題[1].Diffie和Hellman[2]于1976年首次提出公鑰密碼學(public key cryptography, PKC)的概念，開創了密碼學和網絡信息安全發展的新紀元[3].數字簽名(digital signatures)可驗證數據內容的完整性和數據源的真實性，是一種重要的公鑰密碼技術，也是保障數據安全的核心工具之一[4].

數字簽名的傳統安全要求為在自適應選擇消息攻擊下滿足存在不可偽造性(existential unforgeability under adaptive chosen message attacks, EUF-CMA)[5].EUF-CMA要求：已知公鑰pk，概率多項式時間(probability polynomial-time, PPT)攻擊者在獲得它希望得到的有效數據簽名后，能夠為新數據M*計算出有效簽名的概率是可忽略的.如果數字簽名方案滿足上述安全要求，那么有效的數字簽名能讓數據接收者相信其收到的數據沒有被篡改，且數據的發送方就是相應公鑰pk的擁有者.

雖然數字簽名的傳統安全目標能滿足數據認證的基本要求，但也阻礙了對已簽名數據的合理操作，不能滿足很多實際應用的需求.在電子商務、政府文件發布、智能電網、電子醫療記錄等應用中，因為隱私保護或帶寬節省等原因，簽名持有人需要對已簽名數據進行合理的修訂.以電子醫療記錄為例，電子醫療記錄(electronic medical record)是一種新型的健康數據管理模式，其核心內容是用戶的健康數據[6]，包含大量個人信息，如M= {姓名,性別,身份證號碼,住址,聯系電話,病情描述1,病情描述2,……,病情描述n,處方}，與個人的隱私密切相關.多國的法律法規明確規定電子醫療記錄的使用要注意病人的隱私保護[7].以科學研究為目的的數據使用并不需要知道患者的真實姓名、身份證號碼等信息，使用時應將這些敏感個人隱私數據從患者健康數據中刪除.這稱為數字文檔凈化(digital documents sanitizing)[8].

使用具有EUF-CMA性質的數字簽名雖可保障原始數據的完整性，但無法得到凈化后數據的簽名.為了獲得凈化后數據的有效數字簽名，數據持有人可將凈化后的數據發給簽名人，簽名人在核對后對凈化后的數據重新簽名.該過程需要數據持有人和簽名人進行多次交互，不僅計算代價大，而且在簽名人離線的情況下，很難實現實時交互.簽名人還可以預先對所有子數據的組合分別進行簽名，該過程雖然避免了簽名持有人和簽名人之間的多次交互，但計算開銷大且無法控制數據持有人對數據的惡意修訂等行為.

同態數字簽名為上述問題提供了有效的解決方案.圖靈獎獲得者Rivest教授在2001年的學術演講中提出了同態數字簽名(homomorphic signatures)的雛形[9].同態數字簽名不滿足傳統的安全目標EUF-CMA，在不知道簽名人私鑰的情況下，允許簽名持有人對已簽名數據進行合理的授權操作，計算出新數據的有效簽名.例如?,⊕是2個二元運算，簽名人的私鑰是sk，y和y′分別是數據x和x′的簽名.在不知道私鑰sk的情況下，第三方可以直接計算出新數據x*的同態簽名y*，即y*=Sig(sk,x*)，其中y*=y?y′,x*=x⊕x′.在同態數據簽名中，對已認證數據的合理操作不需要私鑰等私密信息，支持外包計算，計算資源/通信資源有限的實體可將這些操作委托給第三方，符合云計算和物聯網的特點，可以有效地解決上述的認證數字文檔凈化問題[8]，在電子投票、智能電網、電子醫療記錄系統等很多實際場合有著廣泛的應用[10-11].

可修訂簽名(redactable signatures)是一類支持編輯操作的具有同態性質的數字簽名，其概念是由Johnson等人[12]于2002年正式提出，但Steinfeld等人[13]于2001年就已經提出了與可修訂數字簽名具有類似功能的數字簽名，稱為內容可截取簽名(content extraction signature, CES).在不與簽名人交互的情況下，簽名持有人(修訂者)可刪除已簽名數據中的敏感子數據，并計算修訂后數據的有效簽名.以集合型數據為例，設σ為集合型數據M={m1,m2,m3,m4,m5}的有效簽名，修訂者可以移除集合M的某個子集(如{m3,m4,m5})，并為余下的數據(即M′={m1,m2})計算有效簽名σ′.該修訂操作不需要簽名人的幫助，修訂者可獨立完成.可修訂簽名要求得到的修訂簽名σ′不泄露被移除元素(即{m3,m4,m5})的任何信息.文獻[13]設定了修訂控制規則以限制簽名持有人的修訂行為，任何不符合修訂規則的操作很難計算出有效簽名，避免了因不合理或惡意的修訂操作所導致的信息歧義、改變原意等情況的發生.除了集合型數據，可修訂數字簽名也支持字符串、樹型以及圖型等數據的修訂操作.

自2001年被正式提出以來，同態數字簽名引起了學術界的極大關注，一直是密碼學與信息安全領域的研究熱點.可修訂數字簽名作為一類支持編輯操作的具有同態性質的數字簽名，近年來被許多國內外的學者從形式化安全定義、提取規則、計算效率、通信效率、簽名更新等多個方面對其進行探索研究，相繼取得了一批有意義的研究成果[12-48].但是網絡技術及其應用的快速發展在不斷地對可修訂數字簽名提出新的要求，本文將從其核心算法定義、安全模型以及現有的代表性方案等方面對可修訂數字簽名進行概括和分析，并探討值得進一步研究的問題.

1 可修訂數字簽名

現有的可修訂數字簽名方案(redactable signa-ture schemes, RSSs)大都針對某一特定的數據結構設計，比如集合型數據[12-18]、鏈表型數據[19-25]、樹型數據[26-36]、圖型數據[37-43]等，相關的定義和安全模型也不相同.在現實生活中數據的存在形式多種多樣，每一種數據的存儲方式以及數據塊之間的組合形式不盡相同，Derler等人[15]于2015年提出首個適用于多樣化數據結構的可修訂數字簽名的一般架構模型，并給出了相應的安全性定義.為了便于理解，本節將基于文獻[15]以集合型數據為例定義可修訂簽名.

1.1可修訂簽名定義

可修訂簽名由4個核心的有效算法構成：

1) 密鑰生成算法KeyGen.輸入系統安全參數λ，該概率性算法輸出簽名人的公私鑰對(pk,sk).

2) 簽名生成算法Sign.輸入簽名人私鑰sk、數據M和修訂控制規則ADM，該算法輸出數據簽名對(M,σ).

3) 簽名修訂算法Redact.輸入簽名人公鑰pk、數據簽名對(M,σ)和修訂指令MOD，該算法輸出修訂后的數據簽名對(M′,σ′).

4) 簽名驗證算法Verify.輸入簽名人公鑰pk和數據簽名對(M,σ)，該確定性算法輸出一個比特值b∈{0,1}.當檢驗簽名有效時，b=1；否則，b=0.

1.2可修訂簽名安全模型

不可偽造性(unforgeability)和隱私性(privacy)是可修訂簽名的2個基本安全要求，相應的形式化安全模型最早由Brzuska等人[28]提出.本節將基于文獻[28]的安全模型，描述這2個安全要求.

1.2.1 不可偽造性

可修訂簽名的不可偽造性可用下面的挑戰者C和攻擊者A之間的游戲Game 1來刻畫：

1) 挑戰者C運行密鑰生成算法(pk,sk)←KeyGen(1λ)，將公鑰pk公開.

2) PPT攻擊者A可自適應地選擇q個數據(Mi,ADMi)詢問簽名預言機，并得到有效數據簽名對(Mi,σi)，其中1≤i≤q.

3) 攻擊者A輸出數據簽名對(M*,σ*).

定義1. 不可偽造性.在適應性選擇消息攻擊下，如果任何PPT攻擊者在游戲Game 1中獲勝的概率是可忽略的，我們就稱該可修訂簽名算法在適應性選擇消息攻擊下滿足存在不可偽造性.

1.2.2 隱私性

在已知簽名人公鑰pk的情況下，PPT攻擊者可以自適應地詢問簽名預言機，可修訂簽名的隱私性要求攻擊者很難推導出被移除數據的信息.

可修訂簽名的隱私性可用下面的挑戰者C和攻擊者A之間的游戲Game 2來刻畫：

1) 挑戰者C運行密鑰生成算法(pk,sk)←KeyGen(1λ)，將公鑰pk公開.

2) PPT攻擊者A可自適應地詢問簽名預言機.最后攻擊者A選擇2個數據{(M0,ADM0,MOD0),(M1,ADM1,MOD1)}發送給挑戰者C，數據滿足M0≠M1,M0MOD0=M1MOD1.

4) 攻擊者A依然可自適應地詢問簽名預言機.最后攻擊者A輸出b*.如果b=b*則說明攻擊者A在游戲Game 2中獲勝；否則，攻擊者A失敗.

設Pr[A]為攻擊者A在Game 2中獲勝的概率，則A的優勢Adv[A]=|Pr[A]-12|.

定義2. 隱私性.若PPT攻擊者在游戲Game 2中的優勢Adv[A]是可忽略的，我們就稱該可修訂簽名算法滿足隱私性要求.

1.2.3 其他安全要求

除了上述2個最基本的安全要求，面向特定應用的可修訂簽名還需要滿足其他安全要求，包括透明性(transparency)[14-15]、不可鏈接性(unlinkability)[44-45]、可審計性(accountability)[22,46]和可合并性(mergeability)[19,24]等.以集合型數據M={m1,m2,m3,m4,m5}為例，原有效數據簽名對為(M,σ).設(M1,σ1)和(M2,σ2)是(M,σ)的2個有效修訂簽名，分別由修訂者R1和修訂者R2執行修訂操作得到，其中M1={m1,m2,m3}，M2={m3,m4,m5}.PPT攻擊者A可自適應地詢問簽名預言機.

可修訂簽名算法的透明性要求：已知(M1,σ1)，攻擊者很難判斷(M1,σ1)是原始簽名還是修訂后的簽名.

可修訂簽名算法的不可鏈接性要求：已知(M1,σ1)和(M2,σ2)，攻擊者無法確定它們是否是從同一個原始簽名(M,σ)修訂得到的.

可修訂簽名算法的可審計性要求：已知(M1,σ1)，審計者可以斷定(M1,σ1)是由修訂者R1執行修訂操作得到的.

可修訂簽名算法的可合并性要求：已知(M1,σ1)和(M2,σ2)，修訂者可以計算出(M,σ).

因為只有特定應用環境下的可修訂簽名才應具有這些安全性要求，所以本節省略這些安全性能的形式化定義.

2 可修訂數字簽名代表性方案

現有的可修訂數字簽名方案主要是基于不同的密碼學工具設計的，如基于向量承諾(CommitVector)的RSS[12,15,17,27]、基于Merkle Hash樹的RSS[13,21,23,26-27,29,33-34,40]、基于雙線性映射(bilinear mapping)的RSS[18,24-25,31-32]以及基于聚合器(accumulator)的RSS[14-15,19,47-48].本節將分別選取一個代表性的方案介紹上述4類RSS的設計思路.

2.1基于向量承諾(CommitVector)的CES方案[13]

Steinfeld等人[13]于2001年提出內容可截取簽名(CES)的概念，是早期可修訂數字簽名的代表性方案之一.該方案針對有序集合數據，利用內容截取訪問結構(content extraction access structure, CEAS)實現對簽名持有人截取權限的限制.CEAS定義了原數據集合中可被截取的數據子集，與1.1節定義的ADM功能相同.以有序數據集合M={m[1],m[2]}為例，若每個子數據都可被截取，則M中允許截取的數據子集數目共有4=22個，分別為{?},{m[1]},{m[2]},{m[1],m[2]}，CEAS(或ADM)即為這4個子集的集合，最多共有16=24種集合情況.如果原數據共有n個子數據，那么CEAS最多共有22n種形式.CEAS和ADM都可以有效地防止簽名持有人不合理或惡意使用簽名等情況的發生.

基于向量承諾的CES方案[13]由4個算法構成：

1) 密鑰生成算法KeyGen(λ).輸入系統安全參數λ，調用標準數字簽名的密鑰生成算法，輸出公私鑰對(sks,pks)；調用消息承諾方案的參數初始化算法，輸出方案的參數字符串sp.最后輸出CES方案的公鑰pk←(pks,sp)和私鑰sk←sks.

2) 簽名生成算法Sig(sk,M,CEAS).為每一個子數據均勻隨機地分配一個隨機數r[i]，計算每個子數據的承諾值c[i]←C(M[i];r[i])，計算所有承諾值串聯的簽名σc←Sig(sks,CEAS,〈c[i]〉i∈[n]).最后輸出CES方案的簽名σF←(CEAS,σc,〈r[i]〉i∈[n]).

3) 截取簽名算法Ext(pk,M,σF,X).X為將被移除的子數據的序號集合，同1.1節定義的MOD功能相同.首先為序號為i∈X的子數據計算承諾值c[i]←C(M[i];r[i]).最后，輸出CES方案的截取簽名σE←(CEAS,σc,〈r[i]〉i∈[n]-X,〈c[i]〉i∈X).

4) 簽名驗證算法Verify(pk,M′,σE).CI(M′)表示數據M′中包含的所有子數據序號的集合.為序號為i∈CI(M′)的子數據計算承諾值c[i]←C(M′[i];r[i])，運行標準數字簽名的驗證算法d←Ver(pks,CEAS,〈c[i]〉i∈[n],σc)，d∈{1,0}.d=1表明CES方案的截取簽名σE是有效的，否則是無效的.

基于向量承諾的CES方案[13]具有不可偽造性和隱私性.其不可偽造性由標準數字簽名的EUF-CMA和消息承諾方案的綁定性(binding)共同保證，隱私性由消息承諾方案的隱藏性(hiding)保證.文獻[13]形式化證明了這2個安全性.該方案原始簽名生成需要執行一次簽名運算和n次承諾運算.與簡單的多次簽名方案相比，基于向量承諾的CES方案[13]的計算代價小.但是因為原始簽名和截取簽名中包含所有被保留子數據的承諾隨機數和被刪除子數據的承諾值，使得簽名的長度較長，通信開銷較大.

2.2基于MerkleHash樹的RSS[12]

Johnson等人[12]于2002年正式定義了具有同態性質的數字簽名，并結合Merkle Hash樹和偽隨機數生成器設計了具體的可修訂簽名方案.基于Merkle Hash樹的RSS[12]主要由7個算法構成：

2) 節點秘密值生成算法：首先選擇k比特長的隨機數kε作為二叉樹T根節點ε的秘密值．如圖1所示：二叉樹T中父節點秘密值kε作為雙倍長偽隨機數生成器G的輸入，得到左右孩子節點的秘密值〈k0,k1〉←G(kε)，繼續計算得到〈k00,k01〉←G(k0)和〈k10,k11〉←G(k1).

Fig. 1 The generation of nodes’ key value圖1 節點秘密值生成

3) 節點Hash值生成算法.葉子節點Hash值vl=H(0,kl,m[l])，父節點Hash值vη=H(1,vη 0,vη 1)，最后計算根節點Hash值vε=H(1,v0,v1).如圖2所示:

Fig. 2 The generation of redaction signature of RSS based on Merkle Hash Tree圖2 基于Merkle Hash樹的RSS修訂簽名生成過程

4) 密鑰生成算法.調用標準數字簽名的密鑰生成算法，輸入系統安全參數λ，輸出簽名人的公私鑰對(sk,pk).

5) 簽名生成算法.調用標準數字簽名的簽名算法，計算簽名σε←Sig(sk,vε).輸出簽名結果σ←M,kε,σε.

6) 修訂簽名生成算法.以數據M={m[1],m[2],m[3],m[4]}為例，如圖2.修訂者收到簽名σ←M,kε,σε.設定MOD={m[3]}，即刪除子數據m[3].利用根節點上的秘密值kε，調用節點秘密值生成算法計算出每個葉子節點上的秘密值.調用節點Hash值生成算法計算出每個節點上的Hash值.公開葉子節點m[3]上的Hash值v10，以及從葉子節點m[3]到根節點路徑上所有節點的兄弟節點上的秘密值k11,k0.輸出修訂簽名結果σ′←M′,k0,k11,v10,σε，其中M′={m[1],m[2],m[4]}.

7) 驗證簽名算法.驗證者收到簽名σ′←M′,k0,k11,v10,σε.利用秘密值k11,k0，調用節點秘密值生成算法計算出每個葉子節點上的秘密值.然后調用節點Hash值生成算法計算出每個節點上的Hash值，得到根節點上的Hash值.調用標準數字簽名的驗證算法驗證d←Ver(pk,,).d=1表明簽名是有效的，否則是無效的.

基于Merkle Hash樹的RSS[12]具有不可偽造性和隱私性.其不可偽造性由標準數字簽名的EUF-CMA和偽隨機數生成器的安全性保證，隱私性由Hash函數的強抗碰撞性保證.文獻[12]形式化證明了所提出的基于Merkle Hash樹的RSS滿足不可偽造性要求.該方案的計算代價小且簽名長度短，通信開銷小.

2.3基于雙線性映射的RSS[18]

基于雙線性映射的RSS[18]由4個算法構成：

1) 密鑰生成算法.均勻隨機地選擇隨機數x←Rp，計算該算法輸出簽名人的公鑰v，私鑰x.

3) 修訂簽名生成算法.修訂者可為修訂控制條件為DASA的子數據重新分配修訂控制條件，具體如下：如果修訂者認為某個子數據必須被保留，則將Ci=DASA變為Ci=DASP，同時刪除σi；如果修訂者想凈化某個子數據，則直接刪除mi,σi,Ci，再計算σ′←σσi.最后輸出修訂簽名結果←(DID,〈mi,σi,Ci〉i∈[n′],σ′)，其中n′為修訂后剩余子數據的數目.

基于雙線性映射的RSS[18]具有不可偽造性、隱私性和透明性.其不可偽造性由計算co-Diffie-Hellmann的困難性保證，隱私性由聚合簽名的安全性和Hash函數的強抗碰撞性保證.因為該方案原始簽名和凈化簽名組成結構相同，且凈化簽名不包含被移除子數據的任何信息，第三方無法判斷收到的簽名是原始簽名還是凈化簽名，因此該方案具有透明性.文獻[18]形式化證明了這3個安全性.該方案的簽名長度短，但雙線性對運算使其計算開銷較大.

2.4基于聚合器的RSS[15]

聚合器(accumulator)可為集合型數據生成累加值，并為每個集合成員生成成員證據[47-48].基于聚合器的RSS[15]由4個算法構成：

1) 密鑰生成算法：調用傳統數字簽名算法，輸入系統安全參數λ，得到傳統數字簽名算法的公私鑰對(skDSS,pkDSS)；調用聚合器的密鑰生成算法，輸入系統安全參數λ，得到聚合器算法的公私鑰對(skacc,pkacc).最后輸出RSS簽名人私鑰sk←(skDSS,skacc,pkacc)和公鑰pk←(pkDSS,pkacc).

2) 簽名生成算法.計算集合型數據M的累加值(accM,aux)←AEval((skacc,pkacc),M)，其中accM為數據M的累加值，aux為輔助信息.計算每個子數據mi∈[n]的成員證據witmi←AWitCreate(skacc,pkacc,accM,aux,mi).調用傳統數字簽名的簽名算法計算數據M累加值的簽名σDSS←Sig(skDSS,accM).輸出簽名結果σ←{σDSS,accM,witmi∈[n],ADM}.

3) 修訂簽名生成算法.輸入修訂指令MOD，修訂后的數據為M′←MMOD，設置WIT′←WIT{witmi}mi∈MOD，即刪除被移除子數據的成員證據.輸出修訂簽名結果σ′←{σDSS,accM,WIT′,ADM}.

基于聚合器的RSS[15]具有不可偽造性、隱私性和透明性.其不可偽造性由聚合器的抗碰撞性和標準數字簽名的EUF-CMA保證.因為修訂后的簽名不包含被移除子數據的信息，攻擊者很難從修訂后的簽名得到與被刪除子數據有關的任何信息，因此該方案具有隱私性.因為原始簽名和修訂后簽名的組成結構相同，攻擊者很難判斷收到的簽名是原始簽名還是修訂后簽名，所以該方案具有透明性.該方案簽名生成的計算代價小，但是由于簽名結果中包含每個子數據的成員證據，導致簽名長度較長.

3 值得進一步研究的問題

3.1細粒度可控的可修訂數字簽名

雖然近年來許多國內外的學者從多個方面對可修訂數字簽名進行了研究，但目前未見支持細粒度修訂規則的可修訂數字簽名的有效設計.在醫療數據提取、數據公開發布等很多應用中，簽名持有人并不完全可信.如果不對提取規則進行限制，任由簽名持有人移除元素并提取出相應的有效簽名，會導致隱私泄露甚至出現與原意不符的數據和簽名.目前僅有少數方案支持對簽名持有人提取操作的限制，規定了允許被刪除或被保留的元素.但這類方案只支持粗粒度的提取規則，不滿足實際應用中對門限(threshold)規則、單調(monotone)規則、非單調(non-monotone)規則等豐富修訂規則的要求.結合已有的可修訂數字簽名方案的設計，定義支持細粒度可控的可修訂數字簽名的安全模型，并提出具體的方案設計，以滿足醫療數據提取、數據公開發布等實際應用對可修訂數字簽名的要求，這是一個值得深入研究的問題.

3.2抗量子攻擊的可修訂數字簽名

隨著量子計算機、量子通信和量子密碼技術的飛速發展，人類社會正在加速步入量子時代.量子技術無疑將會對人類未來生活產生巨大影響，甚至會引起顛覆性的社會變革[49].電子計算機超強的并行運算能力使得許多原本在傳統計算機環境下計算困難的數學問題，在量子計算機環境下卻很容易被解決.經典的數字簽名都是以求解數學問題的復雜性和困難性為基礎的，例如Elgamal簽名算法的安全性是基于求解離散對數的困難性，RSA簽名算法的安全性是基于求解大整數分解的困難性.目前還沒有文獻提出抗量子計算的可修訂數字簽名方案.已被國際密碼學界公認的抗量子計算公鑰密碼體制有基于Hash函數的Merkle樹簽名、基于糾錯碼的公鑰密碼體制、基于格問題的公鑰密碼體制以及多變量公鑰密碼體制[50-52].為了迎接量子計算機的挑戰，結合已有的可修訂數字簽名技術和抗量子聚合器、抗量子簽名方案[53-54]，設計出適用于量子時代的抗量子計算的可修訂數字簽名具有重大的現實意義.

3.3安全高效的可修訂數字簽名

現有的可修訂數字簽名方案大都不夠高效，不是計算代價較大就是存儲/通信開銷較大.在醫療數據存儲/提取、數據公開發布等很多應用中涉及到移動終端.移動終端存儲能力和計算能力受限的特點使得現有的可修訂數字簽名技術在實際應用中受到限制.在保證方案安全性的前提下，設計計算代價小且存儲/通信開銷小的可修訂數字簽名是其成功應用的關鍵.如何結合現代密碼學技術和已有的可修訂數字簽名技術設計出更加安全高效的可修訂數字簽名仍需做進一步的研究.

4 總 結

本文綜述了可修訂數字簽名的研究現狀，描述了其核心算法定義和安全模型，并介紹了現有的具有代表性的可修訂數字簽名方案，最后探討了該研究領域中值得進一步研究的問題.

[1] Brown B, Chui M, Manyika J. Are you ready for the era of “big data”[J]. McKinsey Quarterly, 2011, 4(1): 24-35

[2] Diffie W, Hellman M. New directions in cryptography[J]. IEEE Trans on Information Theory, 1976, 22(6): 644-654

[3] Zhang Futai, Sun Yinxia, Zhang Lei, et al. Research on certificateless public key cryptography[J]. Journal of Software, 2011, 22(6): 1316-1332 (in Chinese)

(張福泰, 孫銀霞, 張磊, 等. 無證書公鑰密碼體制研究[J]. 軟件學報, 2011, 22(6): 1316-1332)

[4] Katz J, Lindell Y. Introduction to Modern Cryptography[M]. New York: CRC Press, 2014: 193-203

[5] Goldwasser S, Micali S, Rivest R L. A digital signature scheme secure against adaptive chosen-message attacks[J]. SIAM Journal on Computing, 1988, 17(2): 281-308

[6] Tang P C, Ash J S, Bates D W, et al. Personal health records: Definitions, benefits, and strategies for overcoming barriers to adoption[J]. Journal of the American Medical Informatics Association, 2006, 13(2): 121-126

[7] Gostin L O, Lazzarini Z, Neslund V S, et al. The public health information infrastructure: A national review of the law on health information privacy[J]. Journal of the American Medical Association, 1996, 275(24): 1921-1927

[8] Miyazaki K, Susaki S, Iwamura M, et al. Digital documents sanitizing problem[J]. Institute of Electronics, Information and Communication Engineers Technical Reports, 2003 [2017-09-01]. http://ci.nii.ac.jp/naid/10026847332/

[9] Rivest R L. Two signature schemes[OL]. [2015-09-14]. http://people.csail.mit.edu/rivest/pubs.html

[10] Traverso G, Demirel D, Buchmann J. Homomorphic Signature Schemes: A Survey[M]. Berlin: Springer, 2016: 53-58

[11] P?hls H C, Peters S, Samelin K, et al. Malleable signatures for resource constrained platforms[C] //Proc of IFIP Int Workshop on Information Security Theory and Practices. Berlin: Springer, 2013: 18-33

[12] Johnson R, Molnar D, Song D, et al. Homomorphic signature schemes[C] //Proc of 2002 Cryptographers Track at the RSA Conf. Berlin: Springer, 2002: 244-262

[13] Steinfeld R, Bull L, Zheng Yuliang. Content extraction signatures[C] //Proc of the 4th Int Conf on Information Security and Cryptology. Berlin: Springer, 2001: 285-304

[14] P?hls H C, Samelin K, Posegga J, et al. Length-hiding redactable signatures from one-way accumulators inO(n), MIP-1201[R]. Passau: Faculty of Computer Science and Mathematics, University of Passau, 2012

[15] Derler D, P?hls H C, Samelin K, et al. A general framework for redactable signatures and new constructions[C] //Proc of the 18th Int Conf on Information Security and Cryptology. Berlin: Springer, 2015: 3-19

[16] Nojima R, Tamura J, Kadobayashi Y, et al. A storage efficient redactable signature in the standard model[G] //LNCS 5735: Proc of the 12th Int Conf on Information Security. Berlin: Springer, 2009: 326-337

[17] Miyazaki K, Iwamura M, Matsumoto T, et al. Digitally signed document sanitizing scheme with disclosure condition control[J]. IEICE Trans on Fundamentals of Electronics, Communications and Computer Sciences, 2005, 88(1): 239-246

[18] Miyazaki K, Hanaoka G, Imai H. Digitally signed document sanitizing scheme based on bilinear maps[C] //Proc of the 2006 ACM Symp on Information, Computer and Communications security. New York: ACM, 2006: 343-354

[19] P?hls H C, Samelin K. On updatable redactable signatures[C] //Proc of the 12th Int Conf on Applied Cryptography and Network Security. Berlin: Springer, 2014: 457-475

[20] Attrapadung N, Libert B, Peters T. Efficient completely context-hiding quotable and linearly homomorphic signatures[C] //Proc of Public Key Cryptography. Berlin: Springer, 2013: 386-404

[21] Bauer D, Blough D M. Analysis of a redactable signature scheme on data with dependencies[R]. Atlanta: Georgia Institute of Technology, 2009

[22] P?hls H C, Samelin K. Accountable redactable signatures[C] //Proc of the 10th Int Conf on Availability, Reliability and Security (ARES). Piscataway, NJ: IEEE, 2015: 60-69

[23] Haber S, Hatano Y, Honda Y, et al. Efficient signature schemes supporting redaction, pseudonymization, and data deidentification[C] //Proc of the 2008 ACM Symp on Information, Computer and Communications Security. New York: ACM, 2008: 353-362

[24] Lim S, Lee E, Park C M. A short redactable signature scheme using pairing[J]. Security and Communication Networks, 2012, 5(5): 523-534

[25] Attrapadung N, Libert B, Peters T. Computing on authenticated data: New privacy definitions and constructions[C] //Proc of the 18th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2012: 367-385

[26] Kundu A, Bertino E. Structural signatures for tree data structures[J]. Proceedings of the VLDB Endowment, 2008, 1(1): 138-150

[27] Chang Chien, Lim C L, Xu Jia. Short redactable signatures using random trees[C] //Proc of the 2009 Cryptographers’ Track at the RSA Conf. Berlin: Springer, 2009, 9: 133-147

[28] Brzuska C, Busch H, Dagdelen O, et al. Redactable signatures for tree-structured data: Definitions and constructions[C] //Proc of the 8th Int Conf on Applied Cryptography and Network Security. Berlin: Springer, 2010: 87-104

[29] Slamanig D, Rass S. Generalizations and extensions of redactable signatures with applications to electronic healthcare[C] //Proc of the 11th Int Conf on Communications and Multimedia Security. Berlin: Springer, 2010: 201-213

[30] Lim S, Lee H S. A short and efficient redactable signature based on RSA[J]. ETRI Journal, 2011, 33(4): 621-628

[31] Samelin K, P?hls H C, Bilzhause A, et al. On structural signatures for tree data structures[G] //LNCS 7341: Proc of ACNS 2012. Berlin: Springer, 2012: 171-187

[32] Samelin K, P?hls H C, Bilzhause A, et al. Redactable signatures for independent removal of structure and content[C] //Proc of the 8th Int Conf on Information Security Practice and Experience. Berlin: Springer, 2012: 17-33

[33] Hirose S, Kuwakado H. Redactable signature scheme for tree-structured data based on Merkle tree[C] //Proc of 2013 Int Conf on Security and Cryptography (SECRYPT). Piscataway, NJ: IEEE, 2013: 1-8

[34] de Meer H, P?hls H C, Posegga J, et al. Redactable signature schemes for trees with signer-controlled non-leaf-redactions[C] //Proc of 2012 Int Conf on E-Business and Telecommunications. Berlin: Springer, 2012: 155-171

[35] Wei Baodian. Applications of trees in special signatures[J]. Computer Engineering and Applications, 2006, 42(11): 16-20 (in Chinese)

(韋寶典. 樹結構在幾種特殊簽名中的應用研究[J]. 計算機工程與應用, 2006, 42(11): 16-20)

[36] Bull L, Squire D M G, Zheng Yuliang. A hierarchical extraction policy for content extraction signatures[J]. International Journal on Digital Libraries, 2004, 4(3): 208-222

[37] Bauer D, Blough D M, Mohan A. Redactable signatures on data with dependencies and their application to personal health records[C] //Proc of the 8th ACM Workshop on Privacy in the Electronic Society. New York: ACM, 2009: 91-100

[38] Wu Zhenyu, Hsueh C W, Tsai C Y, et al. Redactable signatures for signed CDA documents[J]. Journal of Medical Systems, 2012, 36(3): 1795-1808

[39] Brown J, Blough D M. Verifiable and redactable medical documents[C] //Proc of 2012 AMIA Annual Symp. San Francisco: American Medical Informatics Association, 2012: 11-48

[40] Kundu A, Bertino E. Privacy-preserving authentication of trees and graphs[J]. International Journal of Information Security, 2013, 12(6): 467-494

[41] P?hls H C, Karwe M. Redactable signatures to control the maximum noise for differential privacy in the smart grid[C] //Proc of the 2nd Int Workshop on Smart Grid Security. Berlin: Springer, 2014: 79-93

[42] Bull L, Squire D M G, Newmarch J, et al. Grouping verifiable content for selective disclosure[C] //Proc of Australasian Conf on Information Security and Privacy. Berlin: Springer, 2003: 1-12

[43] Camenisch J, Dubovitskaya M, Haralambiev K, et al. Composable and modular anonymous credentials: Definitions and practical constructions[C] //Proc of the 21st Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2014: 262-288

[44] Brzuska C, P?hls H C, Samelin K. Efficient and perfectly unlinkable sanitizable signatures without group signatures[C] //Proc of the 10th European Public Key Infrastructure Workshop. Berlin: Springer, 2013: 12-30

[45] Brzuska C, P?hls H C, Samelin K. Non-interactive public accountability for sanitizable signatures[C] //Proc of the 10th European Public Key Infrastructure Workshop. Berlin: Springer, 2012: 178-193

[46] Ma Jinhua, Liu Jianghua, Wang Min, et al. An efficient and secure design of redactable signature scheme with redaction condition control[C] //Proc of the 12th Int Conf on Green, Pervasive, and Cloud Computing. Berlin: Springer, 2017: 38-52

[47] Derler D, Hanser C, Slamanig D. Revisiting cryptographic accumulators, additional properties and relations to other primitives[C] //Proc of the 2015 Cryptographer’s Track at the RSA Conf. Berlin: Springer, 2015: 127-144

[48] Benaloh J, De Mare M. One-way accumulators: A decentralized alternative to digital signatures[C] //Proc of 1993 Workshop on the Theory and Application of of Cryptographic Techniques. Berlin: Springer, 1993: 274-285

[49] Guo Hong, Li Zhengyu, Hu Bian. Quantum Cryptography[M]. Beijing: National Defence Industry Press, 2016 (in Chinese)

(郭弘, 李政宇, 彭編. 量子密碼[M]. 北京: 國防工業出版社, 2016)

[50] Regev O. Lattice-based cryptography[C] //Proc of the 26th Annual Inte Cryptology Conf. Berlin: Springer, 2006: 131-141

[51] Zeng Guihua. Quantum Cryptography[M]. Beijing: Science Press, 2006 (in Chinese)

(曾貴華. 量子密碼學[M]. 北京: 科學出版社, 2006)

[52] Libert B, Mouhartem F, Nguyen K. A lattice-based group signature scheme with message-dependent opening[C] //Proc of the 14th Int Conf on Applied Cryptography and Network Security. Berlin: Springer, 2016: 137-155

[53] Zhang Jiang, Chen Yu, Zhang Zhenfeng. Programmable Hash functions from lattices: Short signatures and IBEs with small key sizes[C] //Proc of the 36th Annual Cryptology Conf. Berlin: Springer, 2016: 303-332

[54] Libert B, Ling San, Nguyen K, et al. Zero-knowledge arguments for lattice-based accumulators: logarithmic-size ring signatures and group signatures without trapdoors[C] //Proc of the 35th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2016: 1-31

SurveyonRedactableSignatures

Ma Jinhua1,2, Liu Jianghua3, Wu Wei1,2, and Huang Xinyi1,2

1(SchoolofMathematicsandInformation,FujianNormalUniversity,Fuzhou350007)2(FujianProvincialKeyLaboratoryofNetworkSecurityandCryptology(FujianNormalUniversity),Fuzhou350007)3(SchoolofInformationTechnology,DeakinUniversity,Melbourne,Australia3125)

Data security issues have become a serious challenge to national economic, political, defence and cultural security. As a core technology in protecting data security, digital signatures have been widely used for the verification of data integrity and source authenticity. The security definition of conventional digital signatures is existentially unforgeable against adaptive chosen-message attacks. Although it meets the basic security requirement of data authentication, it hampers the reasonable operation of authenticated data which is desirable in many practical applications. As a type of malleable homomorphic signatures for editing, redactable signatures allow the signature holder (redactor) to delete sensitive portions of the signed data and generate a valid signature for the disclosed data without any help from the original signer. It has been a research hotspot in the field of cryptography since it was introduced in 2001. In recent years, many researchers have studied redactable signatures from the aspects of formal security definition, redaction control mechanism, computational cost and communication overhead, and there are lots of research results. However, the rapid development of network technology and its applications are putting forward new challenges to redactable signatures. This paper summarizes and analyses redactable signatures in terms of algorithm definition, security model and representative designs. Furthermore, some existing problems worthy of further study are also discussed.

redactable signatures; homomorphic signatures; digital signature; data authentication; security model

TP309

MaJinhua, born in 1990. PhD. Her main research interests include cryptography and information security.

LiuJianghua, born in 1988. PhD. His main research interests include cryptography and information security.

WuWei, born in 1981. PhD, associate professor. Her main research interests include cryptography and information security.

HuangXinyi, born in 1981. PhD, professor, PhD supervisor. His main research interests include cryptography and information security.