一种云存储中可撤销的关键字搜索公钥加密及搜索方法

摘要

本发明公开了一种云存储中可撤销的关键字搜索公钥加密及搜索方法，属于网络安全技术领域。本发明包括：设置系统的公开参数并把系统时间分成z个时间片段，用户端建立公私钥对；当具有数据存储请求时，选取数据文件的关键字集合，选择任意的对称加密算法加密数据文件，并利用公钥和当前的时间片段加密关键字集合后发送到云服务器；当下一时间片段到达时，再次生成关键字集合密文并在服务器更新云服务器；当具有关键字搜索请求时，用户端利用私钥和当前的时间片段计算关键字的陷门信息发送给云服务器，云服务器得到搜索结果，并返回包含搜索关键字的文件密文给用户。本发明适用于安全性要求高的云存储，具备撤消服务器搜索能力，安全高效。

说明书

技术领域

本发明属于网络安全技术领域，具体涉及安全云存储中可撤销的关键字搜索公钥加密方法及搜索方法。

背景技术

云存储是在云计算概念上延伸和发展出来的一个新概念。云计算是分布式处理、并行处理和网格计算的发展，通过网络将庞大的计算处理程序自动分拆成无数个较小的子程序，再交由多部服务器所组成的庞大系统经计算分析之后将处理结果回传给用户。通过云计算技术，网络服务提供者可以在数秒之内，处理数以千万计甚至亿计的信息，达到和“超级计算机”同样强大的网络服务。

云存储是指通过集群应用、网格技术或分布式文件系统等功能，将网络中大量各种不同类型的存储设备通过应用软件集合起来协同工作，共同对外提供数据存储和业务访问功能的一个系统。云存储服务允许用户存储任意规模的数据，由云服务提供商负责保证数据的安全性，可靠性，可访问性。在云存储服务的帮助下，用户不用担心如何防止数据的丢失、如何保证数据的安全、以及需要提前采购多少空间等数据存储的相关问题，从而把更多的精力放在自身业务的发展。

云存储的优势是显而易见的，但安全问题却成为了制约其发展的重要因素，因为用户数据中存在很多的敏感信息，如果用户把自己的数据存储到云服务器上，就会担心数据的泄露问题。加密技术是用来防止消息泄露和保护敏感数据的有效手段，通过对数据的加密，只允许数据的拥有者才能够对数据进行解密，即使存储在云服务器上的数据发生了泄露，也不会外泄数据的任何内容。虽然通过对云数据的加密可以杜绝数据泄露的可能，但同时造成远程数据访问成为一大难题，数据的搜索和查询更是成为了近乎不可达到的目标。在本说明书中谈到的云数据是指云服务器中存储的用户数据。云服务器是指提供云存储服务、用于存储用户数据的服务器。

关键字搜索公钥加密是公钥密码体制的基础应用之一，利用公钥密码体制，用户可以在不泄漏数据内容的前提下实现加密云数据的搜索和回取功能。

目前，关键字搜索加密主要包括单钥模式和公钥模式。单钥模式以对称密码体制为基础，适用于云数据的拥有者和使用者是相同用户的情形，而对于两者是不同用户的情形，单钥模式需要事先通过安全信道共享会话密钥。所谓安全信道指的是信息以加密形式经过网络传播，网络攻击者虽然可以截获网络上传输的所有数据，但他无法得到数据中包含的真正信息。会话密钥是保证用户跟其它计算机或者两台计算机之间安全通信会话而随机产生的加密和解密密钥。而公钥模式允许数据的拥有者在把数据发送给云服务器前利用数据使用者的公钥来加密数据，实现了数据共享，且避免了协商会话密钥的过程。基于此优点，关键字搜索公钥加密更加适用于安全云存储，不但能够满足云存储用户对加密云数据的搜索和回取需求，而且实现了云数据的隐私保护，搜索过程不会泄漏数据的任何内容。

目前，对关键字搜索公钥加密的研究主要集中在指定搜索者的关键字搜索公钥加密、多关键字搜索的公钥加密、抗离线关键字猜测攻击的关键字搜索公钥加密等方面，将关键字搜索公钥加密直接应用于安全云存储在功能和性能上还存在以下问题：

