UC安全的基于一次签名的广播认证

张俊伟，马建峰，杨力

（西安电子科技大学 计算机网络与信息安全教育部重点实验室，陕西 西安 710071）

1 引言

并发组合是现实网络环境中的实际情形，在孤立模型中证明安全的协议在组合情形下不一定是安全的。因此，在孤立模型中证明协议的安全性还是不够的。UC（universally composable）安全的概念源于由Canetti在2001年提出的基于计算复杂性的UC框架[1]。UC框架主要用于描述和分析并发环境下的协议安全问题。UC框架中最重要的属性是它能够确保协议的UC安全，即在UC框架下证明安全的协议，在与其他协议并发运行的情况下，或者该协议作为一个系统的组件时，仍能保证协议的安全性。理想函数是UC框架中非常重要的安全概念，它扮演着一个不可攻陷的可信第三方的角色，能够完成协议所需的特定功能。UC框架中已经定义了多个最基本的理想函数，如认证消息传输、安全消息传输、密钥交换、公钥加密及签名、承诺、不经意传输[2]等。

Lamport首次提出了一次签名的概念[3]，即使用一对公/私钥对只能对一条消息进行签名。BiBa[4]是第一个高效地适用于低能量设备的一次签名方案。Mitzenmacher和Perrig改进了BiBa并提出了Powerball[5]。然而，BiBa和Powerball仅能在随机预言（RO, random oracle）模型下证明是安全的。Reyzin L和Reyzin N提出了另一个高效的一次签名方案 HORS[6]。HORS的安全性是基于单向函数（one-way functions）和subset-resilient散列函数的。由于 subset-resilient散列函数是一个较强的安全假设，针对HORS出现了一些改进方案：Pieprzyk等设计了一个基于单向函数和cover-free families可证明安全的一次签名方案[7]，但其通信开销和密钥长度都比HORS要大很多，不适合低能量设备。Park和Cho提出了2个一次签名方案[8]：方案1的安全性基于无碰撞散列函数（collision-resistant hash functions）和单向函数，但该方案签名生成的开销较大；而方案2仅是在RO模型下安全的。

基于一次签名的广播认证作为广播认证的一种解决方案具有以下优点[9]：1）计算效率高，一次签名的计算效率比传统的数字签名高，适用于低能量设备；2）即时认证，不存在认证时延，适用于对认证时间敏感的环境；3）不需要时间同步；4）不可否认性。

本文在UC框架下研究了基于一次签名的广播认证的问题。具体贡献如下。1）设计了一次签名的理想函数FOTS，FOTS满足一次签名的安全需求且具有适应性选择消息的不可伪造性（EU-COMA,existential unforgeable against chosen one message attack）。2）改进 HORS，提出了一次签名协议HORS+。基于单向函数和无碰撞散列函数，HORS+能够安全实现理想函数 FOTS。3）构造了广播认证理想函数FBAUTH，在(FOTS，FREG)-混合模型下设计了能够安全实现FBAUTH的协议πBAUTH。4）根据组合定理，组合HORS+，在πBAUTH的基础上构造UC安全的广播认证协议。

文章剩余部分安排如下：第2节简要介绍UC框架的相关概念；第3节设计了一次签名理想函数FOTS和协议HORS+；第 4节提出了广播认证理想函数FBAUTH和协议πBAUTH；第5节是结束语。

2 UC框架

UC框架如图1所示。首先，UC框架定义了现实环境。现实环境描述协议的真实运行情况，其中所有参与方在真实敌手攻击A存在的环境下运行真实协议。其次，UC框架定义了理想环境用来描述密码协议的理想运行。在理想环境下，存在虚拟参与方，理想敌手S和理想函数F。参与方之间以及敌手S与参与方不直接通信；所有参与方和敌手S均与理想函数交互。理想函数本质上是一个不可攻陷的可信角色，用来完成协议所需的理想运行和功能。在UC的安全框架中，环境Z来模拟协议运行的整个外部环境（包括其他并行的协议、攻击者等），Z可以与所有的参与者以及攻击者A和S直接通信，Z不允许直接访问理想函数F。

图1 UC框架

UC仿真[1]。协议 π能够 UC仿真理想函数 F当且仅当对于任意真实敌手 A，存在理想敌手 S，使得任意环境Z，至多以一个可忽略的概率来区分：存在A及协议π的现实环境和存在S及理想函数F的理想环境。如果协议π能够UC仿真理想函数F，称协议π在UC框架下安全实现了理想函数F，也称协议π是UC安全的。

