基于中國剩余定理的門限可傳遞簽名方案

金 琳， 弓曉鋒

（1 貴州大學計算機科學與技術學院， 貴陽 550025； 2 貴州省科技信息中心， 貴陽 550025）

0 引 言

DESMED［1］最早提出了（t，n） 門限方案，實現只有參與簽名的成員不少于指定的閾值t時，才能生成有效的群簽名；之后，DESMED［2］又提出了一種基于RSA 的（t，n） 門限簽名方案。 SHAMIR［3］提出了基于Lagrang 插值多項式的門限簽名方案。 之后，越來越多的門限簽名方案被相繼提出，并被廣泛應用于實際生活場景中。 但在一些特殊的應用環境中，門限簽名的簽名效率并不理想。 例如，在分級診療系統中，如果上級醫院A 向下級醫院B 發送患者轉診請求，醫院B 接收到患者轉診數據時，則上級醫院A 需要向下級醫院B 證明患者轉診單的有效性及醫院A 身份的準確性，即上級醫院A 必須提供由權威機構T 生成的簽名，以證明醫院A 身份的真實性，確保轉診數據的真實性和完整性。 此外，在PKI 中的證書鏈及電子商務信息傳遞中也有類似的情況。 在這些場景下，傳統簽名認證算法需要對等級下的多個簽名依次進行認證，計算花銷大且認證效率低。

2002 年，Micali 等［4］提出了第一個可傳遞簽名方案MRTS，并將可傳遞簽名的概念形式化。 Bellare等［5］提出了“節點簽名范例”，并分別基于大整數因式分解和RSA 困難性問題，構造了兩種可傳遞簽名方案。 Van Heijist 等［6］提出了一種無向傳遞簽名方案，通過安全性分析證明其無向傳遞簽名可以通過“失敗－停止”簽名方案來實現。 Yi［7］指出了有向樹結構中的有向傳遞簽名方案（DTS－HK），不能抵抗偽造攻擊的問題。 Zhou［8］提出了一種基于因式分解和強RSA 的特定傳遞簽名方案，并證明該傳遞簽名方案在自適應選擇消息攻擊下，滿足傳遞不可偽造性。 Zhu［9］通過引入節點簽名和邊簽名算法，提出了一種具體的無向傳遞簽名方案，在傳遞圖上定義的簽名算法由單獨的頂點簽名算法和邊簽名算法組成，這兩種算法可以共享傳遞圖的狀態信息。 馬春光等［10］提出了兩種無狀態圖結構下的無向可傳遞簽名方案，以解決傳統具有狀態的傳遞簽名方案的計算效率問題。 Neven［11］提出了一種基于有向樹困難問題的簡單高效的可傳遞簽名方案，證明其安全性不依賴任何與RSA 相關的安全假設。 沈忠華等［12］提出了一種基于中國剩余定理的（t，n） 有向門限簽名方案。 Peng 等［13］提出了一種通用可傳遞簽名方案，實現雙線性對、離散對數等困難問題下的可傳遞簽名通用框架。 Zhang 等［14］提出了具有方向狀態函數的傳遞簽名方案，并證明了所提方案在自適應CMA 下是安全的。 Zhu 等［15］提出了一種通用指定的多驗證器傳遞簽名方案，允許傳遞簽名持有者將簽名指定給多重驗證者。 Lin 等［16］提出了一種用于無向圖的無狀態傳遞簽名（TS），并在隨機預言機模型中的M2SDH 假設下，證明該方案對自適應選擇消息攻擊具有傳遞不可偽造性。 Geontae 等［17］提出了第一個基于格的無向圖傳遞簽名方案，并證明其方案在隨機預言模型中是安全的。 之后，Geontae 等［18］提出第一個格下的基于身份的傳遞簽名方案。

