一种适用于云存储的改进全同态加密方案
2016-06-21武警工程大学研究生管理大队胡人远
武警工程大学研究生管理大队 胡人远
一种适用于云存储的改进全同态加密方案
武警工程大学研究生管理大队 胡人远
【摘要】全同态加密思想在云存储、密文检索等多方面有重要应用，为了得到更适合云存储的全同态加密方案，对现有的全同态加密方案研究现状进行了分析对比，提出一种基于DGHV方案的改进全同态加密方案。在保证方案安全性的前提下，将单次加密数据量提高到3bit。经论证，改进后单次加密数据量提高的同时，公钥尺寸大大缩小，且降低了计算复杂度，适用于云存储平台。
【关键词】全同态加密；云存储；密文检索
随着云计算技术的不断推广，信息数据的存储与管理成为云计算领域的最热门话题之一。云存储技术作为解决信息数据存储和管理的有效途径之一，由并行存储、分布式存储和网格存储发展而来，但毕竟作为一个新兴技术，各方面仍不是很成熟，尤其是安全方面。使用云计算的外包存储服务［1］就不可避免的要将用户数据上传至云端，用户在失去数据绝对拥有权和控制权的情况下，如何保护用户的数据安全，这将是云存储面临的最大实际问题。在此基础上，在云存储平台实现密文计算，密文检索等功能，这需要继续探索改进数据加密技术。
上世纪70年代， Rivest等人［2］提出了FHE问题，希望通过全同态的性质可以在不解密密文的情况下，对密文进行加减乘除运算，且运算后的结果解密后与对应明文运算后的结果保持一致。随后，国内外学者对同态加密进行了大量的研究，但产生的许多同态加密方案并没有达到全同态加密的要求。直至2009年，IBM研究员Gentry在该领域取得了重大突破，提出基于理想格的全同态加密方案［3］，并其博士论文［4］中对全同态加密进行了更深入的论述。这两篇文章给全同态加密研究领域点亮了前进的方向。为实现密文检索又提供了一种可行性技术。
目前，国内关于整数上的全同态加密技术的研究成果大多停留在基于现有方案基础提出的改进方案的水平。如汤殿华等人［5］在文献［3］的基础上进行改进，与文献［3］相比，具有较小的公钥尺寸、计算效率更高的特点，但是在安全性上存在缺陷。林如磊等人［6］提出一次加密2bit明文，将模2运算改为模4运算，在效率方面进一步提高，并对方案安全性进行分析。全同态加密技术研究还有一个方向是基于LWE困难问题的，但能否运用到云存储上仍需进一步研究分析。
本文主要研究分析云存储的性质特点，结合国内相关的改进思路，对文献［7］中的整数上的全同态加密方案进行了改进，将单次加密数据量由1bit改进为3bit，并使用Gen-try的全同态加密思想，构造全同态加密方案，并采用文献［7］中的技术使公钥尺寸大大缩小，使方案具有更高的效率。
1 理论基础
1.1 同态加密原理
同态是近世代数理论中的一个基础概念。
假设加密函数为EK解密函数为DK运算操作为a和明文M（m0，m1，…，mi），公式为a（DK（M（m0，m1，…，mi）））= D（a（M（m0，m1，…，mi）））
FHE加密方案包含有以下四种算法：
密钥部分（Key） ： 根据给出的参数γ， 生成私钥sk和公钥pk；
加密部分（Enc） ： 明文m通过公钥pk加密后获得密文c；
解密部分（Dec）： 明文m由私钥解密密文c后得到
密文运算算法（Evaluate） ： 输出t个输入的电路C和公钥pk，还有明文对应的密文c。用公式可以表示输出为Evaluate（pk，C，c）。
1.2 DGHV全同态加密
DGHV的具体方案［7］为：
（1）构造一个somewhat加密方案。
生成密钥：选取p作为密钥，其中p满足的条件为：p是一个大素数且p∈［2η-1，2η）；
加密部分：1bit的明文m∈｛0，1｝，m加密生成的密文c=m+pq+2r，在加密过程中随机生成q和r，其中q是一个远大于p的较大整数，r是一个较小的整数且2r小于p/2；
解密部分：解密过程为明文m =（cmodp）mod2。
（2）将somewhat方案构造成非对称公钥方案。
由于q是公开的，那么如果直接将pq作为公钥，则私钥p很容易被计算出来，所以假设一个集合｛xi，xi=pqi+2ri｝ ，选择集合中的任意项构成子集S，将子集中元素的和作为公钥sum（s）=，式子可表示为： c=m+2r+sum（s）。那么具有随机性质的公钥，则可以有效保证密文不被破解出来
（3）使用压缩解密技术对密文不断刷新，控制噪声的增量。
由解密算法可以发现，当密文cmodp （p/2，p/2）之间时，则能解密得出明文。如果超出这个范围则无法还原明文。每次运算前，对“新鲜”密文，进行一次“加密”，从而使要进行运算操作的密文噪声大小控制在一定范围之内，从而达到消减噪声的目的。从而保证运算后的新密文能够被成功解密。
2 改进的基于整数的全同态加密方案
2.1 改进方案原理
通过对文献［7］的研究与分析，提出一种能一次加密3bit密文的基于整数的全同态加密方案，其单次加密数据量更大，公钥更小。
首先对文中使用的符号进行说明：
λ：安全参数；
ρ：噪声的长度，为抵抗暴力攻击，噪声长度应该取ρ=ω（logλ）；
η： 私钥的二进制长度，私钥长度满足η≥ρΘ（λlog2λ）；
γ：公钥的二进制长度，私钥长度满足γ=ω（η2logλ）；
τ： 公钥的个数，τ≥γ+ω（logλ），文中需要的公钥个数为2。
其中ω（）是高阶无穷大量。
2.2 构造全同态加密方案
2.2.1 构造部分同态的somewhat方案
将模2运算改为模23运算，单次可加密3bit明文信息
（1）KeyGen（λ）：由安全参数λ生成η比特的密钥p，令密钥sk=p。
（2）Encrypt（sk，m）：对m∈｛000，001，010，…，111｝进行加密得c=m+23r+pq，其中，r是ρ比特大小的随机整数，q是加密过程中生成γ比特大小的随机整数。
（3）Decrypt（sk，c）：m=（cmodp）mod23。
cmodp的值为噪声大小，只有当|m+23r|＜p/2时，那么噪声cmodp=m+23r，则才能还原出有效的明文。下面对方案的同态性进行验证：
验证得，构造的对称加密方案既满足加法同态又满足乘法同态。但是方案中的噪声会随着运算次数的增加而不断“膨胀”。但噪声值大于p/2时，则以上等式不成立，即无法解密出有效明文。同时有上述公式可见，在加法同态运算中噪声不断线性增长的，而在乘法同态运算中呈几何增长。
2.2.2 转化为公钥加密体制
需要添加一组“0”的密文作为公钥，具体方法步骤如下：
（1）KeyGen（λ）：在加密过程中随机生成η比特的私钥p，令x0=pq0，且x0是奇数并符合rp（x0）被23整除。且b=｛0，1｝，1≤i≤，
（2）Encrypt（pk，m）：τ维向量b=
（3）Decrypt（sk，c）：对密文解密的明文为m=（cmodp）mod23，在加密过程中对x0求模是降低密文大小。
2.2.3 压缩解密电路实现全同态加密方案
按照文献［7］的步骤，利用方案的自举性压缩解密电路，即向公钥中加入一些私钥信息，通过这部分私钥信息对密文进行预处理，保持密文“新鲜”，实现全同态，预处理后的大大加快解密速度，并降低了运算复杂度。
2.3 改进方案安全性分析
该方案的安全性是基于部分近似最大公约数问题（GCD）这一点与DGHV方案相似。其安全级别达到了IND-CPA安全，在Dijk的文献［7］中已得到论证，到目前为止最大公约数问题是不能被解决，所以该方案符合安全性。同时文中的将稀疏子集和问题引入到压缩解密算法中，更加保证了文中算法的安全性。
2.4 改进方案与DGHV方案的比较
Dijk等人提出的基于整数上的全同态加密方案是第一个整数上的全同态加密方案，本文改进的具有较小公钥尺寸的Somewhat同态加密方案也是基于整数上的。所以，下面对改进后的方案与DGHV方案从安全性与效率等方面进行比较，衡量安全性的指标主要有：方案安全级别、基于的困难问题假设等，影响方案效率的指标：公/私钥的尺寸、加/解密算法复杂度、算法吞吐量等。如表1所示：
表1 DGHV方案与改进方案的对比
从表1的对比不难发现，改进后的方案保留了基于整数的全同态加密方案基于困难问题方面的优势，安全性上达到IND-CPA。效率方面，较低了公钥尺寸并增加了单次可加密的数据量，降低了加解密复杂度，加快了加密速度。大大提高了算法处理数据的能力。
3 改进方案在云存储平台中的应用
采用改进后的全同态加密方案对云存储环境中数据进行加密后，在保证数据在传输和存储过程中的安全性的前提下，可以不用解密就可对密文进行检索，与传统加密方法相比，大大缩短了加解密过程，减少了计算的复杂度，提高了效率。且改进方案具有连续性好、计算复杂度低、效率高等特点，提高了云存储平台的信息检索速度。改进方案在云存储环境中应用如图1所示。
图1 全同态加密在云存储平台中的应用
用户通过云服务器端身份认证后与云存储平台建立安全通信信道，保证用户数据传输过程安全。云存储平台中的客户端通过将数据上传/下载至HDFS所处的服务器的本地硬盘的一个临时空间，而后对数据进行加密/解密操作，对加密后的数据进行复制、分块等操作存放到相应数据节点。用户提出对数据进行检索操作时，由客户端建立索引，并生成检索密文关键词通过MapReduce技术对密文进行检索，得出结果后由数据加/解密引擎解密后由客户端传至用户端。
4 结束语
文中通过研究分析近年来国内外全同态加密技术的相关成果，在国内现有研究结果基础上，提出一种适合于云存储平台的全同态加密算法，但改进后在公钥尺寸，计算复杂度等方面相较于传统加密方案效率上仍有一定差距，所以仍需要在该领域不断深入研究降低计算复杂度，提高计算效率，增强安全性。
参考文献
［1］刘帆，杨明.一种用于云存储的密文策略属性基加密方案［J］.计算机应用研究，2012，29（4）∶1452-1456.
［2］RIVEST R L，ADLEMAN L，DERTOUZOS M L. On data banks and privacy homomorphisms ［J］. Foundations of Secure Computation，1978，4（11）∶169-180.
［3］Gentry C.Fully homomorphic encryption using ideal lattices［C］// STOC'09，2009∶169-178.
［4］Gentry C.A fully homomorphic encryption scheme ［D/OL］. Stanford University，2009.http∶//crypto.stanford.edu/craig.
［5］汤殿华，祝世雄，曹云飞.一个较快速的整数上的全同态加密方案［J］.计算机工程与应用，2012，48（28）∶7-122.
［6］林如磊，王箭，杜贺.整数上的全同态加密方案的改进［J］.计算机应用研究，2013，30（5）∶1515-1519.
［7］van Dijk M，Gentry C，Halevi S，et al.Fully homomorphic encryption over the intergers［C］//Proceedings of EUROCRYPT 2010.Riviera，French∶ ［s.n.］，2010∶24-43.