组合定理[1]。如果协议ρ安全实现理想函数F，且 π 是 F-混合模型[1]下的协议，那么协议 πρ/F（用协议ρ替换协议π中的理想函数F所得到的组合协议）UC仿真 F-混合模型下的协议π。特别地，如果协议π在F-混合模型下安全实现理想函数G，那么协议πρ/F也安全实现理想函数G。

通常复杂的协议由多个子协议构成，每个子协议都可以实现某个安全任务。根据组合定理，利用UC安全的协议可以安全构建一个更为复杂的协议，从而实现指定的任务，并保证相应的安全属性。

3 一次签名

3.1 理想函数FOTS

一次签名的理想函数FOTS如下。

Key Generation

当从S收到(KeyGen, sid)后，其中sid = (S, sid’)。

1) 将(KeyGen, sid)发送给敌手。

当从敌手收到(VerificationKey, sid, v’)。

2) 如 果 存 在 记 录 (m’, σ’, v’, 1), 发 送KEY_INVALID给敌手。

3) 否则, 令 v =v’, t=0, 并输出(VerificationKey,sid, v)给 S。

Signature Generation

当从 S收到(Sign, sid, m), 其中 sid=(S, sid’)。

1) 如果 t=1或者 v =⊥, 则发送响应KEY_INVALID。

2) 否则, 发送(Sign, sid, m)给敌手并令t=1。

当从敌手收到(Signature, sid, m, σ), 验证记录(m, σ, v, 0)是否存在:

1) 如果存在, 则令t=0, 输出一个错误信息给S；

2) 否则, 输出(Signature, sid, m, σ)给 S, 并记录(m, σ, v, 1)。

Signature Verification

当从 V 收到(Verify, sid, m, σ, v’), 发送(Verify,sid, m, σ, v’)给敌手。

当从敌手收到(Verified, sid, m, φ):

1) 如果 v’=v且存在记录(m, σ, v, 1), 令 f=1；

2) 否则, 如果 v’=v, 签名者未被攻陷, 且不存在记录(m, σ’, v, 1), 令 f=0 并记录(m, σ, v, 0)；

3) 否则, 如果存在记录(m, σ, v’, f’), 令 f = f’；

4) 否则, 令 f=φ 并记录(m, σ, v’, φ)；

5) 输出(Verified, sid, m, f)给 P。

与传统的数字签名不同，一次签名使用一个公/私钥对只能对一条消息签名。因此，当FOTS收到来自签名者的请求时，FOTS首先验证公钥的正确性。其中，v记录当前的公钥，t表示当前公钥是否被使用。如果不存在公钥或者现有的公钥已经被使用，FOTS不会产生消息的签名。

EU-COMA: 一次签名方案Σ = (gen, sig, ver)，其中gen为密钥生成算法；sig为签名生产算法；ver为签名验证算法。一次签名Σ满足EU-COMA当且仅当对于任意概率多项式时间(PPT, probabilistic polynomial time)的敌手F，在获得一个正确签名(m,σ)后，成功伪造签名(m’, σ’)的概率是可忽略的，即Prob[(m’, σ’)←F(m, σ): ver(m, σ, v)=1; m’≠m; ver(m’,σ’, v)=1] ＜ v(k)。

定理1 一次签名Σ安全实现理想函数FOTS当且仅当一次签名Σ满足EU-COMA。

定理1的证明过程与文献[10]中定理2的证明过程类似，唯一不同的是敌手在一次签名中只能询问一条消息的签名。因此，这里不再赘述。

3.2 一次签名HORS+

HORS的安全性基于强的假设，即散列函数为subset-resilient散列函数[6]。但是，用现有的复杂性理论假设来实现 subset-resilient散列函数仍然是一个公开问题。为了不依赖subset-resilient散列函数，利用单向函数和无碰撞散列函数来构造协议HORS+。单向函数和无碰撞散列函数的定义请参考文献[11]。与HORS不同，在HORS+的密钥生成阶段，签名者计算(x, y=g(x))，将x作为私钥，y作为公钥；在签名生成阶段，签名者将消息与x串联计算散列值，并将x作为签名中的一部分；在签名验证阶段，验证者首先验证x是否为y的原像，然后再计算消息和x的散列值。协议HORS+如下：

安全参数 l, L, k, t

无碰撞散列函数 H: X→Y, L=|Y|=k lb t

单向函数 f, g: X→Y, |X|=|Y|=l

Key Generation