(1)没有解决搜索能力撤销问题；

(2)服务器的搜索能力没有得到限制；

(3)搜索速度慢，搜索请求响应时间长；

(4)搜索效率低，双线性对运算多。

其中前两个问题对用户云数据的安全存储造成极大的威胁，而后两个问题大大消耗了云服务器的计算资源，使其无法同时响应大量用户的搜索请求，造成用户等待时间过长，因此都是需要极力避免的。

发明内容

本发明的发明目的在于：针对上述存在的问题，提供一种云存储中，可撤销的关键字搜索公钥加密方法，以满足高安全性要求的云存储环境需求，用户在必要时，可撤销云服务器的搜索能力，减小系统计算开销，缩短搜索请求响应时间，并在不泄漏云数据内容的条件下，保证云存储环境中加密云数据的安全搜索和回取。

本发明的云存储中可撤销的关键字搜索公钥加密方法，包括下列步骤：

步骤a．系统初始化：

选择安全参数k，设置系统公开参数，并把系统时间划分为整数z个时间片段：t₁,t₂，…,t_z；

步骤b．生成用户公私钥对：

根据用户端选择的私钥s，生成对应的公钥P_Pub；

步骤c．生成文件密文和关键字集合密文：

（c1）当用户有数据存储请求时，用户端选取数据文件M的关键字集合W＝{w_i|i＝1,…,n}，并对数据文件M进行加密，得到数据文件M的文件密文C；

（c2）用户端基于所述公开参数、公钥P_Pub、关键字集合W和当前的时间片段t_i，生成所述关键字集合W对应的关键字集合密文并把所述文件密文C和关键字集合密文发送给服务器存储；

（c3）当新的时间片段t_i+1到达时，用户端基于公开参数、公钥P_Pub、关键字集合W和当前的时间片段t_i+1，生成新的关键字集合密文并把所述关键字集合密文发送给服务器，服务器更新保存的关键字集合密文。

进一步的，所述步骤a中，设置系统公开参数p、q、GF(p)、E、G₁、G₂、P、e、H₁、H₂、Q具体为：

根据所述安全参数k选择大素数p、q，取GF(p)为p阶有限域，E为GF(p)上的椭圆曲线，E(GF(p))为E上的点构成的q阶加法循环群，记为G₁；

P是加法循环群G₁的生成元；

乘法循环群G₂是加法循环群G₁上的点经过双线性对e映射构成的q阶乘法循环群，双线性对e是从加法循环群G₁到乘法循环群G₂的映射，e:G₁×G₁→G₂；

H₁和H₂是抗碰撞的哈希函数，所述H₁是从0和1组成的比特序列集合映射到乘法循环群Z_q^*；H₂是从0和1组成的比特序列集合映射到加法循环群G₁；

Q是加法循环群G₁上的一个随机点。

基于本发明的加密方法，本发明还提供了一种云存储中可撤销的关键字搜索方法，包括下列步骤：

通过本发明的加密方法对用户预存储的云数据文件M进行加密处理，服务器存储文件密文和关键字集合密文，当收到用户的搜索请求时，启动本发明的搜索过程：

用户端根据公开参数，私钥s，公钥P_Pub、搜索请求的关键字w和当前的时间片段t_i，生成所述关键字w对应的陷门并把所述陷门发送给服务器；

服务器收到陷门后，根据公开参数、公钥P_Pub，陷门和存储的关键字集合密文进行验证，若验证成功，则返回对应的数据文件M的密文C；否则不返回任何数据。

综上所述，由于采用了上述技术方案，本发明的有益效果是：

（1）本发明基于公钥密码模式，因此无须通过安全信道传递会话密钥或进行会话密钥协商，从而降低了网络的存储、通信和计算开销，更适合数据共享和高安全性要求的云存储环境；

（2）基于本发明划分的z个时间片段，实现了对服务器端存储的关键字集合密文的定时更新，解决了搜索能力的可撤销问题，限制了服务器的搜索能力，为云数据提供了更好的安全保证；