可傳遞簽名允許簽名者驗證圖中邊的合法性，即任何人給定公鑰和鄰邊（vi，vj）、 邊（vj，vk） 上的兩個簽名，都可以計算邊（vi，vk） 上的第三個簽名，能夠提高簽名的效率性及安全性，但上述可傳遞簽名方案均不適用于群體決策場景中，無法做到門限簽名傳遞。 本文設計了一種基于中國剩余定理的門限簽名算法，結合門限簽名算法、ELGamal 同態加密和節點簽名范例構造有向圖下的可傳遞簽名方案，實現門限簽名的可傳遞認證，提高簽名效率。 并在EUF－TS－CMA 安全模型下，證明本文所提方案是CMA 安全的，能夠在保護隱私安全的同時，抵抗偽造簽名攻擊。

1 基礎知識

1.1 ElGamal 加密算法

ElGamal 加密算法是一種具有乘法同態的公鑰加密系統。 乘法同態加密能夠直接通過密文相乘，得到相應的明文運算結果，而不需要對密文進行解密。 具體算法如下：

KeyGen（1k） 密鑰生成算法：輸入安全參數k，算法輸出公私鑰對（pk，sk）。 令G是階為q的循環群，g為G的生成元，隨機選擇整數x（1 ≤x≤q －2），計算h＝gxmodq，則公鑰pk＝（G，g，q，h），私鑰sk＝x（保密）。

Enc（pk，m） 加密算法：輸入公鑰pk和明文m，輸出密文C。 隨機選擇整數r，計算E（m）＝ （c1，c2）＝（grmodq，mhrmodq）。

Dec（sk，C） 解密算法：輸入私鑰sk和密文C，算法輸出明文m。 計算可得m＝c2·c1－xmodq。 因其為乘法同態，則滿足E（m1）×E（m2）＝E（m1×m2）。

1.2 中國剩余定理

設m1，m2，…，mk是兩兩互素的正整數，則一次同余方程組

對模M有唯一解

其中，ei滿足

1.3 可傳遞簽名

可傳遞簽名方案由一個算法組（TKG，TSig，TVer，Comp） 和4 個集合（KS，KP，M，S） 組成。 其中，KS是私鑰空間；KP是公鑰空間；M是消息空間；S是簽名空間。 算法描述如下：

TKG（1k） 密鑰生成算法：輸入安全參數k，算法輸出公私鑰對（tpk，tsk）。

TSig（tsk，m） 簽名算法：輸入私鑰tsk和待簽名消息m，算法輸出簽名σ。 對具有可傳遞二元關系的邊和節點進行簽名。

TVer（tpk，m，σ） 驗證算法：輸入公鑰tpk、 被簽名信息m和簽名σ。 如果σ是信息m的有效簽名，算法輸出1，否則輸出0。

Comp（tpk；m1，m2；σ1，σ2） 簽名合成算法：輸入公鑰tpk和被簽名信息m1、m2， 以及簽名σ1、σ2。如果σ1和σ2是有效簽名，則算法輸出合成簽名σ，否則輸出⊥。 將具有傳遞關系的兩個邊簽名合成為一個新的邊簽名。

可傳遞簽名的傳遞性可描述為：已知m1和m2的簽名為σ1和σ2，如果m1⊕m2＝m，則任何人都可以調用合成算法Comp生成一個新的簽名σ＝Comp（tpk；m1，m2；σ1，σ2）， 并且滿足TVer（tpk，m，σ）＝1。

2 安全模型

門限可傳遞簽名方案（Threshold Transitive Signature Scheme，TTSS）的安全模型是適應性選擇門限簽名和選擇消息攻擊下，具有存在性不可偽造性（existential unforgeability against adaptive chosen threshold signature and chosen messages attacks，EUFTS－CMA）游戲。 游戲中包含一個挑戰者和一個敵手，挑戰者模擬系統運行并回答敵手的詢問。 具體游戲過程如下：

（1）系統建立：挑戰者運行系統初始化算法Setup（1κ），將生成的公鑰tpk和群公鑰yU發送給敵手A；

