抗代内/间攻击的同态签名方法

摘要

本发明公开了一种抗代内/间攻击的同态签名方法，涉及网络编码技术领域。它由参数设置Setup、消息签名Sign、消息组合Combine和消息验证Verify四个多项式时间算法组成；具体包含如下步骤：准备阶段：每代消息写成m×(n‑1)维矩阵形式，每行数据之和作为行首，转化成m×n维矩阵；算法利用消息向量中前N位信息设计签名信息；参数设置Setup；消息签名Sign(SK,id,v′i)；消息组合Combine；消息验证Verify(id,v,σ,PK)。将代标识符信息应用于签名的构造中，数据验证算法需要固定公钥和代标识符共同完成。理论证明本发明可抵抗代内/间攻击，实现各代信息的独立认证。本方法具有计算开销小，安全性能高的特点，适用于实时通信的系统。

说明书

技术领域

本发明涉及网络编码技术领域，具体涉及一种抗代内/间攻击的同态签名方法。

背景技术

网络编码容易受到网络中恶意节点的污染攻击，信息被恶意篡改或伪造传输后污染整个网络，导致信宿无法正确解密信息，网络资源可能会在成的极大浪费。

2000年，Cai等人提出了网络编码理念后，网络编码被广泛应用于无线网络、应用层多播、P2P文件公享等方面，大幅度提高了网络吞吐量和网络传输速率，还有效提高了网络鲁棒性和稳定性。然而网络编码容易受到恶意节点的污染攻击，信源信息被恶意篡改或伪造，经中间节点的编码传输污染整个网络，导致信宿无法正确解密信息。于是，需要为网络编码设计新的签名算法。Krohn等首次提出利用同态哈希函数来设计同态签名方案的验证算法，该方法可检测出被修改的编码分组，但需执行进行大量双线性对运算，无法实现数据包的即时传输。Yu等提出了一种基于RSA的同态签名方案，可大幅降低同态签名的运算复杂度，但仍有大量模指数运算，而且存在代间污染严重的问题。Liu等提出的同态签名方案为每代消息设置独立且唯一的消息代标识符，并利用消息代标识符产生的哈希值对密钥进行随机处理，从而到达抵抗代内、间攻击的目的，但运算量仍旧较大。

发明内容

本发明的目的是提供一种可抗代内/间攻击，实现各代信源信息独立认证，并且签名、验证速度较快，适用于实时通信系统的抗代内/间攻击的同态签名方法。

为了解决背景技术所存在的问题，本发明是采用以下技术方案：一种抗代内/间攻击的同态签名方法，它由参数设置Setup、消息签名Sign、消息组合Combine和消息验证Verify四个多项式时间算法组成；具体包含如下步骤：

(1)准备阶段：每代消息写成m×(n-1)维矩阵形式，每行数据之和作为行首，转化成m×n维矩阵；算法利用消息向量中前N位信息设计签名信息；

(2)参数设置Setup：

设定安全参数1^τ和m,n之后：

a)生成一个五元组(q,H,G,P,R)，其中，q＞2^τ为一个素数，H为：{0,1}*→F_q的哈希函数，G＝<g>为一乘法循环群，g为G的生成元；为一伪随机数生成器，R一个r×(N+r)的秘密矩阵，r_i＝P(sd_i)(i＝1,2,...,r)，sd_i为随机秘密种子，经系统加密通道发送给信源；

b)生成公密钥；系数β_i(i＝1,2,...,r)在F_q随机选取，有可得密钥SK和公钥PK：

SK＝{r₀,r_i'∈F_q|i＝1,2,...,N+r},

其中

(3)消息签名Sign(SK,id,v′_i)：

设当前代消息向量为则签名步骤如下：

a)给定唯一的代标识符id∈{0,1}^τ，计算k_id,i＝H(id,i)(i＝1,2,...,r)，生成S＝(s_i,j)，

注意：S的子矩阵T应为满秩矩阵，