（3）本发明中，关键字集合W中的每个关键字w_i在固定时间段中，均对应同一个关键字集合密文，从而使得搜索过程中，本发明的服务器无须逐一对关键字集合W中的每个关键字w_i的密文进行验证，将搜索时的验证公式的运行次数从n次降低为1次，显著提高了关键字搜索公钥加密的关键字搜索效率；

（4）本发明中，关键字集合W中的每个关键字w_i在固定时间段中，均对应同一个关键字集合密文，从而使得本发明在搜索验证过程中所需的双线性对运算少，加快了服务器的搜索速度，大大缩短了用户搜索请求的响应时间。

附图说明

本发明将通过例子并参照附图的方式说明，其中：

图1是本发明具体实施方式的公钥加密过程示意图；

图2是本发明具体实施方式的文件密文和关键字集合密文生成过程示意图；

图3是本发明具体实施方式的搜索过程示意图。

具体实施方式

本说明书中公开的所有特征，或公开的所有方法或过程中的步骤，除了互相排斥的特征和/或步骤以外，均可以以任何方式组合。

本说明书（包括任何附加权利要求、摘要和附图）中公开的任一特征，除非特别叙述，均可被其他等效或具有类似目的的替代特征加以替换。即，除非特别叙述，每个特征只是一系列等效或类似特征中的一个例子而已。

本发明是以椭圆曲线密码理论为基础，提出一种安全云存储中可撤销的关键字搜索公钥加密方法，应用于高安全性要求的云存储环境，必要时用户可撤销云服务器的搜索能力，减小计算开销，缩短搜索请求响应时间，并在不泄漏云数据内容的条件下，实现云存储环境中加密云数据的安全搜索和回取。

首先对本发明所应用的数学理论进行简单介绍：

（1）椭圆曲线密码体制ECC

设p和q为大素数，GF(p)为p阶有限域，E为GF(p)上的椭圆曲线，E(GF(p))为E上的点构成的q阶循环群,P∈E(GF(p))是生成元。关于椭圆曲线的定义及其安全参数的选取可以参阅文献：Don Johnson,Alfred Menezes and Scott Vanstone,The Elliptic Curve Digital SignatureAlgorithm(ECDSA),IJLS,vol.1issue1(2001),36-63。

（2）Hash函数

Hash函数就是把任意长的输入消息变换成固定长的输出消息的一种函数，这个输出称为该消息的Hash值。一个安全的Hash函数应该至少满足以下几个条件；①输入长度是任意的；②输出长度是固定的，至少取128bits长，以便抵抗生日攻击；③对每一个给定的输入，能够很容易地计算其输出，即Hash值；④给定Hash函数的描述，找到两个不同的输入消息Hash到同一个值是计算上不可行的，或给定Hash函数的描述和一个随机选择的消息，找到另一个与该消息不同的消息，使得它们Hash到同一个值是计算上不可行的。Hash函数主要用于完整性校验和提高数字签名的有效性。

本发明中Hash函数H₁:{0,1}^*→Z_q^*，是从0和1组成的比特序列集合映射到乘法循环群Z_q^*。H₂:{0,1}^*→G₁，是从0和1组成的比特序列集合映射到椭圆曲线上的加法循环群G₁。

（3）有限域

有限域是一个包含有限个元素的集合，满足对加法和乘法封闭等性质，有限域的阶是域中元素的个数，阶为素数p的有限域一般记为GF(p)。在有限域中，有两个群，一个是GF(p)对加法构成的群，一个是GF(p)-0对乘法构成的群。在乘法循环群中，生成元的所有幂给出群中的所有元素。本发明中Z_q^*表示群Z_q中去掉零元构成的群，G₁是椭圆曲线上的加法循环群，G₂是椭圆曲线上的乘法循环群。

（4）素数和互素

所谓素数，是指任意一大于1的整数p，若它只能被±1和±p整除，就称其为素数；

所谓互素，是指两个整数，若它们的最大公约数为1，则称它们互素。

(5)点标量乘运算

令E是一个定义在域GF(p)上的椭圆曲线，根据“弦和切线”法则，E(GF(p))上的两个点P和Q相加得到E(GF(p))上的第三个点R。点集合E(GF(p))及其这种加法运算构成一个加法交换群，并且O为其无穷远点。