（2）簽名詢問：敵手A可以向挑戰者多項式有界次適應性詢問邊（vi，vj） 的簽名，挑戰者向A返回（vi，vj） 的合法簽名σi，j；

（3）挑戰階段：敵手A偽造簽名GS′＝｛S′，W，R，m｝ ，挑戰者計算u′＝（gS′（yU）RW）modp和Z′＝u′xBmodp來驗證等式R＝h（Z′，W，m）modq是否成立；敵手A偽造邊簽名στ，i←AOTS，OC，OTV1（vτ，vi），挑戰者運行TSig和Comp對其邊進行簽名計算。

（4）當且僅當TVer（tpk，（vi，vk），σi，k） ≠⊥且b＝b′時，游戲輸出“1”；否則游戲輸出“0”。

為便于理解，具體的形式化定義如實驗1 所示：

實驗1

輸入安全參數κ

輸出“0”或“1”

定義1如果對于任意的PPT 敵手A在以上安全模型中輸出“1” 的概率是可忽略的， 即（ε為一個可忽略的概率閾值），則門限可傳遞簽名方案是安全的（CMA）。

3 方案描述

設：U是n個用戶的集合，H是U的子集，H包含t個用戶，有一個可信秘密共享中心（Share Distribution Center，SDC），來生成公共參數和秘密共享。 如果H中的用戶希望為用戶B簽署消息m，則預先約定一個可信任的群簽名生成中心（Designated Combiner，DC），收集H中所有成員的部分簽名，以生成有效群簽名。 在有向圖結構中，每個節點可以看作一個獨立的機構，每個機構有自己的群簽名，將群簽名作為節點簽名的一部分，參與可傳遞簽名算法。 在門限傳遞簽名算法中，當接受者對群簽名認證時，只需驗證一次，且簽名者可以使用邊（vi－1，vi）和（vi，vi＋1） 上的兩個簽名，對邊（vi－1，vi＋1） 進行簽名，在不知道對方私鑰的情況下，實現門限簽名的可傳遞。 如圖1 所示。

圖1 可傳遞簽名Fig. 1 Transitive signature

門限可傳遞簽名方案（TTSS）算法描述如下：

（1）Setup（1κ） →（（tpk，tsk），（xU，yU））： 系統初始化算法，由秘密共享中心SDC 運行，用以確定系統參數、群簽名的公私鑰對（xU，yU） 及傳遞簽名的公私鑰對（tpk，tsk）。

其中，pk為同態加密公鑰；spk為簽名中心的簽名公鑰；sk為同態加密私鑰；ssk為簽名中心的簽名私鑰。 公鑰tpk＝（pk，spk） 對外公開，私鑰tsk＝（sk，ssk） 保密。 算法描述如下：

Setup 算法

輸入安全參數1κ

輸出密鑰對（tpk，tsk） 和（xU，yU）

1 計算（pk，sk） ←KeyGen（1k）

2（spk，ssk） ←Key（1k）

3 SDC 選取整數a（保密）和g（公開）

4 選擇素數p，q及n個整數d1，d2，…，dn，

5 其中p ＞a

6d1＜d2＜... ＜dn

7 對任意的i，gcd（di，p）＝1

8 對i≠j，gcd（di，dj）＝1

9d1d2…dt ＞p dn dn－1…dn－t＋2

10 計算D＝d1d2…dt，即為d1，d2，…，dn中最小的t個di的積

11 選取隨機整數λ，λ∈Z［D／p］， 計算a′＝a＋λp，a′∈ZD

12 設xU＝amodp為U的群密鑰，則SDC 計算群公鑰yU＝gxUmodq

13 SDC 為U中每個用戶計算共享秘密ai（i＝ 1，2，…，n），ai＝a′moddi，i＝1，2，…，n

14 SDC 通過安全信道將（ai，di） 發送至每個成員，ai作為每個成員i的私鑰

