基于批量簽名思想的可截取簽名構造

唐紫鑫，黃欣沂

?

基于批量簽名思想的可截取簽名構造

唐紫鑫1,2，黃欣沂1,2

（1. 福建師范大學數學與信息學院，福建 福州 350007；2. 福建省網絡安全與密碼技術重點實驗室，福建 福州 350007）

根據批量簽名的思想，將Waters數字簽名方案批量化，進而構造可截取簽名。所構造的方案是Steinfeld、Bull、Zheng ( ICISC 2001) 提出的RSAProd方案的改進，以較長的截取簽名長度為代價節省整體的運算時間，并證明所構造方案在適應性選擇消息攻擊下具有不可偽造性和隱私性。

可截取簽名；Waters數字簽名；批量簽名；RSAProd方案

1 引言

數據和信息之間是相互聯系的。數據是反映客觀事物屬性的記錄，是信息的具體表現形式[1]。數據經過加工處理之后，就成為信息；而信息需要經過數字化轉變成數據才能存儲和傳輸[1]。數據不僅是用戶的隱私，更是互聯網財富的源泉。眾多科研機構、研究人員將問題與生活實際聯系起來時，數據提供著必不可少的支撐。在數據驅動型經濟背景下，企業的決策和國家的發展戰略制定都需要以數據為依據，各大企業乃至世界各國陷入一場前所未有的數據爭奪戰。數據安全問題的保障、隱私數據的保護也成為數據爭奪戰中應當考慮的重要問題。

數字簽名[2]是保證數據安全的核心技術之一，在電子政務、電子商務、醫療數據、電子現金等領域有廣泛的用途。數字簽名可提供數據內容的完整性和數據源的真實性檢測。

數字簽名的標準安全要求是在自適應選擇消息攻擊下滿足EUF-CMA安全——存在不可偽造性（existential unforgeability under adaptive chosen message attacks）[3]。EUF-CMA安全的含義：已知簽名者的公鑰，PPT（probability polynomial-time）攻擊者通過適應性詢問獲得需要的有效消息簽名對后，能為某個新消息計算出有效簽名的概率是可以忽略的。若數字簽名方案滿足此標準安全要求，則該數字簽名有效并能讓消息接收者相信收到的消息是完整的且未被惡意篡改，同時消息的來源是相應公鑰的持有者。經典數字簽名方案有ElGamal[4-5]、DSA、ECDSA[6]、RSA-FDH[7]和Schnorr[8]簽名等。

盡管數字簽名方案的標準安全要求能夠滿足數據認證的基本要求，卻也阻礙了簽名持有者對已簽名數據的合理操作。

為了滿足相應的實際需求，Steinfeld、Bull、Zheng（ICISC 2001）提出可截取簽名（CES，contentextraction signature）[9]。截取中“截”意味著刪除，“取”作提取之意。在不與初始簽名人進行交互的情況下，可截取簽名允許簽名的持有者將可以公開進行驗證的數據提取出來組成新數據，并根據初始簽名計算出對新數據的簽名。換言之，可截取簽名允許簽名的持有者對刪除敏感數據后的新數據集生成新的簽名。

由于相對數字簽名所擁有的此種特殊功能，可截取簽名的應用場景相當廣泛。本文以電子病歷為例闡述可截取簽名的功能。假設研究所C為研究某種疾病的治療方案，需要征集廣大患者的病歷。以患者B為例，設B可提供就診醫院A簽發的電子病歷。電子病歷通常記錄著患者的姓名、性別、身份證號、家庭地址、聯系電話、病史和診療記錄（包括病情描述和處方）等相關信息。但是B不愿向研究所透露身份證號、家庭地址、聯系電話等信息。如果A直接用普通數字簽名算法對病歷簽名，那么B無法對病歷進行刪改以保護隱私信息，從而B可能拒絕C的請求。可截取簽名則較好地解決此類問題。若A在簽名階段使用可截取簽名對病歷簽名，則B可以對病歷進行適當的操作，再提供給C。相比普通數字簽名，可截取簽名最大的優勢在于支持刪除操作，且不需要私鑰即可通過初始數據和初始簽名計算出新的數字簽名，并證實所保留數據的真實性。自提出以來，國內外學者對可截取簽名進行了大量深入的研究。