当签名者 S收到(KeyGen, sid), 其中 sid=(S,sid’)。

1) 产生随机数x和t个随机的l-比特串s0, s1,…,st-1, 令 y=g(x)和 vi=f(si) (0≤i≤t-1)。

2) 令 v=(y, v0, v1, … , vt-1), s=(x, s0, s1,…, st-1).将s作为私钥, v作为公钥, 并输出(VerificationKey,sid, v)。

Signature Generation

当签名者 S收到(Sign, sid, m), 其中 sid=(S,sid’)。

1) 计算 h=H(m||x)。

2) 令 h=h1|| h2|| … || hk, ij=hj, 其中|hj|=lb t, 1≤j≤k。

3) σ=(x,si1,si2,…,sik), 输出(Signature, sid, m, σ)。Signature Verification

当验证者 V收到(Verify, sid, m, σ, v), 其中sid=(S, sid’), 令 σ = (x,s1′,s2′, … ,sk′), v = (y, v0,v1, … , vt-1)。如果 y≠g(x)，输出(Verified, sid, m, 0),否则:

1) 计算 h = H(m||x)；

2) 令h=h1|| h2|| … || hk, ij= hj, 其中|hj|=lb t, 1≤j≤k；

3) 如果对于每一个j (1≤j≤k), f(sj′)=vij, 令f=1; 否则, 令 f =0；

4) 输出(Verified, sid, m, f)。

3.3 协议HORS+实现FOTS

定理2 如果f和g是单向函数，H是无碰撞散列函数，那么HORS+满足EU-COMA。

证明 令Setk(x)={x1, x2, … , xk| (x1, x2, … ,xk)=x, |x1|=|x2|=…=|xk|=|x|/k}。 在 HORS+中 ，Setk(σ’) ⊆ Setk(σ)与 Setk(h’) ⊆ Setk(h)等 价 。 令FORGER是伪造签名的攻击者。给定一个合法签名(m, σ)，当敌手 FORGER 成功伪造签名(m’, σ’)时，有以下3种可能的情况。

1) σ’≠ σ 且 Setk(σ’) ⊄ Setk(σ)。 假 定 敌 手FORGER 可以伪造签名(m’, σ’)且满足 σ’≠ σ，Setk(h’)⊄Setk(h)。可以构造敌手 Af求出单向函数 f的逆。假设FORGER能以不可忽略的概率ε1伪造签名。令εf是敌手Af输出z且f(z) = y的概率。可以得到

因此εf也是不可忽略的（通常l至少为80，而2-80是可忽略的），这与单向函数的定义相矛盾，因此，敌手 FORGER成功伪造签名(m’, σ’)的概率是可忽略的。

2) σ’= σ。如果敌手 FORGER可以成功伪造签名(m’, σ)，可以构造敌手AH输出散列函数H的碰撞对。如果敌手FORGER 能以不可忽略的概率ε2成功伪造签名，那么AH输出碰撞对的概率εH为

通常情况下的散列函数，L至少是128，概率2-128是可忽略的，因此εH是不可忽略的。这与无碰撞散列函数的概念相矛盾。由此得出结论，FORGER只能以可忽略的概率伪造签名。

3) σ’≠ σ 且 Setk(σ’)⊆ Setk(σ)。在这种情况下，给定(m, σ)，敌手 FORGER 可以找到 m’满足Setk(h’)⊆ Setk(h)，其中 h = H(m||x)，h’ = H(m’||x’)，y=g(x’)。如果 FORGER找到这样的 m’，可以构造Ag求出单向函数g的原像。如果敌手FORGER成功伪造签名的概率为ε3，则敌手Ag找到单向函数g的原像的概率εg为

需要说明的是(k/t)k可忽略。例如，通常情况下，当|H(x)|=160，k=16，t=1 024，概率为可忽略的2-96。如果ε3是不可忽略的，那么εg也是不可忽略的，这与单向散列函数的定义相矛盾。由此可知，敌手FORGER伪造签名的概率是可忽略的。

综上所述，敌手FORGER伪造签名的概率为

如果f和g为单向函数，H为无碰撞散列函数，那么 εf、εH和 εg都是可忽略的，进而 εFORGER也是可忽略的，即敌手伪造签名的概率是可忽略的。由于篇幅限制，这里的证明省略了 Af、AH和 Ag的详细描述。

因此，HORS+满足EU-COMA。 □

由定理1和定理2，进一步得到定理3。

定理3 如果f和g是单向函数，H为无碰撞散列函数，协议HORS+安全实现理想函数FOTS。

