网络编码中的椭圆曲线多重签名方案*

杨文山

（格尔软件股份有限公司，上海 201112）

0 引 言

网络编码是兼具路由和编码功能的信息通信技术，其优点为信息吞吐量大和鲁棒性强。如果节点以某种方式对消息进行编码后转发，这种网络结构可以获得理论中最大的传输效率。当前，研究人员一直比较关注网络编码安全问题，并设计出一系列防污染/窃听的网络编码签名方案[1-11]。重签名允许多个用户对同样的消息进行签名，每个用户对收到的消息进行部分签名，然后交给签名收集者形成最终签名。

目前没有任何基于椭圆曲线的网络编码多重签名。如何设计安全高效的网络编码多重签名是一个值得研究的问题。基于此，本文设计了防御污染/伪造的网络编码中的椭圆曲线多重签名方案（NC-ECMSS）。每个源节点为消息生成一个有序的多重签名，中间节点对接收的信息进行线性组合。NC-ECMSS 具有抗污染攻击和伪造攻击的特性，而且比起现有技术而言，其验证效率较高、计算复杂度较低。

1 基础知识

1.1 ECDL 问题

椭圆曲线离散对数（Elliptic Curve Discrete Logarithm，ECDL）问题，给定椭圆曲线E和椭圆曲线点X=aG，ECDL 问题是指找到一个正整数a∈，使之满足X=aG在计算上是不可行的。

1.2 多源网络编码知识

2 形式化定义

2.1 算法定义

NC-ECMSS 包含以下6 个概率多项式时间算法。

（1）参数生成算法：输入安全参数μ，输出系统主密钥x和系统公开参数λ。

（2）部分私钥生成算法：输入λ，x，IDi，输出部分私钥di，其中IDi代表用户身份。

（3）密钥生成算法：输入IDi，输出该用户的秘密值δi、公钥yi。

（4）多重签名算法：输入消息向量vi，λ，IDi，di，δi，L，用户IDi(1≤i≤n)验证上个用户IDi-1传来的部分签名σi-1后，输出其部分签名σi，其中L是签名顺序。

（5）组合签名算法：输入消息向量(w1,w2,wl)，输出组合后消息向量w和对应的组合签名σ。

（6）验证算法：输入λ，IDi，yi，vi，σ，如果验证等式成立，接受签名；否则，输出⊥。

2.2 安全模型

防御污染/伪造的网络编码中的椭圆曲线多重签名方案（NC-ECMSS）满足适应性选择消息攻击下的不可伪造性安全性（UF-CMA）。通过挑战者C 与敌手 A1（A2）之间的实验游戏G1（G2）来描述NC-ECMSS 的UF-CMA 安全模型。首先，通过发生器生成两个敌手，，其中，敌手A1模拟的是恶意的密钥生成中心（Key Generation Center，KGC），敌手A2模拟的是不诚实用户，A1不知道主密钥，但能替换任意用户的公钥；A2知道主密钥，但无法更换任意用户公钥。然后，A1（A2）发出一系列适应性询问，详见式（1）。

最后，由 A1（A2）输出一个伪造签名，在询问中，A1不会询问用户的完整私钥，A2也不能询问用户的私钥，伪造的签名不会是任何多重签名谕言机输出的。如果签名验证等式通过，则 A1（A2）在G1（G2）中获胜，反之，则失败。

不可伪造性。如果没有多项式时间敌手A1（A2）在游戏实验G1（G2）中以不可忽略的优势成功，则称防御污染/伪造的网络编码中的椭圆曲线多重签名方案（NC-ECMSS）满足适应性选择消息攻击下的不可伪造性安全性（UFCMA）。

3 方案实例

3.1 参数生成算法

给定μ比特大素数p、椭圆曲线E，定义Gp为加法循环群，G为具有素阶q的椭圆曲线的基点和群Gp的生成元，KGC 随机选取x∈ [1,q]，计算系统公钥ypub=xG。KGC 选择安全的哈希函数为H0: {0,1}t×Gp→，H1: {0,1}*→，H2: {0,1}*→。最后，KGC保密主控钥但公开系统参数为：

3.2 部分私钥生成算法

3.3 密钥生成算法

3.4 签名算法

定义第n个用户Nn对消息vi的有序多重签名为。当第n个用户对消息vi的有序多重签名完成后，将最终的签名发送给中间节点和目的节点，中间节点对消息进行线性组合。

3.5 组合算法

3.6 验证算法

4 正确性论证

4.1 单个签名的验证

计算出单个签名的验证过程如下：

4.2 组合签名的验证

5 安全性分析

定理1：在随机谕言模型下，NC-ECMSS 针对外部敌手 A1是存在性不可伪造的。

证明：假设(G,aG)是椭圆曲线离散对数ECDL 问题的实例，挑战者Γ 的任务是利用A1确定一个正整数a∈的值。挑战者Γ 需要维护初始时都为空的列表list-1，list-2，list-3，list-4，以存储针对相应谕言机的询问-应答值。IDγ为挑战者身份，其中γ∈ (1,2,…,l)是一个正整数，l为询问H0谕言机的次数。挑战者Γ 首先运行参数生成算法得到系统参数λ（ypub=aG），输出λ给A1。然后，A1执行以下多项式有界次适应性询问。

（6）秘密值询问：A1询问IDi的秘密值。如果对应公钥未被替换，则Γ 查询列表list-4 并输出δi给 A1。

（7）公钥替换询问：A1询问IDi的公钥替换询问。如果IDi=IDγ，则Γ 终止游戏；否则，Γ 选取yi∈Gp替换IDi的公钥，并用(IDi,-,y i,Ri,di)更新列表list-4。