文獻[10]將可截取簽名應用于以數字圖書館為典型代表的環境，提出采用分級群組策略的可截取簽名方案，這是對文獻[9]提出的可截取簽名的直接應用。文獻[11]提出新的基于身份的可截取簽名方案，該方案不需要對每個子消息進行簽名，這提高了簽名效率，且能夠防止私鑰產生機構偽造簽名。文獻[12]提出一種滿足強安全性、基于離散對數困難問題的可截取簽名方案，此方案還包含身份信息，指數計算較少，相應地減少了計算量。文獻[13]的方案基于FDH-RSA簽名方案改進，在保持原方案安全性能不變的基礎上，優化截取文檔的結構，解決了截取后文檔存在的板式凌亂問題。文獻[14]提出一種能把密鑰泄露帶來的損失減小到最低的可截取簽名方案。文獻[15]提出一種細粒度的訪問控制，在加密數據的同時把符合屬性的子消息傳送給用戶，對存儲中訪問控制的問題進行細化，提高消息的利用率。文獻[16]則將截取消息分為必須截取和可選截取兩部分，允許對部分消息進行統一簽名和驗證。這些重要研究在文獻[9]的基礎上從不同角度繼承和發展，豐富了可截取簽名的研究。

上述應用方案的改進與文獻[9]中提出的CV（commit vector）、HT（hash tree）、RSA積（RSAP，RSAProd）、MERP（multi-exponent RSAProd）4種方案聯系密切。CV方案基于向量承諾設計，用個簽名取代一個簽名。方案以個承諾為代價，只要能減少承諾的計算量，那么簽名的計算量也會相應減少。但提取子消息的隨機值和刪除的子消息的承諾值使簽名長度很長，與子消息的數量呈線性關系。為了減少刪除的子消息的承諾值造成的簽名冗長，改進的HT方案巧妙地使用抗碰撞的散列函數構造二叉樹，將數據存儲在二叉樹中，減少了簽名長度，然而計算量仍很大。RSAP方案的構造基于RSA簽名的同態性質，因而驗證者只需驗證RSA簽名的乘積模的值是否等于散列值乘積的簽名模的值。因此，方案減少了傳送給驗證者的簽名長度，缺點在于沒有減少簽名者與數據持有者之間所傳遞簽名的長度。而MERP方案對這個缺點進行了改進，節省了簽名者的計算量但失去了快速驗證的性質。這幾個方案的設計目標都是既能快速簽名又能快速驗證的可截取簽名，且都是基于批量簽名[17]設計的。

批量簽名的概念由Fiat于1989年提出，能夠用一次簽名對若干個不同消息簽名，并且可以對每一條消息進行獨立驗證。此后，批量簽名得到廣泛的應用和發展，其中影響很大的工作之一是文獻[18]提出的基于樹結構的批量簽名算法。此結構與任何可證明安全的數字簽名進行結合都可以得到安全的批量簽名方案。文獻[9]中的HT方案所用的樹結構便是根據樹結構的批量簽名改造而來。不同之處在于，文獻[18]的方案不能滿足可截取簽名隱私性的要求，于是文獻[9]中的一個方案運用向量承諾[19]的隱藏性保證隱私性，此即為HT方案奠定基礎的CV方案。文獻[9]中的RSAP方案具有批量驗證的性質，但是不能批量簽名。MERP方案應用文獻[17]中的Fiat變換進行多指數RSA批量化，使方案具有批量簽名的性質，但失去快速驗證的性質。另外，文獻[13]也引入批量簽名的思想，改進了簽名和認證部分。由此，將批量簽名改進成可截取簽名是構造可截取簽名值得研究的一個方向，改進的過程中關鍵在于如何在保護數據隱私性的同時使計算量和簽名長度同時達到最優。

