无双线性对的网络编码无证书签密

俞惠芳杨 柯

(西安邮电大学网络空间安全学院 西安 710121)

1 引言

网络编码[1,2]是一种数据路由方法。不同于传统路由机制，网络编码允许中间节点在传输数据包之前对其进行编码。这种做法可让网络达到最大流最小割定理所规定的最大吞吐量。网络编码实际应用中的污染问题较为严重，如果网络节点未检测出被污染的数据包直接编码转发，会导致污染多个节点甚至整个网络。RSA同态签名[3]能应对污染攻击和代间重放攻击。有双线性对的同态签名[4]使用了组合签名和相应节点的公钥来验证组合数据包，能抗污染攻击。

无证书公钥密码体制由用户和密钥生成中心(Key Generation Center,KGC)合作生成用户完整私钥，解决了证书管理和密钥托管。无证书公钥体制与签密体制相结合形成无证书签密(Certificate-Less SignCryption,CLSC)，首个CLSC[5]不能防止伪造攻击。目前大部分CLSC都采用了双线性对运算，双线性对的运算复杂性高。因此，Selvi等人[6]提出安全的无对运算的CLSC。现有没有使用双线性映射的无证书签密[7—9]不适合直接用在网络编码环境中。

无证书的网络编码同态签名[10,11]可摆脱繁琐的证书管理和对公钥基础设施的严重依赖，同时具有抗污染攻击的特性。为了获得更低的计算复杂度，本文构建可证安全的不使用双线性对的网络编码无证书签密(CertificateLess Pairing-Free SignCryption for Network Coding,NC-CLPFSC)，这是一个多源的网络编码方法，避免了证书的管理和密钥的托管，没有双线性对运算使计算效率有所提高，同时通过同态哈希函数具备防御污染攻击能力。

2 基础知识

2.1 网络编码模型

网络编码模型按源节点个数分成单源节点的单源网络编码和多源节点的多源网络编码。多源网络编码模型用无环多重图G=(E,M)表示，E是边集，M是点集。S={s1,s2,···,sm}∈M表示源节点，T={t1,t2,···,tm}∈M表示目的节点。图1展示网络中信息流沿一个方向从源节点流向非源节点。

图1 多源网络传输模型

每个消息Vi∈{V1,V2,···,Vm}由有限域F中n个元素组成，表示为Vi={vi,1,vi,2,···,vi,m}。每个中

Ho等人[12]描述的随机线性网络编码允许选择用于执行分组的线性组合的编码系数。在随机线性网络编码中，源节点将m维消息向量Vi扩展为m+n维，给每个消息向量添加一个规范向量。扩展后消息向量表示为

2.2 困难问题

计算性D iffie-Hellm an(Com pu tational D iffie-Hellman,CDH)问题：给定大素数阶q的乘法群G,g表示群G的任意生成元，已知(g,ga,gb)∈G，对任意未知的a,b∈,CDH问题的目标是计算

离散对数(Discrete Logari thm,DL)问题：给定大素数阶q的乘法群G,g表示群G的任意生成元，已知∈G,DL问题的目标是计算

3 具体方案

3.1 系统初始化

乘法循环群G的阶为大素数q,g是G的一个生成元。密钥生成中心(Key Generation Cen ter,KGC)选择安全的哈希函数

其中，l1表示任意身份的长度，l2表示签名的验证标识符id长度，l3表示任意消息长度。KGC随机选取主公钥s∈，并计算系统的公钥Ypub=gs∈G。公开系统的全局参数φ={q,G,g,Ypub,H1,H2,H3,ID,M}，其中ID是身份空间，M是明文消息空间。

3.2 密钥生成

(1)源节点用户si选取任意的di∈，计算Y i=g d i，其中Yi是公开的，随机值di是保密的。

(2)K G C 随机选取ri∈，分别计算N i=g r i∈G(Ni是公开的)，h1i=H1(IDi,N i,Y i),t i=(r i+sh1i)modq，KGC发送ti给源节点用户。源节点用户使用公式进行验证。如果验证通过，说明Yi是源节点用户的公钥，相应的私钥是(ti,di)。

3.3 签密

给定源节点用户身份信息IDs。源节点用户发送消息向量vi的密文给目的节点。每个源节点用户在发送消息时都会附上一个消息标识符id作为整个数据包的一部分而发送到下游节点，下游节点能根据对应的id确定出收到的签名是由哪一个节点发送的，从而达到确定出污染节点位置信息的目的。签密操作如下：

3.4 组合

3.5 解签密

4 正确性分析

(1)解密阶段正确性分析

(2)单个数据包签名验证正确性分析

(3)组合验证

5 安全性分析

NC-CLPFSC易受到AI和AII两类敌手的攻击。外部攻击者AI可更改任何用户的公钥，却无法得知系统主密钥；内部攻击者AII掌握系统的主密钥，却不能修改任何用户的公钥。注意不允许相同身份的询问。