（2）SignGen（Ki1，Ki2） →sji： 部分簽名生成算法，由群簽名成員運行該算法，通過各自擁有的共享秘密（ajt，djt），生成對應t個成員各自的部分簽名sji。 算法描述如下：

SignGen 算法

輸入整數Ki1，Ki2∈ZP

輸出部分簽名sji

1 假設U中的t個成員（Uj1，Uj2，…，Ujt構成集合H） 同意為用戶B對消息m進行簽名，其分別擁有共享秘密（aj1，dj1），（aj2，dj2），…，（ajt，djt）

2 用戶B選擇自己的密鑰xB， 然后計算并將yB對H中的所有成員公開

3 每個成員Uji隨機選擇Ki1，Ki2∈ZP

6 計算R＝h（Z，W，m）modp

7 所有成員Uji在H范圍內公開dji，H中每個成員都計算D1＝dj1dj1...djt

9 每個成員計算KSji＝ajiδ′jiδjimodD1，i＝1，2，…，t

10 隨機選取整數Ki1

11 計算各自的部分簽名sji＝（Ki1－ KSji°R）modD1

12 所有成員完成各自的部分簽名后，都將其發送給群簽名生成中心DC

（3）GSignGen（sji） →GS：群簽名生成算法，由DC 運行，通過中國剩余定理生成群簽名GS，并將其發送給用戶B，用戶B可以用自己的私鑰xB判定群簽名的有效性。 算法描述如下：

GSignGen 算法

輸入t個成員的部分簽名sji

輸出群簽名GS

1 DC 收到t個成員的部分簽名sji后，生成群簽名GS＝｛S，W，R，m｝，其中

2 將GS發送給用戶B

3B收到DC 的群簽名GS后計算u＝（gS（yG）RW）modq，Z＝uxBmodq

4R′＝h（Z，W，m）modp

5 若R′＝R，證明生成的群簽名有效

（4）TSig（tsk， （vi，vj），GSi，GSj） →（（li，Σi），（lj，Σj），σi，j）：傳遞簽名生成算法，通過計算生成節點簽名和邊簽名。 其中，Enc為同態加密算法，Sig為標準簽名算法，?為同態映射。 算法描述如下：

TSig 算法

輸入傳遞簽名私鑰tsk， 節點vi，vj， 群簽名GSi，GSj

輸出邊簽名σi，j

1 算法檢測vi，vj∈V， 如果vi?V， 則操作如下：

2 將節點vi加入到V中，隨機選擇li∈Z?N為節點vi的私有標簽

3 計算pli＝Enc（pk，li） 作為節點vi的公共標簽

4 計算節點vi的標準簽名σi＝Sig（ssk，vi‖pli）

5 生成節點vi的證書Σi＝（vi，pli，GSi，σi）

6 同理，如果vj?V，則將節點vj加入到V中，為其生成私有標簽lj、 公共標簽plj及其證書Σj＝（vj，plj，GSj，σj）

7 輸出邊（vi，vj） 的簽名σi，j＝（Σi，Σj，δi，j），其中

（5）Comp（（vi，vj），（vj，vk）；σi，j，σj，k） →σi，k：邊簽名合成算法，輸入邊（vi，vj） 的簽名σi，j和邊（vj，vk） 的簽名σj，k。 其中，邊（vi，vj） 和邊（vj，vk）是具有傳遞關系的兩條邊。 算法描述如下：

Comp 算法

輸入邊（vi，vj），（vj，vk） 及邊簽名σi，j，σj，k

輸出合成邊簽名σi，k

1 計算δi，k＝?（li，lk）＝?（li，lj） °?（lj，lk）＝δi，j°δj，k

2σi，k＝（Σi，Σk，δi，k）

3 即Comp（（vi，vj），（vj，vk）；σi，j，σj，k） →σi，k