3.4 相关工作比较

表 1将 HORS+与 BiBa、Powerball、HORS以及文献[8]中的2个协议作比较。基于单向函数和无碰撞散列函数，HORS+是可证安全的，HORS+的安全性不依赖于 RO模型。与 HORS相比，HORS+的安全性基于更弱的假设。同时，比较了RO模型下各个方案的安全性，即敌手在RO模型下伪造签名的概率（见表1）。与HORS相比，HORS+在密钥生成和签名验证中增加了一次单向函数的计算，而签名长度和密钥长度增加一个 l bit的 x。

表1 一次签名协议比较

4 UC安全的广播认证协议

4.1 理想函数FBAUTH

广播认证的理想函数保证广播网内的合法用户从未被攻陷的广播者B收到消息m当且仅当B发送了这个广播消息。广播认证的理想函数FBAUTH如下。

当从未被攻陷的B收到(Broadcast, sid, m), 其中 sid=(B, sid’): 发送(Broadcasted, sid, m)给敌手。

当从敌手收到(Broadcast, sid, m’):

1) 如果 B未被攻陷, 给广播网中的所有接受者发送(Broadcasted, sid, m)；

2) 如果B被攻陷且m尚未发送, 给广播网中的所有接受者发送(Broadcasted, sid, m’)。

非机密性：FBAUTH将广播认证消息的内容发送给敌手。因此，FBAUTH不保证消息的机密性。

认证性：如果B（未被攻陷）广播消息m，广播网中的接收者会收到消息m。如果发送者被攻陷且消息尚未发送，敌手可以篡改广播消息。

4.2 广播认证协议πBAUTH

在(FOTS, FREG)-混合模型下，构造了广播认证协议πBAUTH。πBAUTH利用FREG注册签名者的公钥，验证者从FREG获得已注册的公钥（FREG的详细描述见文献[1]）。πBAUTH操作如下。

当收到(Broadcast, sid, m)时, 其中 sid=(B,sid’)。

1) B发送(KeyGen, sid)给FOTS，当从FOTS收到(VerificationKey, sid, v0), 令 v = v0。

2) B发送(Sign, sid, m)给FOTS, 之后从FOTS收到(Signature, sid, m, σ)。

3) B发送(Broadcast, sid, m, σ), 同时, B发送(Register, sid, v)给 FREG。

当收到(Broadcasted, sid, m, σ), 其中 sid=(B,sid’)。

1) 如果v=⊥, R发送(Retrieve, sid)给FREG, 并获得(Retrieve, sid, v’)。如果 v’=⊥或者存在一条记录(m’, v’), R 忽略这条消息; 否则, 令 v=v’。

2) R 发送(Verify, sid, m, σ, v)给 FOTS，随后从FOTS收到(Verified, sid, m, f)。

3) 如果f =1, R记录(m, v)并令v =⊥, 随后R输出(Broadcasted, sid, m)，否则R忽略这条消息。

4.3 协议πBAUTH实现FBAUTH

定理4 协议πBAUTH在(FOTS, FREG)-混合模型下安全实现理想函数FBAUTH。

证明 令A为现实敌手。构造理想敌手S使得对于任意环境 Z只能以可忽略的概率区分：协议πBAUTH及A交互的现实环境和理想函数FBAUTH及S交互的理想环境。

1) 构造S。

Simulating the sender

当未被攻陷的B收到(Broadcast, sid, m)后, S从FBAUTH获得这个值并为A仿真协议πBAUTH。

当从FOTS获得(KeyGen, sid), S发送(KeyGen, sid)给A, 然后将A的响应(VerificationKey, sid, v)转发给FOTS。

2) 当从 FOTS收到(Sign, sid, m)后, 给 A 发送(Sign, sid, m), 并将 A 的响应(Signature, sid, m, σ)转发给FOTS。

3) 当 A 发送(Broadcast, sid, m, σ), S发送(Broadcast, sid, m, σ)。当从 FREG收到(Registered, sid,v), S转发给A。

当已被攻陷的B收到(Broadcast, sid, m)后, S从FBAUTH获得这个值并为A仿真FOTS和FREG。

1) 当从FOTS获得(KeyGen, sid), S发送(KeyGen,sid) 给A, 然后将A的响应(VerificationKey, sid, v0)转发给FOTS。

2) 当从 FOTS收到(Sign, sid, m)后, 给 A 发送(Sign, sid, m), 并将 A 的响应(Signature, sid, m, σ)转发给FOTS。当从FREG收到(Registered, sid, v), 转发给A (v可以不等于v0)。