定理1(AI攻击下的机密性)如果AI能攻破NC-CLPFSC的保密性，则必然存在算法C能解决CDH问题。

证明 假设C是解决CDH问题实例＜g,ga,gb＞的挑战者，a,b∈对于C和AI是未知的，C的目标在于计算gab∈G。AI在游戏中扮演C的子程序。C从q(对H1的询问次数)个身份中选择挑战身份IDt，＜IDt,t＞对AI是未知的。C维护起初为空的列表＜L1,L2,L3,L4,LK＞。

C首先输出运行设置算法得到的φ=＜ q,G,g,Ypub=gb,H1,H2,H3,ID,M ＞。然后，AI在阶段1执行一系列适应性询问。

H2询问：C收到AI对H2的询问时，C检查L2中是否存在＜id,vi,h2i＞。如果存在，C返回h2i给AI；否则，C返回任意选取的h2i∈，储存＜id,vi,h2i＞到L2中。

H3询问：C收到AI对H3的询问时，C检查L3中

挑战：阶段1结束时，AI生成两个等长vi0,vi1∈M和身份IDs,IDr(IDs,IDr表示源节点用户和目的节点用户的身份信息)。在阶段1中IDr的完整私钥不能询问。如果IDr≠IDt，C放弃游戏；否则，C调用H1谕言机和公钥谕言机分别获得＜Ys,Yr＞和＜ts,ds＞，然后计算得到挑战密文σ*：

AI在阶段2发出与阶段1相同的询问。AI不能询问IDr的私钥也不能对(σ*,c*,R*)执行解签密询问。L2存储的元组中存在一个元组含有CDH问题实例的解答。最后，C输出CDH问题实例的解答

在概率分析中e 表示自然对数底，qs是询问私钥的次数，qp是询问部分私钥的次数，qr是替换公钥的次数，q3是询问H3的次数，ε1表示AI攻破NCCLPFSC保密性的概率。根据文献[13]方法可得，C在游戏中获得CDH问题实例解答的概率是证毕

定理2(AII攻击下的机密性)如果AII能攻破NC-CLPFSC的保密性，则必定存在算法能解决CDH问题。

证明 假设C是解决CDH问题实例＜g,ga,gb＞的挑战者，a,b∈对于C和AII是未知的，C的目标在于计算gab∈G。AII在游戏中扮演C的子程序。C从q(对H1的询问次数)个身份中选择挑战身份IDt，＜IDt,t＞对AII是未知的。C维护起初为空的列表＜L1,L2,L3,L4,LK＞。

C首先输出运行设置算法得到的＜φ,s＞给AII。然后，AII执行多项式有界次适应性询问。H2,H3询问与定理1相同，故略去。

公钥询问：AII询问身份IDi的公钥。如果IDi=IDt，C设置Y i=g b,N i=g r i(ri∈)。C返回公钥Yi给AII，添加＜IDi,ri,*,*,Ni,Yi＞到LK中；否则，C选择＜ri,di＞∈Zq*，计算Y i=g d i,N i=g r i，返回Yi给AII，添加＜IDi,ri,di,*,Ni,Yi＞到LK中。

H1询问：C收到AII对H1的询问时，C检查L1中是否存在元组＜IDi,Ni,Yi,h1i＞。如果存在，C返回h1i给AII；否则，C调用公钥谕言机，返回相应的h1i给AII，储存＜IDi,Ni,Yi,h1i＞在L1中。

部分私钥询问：收到身份IDi的私钥询问时，C从L1找到h1i，AII掌握主密钥s，自行计算出部分私钥，使用＜IDi,ri,di,ti,Ni,Yi＞更新LK。

私钥询问：收到身份IDi的私钥生成询问时，C检查是否IDi=IDt。如果相等，C终止游戏；否则，C从LK中获得元组＜IDi,ri,di,ti,Ni,Yi＞，返回完整的私钥＜ti,di＞给AII。

签密询问：C收到元组＜IDs,IDr,vi＞的签密询问。如果IDs≠IDt，C通过签密算法返回密文给AII；否则，C执行下述操作：

挑战：阶段1 结束时，AII生成等长vi0,vi1∈M和身份IDs,IDr(IDs,IDr分别是源节点用户和目的节点用户的身份信息)。阶段1中IDr不能询问。如果IDr≠IDt，C放弃游戏；否则，C调用H1谕言机和公钥提取算法分别获得＜Ys,Yr＞和＜ts,ds＞，然后通过计算得到挑战密文σ*：

AII在阶段2发出与阶段1相同的询问。AII不能询问IDr的秘密值也不能对(σ*,c*,R*)进行解签密询问。

L2存储的元组中存在一个元组含有CDH问题实例的解答。C从L中随机选择＜id,vi,h2＞，输出为C D H 问题的解答

