应用基于格的线性同态签名的云存储数据的动态验证方法

摘要

本发明公开了一种应用基于格的线性同态签名的云存储数据的动态验证方法，包括数据完整性验证：生成格上的线性同态签名算法的公钥和私钥；将文件分为多个数据块，对各数据块进行签名,然后基于默克尔哈希树求出根节点的值，并对根节点的值签名，将数据块、数据块的签名以及根节点的签名发送给云端服务器；将公钥和文件的标识符提供给第三方审计，第三方审计向云端服务器发起挑战验证所述数据块是否变化；云端服务器根据第三方审计发起的挑战提供相应证明；第三方审计根据云端服务器提供的证明判断数据块是否完整，并将验证结果反馈给用户。本发明可以抵抗未来量子计算机发起的量子攻击，在保证用户私密信息的同时支持云端动态操作验证。

说明书

技术领域

本发明涉及加密技术领域，特别是涉及一种应用基于格的线性同态签名的云存储数据的动态验证方法。

背景技术

云存储是云计算的一项基础服务，云存储提供商为用户提供大量的存储空间，用户可以随时随地访问云端数据，其在为用户提供便利的同时，也带来了新的安全隐患。用户将本地数据上传至云端服务器之后，失去对数据的直接控制，恶意云端服务提供商可能出于好奇或者其他不为人知的目的窥探或篡改用户的数据，因此，云端数据的完整性及可用性成为亟待解决的问题。基于传统密码方案的云端验证协议一般规约到某个困难问题的难解性，比如，基于RSA签名算法的验证协议，基于Diffie-Hellman困难问题的双线性映射的验证协议。伴随着科学技术的发展，使得量子计算机的问世成为可能。量子计算机可以在多项式时间内解决上述困难问题，从而基于传统密码方案的数据验证协议将不再安全。

根据目前的研究结果，对格上困难问题还没有有效的破解算法，基于格的困难问题构造的密码方案，是当前密码体制研究的一个重要方向，根据文献中格的定义，基于格的验证协议有以下优点：格在代数上是一个加法交换群，且格密码方案大都使用整数格，格上的线性运算与指数运算相比效率有很大提高；基于格的困难问题有现成的规约证明，保证格密码的安全性。Gentry，Peikert和Vaikuntanathan设计的签名方案(一下简称为GPV签名)作为标准数字签名方案，成为许多格公钥密码算法的基本工具。F.Wang使用GPV签名构建了二元域上基于格的线性同态签名方案(LHS)，H.Liu在LHS的基础上又提出了云存储公有验证方案。然而，此方案不支持数据动态验证，在云存储验证中，由于时常会有文件或数据的插入、修改或删除，数据动态验证就显格外重要。

发明内容

本发明的目的在于克服现有技术的不足，提供一种应用基于格的线性同态签名的云存储数据的动态验证方法，使用基于格的线性同态签名、默克尔哈希树以及随机预言模型下安全抗碰撞哈希函数，构造了新的云存储数据动态验证方法。

本发明的目的是通过以下技术方案来实现的：应用基于格的线性同态签名的云存储数据的动态验证方法，包括数据完整性验证，所述数据完整性验证包括：

密钥生成：利用格上的陷门基生成算法生成格上的线性同态签名算法的公钥和私钥；

数据块签名：将文件划分为多个数据块，利用格上的线性同态签名算法对各数据块进行签名,然后基于默克尔哈希树求出根节点的值，并对根节点的值签名，最后将数据块、数据块 的签名以及根节点的签名发送给云端服务器；

第三方挑战：将公钥和文件的标识符提供给第三方审计，第三方审计向云端服务器发起挑战验证云端服务器中的数据块是否变化；

服务器证明：云端服务器根据第三方审计发起的挑战提供相应证明；

第三方验证：第三方审计根据所述云端服务器提供的证明判断云端服务器中的数据块是否完整，并将验证结果反馈给用户。

所述密钥生成的方式如下：