（6）TVer（tpk，（vi，vj），σi，j） →｛0，1｝： 簽名驗證算法，輸入tpk， 節點vi、vj及邊簽名σi，j， 用來驗證節點簽名及邊簽名的合法性。 算法描述如下：

TVer 算法

輸入公鑰tpk，節點vi，vj及邊簽名σi，j

輸出“1”或“0”

1 驗證節點vi，vj的證書Σi和Σj的合法性

3 其中，li°＝?（li，lj）

4 若以上驗證都通過，則算法輸出“1”，否則輸出“0”

5 即TVer（tpk，（vi，vj），σi，j） →｛0，1｝

其中，HE＝（KeyGen，Enc，Dec） 為IND－CPA 安全的同態加密方案，SG＝（Key，Sig，Ver） 是CMA 安全的標準簽名方案，消息運算符記為“°”，密文運算符記為“?”，消息x的逆為x－1。

4 方案分析

4.1 正確性分析

由于t個成員Uj1，Uj2，…，Ujt分別擁有共享秘密（aj1，dj1），（aj2，dj2），…，（ajt，djt）， 且滿足以下同余式：

已知gcd（dji，djk）＝1，ji≠jk，根據中國剩余定理可知，同余方程有唯一解

則

故

4.2 安全性分析

定理1若DLP 是困難的，則該方案具有隱私保護性。

證明已知yU＝gxUmodq， 若敵手A想要通過群公鑰yU來獲取群密鑰xU， 其難度相當于求解離散對數，而且敵手A想要通過di來獲取每個成員的密鑰ai是不可能的。 因為ai≡a′moddi，在此同余方程中a′為SDC 秘密保留， 故只通過di想要從同余方程ai≡a′moddi中解得ai是不可能的。 在部分簽名的生成階段， 敵手A不可能獲取整數Ki1、共享密鑰ai和部分簽名sji。 因為sji＝（Ki1－ KSji°R）modD1，其中KSji＝ajiδ′jiδjimodD1，敵手A無法得到sji、Ki1和ai，故無法確定同余方程的解。 在群簽名產生過程中，群簽名中心DC 只知道每個成員的部分簽名sji， 則敵手A不可能通過同余式sji＝（Ki1－KSji°R）modD1獲得ai和xU等其他信息。

綜上，該方案具有隱私保護性。

定理2若門限可傳遞簽名方案EUF－TS－CMA安全，則該方案可以抵抗偽造簽名攻擊。

證明根據門限可傳遞簽名算法滿足EUF－TS－CMA 可知，即便多項式時間敵手A偽造簽名GS′＝｛S′，W，R，m｝ 給用戶B，用戶B可以通過計算u′＝（gS′（yU）RW）modp和Z′＝u′xBmodp來驗證等式R＝h（Z′，W，m）modq是否成立，來判斷簽名的真實性。故敵手A不能為自己選定的消息偽造一個合法的簽名，故該方案能夠抵抗偽造簽名攻擊。

定理3少于t個成員是無法獲知系統的關鍵參數a′，進而敵手A無法知道群密鑰。

證明假設敵手A知道t －1 個成員的共享秘密（aj1，dj1），（aj2，dj2），…，（ajt－1，djt－1）， 就可能知道a′關于模D2＝dj1dj2...djt－1有唯一解x。 但由于D＝d1d2…dt為最小的t個di的乘積，所以D／p大于任意一個t －1 個di之積，因此D／D2＞p，又gcd（p，D2）＝1，使得x≤D和x≡a′modD2的整數a′在模p的所有同余類上均勻地分布，故敵手A就無法獲得足夠的信息去確定a′，進而無法確定群密鑰xU。

定理4若方案TTSS 是CMA 安全性的，當且僅當同態加密方案是IND－CPA 安全的，且簽名方案SG 是適應性CMA 安全的。

證明在方案攻擊實驗中，允許任意PPT 敵手A選擇任意消息的請求，其在多項式時間內產生與現有有效簽名不同簽名的概率可以忽略不計，即敵手A的攻擊優勢是可忽略的，其成功率為

