线性同态加密之云隐私保护 - 夏冰加密软件技术博客

云存储是未来信息存储的一种理想方式，它提供方便易用的外包存储空间，以缓解爆炸增长的信息对存储空间的海量需求，然而，数据的存储存在着安全与隐私泄露等问题，致使云存储服务的推广与普及存在困难。针对用户各数据的安全需求，我们提出了一高效的线性同态加密方案( IHES)，其安全性基于多项式环上差错学习(R-IWE)问题的困难性。

一、基础知识

1、格

格是n维空间中一类具有周期性结构离散点的集合，具体描述如下：

定义1己知，n个线性无关的向量b1，…，bn∈Rm，则格定义为:

其中，b1，…，bn称为格的一组基，秩为n。

下面以判定形式给出最坏情形下近似最短向量问题（GapSVPr）。

定义2（GapSVP ）已知(B，d)为GapSVPr的输入，其中B为-n维格的基，deR。

如果λ1(L(B))≤d，则为YES，如果λ1(L(B))>y(n)d，则为NO，其中λ1(L(B))为格/(B)的最小距离。

2、 LWE问题

对于整数q>2，误差分布z∈Zq，，z∈z，随机选择向量S∈Zn。定义两个Zn xZ。上的分布：1）（a，ars+x），其中以为z：中随机均匀选取，x服从形分布.)）Z×z上的均匀分
布。以上分布不可区分。

对适合的模数g及误差分布甲口，利用传统（多项式概率时间）规约，Peikert证明了LWEq.\ya至少跟求解最坏情形下近似GapSVP问题是一样困难的。

定理1令a=a(n)∈(o，1)为一实数，且。则存在从解决最坏情形下GapSVPc，y问题到LWE问题的概率多项式
时间规约。

3、R-LWE问题