本文從Waters簽名方案[20]著手，先把數字簽名批量化，構造批量化的Waters簽名，再將批量簽名轉化為可截取簽名（稱之為基于Waters簽名方案的可截取簽名WCES）。此方案為可截取簽名的構造提供了較為一般的方法，與其他可截取簽名方案進行橫縱向對比，說明此方案運行速度較快。

2 預備知識

2.1 雙線性對

2.2 困難假設

2.3 數字簽名

2.4 Waters簽名方案

定義4[21]Waters簽名方案包括3個多項式時間算法。

2.5 批量簽名

對很多消息同時簽名時，批量簽名能夠用一次簽名完成對若干個不同的消息簽名，并且可以對每一條消息進行獨立驗證[17]，從而批量對消息簽名大大提高了效率。

批量簽名應用非常廣泛，能用于電子商務、電子現金等領域。因其應用領域的相似性，可考慮轉化為可截取簽名。與批量簽名不同的是，可截取簽名可將待簽名消息做適當處理以保護隱私信息。

2.6 可截取簽名

可截取簽名的安全模型包括不可偽造性和隱私性兩部分。

隱私性是指已知截取消息和截取簽名，攻擊者不能知道被刪除消息的內容。

2.7 弱序CES不可偽造性

3 批量化Waters數字簽名方案

本節呈現由數字簽名到批量簽名的轉換過程。

3.1 方案描述

3.2 方案安全性分析

4 基于Waters簽名方案的可截取簽名

4.1 方案描述

刪除相應子消息的簽名，截取過程如下。

4.2 方案正確性分析

該方案的正確性包括以下兩部分。

(2)

4.3 方案安全性分析

應用引理1，有

經計算得

這包含要證的式子。

2) 此可截取簽名的隱私性是顯然的，因為截取簽名統計上獨立于刪除的子消息。

4.4 效率分析

表1 符號說明

表2 種方案算法復雜度縱向比較

表3 種方案算法復雜度橫向比較

5 結束語

[1] 中興通訊學院.對話多媒體通信[M]. 北京: 人民郵電出版社, 2010. ZTE UNIVERSITY. Talk to multimedia communication[M]. Beijing: Posts and Telecom Press, 2010.

[2] RIVEST R L, SHAMIR A, ADLEMAN L A. Method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM, 1978, 21(2): 120-126.

[3] GOLDWASSER S, MICALI S, RIVEST R L. A digital signature scheme secure against adaptive chosen-message attacks[J]. Siam Journal of Computing, 1988, 17(2): 281-308.

[4] ELGAMAL T. A public key cryptosystem and a signature scheme based on discrete logarithms[C]//Workshop on the Theory and Application of Cryptographic Techniques (Eurocrypt 1984). 1984: 10-18.

[5] ELGAMAL T. A public key cryptosystem and a signature scheme based on discrete logarithms[J]. IEEE Trans inf theory, 1984, 31(4): 469-472.

[6] STANDARDS N I O. Digital signature standard (DSS)[J]. Federal Information Processing Standards Publication 186-2, 2000, 25.

[7] BELLARE M, ROGAWAY P. The exact security of digital signatures-how to sign with RSA and rabin[C]//International Conference on Theory and Application of Cryptographic Techniques. 1996: 399-416.

[8] SCHNORR C P. Efficient signature generation by smart cards[J]. Journal of Cryptology, 1991, 4(3): 161-174.

[9] STEINFELD R, BULL L, ZHENG Y. Content extraction signatures[C]//The International Conference on Information Security and Cryptology ( ICISC 2001). 2001: 285-304.

[10] BULL L, SQUIRE D M G, ZHENG Y. A hierarchical extraction policy for content extraction signatures[J]. International Journal on Digital Libraries, 2004, 4(3): 208-222.

