唐紫鑫，黃欣沂

?

基于批量簽名思想的可截取簽名構(gòu)造

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

（1. 福建師范大學(xué)數(shù)學(xué)與信息學(xué)院，福建 福州 350007；2. 福建省網(wǎng)絡(luò)安全與密碼技術(shù)重點實驗室，福建 福州 350007）

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

可截取簽名；Waters數(shù)字簽名；批量簽名；RSAProd方案

1 引言

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

數(shù)字簽名[2]是保證數(shù)據(jù)安全的核心技術(shù)之一，在電子政務(wù)、電子商務(wù)、醫(yī)療數(shù)據(jù)、電子現(xiàn)金等領(lǐng)域有廣泛的用途。數(shù)字簽名可提供數(shù)據(jù)內(nèi)容的完整性和數(shù)據(jù)源的真實性檢測。

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

盡管數(shù)字簽名方案的標(biāo)準(zhǔn)安全要求能夠滿足數(shù)據(jù)認(rèn)證的基本要求，卻也阻礙了簽名持有者對已簽名數(shù)據(jù)的合理操作。

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

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

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

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

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

本文從Waters簽名方案[20]著手，先把數(shù)字簽名批量化，構(gòu)造批量化的Waters簽名，再將批量簽名轉(zhuǎn)化為可截取簽名（稱之為基于Waters簽名方案的可截取簽名WCES）。此方案為可截取簽名的構(gòu)造提供了較為一般的方法，與其他可截取簽名方案進(jìn)行橫縱向?qū)Ρ?，說明此方案運(yùn)行速度較快。

2 預(yù)備知識

2.1 雙線性對

2.2 困難假設(shè)

2.3 數(shù)字簽名

2.4 Waters簽名方案

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

2.5 批量簽名

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

批量簽名應(yīng)用非常廣泛，能用于電子商務(wù)、電子現(xiàn)金等領(lǐng)域。因其應(yīng)用領(lǐng)域的相似性，可考慮轉(zhuǎn)化為可截取簽名。與批量簽名不同的是，可截取簽名可將待簽名消息做適當(dāng)處理以保護(hù)隱私信息。

2.6 可截取簽名

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

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

2.7 弱序CES不可偽造性

3 批量化Waters數(shù)字簽名方案

本節(jié)呈現(xiàn)由數(shù)字簽名到批量簽名的轉(zhuǎn)換過程。

3.1 方案描述

3.2 方案安全性分析

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

4.1 方案描述

刪除相應(yīng)子消息的簽名，截取過程如下。

4.2 方案正確性分析

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

(2)

4.3 方案安全性分析

應(yīng)用引理1，有

經(jīng)計算得

這包含要證的式子。

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

4.4 效率分析

表1 符號說明

表2 種方案算法復(fù)雜度縱向比較

表3 種方案算法復(fù)雜度橫向比較

5 結(jié)束語

[1] 中興通訊學(xué)院.對話多媒體通信[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] 藍(lán)才會, 王彩芬. 基于身份的可截取簽名方案[J]. 計算機(jī)應(yīng)用, 2007, 27(10): 2456-2458.LAN C H, WANG C F. ID-based content extraction signature[J]. Journal of Computer Applications, 2007.

[12] 曹素珍, 王彩芬. 基于離散對數(shù)問題的可截取簽名方案[J]. 計算機(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ìn)方案[J]. 計算機(jī)工程與應(yīng)用, 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]. 計算機(jī)工程與科學(xué), 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ìn)[J]. 網(wǎng)絡(luò)與信息安全學(xué)報, 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

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

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

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

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