最后，A1输出一个伪造签名σ。在询问过程中，A1不能询问用户IDi的完整私钥，签名谕言机不返回σ*。如果≠IDγ，则Γ 终止游戏；否则，Γ 伪造另一个签名σ**。则有：

Γ 调用相关谕言机，利用分叉引理计算得出ECDL 问题实例解答：

评估Γ 取得成功的概率。令E1表示Γ 不终止游戏的概率；E2表示 A1成功伪造一个签名的概率；E3表示在成功伪造一个签名的情况下至少存在一条与非目标身份有关的记录。如果这3个事件全部发生，则Γ 取得成功。事件E1存在一次及以上没有对目标身份进行部分私钥询问的概率是 Pr[E1] ≥ 1/(ls+l x+lr)（ls为询问秘密值的次数，lx为询问部分私钥的次数，lr为公钥替换的次数）；事件E2表示 A1成功伪造一个签名的概率是 Pr[E1|E2]≥ε；事件E3表示在n次重复询问中，该事件出现一次及以上的概率是Pr [E3|E1∩E2]≥1 /n。因此，解决ECDL 问题的成功概率为：

定理2：在随机谕言模型下，NC-ECMSS 针对外部敌手A2是存在性不可伪造的。

证明：假设(G,aG)是ECDL 问题的实例，挑战者Γ 的任务是利用A2确定一个正整数a∈的值。挑战者Γ 需要维护初始时都为空的列表list-1，list-2，list-3，list-4，以存储针对相应谕言机的询问-应答值。IDγ为挑战者身份，其中γ∈ (1,2,…,l)是一个正整数，l为询问H0谕言机的次数。挑战者Γ 首先运行参数生成算法得到系统参数λ（ypub=xG），输出λ给A2。然后，A2执行以下多项式有界次适应性询问，其中哈希询问与定理1 相同，这里不再赘述。

（1）公钥询问：A2询问IDi的公钥。Γ 选取δi∈R，输出yi=δiG，添加 (IDi,δi,yi,-,-)到列表list-4 中。

（2）部分私钥询问：A2询问IDi的部分私钥。如果IDi=IDγ，则Γ 终止游戏；否则，Γ 选取ri∈R，设置Ri=aG，计算di，使得d i=Ri+xH iG，输出di给A2，并用(IDi,δi,yi,Ri,di)更新列表list-4，其中1≤i≤n，，Hi源自列表list-1。

（3）秘密值询问：A2询问IDi的秘密值。如果IDi=IDγ，则Γ 终止游戏；否则，Γ 查询list-4 并输出δi给A2。

最后，A1输出一个伪造签名σ。在询问过程中，A2不能询问用户IDi的完整私钥，签名谕言机不返回σ。如果≠IDγ，则Γ 终止游戏；否则，Γ 伪造另一个签名σ*。则有：

Γ 调用相关谕言机，利用分叉引理计算得出ECDL 问题实例解答：

评估Γ 取得成功的概率。令E1表示Γ 不终止游戏的概率；E2表示 A1成功伪造一个签名的概率；E3表示在成功伪造一个签名的情况下至少存在一条与非目标身份有关的记录。如果这3 个事件全部发生，则Γ 取得成功。事件E1存在一次及以上没有对目标身份进行部分私钥询问的概率是 Pr[E1] ≥ 1/(ls+l x+lr)（ls为询问秘密值的次数）；事件E2表示 A1在游戏中获胜的概率是 Pr[E1|E2]≥ε；事件E3表示在n次重复询问中，该事件出现一次及以上的概率是Pr [E3|E1∩E2]≥1 /n。因此，解决ECCDH 问题的成功概率为：

定理3：在多源网络编码环境下，防御污染/伪造的网络编码中的椭圆曲线多重签名方案（NC-ECMSS）能抵抗污染攻击。

在NC-ECMSS 中，如果敌手想要伪造多重签名，需要知道签名人的私钥，而私钥的破解是非常困难的。

为了防止网络中的污染攻击，NC-ECMSS利用同态哈希函数的安全性和ECDL 问题的难解性，解决签名过程发生在源节点处和中间节点处。对于源节点处，敌手可以捕获网络中的任何节点并利用它发起攻击。如果在此节点发送污染的信息或伪造签名给下一个节点，那么敌手通过签名者公钥计算签名者私钥的行为相当于解决了ECDL 问题。对于中间节点处，敌手可以捕获源节点发送的完整签名伪造多重签名，只要破解出每个签名者的私钥和随机数，同样相当于解决了ECDL问题。解决ECDL 问题在计算上是不可行的，因此CL-NCBMS 能够抗多源网络编码环境下的污染攻击。

6 效率分析

本节对NC-CLMSS 的计算效率进行分析。实验设备使用Lenovo v310-15-ISK，Windows 10 系统，2.5 GHz CPU、8 G 内存。仿真平台为MATLAB2016a。主要的密码操作在系统中的计算开销如表1 所示。签名、验证阶段性能比较如表2 所示。总体而言，NC-CLMSS 具有相对较小的计算复杂度。

表1 计算耗时比较

表2 计算效率比较

7 结 语

本文利用同态哈希安全性和椭圆曲线离散对数ECDL 问题设计了防御污染/伪造的网络编码中的椭圆曲线多重签名方案（NC-ECMSS），其具有抗污染攻击和伪造攻击的特性，且验证效率更高，计算复杂度更低。在随机谕言模型下，证明NC-ECMSS 满足适应性选择消息攻击下的不可伪造性安全性，但其安全性仍需进一步研究如何在不利用谕言模型的情况下，实现适应性随机消息攻击下的不可伪造性，构造出多播网络的一系列防污染/窃听的网络编码签名方案。