(pk,sk)←TrapGen(1ⁿ)

$>pk=A\in Z_q^{n*m},sk=T\in Z_q^{m*m}$>

式中，TrqpGen(1ⁿ)为格上的陷门基生成算法，pk为公钥，sk为私钥，为q进制的m*m整数矩阵构成的群。

所述数据块签名包括：

将文件F分割为l个数据块，F＝{u₁,u₂,…,u_l}，其中为m维的列向量构成的群；

计算系数1≤j≤n，其中，id为文件F的标识符，j表示第j个数据块，是随机预言模型下的抗碰撞安全哈希函数，n表示系统安全参数；

将系数α_j与每个数据块求内积令内积向量V_i＝(V_i1,V_i2,…,V_in)^T，1≤i≤l,1≤j≤n；

调用SamplePre(A,T,σ,V_i)生成数据块的签名e_i，1≤i≤l，令签名集合Φ＝{e₁,e₂,…,e_l}，>

根据签名集合Φ构建默克尔哈希树，默克尔哈希树的叶子节点由签名e_i按照预设顺序排列而成；非叶子节点的值由其子节点使用抗碰撞哈希函数得到，并计算出根节点的值h_R；对根节点的值h_R采用SamplePre(A,T,σ,h_R)算法对其签名，得到根节点的值的签名Sig(h_R)；

用户将{F,Φ,id,Sig(h_R)}发送给云端服务器CSP，并将文件F、签名集合Φ和签名Sig(h_R)从本地删除。

所述数据块签名还包括采用SamplePre(A,T,σ,id)对文件F的标识符id进行签名。

所述第三方挑战包括：

用户将审计请求AuditQuest＝(Sig(id)||id)发送给第三方审计，其中Sig(id)表示对标识符id的签名；

第三方审计接收到审计请求AuditQuest＝(Sig(id)||id)后，对签名Sig(id)进行验证，若所述签名Sig(id)成立，则第三方审计任意选取子集作为待抽样数据的下标集合，其中[l]＝{1,2,…,l}，S₁≤S₂≤…≤S_θ；定义挑战chal＝{id,c_i,i}_i∈I，c_i∈Z_q，其中c_i为第三方审计任意选取的随机系数，并将挑战chal＝{id,c_i,i}_i∈I发送给云端服务器。

所述服务器证明包括：

云端服务器接收到第三方审计发来的挑战chal＝{id,c_i,i}_i∈I后，取矩阵B＝(α₁,α₂,…,α_n)，α_j＝H₂(id||j)，1≤j≤n；定义BC^T＝0(modq)，云端服务器计算得到>云端服务器随机选取计算u_i′＝C^Tp_i+u_i，1≤i≤l；

云端服务器根据chal＝{id,c_i,i}_i∈I计算抽样数据块聚合之后的数据：

云端服务器将证明发送给第三方审计，其中Ω_i是第i个叶子节点到根节点的兄弟节点所构成的辅助信息。

所述第三方验证包括：

第三方审计接收到来自云端服务器的证明后，根据 求得根节点的值h′_R，判断A·Sig(h_R)＝h′_R和是否均成立：

若不成立则说明云端服务器存在不完整的数据块，返回0；

