基于中国剩余定理的门限可传递签名方案

金 琳， 弓晓锋

（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） 门限可传递签名方案，能够保护用户隐私安全的同时，抵抗伪造签名攻击，提高传递签名的算法效率，解决签名认证安全和效率问题。 本方案在上下级群体决策中有较好的应用前景，如何将本方案更好地应用到分级诊疗系统中将是下一步的研究工作。