令P=(x₁，y₁)和Q=(x₂，y₂)是椭圆曲线E上的两个不同的点，则P与Q之和R=(x₃，y₃)如下定义：首先画一条连接P和Q的直线，这条直线与椭圆曲线相交于第三点，则这个交点关于x轴的对称点就是R点。

若P=(x₁，y₁)和Q=(x₂，y₂)是椭圆曲线E上的两个相同的点，则求P与Q之和相当于求点P的倍点R=(x₃，y₃)：首先在P点画椭圆曲线的切线，这条切线与椭圆曲线相交于第二点，这个交点关于x轴的对称点就是倍点。

点标量乘运算是椭圆曲线公钥密码体制中最基本也是最重要的环节。椭圆曲线上的点标量乘运算Q＝kP定义如下：给定一条椭圆曲线E和曲线上的一个点P，曲线E上的P点的点乘kP，定义为点P与自身相加k次之和，kP＝P+P+…+P共k个P相加。点标量乘运算又称为点乘运算，它是在椭圆曲线上进行的基本的相同点的多次点加运算，其运行时间决定着椭圆曲线密码体制的实现时间，故决定着椭圆曲线密码体制的运算速度。关于点标量乘运算的具体计算方法可以参阅文献：Stinson A.R.著，冯登国等译.密码学原理与实践.第三版，北京：电子工业出版社，2009.201-208。

（6）双线性对

假设G₁是加法循环群，G₂是乘法循环群，群的阶皆为q，P为群G₁的生成元。映射e:G₁×G₁→G₂满足下面三个条件，则称之为双线性对。

（1）双线性，即对于任意e(aP，bP)=e(P，P)^ab成立；

（2）非退化性，即

（3）e可被有效的计算。

这样的双线性对可以通过有限域上的超奇异椭圆曲线以及超奇异超椭圆曲线的Tate对或Weil对来构造。关于双线性对运算的构造和应用，可以参考文献:Boneh D.,Franklin M.,2001.Identity-based encryption from the Weil pairings,in:Advances in Cryptology-Crypto,in:LNCS,vol.3494,Springer-Verlag,Berlin,2001:213-229。

参照图1，本发明的具体实现如下：

步骤S100.系统初始化：

步骤S101：选择安全参数k，设置系统公开参数(p,q,GF(p),E,G₁,G₂,P，e,H₁,H₂,Q)如下：根据安全参数k选择大素数p和q，GF(p)为p阶有限域，E为GF(p)上的椭圆曲线，E(GF(p))为E上的点构成的q阶加法循环群,记为群G₁，P∈G₁是生成元。群G₂是群G₁上的点经过双线性对e映射构成的q阶乘法循环群，双线性对e是从群G₁到群G₂的映射e:G₁×G₁→G₂。H₁和H₂是抗碰撞的Hash函数，Q是群G₁上的一个随机点。

步骤S102：根据安全参数k把系统时间划分为z个时间片段t₁,t₂，...,t_z，系统当前的第i个时间片段记为t_i。

步骤S200.生成用户公私钥对：

用户端随机选择秘密整数作为私钥，计算相应的公钥P_Pub＝sP。

步骤S300.生成文件密文和关键字集合密文：

当用户有数据文件M的存储请求时，用户端首先选择数据文件M的关键字集合W＝{w₁,…,w_n}，选取任意一对称加密算法（例如高级加密标准算法AES）加密数据文件M，得到文件密文C。本发明中，对数据文件M的加密既可采用对称加密算法，也可以为非对称加密算法，当采用非对称加密算法时，则利用用户端公钥P_Pub加密数据，解密时利用私钥s。

然后利用系统公开参数，公钥P_Pub和当前的时间片段t_i加密关键字集合{w₁,…,w_n}，生成t_i时段的关键字集合密文并把与文件密文C一起发送服务器保存。当下一时间片段t_i+1到达时，用户端计算新的关键字集合密文并把服务器存储的更新为参照图2，本过程的具体实现如下：

步骤S301：当用户有数据存储请求时，用户首先选取数据文件M的W＝{w_i|i＝1,…,n}，然后选取对称加密算法对数据文件进行加密，得到数据文件M的文件密文C；

