唐張穎，王志偉，2

(1.南京郵電大學(xué)計(jì)算機(jī)學(xué)院、軟件學(xué)院、網(wǎng)絡(luò)空間安全學(xué)院，江蘇 南京 210023 2.南京郵電大學(xué)江蘇省大數(shù)據(jù)安全與智能處理重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210023)

隨著全球數(shù)字化進(jìn)程的深入推進(jìn)，區(qū)塊鏈產(chǎn)業(yè)也在飛速發(fā)展。這期間，區(qū)塊鏈錢(qián)包也由單資產(chǎn)錢(qián)包、單鏈錢(qián)包發(fā)展為多鏈多資產(chǎn)錢(qián)包，從單一的轉(zhuǎn)賬收款錢(qián)包發(fā)展為區(qū)塊鏈生態(tài)服務(wù)平臺(tái)。比特幣以及其他加密貨幣系統(tǒng)中廣泛使用了ECDSA簽名算法，通過(guò)驗(yàn)證簽名來(lái)保證信息的真實(shí)性［1］，確保交易過(guò)程順利執(zhí)行。SM2簽名算法［2］作為我國(guó)自主研發(fā)的公鑰密碼算法，加入了用戶特異性等信息且橢圓曲線參數(shù)需要利用算法產(chǎn)生，使SM2算法相較于ECDSA算法安全性有所提升。為了保證用戶的數(shù)字資產(chǎn)，使用更安全的簽名算法是有必要的。

錢(qián)包系統(tǒng)中私鑰一旦丟失或泄露，用戶的資產(chǎn)安全將受到嚴(yán)重威脅?，F(xiàn)實(shí)生活中通過(guò)借助可信第三方來(lái)對(duì)應(yīng)用戶身份和密鑰，以此保護(hù)用戶資產(chǎn)。但在區(qū)塊鏈系統(tǒng)中，借助可信第三方生成私鑰［3］的方式會(huì)導(dǎo)致出現(xiàn)非法者惡意攻擊可信第三方、獲取用戶的個(gè)人隱私、發(fā)送錯(cuò)誤信息等違法行為。為了解決這個(gè)問(wèn)題，國(guó)內(nèi)外學(xué)者提出了門(mén)限簽名［4］的思想，簽名私鑰存儲(chǔ)于多個(gè)參與方手中，只有當(dāng)指定人數(shù)的參與方同意時(shí)才可以生成特定消息下的簽名，有效地實(shí)現(xiàn)了權(quán)力的分配。門(mén)限簽名的思想能夠有效地抵抗惡意行為，保護(hù)用戶資產(chǎn)，因此，構(gòu)造一個(gè)門(mén)限SM2簽名方案是有意義的。

1 相關(guān)工作

門(mén)限思想最早由Shamir和Blakley分別獨(dú)立提出，Desmedt和 Frankel［5-6］引入了門(mén)限密碼的概念，徹底打開(kāi)了門(mén)限密碼研究的大門(mén)。門(mén)限簽名是門(mén)限秘密共享技術(shù)和數(shù)字簽名的一種結(jié)合，由至少門(mén)限值數(shù)量的參與方合作運(yùn)行，任意少于門(mén)限數(shù)量的參與方無(wú)法合謀進(jìn)行簽名。

Gennaro等［7］提出的門(mén)限簽名方案中，需要 n方參與者集合中不少于2n／3的參與者合作進(jìn)行簽名，但很容易受到敵手控制n／3或者更多參與者的攻擊。 改進(jìn)的 （t，n）門(mén)限 ECDSA 方案［8］需要事先選擇一個(gè)包含t位誠(chéng)實(shí)參與者的簽名小組，然而只要小組內(nèi)有一方崩潰或者某一方是惡意的敵手，簽名就會(huì)失敗，這可能會(huì)演變?yōu)閷?duì)手控制一方或少數(shù)參與者來(lái)阻止系統(tǒng)簽名。Mackenzie等［9］提出特定兩方協(xié)議，但該協(xié)議嚴(yán)重依賴于低效的零知識(shí)證明，因此產(chǎn)生的協(xié)議沒(méi)有實(shí)際意義。

尚銘等［19］針對(duì)國(guó)產(chǎn)SM2簽名算法提出了SM2橢圓曲線門(mén)限密碼算法，私鑰信息被分享給獨(dú)立的多個(gè)參與者，但是該算法中總成員數(shù)n必須大于等于2t＋ 1，不適用（2，3）等區(qū)塊鏈簽名。 Zhang 等［20］提出的SM2簽名算法的兩方協(xié)同方案也使用了Paillier同態(tài)加密技術(shù)，同樣需要復(fù)雜的范圍證明。