Simulating the recipient

当A发送(Broadcasted, sid, m, σ)给R时, S为A仿真协议πBAUTH。

1) 如果 v =⊥, 为 A仿真来自 FREG的消息(Retrieve, sid)。当A响应后, 从FREG获得(Retrieve,sid, v’)。如果 v’=⊥或者存在记录(m’, v’), 不做任何行动; 否则令v = v’。

2) 当从FOTS收到(Verify, sid, m, σ, v), 给A发送(Verify, sid, m, σ, v), 随后将A的响应转发给FOTS。

3) 如果 FOTS输出(Verified, sid, m, σ, f = 1)给 R,记录(m, v)并将来自FBAUTH的(Broadcasted, sid, m)发送给R。否则, 不做任何行动。

Simulating party corruption

当A攻陷一个参与方，S也攻陷相应的参与方并将其内部状态提供给A。

IDEAL和REAL不可区分

定义事件P为：对于消息(Broadcasted, sid, m,σ)，当接收者从 FOTS收到(Verified, sid, m, σ, f=1)，而 B在消息传输的时刻尚未被攻陷且从未发送过(Broadcast, sid, m, σ)。然而，根据 FOTS和FREG，事件P不会发生。原因如下：首先，接收者会从 FREG获得一个正确的验证密钥(否则，FOTS不会发送(Verified, sid, m, σ, f = 1))；然后，如果 B未被攻陷且未发送(Broadcasted, sid, m,σ)，那么消息m不会被FOTS签名。因此，R会从FOTS收到(Verified, sid, m, σ, f = 0) (否则，与 FOTS的EU-COMA相矛盾)。

由于事件P不会发生，因此上述仿真是完美的，即 πBAUTH在(FOTS, FREG)-混合模型下安全实现了理想函数FBAUTH。 □

5 结束语

本文在UC框架研究了基于一次签名广播认证协议。首先，设计了一次签名理想函数FOTS并提出了UC安全的一次签名协议HORS+。与HORS相比，HORS+的安全依赖于较弱的安全假设。其次，给出了广播认证理想函数 FBAUTH，在(FOTS, FREG)-混合模型下构造了 UC安全的广播认证协议πBAUTH。根据组合定理，利用HORS+构造的组合协议在 FREG-混合模型下可以安全实现理想函数FBAUTH。

[1] CANETTI R. Universally composable security: a new paradigm for cryptographic protocols[EB/OL]. http://eprint. iacr.org/2000/067.

[2] 李凤华, 冯涛, 马建峰. 基于VSPH的UC不经意传输协议 [J]. 通信学报, 2007, 28(7):28-34.LI F H, FENG T, MA J F. Universally composable oblivious transfer protocol based on VSPH[J]. Journal on Communications, 2007,28(7):28-34.

[3] LAMPORT L. Constructing Digital Signatures From a One-Way Function[R]. Technical Report SRI-CSL-98, SRI International Computer Science Laboratory, 1979.

[4] PERRIG A. The BiBa one-time signature and broadcast authentication protocol[A]. ACM Conference on Computer and Communications Security[C]. 2001. 28-37.

[5] MITZENMACHER M, PERRIG A. Bounds and Improvements for BiBa Signature Schemes[R]. No. TR-02-02, Computer Science Group,Harvard University, USA, 2002.

[6] REYZIN L, REYZIN N. Better than BiBa: short one-time signatures with fast signing and verifying[A]. Information Security and Privacy,7th Australian Conference, ACISP 2002[C]. 2002. 144-153.

[7] PIEPRZYK J, WANG H X, XING C P. Multiple-time signature schemes against adaptive chosen message attacks[A]. Selected Areas in Cryptography, SAC 2003[C]. 2003. 88-100.

[8] PARK Y, CHO Y. Efficient one-time signature schemes for stream authentication[J]. Journal of Information Science and Engineering 22,2006.611-624.

[9] LUK M, PERRIG A, WHILLOCK B. Seven cardinal properties of sensor network broadcast authentication[A]. ACM Workshop on Security of Ad Hoc and Sensor Networks, (SASN’ 06)[C].2006.

[10] CANETTI R. Universally composable signatures, certification, and authenticated communication[A]. Proceedings of 17th Computer Security Foundations Workshop[C]. 2004.

[11] GOLDREICH O. The Foundations of Cryptography[M]. Cambridge University Press, 2001.