T＝(s_ik)(i＝1,2,...,r,k＝N+1,N+2,...,N+r)；

b)构造线性方程组并生成签名信息：

(T^-1S)·(x₁,x₂,...x_N,x_N+1,,...x_N+r)^T＝0

将(x₁,x₂,...,x_N)＝(v_i1,v_i2,...,v_iN)＝v_i代入线性方程组，v_i的签名向量σ_i：σ_i＝(x_N+1,x_N+2,...,x_N+r)；

c)利用随机线性网络编码的规则将签名信息向量u′_i＝{v′_i,σ_i}，扩展为量u_i；

(4)消息组合Combine(id,α_i,v_i,σ_i)：信息传输过程中，中继节点将收到第id代签名消息进行线性组合，其中，α₁,α₂,...α_l∈F_q；

(5)消息验证Verify(id,v,σ,PK)：

给定id，验证者签名消息中提取签名所用的N位信息和签名信息得到u＝(v,σ)代入下式，

其中h_i＝p_i(i＝n+1,...n+r)；

则若上式成立，接收消息；否则拒绝消息。

采用上述技术方案后，本发明具有以下有益效果：

将代标识符信息应用于签名的构造中，数据验证算法需要固定公钥和代标识符共同完成。理论证明本发明可抵抗代内/间攻击，实现各代信息的独立认证。本方法具有计算开销小，安全性能高的特点，适用于实时通信的系统。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合具体实施方式，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施方式仅用以解释本发明，并不用于限定本发明。

本具体实施方式采用以下技术方案：一种抗代内/间攻击的同态签名方法，它由参数设置Setup、消息签名Sign、消息组合Combine和消息验证Verify四个多项式时间算法组成；具体包含如下步骤：

(1)准备阶段：每代消息写成m×(n-1)维矩阵形式，每行数据之和作为行首，转化成m×n维矩阵；算法利用消息向量中前N位信息设计签名信息；

(2)参数设置Setup：

设定安全参数1^τ和m,n之后：

1)生成一个五元组(q,H,G,P,R)，其中，q＞2^τ为一个素数，H为：{0,1}^*→F_q的哈希函数，G＝<g>为一乘法循环群，g为G的生成元；为一伪随机数生成器，R一个r×(N+r)的秘密矩阵，r_i＝P(sd_i)(i＝1,2,...,r)，sd_i为随机秘密种子，经系统加密通道发送给信源；

2)生成公密钥；系数β_i(i＝1,2,...,r)在F_q随机选取，有可得密钥SK和公钥PK：

SK＝{r₀,r_i'∈F_q|i＝1,2,...,N+r},

其中

(3)消息签名Sign(SK,id,v′_i)：

设当前代消息向量为v′_i＝(v_i1,v_i2,...,v_in)∈F_qⁿ(i＝1,2,...,m)，则签名步骤如下：

a)给定唯一的代标识符id∈{0,1}^τ，计算k_id,i＝H(id,i)(i＝1,2,...,r)，生成S＝(s_i,j)，

注意：S的子矩阵T应为满秩矩阵，

T＝(s_ik)(i＝1,2,...,r,k＝N+1,N+2,...,N+r)；

b)构造线性方程组并生成签名信息：

(T^-1S)·(x₁,x₂,...x_N,x_N+1,,...x_N+r)^T＝0

将(x₁,x₂,...,x_N)＝(v_i1,v_i2,...,v_iN)＝v_i代入线性方程组，v_i的签名向量σ_i：σ_i＝(x_N+1,x_N+2,...,x_N+r)；

c)利用随机线性网络编码的规则将签名信息向量u′_i＝{v′_i,σ_i}，扩展为量u_i；

(4)消息组合Combine(id,α_i,v_i,σ_i)：信息传输过程中，中继节点将收到第id代签名消息进行线性组合，其中，α₁,α₂,...α_l∈F_q；

(5)消息验证Verify(id,v,σ,PK)：