為了解決上述問(wèn)題，本文基于同態(tài)加密CL方案，提出一種基于SM2簽名算法的門(mén)限簽名方案，方案的貢獻(xiàn)如下：

（1）門(mén)限方案僅限制簽名人數(shù)n≥t＋1，即使簽名者集合中惡意者占多數(shù)，方案仍能提供安全有效的簽名。

（2）多方參與者利用CL同態(tài)加密方案生成各自的簽名，同時(shí)對(duì)CL密文提供相應(yīng)的零知識(shí)證明，保證密文格式正確。

（3）文中采用了針對(duì)離散對(duì)數(shù)關(guān)系的零知識(shí)證明算法ZKPoRepS，算法通過(guò)使用額外一輪挑戰(zhàn)消除階已知的群F＾上的元素，借助通用群模型證明了HSM群上離散對(duì)數(shù)關(guān)系的安全性；額外的挑戰(zhàn)使證明輪數(shù)降為一次，相對(duì)于同類方案［4］中使用的零知識(shí)證明算法，通信開(kāi)銷和計(jì)算速度都得到提升。

2 預(yù)備知識(shí)

2.1 SM2簽名方案

簽名者首先輸入系統(tǒng)公共參數(shù)p、q、E、P。 其中，p是大素?cái)?shù)，E是定義在有限域Fp上的橢圓曲線，G是E上的q階基點(diǎn)。簽名方案包括以下算法：

（1）密鑰生成算法。簽名者選擇隨機(jī)的私鑰d，d∈ ［1，q-1］，計(jì)算公鑰 P ＝ dG。

（3）驗(yàn)證算法。驗(yàn)證方收到簽名者發(fā)來(lái)的消息m 和簽名 （r′，s′） 后，首先判斷 r′，s′∈ ［1，q-1］，r′＋s′≠q是否成立，若不成立則驗(yàn)證失?。挥?jì)算t＝（r′＋ s′）， 若 t＝ 0， 驗(yàn)證失??；計(jì)算 （x′1，y′1） ＝ s′G ＋tP； 最后計(jì)算 R ＝ （e′＋ x′1）mod q； 若 R ＝ r′， 驗(yàn)證通過(guò)，否則驗(yàn)證失敗。

2.2 基于HSM群的CL加密方案

根據(jù)文獻(xiàn)［14］提出的群生成算法構(gòu)造HSM群，輸入安全參數(shù)1λ和素?cái)?shù)p，GGenHSM算法輸出公共參數(shù)。 其中，有限交換群的階為·q，在多項(xiàng)式時(shí)間內(nèi)可以判斷某元素是否在群上。是生成元的階。是上階為q的循環(huán)子群，由生成，多項(xiàng)式時(shí)間內(nèi)可以通過(guò) Slove（·）［4］算法解決中的離散對(duì)數(shù)問(wèn)題。 G是中階為q·s的循環(huán)子群，由g生成，s劃分了。Gq是群G上階為s的子群，由gq生成。方案中設(shè)gq由經(jīng)過(guò)冪運(yùn)算得到，具有隨機(jī)性。通過(guò)構(gòu)造? G，有成立。 CL 加密方案包括以下算法：

（2）加密算法。輸入公鑰pk和消息m，選擇隨機(jī)數(shù) ρ， 計(jì)算密文 （C1，C2）， 其中，

（3）解密算法。輸入私鑰sk和密文（C1，C2），計(jì)算， 使用 Slove（·）算法解決上的離散對(duì)數(shù)問(wèn)題，返回明文m←Slove（M）。

2.3 數(shù)學(xué)假設(shè)

對(duì)于門(mén)限SM2簽名方案，依賴以下困難假設(shè)：（1） HSM 假設(shè)。gq由經(jīng)過(guò)冪運(yùn)算得到且具有隨機(jī)性，因此區(qū)分群G上的某元素是否在子群Gq上是困難的。設(shè)群由生成，整數(shù)上的分布D（Dq） 距離群 G（） 上的均勻分布的距 離少于 2-λ， 概率為敵手A的優(yōu)勢(shì)，若對(duì)于所有概率時(shí)間算法，A的優(yōu)勢(shì)可以忽略，稱HSM問(wèn)題在G上是困難的。

3 安全模型與定義

本文采用基于游戲的安全定義［4］：選擇明文攻擊下的門(mén)限不可偽造性（tu-cma）。通過(guò)構(gòu)造模擬協(xié)議，利用與敵手的交互，將安全性歸約到原始簽名方案的安全假設(shè)。