步骤S302：用户端根据公开参数，公钥P_Pub对{w₁，…,w_n}进行加密，生成当前时间片段t_i的关键字集合密文

步骤S302-a：随机选择计算C₁=γP和C₂=e(P_pub,Q)^γ；

步骤S302-b：对每个i＝1,…,n，计算x_i=H₁(w_i)，利用{x₁,…,x_n}构造拉格朗日差值多项式，得到每n个多项式f_i(x)，

$>f_i\left(x\right)=\underset{1\le j\ne i\le n}{\Pi }\frac{x-x_j}{x_i-x_j}=a_{i,1}+a_{i,2}x+...+a_{i,n}{x}^{n-1},$>

n是选定的关键字集合中元素的个数，多项式f_i(x)的系数a_i,1,a_i,2,…,

步骤S302-c：对每个i＝1，…,n,，用户端选择一个随机数根据多项式f_i(x)的系数a_i,1,a_i,2,…,a_i,n计算y_i＝α_i^-1γ和

步骤S302-d：对每个i＝1,…,n，计算x_i′＝H₂(w_i||t_i)，t_i是当前的时间片段，根据a_i,1,a_i,2,…,a_i,n计算其中符号“||”表示追加操作，即把t_i追加在w_i之后；

步骤S302-e：发送文件密文C和关键字集合密文给服务器；

步骤S303：当下一个时间片段t_i+1到达，用户端再次利用系统公开参数，公钥P_Pub和下一个时间片段t_i+1重新计算第（S302-c）和（S302-d）步，得到新的关键字集合密文并发送给服务器，服务器收到后，将存储关键字集合密文更新为

步骤S303-a：对每个i＝1,…,n,，选择一个随机数根据（S302-b）中时间片段t_i的多项式系数a_i,1,a_i,2,…,a_i，n，计算和其中γ的值与时间片段t_i的值相同；

步骤S303-b：对每个i＝1,…,n，计算t_i+1是时间片段t_i的下一个时间片段，根据多项式f_i(x)的系数a_i，1，a_i,2,…,a_i,n计算和

步骤S303-c：生成关键字集合密文其中C₁,C₂与时间片段t_i中计算的值相同。用户端把发送给服务器，服务器收到后，将更新为

步骤S400.用户进行关键字搜索过程：

当用户具有关键字搜索请求时，用户端根据私钥s和当前的时间片段t_i生成所述关键字w对应的陷门并发送给服务器，服务器根据陷门判断关键字集合密文与陷门是否满足验证公式，若是，则返回相应的数据文件M的文件密文C，否则不返回任何信息。参照图3，本过程的具体实现如下：

步骤S401：当用户具有某个关键字w的搜索请求时，用户端根据公开参数，私钥s，搜索请求的关键字w和当前的时间片段t_i，生成所述关键字w对应的陷门信息：

步骤S401-a：根据Hash函数H₁计算信息中的分量T₁=H₁(w)，根据Hash函数H₂计算T＝H₂(w||t_i)，所述t_i是系统当前的时间片段；

步骤S401-b：根据公开参数中的随机点Q和私钥s计算陷门信息中的分量T₂s(Q+T)；

关键字w在时间片段t_i对应的陷门为用户把关键字陷门发送给服务器；

步骤S402：服务器收到陷门后，根据公开参数，公钥P_Pub，陷门和存储的关键字集合密文搜索中是否包含陷门对应的关键字，并返回搜索结果。

步骤S402-a：服务器根据陷门中的T₁和密文中的(R₁,…，R_n,U₁,…U_n)分别计算λ＝R₁+R₂T₁+…+R_nT₁^n-1(modq)，v=U₁+U₂T₁+…+U_nT₁^n-1(modq)；

步骤S402-b：服务器根据得到的v和λ的值检验公式C₂＝e(C₁,T₂)/e(v,λ)是否成立；若是，则说明关键字w∈{w₁,w₂,…,w_n}，服务器把满足条件的数据文件M的文件密文C返回用户；否则，即则不返回任何数据。

本发明并不局限于前述的具体实施方式。本发明扩展到任何在本说明书中披露的新特征或任何新的组合，以及披露的任一新的方法或过程的步骤或任何新的组合。