给定id，验证者签名消息中提取签名所用的N位信息和签名信息得到u＝(v,σ)代入下式，

其中h_i＝p_i(i＝n+1,...n+r)；

则若上式成立，接收消息；否则拒绝消息。

实施例：

一、分析本发明提出的一种抗代内/间攻击的同态签名方法的正确性：

假设节点易受到攻击，下面证明本发明的正确性。

证明：令V＝span{s₁,s₂,...s_r}，Sign输出消息和签名向量u_i＝{v_i,σ_i}，由公式(4.3)易知u⊥V，只需证明Verify(id,v,σ,PK)＝1

由于令

{v,σ}＝Combine(id,α_i,v_i,σ_i),(i＝1,2,...,l)，由公式(4.5)可知

其中，v_j和σ_j分别表示u第j、n+j个分量，v_ij和σ_ij分别表示u_i第j、n+j个分量，

由u⊥V可推知推出：

定理得证。

二、证明本发明的安全性：

攻击者A对防守者C发动攻击博弈描述如下：

(1)Intialize:C生成SK、PK等基本参数，A可获得PK等公开信息。

(2)Request:A在第i代消息空间V_i＝span{v₁,v₂,...v_m}(i＝1,2,...,ω)中依次挑选v_i向量，并向C发出连续的签名请求(Request)，C选出id'∈{0,1}^τ，对整个空间V_i签名，并将id'和σ'＝Sign(id',v_i,SK)(i＝1,2,...m)发送给A。

(3)Forge:A产生id^*∈{0,1}^τ和一虚假的消息和签名如果Verify(id,v^*,σ^*,PK)＝1，并满足下面某个条件

1)存在id_i＝id',i∈{1,2,...,ω}，且y不属于消息空间，(代内污染攻击)；

2)id'≠id_i,i∈{1,2,...,ω}中的任何一个，称攻击为(代间污染攻击)。

则称攻击者A获胜。

定义1称同态签名方法是安全的，假如对于拥有多项式时间计算能力的攻击者A，其制造的合法签名信息的概率不大于1/q.

定理1针对代内攻击，本同态签名方法是安全的。

证明：攻击者A能够捕获PK和消息空间V₁＝span{v₁,v₂,...v_m}的签名σ'＝Sign(id',v_i,SK)(i＝1,2,...m)。

首先证明A无法得到密钥矩阵S。因为R未知，A无法直接推出S。S·(x₁,x₂,...x_N,x_N+1,,...x_N+r)^T＝0的解向量u_i＝{v_i,σ_i}构成矩阵U中的第i个列向量，A企图通过U来推出秘密矩阵S。由于SU＝0，假设系数矩阵S的秩为r，矩阵U的秩为λ(λ≤min(m,N))，U^TS^T＝0，U不为满秩方阵，仍不能推出S。综上可知，A无法获取秘密矩阵S。

令V＝span{s₁,s₂,...s_r}，依据矩阵论理论，容易找到一组线性无关向量b₁,b₂,...,b_N，有V^⊥＝span{b₁,b₂,...,b_N}，A欲施展代内攻击，伪造v'的签名消息σ^*需满足为正交于V的向量，V^⊥中有q^N个向量，伪造签名通过验证的概率是q^λ/q^N＝1/q^N-λ。

由定义1可知，本同态签名方法是安全的。

定理2对于代间攻击，本同态签名方法是安全的。

证明：守护者C任意两代之间进行开展代间攻击。

C随机生成密钥矩阵R，攻击者从{0,1}^τ任选两代id和id*(id^*≠id)并进行签名操作。

首先证明这两代签名向量{v,σ}不为同一秘密矩阵S的解向量。

C依据R生成S、S^*。

其中，(i＝1,2,...,N)，在多项式时间内A不能找到id＝id^*，则S＝S^*的概率为1/q^N，所以S与S^*以接近概率1相互独立。所以两代签名向量从属于不同S的解空间。