3.1 安全模型

假設(shè)存在一個(gè)多項(xiàng)式時(shí)間算法A破壞了門(mén)限SM2方案的密鑰生成過(guò)程和簽名過(guò)程，偽造者F可以利用A算法來(lái)打破標(biāo)準(zhǔn)SM2簽名算法的不可偽造性。模型中F模擬A的環(huán)境，使A無(wú)法區(qū)分自己處于真實(shí)環(huán)境還是正在與F交互。若A摧毀了某參與方 ｛Pj｝j＞1，F(xiàn) 模擬參與者 Pi， 算法過(guò)程中 F 的輸出和A與誠(chéng)實(shí)Pi交互得到的輸出難以區(qū)分。F擁有SM2簽名算法的公鑰P，可以向簽名預(yù)言機(jī)詢問(wèn)選擇的消息，詢問(wèn)之后必須輸出偽造的消息簽名σ。

3.2 安全性定義

數(shù)字簽名方案所需的標(biāo)準(zhǔn)安全概念是選擇明文攻擊下的存在性不可偽造。針對(duì)此標(biāo)準(zhǔn)，傳統(tǒng)簽名方案的安全性已經(jīng)得到了證明［21］。

（1）存在性不可偽造（eu-cma）。假設(shè)一個(gè)數(shù)字簽名方案S包含產(chǎn)生密鑰、生成簽名和驗(yàn)證3個(gè)過(guò)程。某概率多項(xiàng)式時(shí)間算法A輸入公鑰vk后可以訪問(wèn)簽名算法的預(yù)言機(jī)Sign（sk，·），此預(yù)言機(jī)可以自適應(yīng)地對(duì)其選擇的消息請(qǐng)求簽名。對(duì)于算法A，數(shù)字簽名方案S是存在性不可偽造的。設(shè)M為詢問(wèn)的消息集合，A對(duì)不屬于M的消息m產(chǎn)生合理簽名的概率是關(guān)于安全參數(shù)λ的函數(shù)，可以忽略不計(jì)。

（2）門(mén)限簽名不可偽造（tu-cma）。假設(shè)一個(gè)（t，n）門(mén)限數(shù)字簽名方案IS包含產(chǎn)生密鑰、生成簽名和驗(yàn)證3個(gè)過(guò)程，方案中存在一個(gè)最多攻擊t個(gè)參與者的概率多項(xiàng)式時(shí)間算法A，可以看到產(chǎn)生密鑰、自適應(yīng)地選擇消息和對(duì)消息簽名的過(guò)程。對(duì)于算法A，門(mén)限數(shù)字簽名方案IS是不可偽造的。A對(duì)不屬于M的消息m產(chǎn)生合理簽名的概率是關(guān)于安全參數(shù)λ的函數(shù)，可以忽略不計(jì)。

4 門(mén)限SM2簽名方案

門(mén)限SM2簽名方案包含3個(gè)階段：生成CL方案公共參數(shù)、產(chǎn)生密鑰、生成簽名。算法表1、2、3、4直觀地展現(xiàn)了各階段的交互過(guò)程，除表4的階段2由參與方兩兩成對(duì)完成，其他階段每個(gè)參與方執(zhí)行相同的操作，因此文中僅描述某參與方Pi執(zhí)行的操作，當(dāng)Pi廣播某些信息時(shí)，也隱式地從其他參與方 ｛Pj｝j≠i接收到這些信息。表中點(diǎn)對(duì)點(diǎn)通信用單箭頭表示，廣播用雙箭頭表示。

4.1 生成CL方案公共參數(shù)

4.1.1 生成隨機(jī)公共素?cái)?shù)

（1）各參與方Pi首先選擇隨機(jī)數(shù)ri，計(jì)算ri的承諾 （gci，gdi）［22-23］，向其他成員廣播gci。

（2） 接著，Pi收到其余方 ｛Pj｝j≠i的承諾｛gcj｝j≠i后，廣播gdi； 待收到 ｛Pj｝j≠i廣播的gdj后，Pi執(zhí)行ri← Open（gci，gdi） 打開(kāi)承諾。

（3） 最后，Pi算出公共輸出

4.1.2 生成公共參數(shù)gq

（1） 得到 （，q） 后，Pi首先通過(guò)文獻(xiàn)［14］中的方法算出生成元。

（2） 然后，Pi選擇隨機(jī)的ti， 并計(jì)算； 接著，Pi計(jì)算gi的承諾并廣播。