Pr［（ATSig（κ，）＝（vτ，Σ′τ，σ′τ，κ）） ∧vτ?V∧（TVer（tpk，vτ，Στ，στ，κ）＝1） ∧στ，κ?Span｛σi，j｝］

其中， ｛m1，m2，…，mn｝ 為已簽名消息集；κ為安全參數；ATSig（κ，）＝（m，σm） 表示敵手A把TSig作為預言機訪問產生簽名（m，σm）。

定義敵手在CMA 安全性概念下攻破TTSS 的成功率為：在IND－CPA 安全性概念下攻破同態加密HE 的優勢為：在適應性CMA 安全性概念下攻破SG 的成功率為：

實驗2

輸入安全參數κ

輸出“0”或“1”

1 （tpk，tsk） ←Key（1k）

實驗3

輸入安全參數κ

輸出“0”或“1”

1c←AOE1（m）

2b←｛0，1｝

3cb←Enc（pk，mb）

4b′←AOE1（sk，cb，m0，m1）

5 如果b＝b′返回“1”；否則返回“0”

采用反證法證明該安全性定理。 首先假設TTSS 滿足CMA 安全性，但HE 不滿足CPA 安全性，且SG 不滿足IND－CMA 安全性。 構造算法A以不可忽略概率攻破方案TTSS。

即TTSS 不滿足CMA 安全，與假設矛盾。 故方案TTSS 滿足CMA 安全性一定有HE 滿足CPA 安全性，且SG 滿足IND－CMA 安全性。 反之，假設HE滿足CPA 安全性，且SG 滿足IND－CMA 安全性，但TTSS 不滿足CMA 安全性。

由于TTSS 不滿足CMA 安全，則存在一個敵手算法A在多項式時間內攻破TTSS 的成功率不可忽略，即（ε是不可忽略的概率）。

可知，若σi，j，σj，k∈Span｛σi，j｝， 則TSig（tsk，（vi，vk）） →（（li，Σi），（lk，Σk），σi，k） 與Comp（（vi，vj），（vj，vk）；σi，j，σj，k） →σi，k是不可區分的。

故HE 不滿足CPA 安全性，且SG 不滿足INDCMA 安全性，與假設矛盾。

綜上所述，方案TTSS 是CMA 安全性的，當且僅當同態加密方案是IND－CPA 安全的，且簽名方案SG 是適應性CMA 安全的。

4.3 性能分析

將本文方案與方案MRTS［4］、RSATS［14］在簽名開銷、驗證開銷、簽名合成開銷等方面進行分析比對，其結果見表1。 表1 中，ops為比特運算量；Te為一次求冪運算時間；H.為同態加密算法；Tm為一次求加／差／積運算時間；TS.為標準簽名方案；Tp為一次雙線性對運算時間；G為q階有限群。

表1 性能對比分析Tab. 1 Performance comparison analysis

根據表1 可知，所提方案TTSS 中，簽名開銷較之前沒有明顯降低，但簽名驗證開銷和簽名合成效率都有很大提高。 總體上，本方案在性能方面具有一定優勢。

5 結束語

在多簽名場景中，傳統簽名認證需要對多個簽名進行逐個認證，而且簽名長度與簽名者人數有關，計算花銷大且認證效率低。 針對以上問題，本文提出了一種門限可傳遞簽名方案。 通過引入中國剩余定理、ELGamal 公鑰密碼理論，并結合“節點簽名范例”構造有向圖結構下的（t，n） 門限可傳遞簽名方案，能夠保護用戶隱私安全的同時，抵抗偽造簽名攻擊，提高傳遞簽名的算法效率，解決簽名認證安全和效率問題。 本方案在上下級群體決策中有較好的應用前景，如何將本方案更好地應用到分級診療系統中將是下一步的研究工作。