σ_id为第id代信息v_id的签名信息，u_id＝(v_id,σ_id)张成的空间为V_id，因为S·u_id＝0，则

A为求到达代间攻击的目的，需要伪造一个组合向量使得e∈S^*⊥且并有Verify(id,v^*,σ^*,PK)＝1.

下面将说明实施一次成功的代间伪造攻击其难度等同于去解离散对数问题。

假设C试图去解离散对数d＝g^x。当A请求一个子空间V_id＝span{v₁,v₂,...v_m}的签名时，C可以任意选取σ_id∈F_q作为向量v_i(1,2,...,m)的签名。这里，把由向量(1,2,...,m)张成的空间记为然后，C将在式(4-11)关于未知数x_i(1,2,...,N+r)的方程组的解空间中随机地选择解向量和

于是，C可以构造初始公钥如下：

然后将其发送给A。

根据4.2节描述的步骤，用于验证代id所用的公钥即为

假如A能成功地伪造一个向量且能通过用于代id的检测，使得公式(4-6)成立。根据第一部分的讨论，易知且结合公式(4-11)，C将以大于1-1/q^r的概率得到当q充分大时，这就意味着C可以接近1的概率解出

基于同样的讨论，A只能以可忽略的优势概率伪造一个三元组(id^*,y^*,σ^*)，其中id^*是敌手伪造的任意一个代标识符。

定理得证。

三、从通信和计算开销两方面分析本发明的性能：

通信开销包括分发给各个节点的公钥、密钥信息以及签名信息和代标识符。本发明中需生成N+r位密钥和公钥，且生成后固定不变的，数据包含r位签名信息和1位代标识符，且签名位数r是可调的参数，r＝1即可保证签名信息的安全性。

Yu方案和Liu方案的密钥/公钥数量约为m+n，Yu方案没有采用代标识符设计签名方案，存在代间污染严重的问题，Liu方案为每代消息设置1位独立的代标识符，通过比较，本发明的通信开销较少。

令T_pair、T_me、T_mul、T_add分别表示计算一个线性对运算、模幂运算、乘运算、加运算所需时间。

在Setup阶段，为在有限域F_q上形成私钥SK和公钥PK需要进行了r(N+r)次模乘运算和N+r次模指运算。

在Sign阶段，为产生秘密矩阵S需进行r次模乘法，由于S为确定矩阵，为缩短签名时间可以提前左乘T^-1操作，则信息签名需进行rN次模乘运算。

在Verify阶段，需要对待验证消息数据包进行验证，验证节点需要2N+r次模指和模乘运算，若验证节点可以提前接收到代标识符参数，减少为N次模乘运算。

模乘模加运算，其运算开销远小于模指数运算，所以常常只考虑模指数运算所造成的开销。本发明采用“平方迭代”方法，可用1.5次乘法运算求解指数运算。Yu方案中有大量模指数运算，而且存在代间污染严重的问题。Liu方案可以有效抵抗代内、间攻击，但运算开销仍旧较大，签名和验证效率具有一定的通信延迟。本发明的计算开销比较可见表1。速度较快，实时性好。

表1计算开销

综上所述，本发明具有较少的计算开销，适用于实时应用。

对于本领域技术人员而言，显然本发明不限于上述示范性实施例的细节，而且在不背离本发明的精神或基本特征的情况下，能够以其他的具体形式实现本发明。因此，无论从哪一点来看，均应将实施例看作是示范性的，而且是非限制性的，本发明的范围由所附权利要求而不是上述说明限定，因此旨在将落在权利要求的等同要件的含义和范围内的所有变化包括在本发明内。

此外，应当理解，虽然本说明书按照实施方式加以描述，但并非每个实施方式仅包含一个独立的技术方案，说明书的这种叙述方式仅仅是为清楚起见，本领域技术人员应当将说明书作为一个整体，各实施例中的技术方案也可以经适当组合，形成本领域技术人员可以理解的其他实施方式。