在概率分析中e表示自然对数底，qs表示询问私钥的次数，q3表示询问H3的次数，ε1表示AII攻破NC-CLPFSC保密性的概率。由定理1可得，C在游戏中未终止且C解决CDH问题的概率是：e—1ε1/q3qs。证毕

5.1 不可伪造性

定理3(AI攻击下的不可伪造性)如果AI能攻破NC-CLPFSC的不可伪造性，则必定存在算法C能解决DL问题。

证明 假设C是解决DL问题实例＜g,gb＞的挑战者，其目的在于计算b∈。AI在游戏中扮演C的子程序。C从q1个身份中选择第t个身份作为挑战身份IDt，＜IDt,t＞对AI是未知的。C维护起初为空的列表＜L1,L2,L3,L4,LK＞。

C首先输出运行设置算法得到的φ=＜q,G,g,Ypub=gb,H1,H2,H3,ID,M＞。然后，AI进行和定理1的阶段1完全相同的多项式有界次适应性询问。

伪造：阶段1询问结束时，AI输出伪造密文。AI无法得知IDt的私钥，IDt的部分私钥不能提取且其公钥不能替换，AI不能对伪造密文发出解签密询问。如果IDt≠IDi，C失败。根据分叉引理，AI通过生成另一个伪造密文。如果C成功，则式(14)成立

根据式(14)，C输出D L问题实例解答b=

如果C在游戏过程中没有终止且AI以概率ε1攻破NC-CLPFSC的不可伪造性，则根据定理1可得，C解决DL问题的优势是：e—1ε1/(qs+qp+qr)。证毕

定理4(AII攻击下的不可伪造性)若AII能攻破NC-CLPFSC的不可伪造性，则必定存在算法C能解决DL问题。

证明 假设C是解决DL问题实例＜g,gb＞的挑战者，其目标在于计算b∈。AII在游戏中扮演C的子程序。C从q1个身份中选择第t个身份作为挑战身份IDt，＜IDt,t＞对AII是未知的。C维护起初为空的列表＜L1,L2,L3,L4,LK＞。

C首先输出运行设置算法得到的＜φ,s＞给AII。然后AII执行和定理2的阶段1完全相同的多项式有界次适应性询问。

伪造：经过上述询问时，AII输出伪造密文。IDt的私钥不能提取且AII不能对伪造密文发出解签密询问。如果IDt≠IDi，C失败；否则，根据分叉引理，AII生成另一个伪造密文。如果C成功，则式(15)成立

根据式(15)，C输出D L问题实例解答b=

如果AII以概率ε1攻破NC-CLPFSC的不可伪造性，则根据定理3可得C解决DL问题的优势是：e—1ε1/qs。证毕

5.2 抗污染攻击

定理5 NC-CLPFSC能有效防御多源网络编码环境下的污染攻击。

证明 如果攻击者试图伪造一个密文，就必须得解决离散对数问题获得签密私钥，然而成功求解离散对数问题的概率几乎可忽略。如果攻击者想要伪造一个有效密文，攻击者需要伪造秘密值对消息签密。从Ri得到秘密值ui等价于解决离散对数困难问题。因此，敌手不可能获得有效密文。综上，NCCLPFSC具有抗污染特性。

6 性能分析

本节依据计算效率比较NC-CLPFSC与文献[14—16]的方案。

表1描述使用软件VC++调用基于双线性对的密码学库(Pairing-Based C ryp tography library,PBC)获得的各种密码操作的平均计算时间。表2主要描述4种方案在各个阶段的耗时比较。表3主要描述4种方案总耗时比较。

表1 各密码操作的计算时间(m s)

表2 分段耗时比较(m s)

表3 总耗时比较(m s)

做仿真实验的计算机的主要性能参数：W in10操作系统，CPU 1.60 GHz，内存16 GB。Origin工具绘制仿真实验结果图。图2—图5中横坐标表示消息向量维度，纵坐标表示计算消耗时长。伴随着消息向量维度的增多，在各阶段、整体方案的计算消耗时增长相对比较缓慢，这说明NC-CLPFSC计算开销更小。

图2 系统初始化及密钥生成耗时比较

图3 签密耗时比较

图4 解签密耗时比较

图5 总耗时比较

7 结束语

多源网络编码环境下不使用双线性对的无证书签密(NC-CLPFSC)的安全证明中，挑战者用1次成功伪造不足以解决困难问题，需要两个及以上特定关系的成功伪造才能攻破难题，此情况下需要使用分叉引理进行安全性证明，因而NC-CLPFSC在不可伪造性证明过程中使用了分叉引理。

NC-CLPFSC支持节点间处理数据，是很好的网络路由解决方案。NC-CLPFSC在计算D iffie-Hellman问题和离散对数问题的困难假设下可保证消息的机密性、不可伪造性和不可污染等安全属性。从仿真实验结果得出NC-CLPFSC的计算开销更低。