門限SM2簽名方案

唐張穎，王志偉，2

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

2 預備知識

2.1 SM2簽名方案

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

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

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

2.2 基于HSM群的CL加密方案

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

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

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

2.3 數(shù)學假設

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

3 安全模型與定義

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

3.1 安全模型

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

3.2 安全性定義

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

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

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

4 門限SM2簽名方案

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

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

4.1.1 生成隨機公共素數(shù)

（1）各參與方Pi首先選擇隨機數(shù)ri，計算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） 打開承諾。

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

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

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

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

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

表1 ZKPoRepS零知識證明

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

4.2 產(chǎn)生密鑰

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

表3 生成簽名方案公私鑰

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

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

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

4.3 生成簽名

簽名的整個過程如表4所示。定義S?［n］為對消息m簽名的參與者集合，設｜S｜＝t時Pi可以使用適當?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 簽名過程

4.3.1 對隨機份額加密

5 安全性

本文所設計的門限SM2簽名方案的安全性是基于原始SM2簽名方案的可證明安全性。本節(jié)主要證明了方案中生成簽名階段的安全性，生成參數(shù)階段和產(chǎn)生密鑰階段的安全性可以通過引用文獻［4］來證明。簽名過程中所有參與方都執(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交互的過程。模擬過程中，一旦A拒絕打開任何承諾，或者零知識證明失敗，或者簽名（r，s）未通過驗證，F(xiàn)都會中止操作。

5.1.1 對隨機份額加密

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

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

5.1.2 計算中間變量 （ρi，σi，δi）

（a）F向SM2簽名預言機詢問m的簽名 （r，s），計算R ＝s（G ＋P） ＋rP ＋m∈Z／qZ，r＝Rx＋e。

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

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

5.2 證明總結(jié)

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

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

6 效率

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

表5 門限SM2和門限ECDSA方案計算量對比

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

表6 不同安全級別下通信開銷對比

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

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

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

7 結(jié)束語

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