若成立，则，计算系数计算令V_com＝(V_com,1,V_com.2,…V_com,n)^T；根据BLS签名的线性属性，聚合签名验证Ae_com＝V_com(mod>是否均成立，若成立，则说明抽样数据块是完整的，返回1；否则说明抽样数据块不完整，返回0。

所述动态验证方法还包括修改数据：

用户将修改数据块使用基于格的线性同态签名算法求出对应的签名令更新信息 并将更新信息发送给云端服务器；

云端服务器执行多项式时间算法ExeUpdate(F,Φ,Update)，云端服务器根据修改数据块 的下标i将待修改数据块u_i替换为修改数据块签名e_i替换为得到文件签名集合根据签名集合Φ^*计算出新的根节点的值云端服务器将证明发送给用户；

用户根据(Ω_i,e_i)求出对应默克尔哈希树MTH的根节点的值h′_R，判断A·Sig(h_R)＝h′_R和>是否均成立，若A·Sig(h_R)≠h′_R，则说明修改数据之前的数据块不完整；若成立，则用户根据签名和(Ω_i,e_i)求出根节点的值h_R，若则用户对根节点的值h_R进行签名得到Sig(h_R)，并将Sig(h_R)发送给云端服务器，执行数据完整性验证，数据完整性验证成功后，将本地的修改数据块签名P_Update和Sig(h_R)删除。

所述动态验证方法还包括插入数据：

用户利用基于格的线性同态签名算法得到插入数据块^*'的签名e^*′，并将更新信息Update＝{I,i,u^*',e^*'}发送给云端服务器；

云端服务器执行多项式时间算法ExeUpdate(F,Φ,Update)，将插入数据块u^*'存储在云端服务器，将签名e^*'放在签名e_i之后，得到文件签名集合计算新的根节点的值云端服务器将发送给用户；

用户根据(Ω_i,e_i)求出默克尔哈希树的根节点的值h″_R，判断A·Sig(h_R)＝h″_R和是否均成立，若A·Sig(h_R)≠h″_R，则说明插入数据之前的数据块不完整；若成立，则用户根据签名e^*'和(Ω_i,e_i)求出根节点的值h_R，若则用户对根节点的值h_R进行签名得到Sig(h_R)，并将Sig(h_R)发送给云端服务器，执行数据完整性验证，数据完整性验证成功后，将本地的块插入数据块u^*'、签名e^*'、P_Update和Sig(h_R)删除。

所述动态验证方法还包括删除数据：

用户发送更新信息Update＝{D,i}给云端服务器，云端服务器执行多项式时间算法 ExeUpdate(F,Φ,Update)，将存储在云端服务器上的数据块u_i及其签名e_i删除，得到文件F＝{u₁,u₂,…,u_i-1,u_i+1,…,u_l}，签名集合Φ^*"＝{e₁,e₂,…,e_i-1,e_i+1,…,e_l}，计算新的根节点的值云端服务器将发送给用户；

用户根据(Ω_i,e_i)求出默克尔哈希树的根节点的值h″′_R，判断A·Sig(h_R)＝h″′_R和是否均成立，若A·Sig(h_R)≠h″′_R，则说明删除数据之前的数据块不完整；若成立，则用户根据Ω_i求出根节点的值h_R，若则用户对根节点的值h_R进行签名得到Sig(h_R)，并将Sig(h_R)发送给云端服务器，执行数据完整性验证，数据完整性验证成功后，将本地的P_Update和Sig(h_R)删除。

本发明的有益效果是：

(1)本发明中基于格的线性同态签名保证可以抵抗未来量子计算机发起的量子攻击，抗碰撞哈希函数保证用户数据的不可伪造性，格上的线性运算保证运算效率较传统中的指数运算有很大提高；

(2)本发明支持云端动态操作验证，比如文件或数据的修改、插入、删除；

(3)支持公有审计，在借助第三方审计进行验证的同时，还能达到隐私保护的目的。

附图说明

图1为本发明的一个框架示意图；

图2为本发明中数据完整性验证的一个实施例的流程示意图；

图3为本发明中修改数据的一个实施例的示意图；

图4为本发明中插入数据的一个实施例的示意图；

图5为本发明中删除数据的一个实施例的示意图。

具体实施方式

下面结合附图进一步详细描述本发明的技术方案，但本发明的保护范围不局限于以下所述。

如图1所示，用户将数据上传至云端服务器，由于用户的软硬件设施、时间以及计算能力等方面的局限性，无法做到随时随地验证上传至云端服务器的数据的完整性，因而借助第三方审计(Third Party Auditor，TPA)来完成验证。用户想第三方审计发送数据完整性审计请求，第三方审计根据用户的请求向云端服务器(CSP)发送挑战从而代替用户进行验证，最后再将验证结果反馈给用户。

实施例一

如图2所示，应用基于格的线性同态签名的云存储数据的动态验证方法，包括数据完整性验证，所述数据完整性验证包括：

S01.密钥生成：利用格上的陷门基生成算法生成格上的线性同态签名算法的公钥和私钥。

密钥生成的方式如下：

(pk,sk)←TrapGen(1ⁿ)

$>pk=A\in Z_q^{n*m},sk=T\in Z_q^{m*m}$>

式中，TrqpGen(1ⁿ)为格上的陷门基生成算法，pk为公钥，sk为私钥，为q进制的m*m整数矩阵构成的群，矩阵A是从这个群随机获取的，服从均匀分布。的设置没有明确规定，只要是m*m维，且每个元素是整数取模q即可。

S02.数据块签名：将文件划分为多个数据块，利用格上的线性同态签名算法对各数据块进行签名,然后基于默克尔哈希树求出根节点的值，并对根节点的值签名，最后将数据块、数据块的签名以及根节点的签名发送给云端服务器。

所述数据块签名包括：

S021.将文件F分割为l个数据块，F＝{u₁,u₂,…,u_l}，其中是m维的列向量构成的群，每个元素的值是整数模q得到。

S022.计算系数1≤j≤n，其中，id为文件F的标识符，j表示第j个数据块，是随机预言模型下的抗碰撞安全哈希函数，n表示系统安全参数。

S023.将系数α_j与每个数据块求内积令内积向量V_i＝(V_i1,V_i2,…,V_in)^T，1≤i≤l,1≤j≤n。

S024.调用SamplePre(A,T,σ,V_i)生成数据块的签名e_i，1≤i≤l，令签名集合Φ＝{e₁,e₂,…,e_l}，Sample Pre(A,T,σ,V_i)是格上的一个抽样算法，基于格的加密方案都是建立在LWE-learning>

S025.根据签名集合Φ构建默克尔哈希树(MHT)，默克尔哈希树的叶子节点由签名e_i按照预设顺序排列而成；非叶子节点的值由其子节点使用抗碰撞哈希函数得 到，并计算出根节点的值h_R；对根节点的值h_R采用SamplePre(A,T,σ,h_R)算法对其签名，得到根节点的值的签名Sig(h_R)。

S026.用户将{F,Φ,id,Sig(h_R)}发送给云端服务器CSP，并将文件F、签名集合Φ和签名Sig(h_R)从本地删除。

所述数据块签名还包括采用SamplePre(A,T,σ,id)对文件F的标识符id进行签名，签名算法采用SamplePre(A,T,σ,id)是为了在第三方挑战时告知第三方审计请求来自那一个用户以及所要验证的文件。

S03.第三方挑战：将公钥和文件的标识符提供给第三方审计，第三方审计向云端服务器发起挑战验证云端服务器中的数据块是否变化。

所述第三方挑战包括：用户将审计请求AuditQuest＝(Sig(id)||id)(AuditQuest是用户发给第三方审计的审计请求，内容包括要审计的文件的id以及对id的签名；对id再次签名是为了告诉第三方审计这个审计请求来源于特定的用户。第三方审计拥有用户X的公钥，如果id的签名验证不通过，说明请求不是来自于用户X，就不接受请求受理，这是为了避免其他用户冒充用户X)发送给第三方审计，其中Sig(id)表示对标识符id的签名；第三方审计接收到审计请求AuditQuest＝(Sig(id)||id)后，对签名Sig(id)进行验证，若所述签名Sig(id)不成立，则第三方审计不接收请求，要求用户重发；若所述签名Sig(id)成立，则第三方审计任意选取子集作为待抽样数据的下标集合，其中[l]＝{1,2,…,l}，S₁≤S₂≤…≤S_θ；定义挑战chal＝{id,c_i,i}_i∈I，c_i∈Z_q，其中c_i为第三方审计任意选取的随机系数，确保云端服务器不会伪造证明，并将挑战chal＝{id,c_i,i}_i∈I发送给云端服务器，要求云端服务器给出相应的证明。

S04.服务器证明：云端服务器根据第三方审计发起的挑战提供相应证明。

所述服务器证明包括：云端服务器接收到第三方审计发来的挑战chal＝{id,c_i,i}_i∈I后，取矩阵B＝(α₁,α₂,…,α_n)，α_j＝H₂(id||j)，1≤j≤n；定义BC^T＝0(modq)，云端服务器计算得到云端服务器随机选取计算u_i′＝C^Tp_i+u_i，1≤i≤l，这样处理是为了不向第三方审计泄露任何有关数据块u_i的信息；定义BC^T＝0的目的是通过B来确定与之正交的矩阵C，然后处理u_i′＝C^Tp_i+u_i，中，是整数模q得到的n维列向量构成的群，p_i就是从这个群里随机选取的，目的是作为系数，增加u_i′的安全性，由于p_i是完全随机获取的，第三方审计就不可能从u_i′中得到任何关于u_i的信息，保证用户数据不被第三方审计窃取。

云端服务器根据chal＝{id,c_i,i}_i∈I计算抽样数据块聚合之后的数据：

云端服务器将证明发送给第三方审计，其中Ω_i是第i个叶子节点到根节点的兄弟节点所构成的辅助信息。

S05.第三方验证：第三方审计根据所述云端服务器提供的证明判断云端服务器中的数据块是否完整，并将验证结果反馈给用户。

所述第三方验证包括：第三方审计接收到来自云端服务器的证明后，根据求得根节点的值h′_R，判断A·Sig(h_R)＝h′_R和是否均成立：(此处验证根节点的签名是否正确，目的是判断接收的证明Proof的信息是否有误，如果根节点的签名正确，A·Sig(h_R)＝h′_R，成立，那么h′_R的计算正确，从而证明Proof中的Ω_i与Sig(h_R)正确)

若不成立则说明云端服务器存在不完整的数据块，返回0；

若成立，则，计算系数计算令V_com＝(V_com,1,V_com.2,…V_co_m,n)^T；根据BLS签名的线性属性，聚合签名验证Ae_com＝V_com(mod>是否均成立，若成立，则说明抽样数据块是完整的，返回1；否则说明抽样数据块不完整，返回0。此处的验证是为了证明抽样数据块的聚合数据U_com的完整性。

中，e_i是默克尔哈希树的叶子节点的值，Ω_i是第i个叶子节点到根节点的辅助信息，由第i个叶子节点的兄弟节点以及父亲节点的兄弟节点组成(简而言之，一直到能够获得根节点为止的信息都是辅助信息)。

BLS：是一种签名的缩写，全称：Lattice-based Linear Signature，原数据块的线性组合构成的聚合数据；这个聚合数据的签名我的获取方法：因为签名是线性同态的，那么聚合后的签名就可以是原数据块的签名的线性组合。

V_com,j＝h_αj(u_com)＝＜α_j,u_com＞表示与α_j内积得到，这个下标com是根据U_com而来，表示由抽样数据块聚合(其实就是线性组合)而来，与之对应的下标就使用V_com,j。

实施例二

在实施例一的基础上，本实施例中，所述动态验证方法还包括修改数据：以M表示进行数据修改的请求信息，以用户要将数据块u_i修改为为例，用户将修改数据块使用基于格的线性同态签名算法求出对应的签名令更新信息并将更新信息 发送给云端服务器；

云端服务器执行多项式时间算法ExeUpdate(F,Φ,Update)，云端服务器根据修改数据块的下标i将待修改数据块u_i替换为修改数据块签名e_i替换为得到文件签名集合根据签名集合Φ^*计算出新的根节点的值如图3所示，云端服务器将证明发送给用户；P_Update是云端服务器发送给验证者的数据是否正确更新的证明，即：Proof>

用户根据(Ω_i,e_i)求出对应默克尔哈希树MTH的根节点的值h′_R，判断A·Sig(h_R)＝h′_R和是否均成立，若A·Sig(h_R)≠h′_R，则说明修改数据之前的数据块不完整；若成立，则用户根据签名和(Ω_i,e_i)求出根节点的值h_R，若说明云端服务器按照用户的要求进行了数据更新操作，则用户对根节点的值h_R进行签名得到Sig(h_R)，并将Sig(h_R)发送给云端服务器，执行数据完整性验证，数据完整性验证成功后，将本地的修改数据块签名P_Update和Sig(h_R)删除。

在图3中，更改第3个数据块的值，依次计算h_a＝H₁(h_c||h_d)，从而

实施例三

在实施例一的基础上，本实施例中，所述动态验证方法还包括修改数据：以I表示进行数据插入的请求信息，以用户在第i个数据块之后添加数据块u^*'为例。

所述动态验证方法还包括插入数据：用户利用基于格的线性同态签名算法得到插入数据块u^*'的签名e^*'，并将更新信息Update＝{I,i,u^*',e^*'}发送给云端服务器；

云端服务器执行多项式时间算法ExeUpdate(F,Φ,Update)，将插入数据块u^*'存储在云端服务器，将签名e^*'放在签名e_i之后，得到文件签名集合计算新的根节点的值(如图4所示)；云端服务器将发送给用户；

用户根据(Ω_i,e_i)求出默克尔哈希树的根节点的值h″_R，判断A·Sig(h_R)＝h″_R和是否均成立，若A·Sig(h_R)≠h″_R，则说明插入数据之前的数据块不完整；若成立，则用户根据签名e^*'和(Ω_i,e_i)求出根节点的值h_R，若说明云端服务器按照用户的要求进行了数据插入的操作，则用户对根节点的值h_R进行签名得到Sig(h_R)，并将Sig(h_R)发送给云端服务器，执行数据完整性验证，数据完整性验证成功后，将本地的块插入数据块u^*'、签名e^*'、P_Update和Sig(h_R)删除。

在图4中，在第4个节点处出入新的数据块e^*'，则节点h_g＝H₁(e₄||e^*′)，依次计算，求出

实施例四

在实施例一的基础上，本实施例中，所述动态验证方法还包括修改数据：以D表示进行数据删除的请求信息。

所述动态验证方法还包括删除数据：用户发送更新信息Update＝{D,i}给云端服务器，云端服务器执行多项式时间算法ExeUpdate(F,Φ,Update)，将存储在云端服务器上的数据块u_i及其签名e_i删除，得到文件F＝{u₁,u₂,…,u_i-1,u_i+1,…,u_l}，签名集合Φ^*"＝{e₁,e₂,…,e_i-1,e_i+1,…，e_l}，计算新的根节点的值(如图5所示)，云端服务器将发送给用户。

用户根据(Ω_i,e_i)求出默克尔哈希树的根节点的值h″′_R，判断A·Sig(h_R)＝h″′_R和是否均成立，若A·Sig(h_R)≠h″′_R，则说明删除数据之前的数据块不完整；若>i求出根节点的值h_R，若说明云端服务器按照用户的要求进行了数据删除的操作，则用户对根节点的值h_R进行签名得到Sig(h_R)，并将Sig(h_R)发送给云端服务器，执行数据完整性验证，数据完整性验证成功后，将本地的P_Update和Sig(h_R)删除。

在图中，将第3个数据块删除，只需要取h_d＝e₄即可。

以上所述仅是本发明的优选实施方式，应当理解本发明并非局限于本文所披露的形式，不应看作是对其他实施例的排除，而可用于各种其他组合、修改和环境，并能够在本文所述构想范围内，通过上述教导或相关领域的技术或知识进行改动。而本领域人员所进行的改动和变化不脱离本发明的精神和范围，则都应在本发明所附权利要求的保护范围内。