（3）待Pi揭開(kāi)其他參與方的承諾后，計(jì)算關(guān)于ti的零知識(shí)證明 ZKPoRepS［24］（如表1所示，其中B是安全參數(shù)），以此向其他參與方證明自己知道ti。一旦證明驗(yàn)證失敗，中止方案。

表1 ZKPoRepS零知識(shí)證明

表2 生成CL方案的參數(shù)

4.2 產(chǎn)生密鑰

在產(chǎn)生密鑰的算法中，對(duì)于n方參與者，設(shè)定門(mén)限值t，其中n＞t。 整個(gè)流程如表3所示。

表3 生成簽名方案公私鑰

（1）Pi首先選擇隨機(jī)的ui∈Z／qZ，計(jì)算uiG的承諾，并生成CL加密方案的公私鑰（ski，pki）；之后廣播自己的公鑰和對(duì)uiG的承諾。

（3）然后，Pi對(duì)秘密值ui執(zhí)行基于Shamir秘密共享［25］的 Feldman-Vss 算法［26］，執(zhí)行該算法得到的結(jié)果di是簽名私鑰d的 （t，n）Shamir秘密共享。

（4） 最后，Pi使用 Schnorr［27］提供的零知識(shí)證明ZKPoK，向其他參與方證明自己知道di。

4.3 生成簽名

簽名的整個(gè)過(guò)程如表4所示。定義S?［n］為對(duì)消息m簽名的參與者集合，設(shè)｜S｜＝t時(shí)Pi可以使用適當(dāng)?shù)睦窭嗜障禂?shù)將私鑰d的（t，n）份額｛di｝i∈［n］轉(zhuǎn)換為d的 （t，t） 份額 ｛wi｝i∈S， 也可以將（1＋d）-1的 （t，n） 份 額 轉(zhuǎn) 換 為 （t，t） 份 額｛vi｝i∈S。

表4 簽名過(guò)程

4.3.1 對(duì)隨機(jī)份額加密

5 安全性

本文所設(shè)計(jì)的門(mén)限SM2簽名方案的安全性是基于原始SM2簽名方案的可證明安全性。本節(jié)主要證明了方案中生成簽名階段的安全性，生成參數(shù)階段和產(chǎn)生密鑰階段的安全性可以通過(guò)引用文獻(xiàn)［4］來(lái)證明。簽名過(guò)程中所有參與方都執(zhí)行了相同的操作，因此模擬器F只需要模擬其中某一位參與方P1。

5.1 模擬簽名的生成

在密鑰生成階段的模擬中，模擬器F獲得了其他參與者的秘密值 ｛wj｝j∈S，j≠1、 ｛vj｝j∈S，j≠1和公鑰｛p kj｝j∈S。 在模擬簽名階段，F(xiàn)輸入消息 m 后，需要模擬與敵手A交互的過(guò)程。模擬過(guò)程中，一旦A拒絕打開(kāi)任何承諾，或者零知識(shí)證明失敗，或者簽名（r，s）未通過(guò)驗(yàn)證，F(xiàn)都會(huì)中止操作。

5.1.1 對(duì)隨機(jī)份額加密

（2） 接著，F(xiàn) 發(fā)布密文 ck1，c＾v1對(duì)應(yīng)的 ZKAoK 零知識(shí)證明 π1，π′1，并計(jì)算 Γ1＝ γ1G 的承諾 （sc1，sd1）。

（3）當(dāng)F接收到A發(fā)送的密文、承諾和零知識(shí)證明 （ckj，cvj，scj，πj，π′j） 后， F 廣播 （ck1，c＾v1，sc1，π1，π ′1） 。

5.1.2 計(jì)算中間變量 （ρi，σi，δi）

（a）F向SM2簽名預(yù)言機(jī)詢問(wèn)m的簽名 （r，s），計(jì)算R ＝s（G ＋P） ＋rP ＋m∈Z／qZ，r＝Rx＋e。

（b）接著，F(xiàn)對(duì)A重放（1）的步驟，在不被A發(fā)現(xiàn)的前提下模糊P1對(duì)Γ1的承諾。

（c） F 從 A 接收到 ｛s dj｝j∈S，j≠1后打開(kāi)承諾，獲

5.2 證明總結(jié)

F可以判斷自己是否處于半正確的執(zhí)行過(guò)程，因此F能及時(shí)調(diào)整模擬，令A(yù)無(wú)法察覺(jué)，簽名階段所有的模擬都和真實(shí)協(xié)議的執(zhí)行不可區(qū)分。F從自己的SM2挑戰(zhàn)那里得到系統(tǒng)公鑰，當(dāng)A破壞了門(mén)限SM2方案中的t位參與方時(shí)，F(xiàn)把最終生成的簽名作為自己的偽造，從而打破SM2簽名算法的存在性不可偽造。