令f(x)=f+I∈Z[x]，其中安全参数n为2的整数幂，并使得f(x)在有理数域上不可约，r=Z[x]／<f(x)>为模f (x)的整多项式环，模数q=Imod 2n（由以的多项式界定）为一足够大的素数，而且q= Rl=zrq／<f(x)>为模f (x)和g的整多项式环。Rq中的元素由次数低于n的多项式表示，其系数在{0，l，…，q-l）取得。

类似于LWE问题，R-LWE问题可描述如下：设s=s(x)∈R为一随机均匀的的环元素（保密）。定义两个Rq×Rq上的分布：

1）(n，b=axs+e)∈Rq×Rq，其中随机均匀的选择a∈Rq，P为取自于尺上某一分布中“较小”的随机误差项；

2）（a，c），a，c为Rq上随机均匀选择的环元素。则以上分布不可分。

证明了在理想格问题的困难性假设下R-LWE问题是困难的（见定理2）。

定理2假设对于多项式时间量子算法求解R中理想格上最坏情形近似最短向量(SVP)问题是困难的，则对多项式时间（甚至量子）攻击者而言，从R-LWE分布中的任意多项式次取样都是伪随机的。

二、云存储隐私保护策略

云存储中用户数据不再被用户本地拥有，且被分布式地存储在不可控的云端，各用户数据具有无边界性，因此需要有方法让用户确信：他们的数据只能被自身所访问，即使云服务
提供商也不具备用户数据的访问权限，即数据的机密性保障。为此，本文采用同态加密方案配置云存储隐私保障策略，如图1所示：

可信的管理机构运行Setup(A)算法，生成用户公钥pk发送至各服务器，生成用户私钥sk发送至用户。用户向云端存储数据m，首先将m拆分成mi，…，mi，执行Encrypt(pk，id, mi)算法得到ci，并将密文ci分布式存储在不同的服务器上。当云端接收到来自该用户的数据请求，则云端执行Circuit(pk，id，fc，((ai，ci))；算法将数据密文合成之后传送聚合密文c至用户。用户在接收到标识为i的密文数据c后，执行Decrypt算法能成功地获取所需数据m。

由此，数据以密文的形式分布式存储在云端各服务器上，云服务提供商或攻击者从物理上拥有数据依然无法访问数据。

三、基于R．LWE的同态加密方案

1、同态加密的定义
定义3基于公钥密码体制的安全同态加密方案由一组概率多项式时间(PPT)算法(Setup，Encrypt，Circuit, Decrypt)组成：

Setup(l“，1‘)：输入安全参数儿及最大用户数Z，输出用户私钥sk和公钥pk；

Encrypt(id，pk，mj)：给定数据标识id，用户公钥pk与明文mj，输出密文cj；

：输入数据标识id，密文CI，…，c，及相应权值ai，…，ai，输出运算结果
Decrypt(id，sk，c)：己知数据标识id，用户私钥sk与密文CCi，，输出明文

2/线性同态加密方案
基于R-LWE问题，本文提出的LHES如下：

Setup(l”，15)：输入安全参数n=2k(k∈Z)，最大用户数Z及正整数p<g=lmod(2n)，g为素数。随机选取s∈r4= Zq [x]/<f(x)>(x)=f+1∈zM）作为私钥，公钥为(a，b=axs+pe)，其中a到r4是均匀随机选取的，误差项e从误差分布／cr。中独立选取；

Encrypt(id，pk，他mi)：给定数据标识id及用户公钥（a，b），为了加密-n比特的明文消息mi∈{0,1)”c Rp，均匀随机选取ti∈R4输出密文(c；D，Cj2’)=a×ti+pei(1)，a×ti+pei(2)+ mi），其中g’（j=1，2）从分布y中独立选取，其中r4中多项式加法为普通多项式相加，乘法为普通多项式相乘模xn+1;

：输入数据标识id，权值为ai，…，ai的密文(clu)，cl'2’)…，，(cf'D，c2'2’)，输出密文；
Decrypt(id，sk，c)：收到数据标识id，用户私钥sk及密文(q，C2)后，计算(C2 -cl×s)mod p可得明文。

结论1上述LHES方案是正确的。

证明：对密文进行解密运算，设密文为：

因此，上述LHES是正确的。

结论2本文中加密方案是线性同态的。
证明：己知消息及权值，则消息；对应的密文为。另一方面，由上述加密方案中算法Circuit知对密文
的操作为，由解密算法Decrypt知对应的明文为，显然密文对
应的明文也是。因此，本文中加密方案是线性同态的。

四、方案的性能分析

1、安全性分析

定义4己知安全参数为n，如果任意PPT敌手A的赢得下面游戏的优势是可以忽略的，则称同态加密方案(Setup，Encrypt，Circuit，Decrypt)是CPA安全的。

游戏规则如下：

Setup：挑战者运行Setup(l”)获取密钥(sk，pk)，并将公钥pk发送至敌手A；

Queries:A随机选择(id，mi)并发送至挑战者，其中id为消息他的标识，挑战者计算:

把ci发送至A；

Challenge：询问结束后，A随机定义两组不同的明文mo1…，，moi和m11…，，m1i，并发送至挑战者，唯一的条件是m0J与m1j(j=1，…，2)未被询问过。挑战者随机选取b∈{O，1}并计算cj=Encrypt(id, pk，mbi)（j=1…，，l），最后挑战者将密文聚合:

再发送至A：

Output：A输出b的猜测值b'。
如果b'=b，则称敌手A赢得游戏，其概率记为Pr(b'=b），敌手的优势定义为:

结论3本文中LHES是CPA安全的。

证明：敌手在询问结束后收到聚合密文c，并不知道其对应的密文CI，C2，…，CI即使知道密文，也不能进行解密得到相应的易，因为密文C1，C2，…，CI是由伪随机R-LWE分布中的f组样本组成，密文中隐藏着消息mbj（j=1，…，l）及公钥。如果挑战者没有对消息moj或mij(j =1，…，l)进行回应，敌手仍能正确猜测出易，则表明敌手可以成功解决R-LWE问题，因此敌手不可能猜出易的值，因此本文中LHES是CPA安全的。

2、效率分析

由于R-LWE问题具有更加简单的代数结构，而且解密时采用了取模的方法，因此本文提出的LHES是非常高效的，而且具有描述简单、易于分析等优势。下面就该方案的加密及
解密部分同方案进行比较，效率改进情况如表1所示。

表1中数据表明本文加密方案在效率方面较方案有了很大的改进，尤其是公钥长度、扩展因子及每加密1比特消息对应的基本运算次数都是普通基于LWE问题的加密方案所无法比拟的。另一方面，由于加密方案具有同态特征，故根据算法Circuit可将多个消息或密文压缩为一个，在消息聚合之后使得加解密效率又提高了l倍，从而大大提高信息传输效率。

线性同态加密之云隐私保护

本文采用一普通个人电脑对表一中的两个方案进行了模拟运算，电脑操作系统为微软Windows XP 2002专业版，处理器Core (TM)2 Duo CPU E7400 2.8GHz，内存2.OGB，模拟
过程借助于Shoup's NTL library [14] version 5.5.2，代码用Visual C++ 6.0编写。

表2及表3分别给出了两种加密方案运行时间的模拟结果，通过表中数据可发现本文中基于R-LWE问题加密方案的运行时间较方案在完全相同的条件下提高了几个数量级，尤其是密钥生成时间和加密时间。其中，模数q取满足两方案条件的最小整数，的m取为Sn。

线性同态加密之云隐私保护