[11] 藍才會, 王彩芬. 基于身份的可截取簽名方案[J]. 計算機應用, 2007, 27(10): 2456-2458.LAN C H, WANG C F. ID-based content extraction signature[J]. Journal of Computer Applications, 2007.

[12] 曹素珍, 王彩芬. 基于離散對數問題的可截取簽名方案[J]. 計算機工程, 2013, 39(4): 132-136.CAO S Z, WANG C F. Content extraction signature scheme based on DLP[J]. Computer Engineering, 2013, 39(4): 132-136.

[13] 李旭, 杜小妮, 王彩芬,等. 基于RSA的可截取簽名改進方案[J]. 計算機工程與應用, 2014,50(24): 96-99.XU L I, XIAONI D U, WANG C, et al. Improved scheme of content extraction signatures based on RSA[J]. Computer Engineering & Applications, 2014.

[14] WANG C, LI Y, HUANG S Y, et al. A new forward secure content extraction signature scheme[C]//International Conference on Fuzzy Systems and Knowledge Discovery. 2016: 1698-1702.

[15] 王彩芬, 徐婷, 張玉磊, 等. 基于可截取簽名和屬性加密的云存儲訪問控制方案[J]. 計算機工程與科學, 2015, 37(2): 238-244. WANG C F, TING X U, ZHANG Y L, et al. An access control scheme in cloud storage based on content extraction signature and attribute encryption[J]. Computer Engineering & Science, 2015.

[16] 王敏, 馬金花, 劉江華,等. 兩類可截取簽名方案的改進[J]. 網絡與信息安全學報, 2017,3(4): 69-77.WANG M, MA J H, LIU J H, et al. The two improvements of the content extraction signature [J]. Chinese Journal of Network and Information Security, 2017, 3(4): 69-77.

[17] FIAT A. Batch RSA[J]. Journal of Cryptology, 1997, 10(2): 75-88.

[18] PAVLOVSKI C J, BOYD C. Efficient batch signature generation using tree structures[C]//International Workshop on Cryptographic Techniques and E-Commerce (CrypTEC 1999). 1999: 70-77.

[19] CATALANO D, FIORE D. Vector commitments and their applications[M]//Public-Key Cryptography–PKC 2013. Springer Berlin Heidelberg, 2013: 55-72.

[20] WATERS B. Efficient identity-based encryption without random oracles[J]. Eurocrypt, 2005, 2004(2004): 114-127.

[21] KATZ J. Digital signatures[M]. Springer US, 2010: 127-128.

Construction of the content extraction signature scheme based on the thought of the batch scheme

TANG Zixin1,2, HUANG Xinyi1,2

1. School of Mathematics and Information, Fujian Normal University, Fuzhou 350007, China 2. Fujian Provincial Key Laboratory of Network Security and Cryptology, Fuzhou 350007, China

The Waters scheme was transformed into the content extraction signature scheme at the bridge of the thought from the batch signature scheme. The proposed scheme is improved by the RSAProd scheme, presented by Steinfeld, Bull, Zheng (ICISC 2001). The operation time is saved in every stage at the slight sacrifice of the length of extraction signatures. The security was proved that the proposed scheme is existentially unforgeable under chosen message attacks while the privacy is maintained.

content extraction signature, Waters scheme, batch signature,RSAProd scheme

TP393

A

10.11959/j.issn.2096-109x.2018102

2018-10-25；

2018-11-20

黃欣沂，xyhuang81@yahoo.com

國家自然科學基金資助項目（No.61822202，No.61872089）

The National Natural Science Foundation of China (No.61822202, No.61872089)

唐紫鑫（1993-），男，湖南株洲人，福建師范大學碩士生，主要研究方向為密碼學和信息安全。

黃欣沂（1981-），男，江蘇儀征人，福建師范大學教授、博士生導師，主要研究方向為密碼學和信息安全。