假設(shè)SM2簽名算法是存在性不可偽造的，數(shù)學(xué)假設(shè)成立，CL加密方案是選擇明文下不可區(qū)分的，則門(mén)限SM2簽名方案是存在性不可偽造的。

6 效率

在本文中，設(shè)計(jì)實(shí)驗(yàn)對(duì)門(mén)限SM2簽名方案和門(mén)限ECDSA簽名方案［4］的效率進(jìn)行了對(duì)比分析，從產(chǎn)生密鑰、生成簽名的計(jì)算量進(jìn)行了評(píng)估。令簽名者集合記為n，門(mén)限值記為t，群F＾上的冪運(yùn)算相對(duì)于類群中的冪運(yùn)算幾乎可以忽略，因此文中省略了群F＾上的計(jì)算次數(shù)，僅列出了類群中的冪運(yùn)算。由表5可知，本方案在產(chǎn)生密鑰階段的零知識(shí)證明計(jì)算量減少，這是因?yàn)槲墨I(xiàn)［4］構(gòu)造的零知識(shí)證明算法對(duì)所證明的離散對(duì)數(shù)關(guān)系做了修改，之后使用最低公共多重（lcm）技巧來(lái)證明修改后的離散對(duì)數(shù)關(guān)系，協(xié)議需要重復(fù)執(zhí)行多輪來(lái)保證安全性。本文方案采用的緊湊型零知識(shí)證明算法ZKPoKRepS使用額外一輪挑戰(zhàn)來(lái)消除群F＾上的元素，借助通用群模型，證明輪數(shù)僅需要一次，使該階段的計(jì)算速度相對(duì)于文獻(xiàn)［4］提升了約46%。

表5 門(mén)限SM2和門(mén)限ECDSA方案計(jì)算量對(duì)比

在通信開(kāi)銷方面，如表6所示，本方案由于采用ZKPoKRepS算法，產(chǎn)生密鑰階段的通信開(kāi)銷也降低了60%以上；生成簽名階段本方案的通信開(kāi)銷要略高于門(mén)限ECDSA方案，這是因?yàn)镾M2簽名算法自身非線性的特征，參與方計(jì)算密文和同態(tài)加密，以及零知識(shí)證明都需要更多次冪運(yùn)算，使簽名者之間交互產(chǎn)生的通信開(kāi)銷相應(yīng)增加。

表6 不同安全級(jí)別下通信開(kāi)銷對(duì)比

為了顯示不同簽名人數(shù)的情況，選?。╰，n）分別為（1，3），（2，4），（2，5）來(lái)分析不同簽名人數(shù)和門(mén)限值的通信開(kāi)銷。隨著簽名人數(shù)的增加，通信開(kāi)銷也在線性增長(zhǎng)，由圖1可以更直觀地發(fā)現(xiàn)本方案在密鑰階段的通信開(kāi)銷上得到了提升。

圖1 128比特安全下（t，n）門(mén)限簽名方案

綜合考慮，雖然本文方案在簽名階段通信開(kāi)銷要略大于門(mén)限ECDSA方案，但是在密鑰階段要遠(yuǎn)遠(yuǎn)小于后者，并且ECDSA方案對(duì)消息不做任何處理，本SM2簽名方案需要對(duì)消息作預(yù)處理，處理后消息加入了用戶特異性等信息，使本方案的安全性也有明顯提升。

7 結(jié)束語(yǔ)

本文基于門(mén)限簽名的思想設(shè)計(jì)了門(mén)限SM2簽名方案，允許在簽名群體中惡意者占多數(shù)的情況下保證簽名的順利進(jìn)行。門(mén)限SM2簽名方案基于HSM困難問(wèn)題，利用CL算法傳輸密文，簽名過(guò)程由各方合作完成，實(shí)現(xiàn)了權(quán)利的分配。文中采用基于模擬的證明方法，通過(guò)構(gòu)造模擬協(xié)議，利用與敵手的交互將安全性歸約到原始簽名方案的安全性。最后，本文針對(duì)通信量和計(jì)算量與Castagnos等［4］的門(mén)限ECDSA方案進(jìn)行對(duì)比，在產(chǎn)生密鑰階段明顯優(yōu)于門(mén)限ECDSA方案。由于SM2算法自身非線性的特征，在簽名過(guò)程中需要額外傳輸乘法份額的密文等信息，在簽名階段需要更多的通信開(kāi)銷。