ABSTRACT

For the current fully-homomorphic encryption scheme based on LWE (Learn With Errors) structure, Gaussian function sampling and public key size are generally needed. This paper adopts the efficient LWR (Learning With Rounding) to replace the traditional LWE scheme and proposes key-policy-attribute-based full-homomorphic encryption (LWR-ABFHE) scheme for end-to-end data protection in multi-users cloud environments. The LWR-ABFHE scheme proposed in this paper can perform homomorphic computing while performing fine-grained access to encrypted data, and achieve the effect of handling monotonic access structures on a set of authorization attributes without sacrificing the computational power of homomorphic encryption. In this paper, the IND-CPA security of the proposed scheme under LWR assumption is proved.

Keywords:LWR, LWE, Attribute-Based Encryption, Fully Homomorphic Encryption, Monotonic Access Structure

一种基于LWR的属性全同态加密方案

张兴兰，卢玉顺^*

北京工业大学，信息学部，北京

收稿日期：2018年4月4日；录用日期：2018年4月21日；发布日期：2018年4月28日

摘 要

针对目前基于LWE (Learn With Errors)构造的全同态加密方案普遍需要高斯函数抽样以及公钥尺寸过大等问题，本文采用高效的LWR (Learning With Rounding)替换传统的LWE方案，提出了多用户云环境中提供端到端数据保护的基于密钥策略–属性的全同态加密(LWR-ABFHE)方案。本文提出的LWR-ABFHE方案能够在对加密数据进行细粒度访问的同时执行同态计算，并且在不牺牲同态加密的计算能力情况下，达到在一组授权属性上处理单调访问结构的效果。本文在LWR假设下，证明了LWR-ABFHE方案在选择明文攻击下的安全性。

关键词 :LWR，LWE，基于属性，全同态加密，单调访问结构

Copyright © 2018 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

随着互联网的快速发展和云计算的普及，人们对数据隐私越来越重视。针对如何保证用户数据的私密性产生了很多加密方案，其中全同态加密占据主流的研究地位。全同态加密(FHE)是一种特殊的加密方案，可以解决云计算、电子商务等安全问题，因为它允许第三方对加密数据进行任何操作，而无需预先解密。2009年Craig Gentry [1] 实现了第一个全同态加密(FHE)方案，其允许对加密的密文数据执行任何加法和乘法的功能。

自Gentry实现第一个全同态加密方案后，FHE方案逐渐成为了研究的热点，至今产生了各种相关的实现及优化。当前研究全同态加密的主流方案是基于LWE困难问题的安全性假设。因为LWE问题理论上可以量子规约到格上的求解SIVP困难问题和GapSVP困难问题，因此认为基于LWE的全同态加密方案具有牢固的安全性保证。2011年Brakerski等 [2] [3] 提出基于LWE问题构造全同态加密方案的思想，方案利用“重线性化”技术实现密文之间的同态运算，但是同态过程需要用到额外的运算公钥evk，导致密文运算复杂而且效率低下；2012年Brakerski等人 [4] 基于LWE又提出了模不变的全同态方案，省略了模交换技术的消耗，但是该方案在保证安全性的前提下，模数q的取值很大，导致了较高的复杂度；2013年，Gentry [5] 在Crypto国际会议中提出利用近似特征向量方法构造全同态加密方案。该方案的优势是密文之间乘积不会导致维数的膨胀，消除了秘钥交换技术。但是密文的同态计算由向量转换为矩阵之间的加法和乘法，计算复杂；文献 [6] [7] 分别提出利用多键和舍弃自举技术等方案在一定程度上改进了全同态方案的效率，但是这些方案基于LWE问题都需要高斯噪声抽样，时间开销很大，计算上也存在瓶颈。所以消除高斯噪声带来的高昂实际代价很有必要，Bogdanov [8] 和Costache [9] 提出的LWR方案是LWE问题的变体，安全性与LWE问题一样困难，而且LWR问题消除了高斯函数抽样，显著提高了计算效率。

为了支持多用户需求，到目前为止所回顾的所有方案都受到这样的事实的影响，即对同态加密方案的引入扩展对计算能力具有负面影响。Xiao等人方案 [10] 和Lopez方案 [11] 均通过密钥代理或CSP服务器来实现额外的密钥转换过程。同时，Gentry方案 [5] 和Clear-Mc Goldrick方案 [12] 能够提供对用户属性进行加密的细粒度控制访问。然而，Gentry方案 [5] 和Clear Mc Goldrick方案 [12] 仅允许用相同属性加密的数据执行计算，因此无法支持多用户设置下的同态加密。尽管Clear-Mc Goldrick方案 [13] 能够支持多属性计算，但是它们的方案继承了Lopez方案 [11] 的性能瓶颈。本文提出的方案与现有的工作 [5] [11] [12] [13] [14] 之间的主要区别是三个方面。首先，利用LWR问题构造基于属性的全同态加密方案，不仅消除了高斯噪声抽样和运算秘钥，而且公钥尺寸更加小，具有更加高效的计算效率。其次，与现有的ABHE方案 [5] [12] [13] [14] 相比，它们仅将其访问结构视为单一属性 [5] [12] ；或者使用单个属性来表示一组“子属性” [13] ；所提出的方案使用LSSS矩阵(G，p)在一组属性上表示单调访问结构。最后，所提出的LWR-ABFHE方案不是将同态加密和ABE方案直接融合成单个密文，而是将密文分解为两个子分量。第一个分量用公钥PK对数据进行加密；而第二个组件包含一组授权属性U。同态评估只涉及第一个组件。同时，第二个组件用于细化加密数据的访问控制。用户的秘密密钥SK通过一组授权属性与单调访问结构A关联。单调访问结构中的每个授权属性 $A_1$ 都拥有密钥SK的有效份额。因此，当且仅当 $A_1\in A$ 时，才能正确解密加密数据。另外，为了防止多个用户之间的共谋攻击，所提出的LWR-ABFHE方案扩展了密钥随机化技术 [15] [16] ，以使用户的秘密密钥失效，其中多个用户不能将他们的属性集中在一起并重建一个有效的密钥。

2. 预备知识

本文中用粗体小写字母表示向量，例如r；向量的第i个分量用r[i]表示；向量均以列向量形式表示，向量转置用 ${\text{r}}^{\text{T}}$ 表示； $\lceil ·\rceil$ 表示向上取整，表示四舍五入取整；向量范数 ${\Vert x\Vert }_{\infty }^{can}$ 表示所有向量元素绝对值中的最大值。文中对数log默认底是2，向量加法和乘法运算均在模q或者模p意义下进行。

2.1. LWE和LWR问题

定义1. (LWE问题)选取整数n和 $q\ge 2$ ，对于选定的向量 $s\in Z_q^n$ 和随机均匀选择的向量 $a\leftarrow Z_q^n$ ，输出 $\left(a,\langle a,s\rangle +e\right)\in Z_q^{n+1}$ ，其中e是服从离散高斯分布的噪音向量。LWE问题的本质就是从上述LWE函数生成的独立样本中恢复向量 $s$ 。

定理1. (LWE问题难解性假设)选取整数n，令 $\alpha =\alpha \left(n\right)\in \left(0,1\right)$ 和素数 $q=q\left(n\right)$ 满足条件 $q>\frac{2\sqrt{n}}{\alpha }$ 。如果存在一个攻击者A能够在多项式时间内破解 $\text{LWE}{}_{n,m,q,\chi }$ 问题，则存在一个以 $O\left(\frac{n}{\alpha }\right)$ 为近似因子的有效算法求解格上的GapSVP问题。

定义2. (LWR问题)选取整数n，q和p，并且满足 $n\ge 1$ 以及 $q\ge p$ ，定义LWR问题(带舍入学习)如下：对向量 $s\in Z_q^n$ ，均匀随机选取 $a\leftarrow Z_q^n$ ，输出。 ${\text{LWR}}_{n,q,p}$ 问题的本质是区分若干抽样 $\left(a_i,b_i\right)$ 与等量的均匀抽样 $\left(c_i,d_i\right)\in Z_q^n\times Z_p$ 。

定理2. 假设c是任意 $Z_q$ 上B有界分布的LWR问题取样，而且c可以有效的取样。令 $B<q/2p$ .则对于求解任一分布上 $\text{s}\in Z_q^n$ 的LWR问题，我们认为困难程度等价于求解相同分布上 $\text{s}\in Z_q^n$ 的LWE问题。

2.2. 访问控制相关概念

定义3. (单调访问结构)：令 $U=\left\{u_1,u_2,\cdots ,u_n\right\}$ 表示一组属性。如果对于任意的B、C满足条件 $B\in A$ 并且 $B\subseteq C$ ，意味着 $C\in A$ ，则集合 $A\subseteq U$ 是单调的。单调访问结构是 $\left\{u_1,u_2,\cdots ,u_n\right\}$ 的非空子集的单调集合A。A中的集合称为授权集合，而不在A中的集合称为未授权集合。

一般来说，在CP-ABE方案中有三种方法来表示布尔公式，访问树和线性秘密共享方案(LSSS)。在本文中，访问策略是基于LSSS方法构建的，因为已经证明LSSS能够表达任何单调访问结构 [17] 。接下来，LSSS方案定义如下。

定义4. 线性秘密共享方案(Linear Secret-Sharing Schemes (LSSS))：由访问策略形成的线性秘密共享矩阵的每一行对应一个属性值，即行向量与属性值形成一一映射的关系。如果满足以下两个性质，则在 $U=\left\{u_1,u_2,\cdots ,u_n\right\}$ 集合上的秘密共享方案P称为线性的(通过 $R_q$ )：

1) 每个属性的共享秘钥是在 $R_q$ 上形成的一个向量；

2) 存在P的秘密共享矩阵，表示为矩阵 $G\in R_q^{n\times m}$ ，其中行标签 $p\left(i\right)\in U$ ， $\forall i\in \left[n\right]$ ，给定一个秘密分享列向量 $v=\left(s,r_2,\cdots ,r_m\right)$ ，其中 $s\in R_q$ 是要共享的秘钥并且随机选择 $r_2,\cdots ,r_m\leftarrow R_q$ ， $Gv$ 表示根据P的n个共享秘钥的向量。共享 ${\delta }_i={\left(Gv\right)}_i$ ，即内积 $G_i\cdot v$ 属于属性p(i)，其中p是从 $\left\{1,\cdots ,n\right\}$ 到U的函数。

LSSS享有如下的线性重构性质 [7] 。假设P是一个代表访问机构A的LSSS方案。设 $C\in A$ 是一个授权的集合，并且 $I\subset \left\{1,2,\cdots ,n\right\}$ 被定义为 $I=\left\{i:p\left(i\right)\in C\right\}$ 。存在常数 ${\left\{w_i\in R_q\right\}}_{i\in I}$ ，使得 ${\delta }_i$ 是依据P的秘钥SK的有效分享，那么 ${\displaystyle {\sum }_{i\in I}{\delta }_i{w}_i}=s$ 。此外，这些常数 $w_i$ 可以以共享生成矩阵G的大小在多项式时间内找到。对于任何未授权的集合，不存在这样的常数。在本文中，LSSS矩阵 $\left(G,p\right)$ 将用于表示与用户密钥相关的访问结构。

2.3. 密文策略基于属性的加密(CP-ABE)

定义5. 基于密文策略属性的加密方案由以下四种算法组成：

$Setup\left(\lambda ,U\right)$ ：设置算法将安全参数l和属性U的全局作为输入。它输出公共参数PP和主密钥MSK。

$Encrypt\left(PP,M,\text{D}\right)$ ：加密算法采用公共参数PP，明文消息M和包含全部属性的U上的访问结构D作为输入。该算法对明文消息M进行加密并输出密文CT，使得只有符合条件的用户拥有满足访问结构的一组属性才能够解密该消息。

$KeyGen\left(MSK,A\right)$ ：密钥生成算法使用主密钥MSK和描述密钥的一组属性A。它输出一个对应于属性A的私钥SK。

$Decrypt\left(PP,CT,SK\right)$ ：解密算法采用公开参数PP，由访问结构D组成的密文CT和属性集合A的私钥SK。如果属性集合A满足访问结构D使得 $A\in D$ ，那么算法输出消息M，否则输出一个解密失败符号 $\perp$ 。

3. 利用LWR构建基于关键策略属性的全同态加密方案

本章节首先构造高效的基于LWR的属性全同态加密方案(以下简称LWR-ABFHE方案)。在所提出的方案中，访问策略被构建在密文中，并且用户的私钥与一组属性相关联。这随后允许在不知道实际用户数的情况下加密数据。当且仅当其私钥满足加密数据中的访问策略时，新用户才能访问加密数据。接下来，提出的LWR-ABFHE方案被正式定义如下。

3.1. LWR-ABFHE方案构造

本节提出的LWR-ABFHE方案由LWR-ABFHE. Setup (初始化)、LWR-ABFHE. Key Gen (秘钥生成)、LWR-ABFHE.Enc (加密)、LWR-ABFHE. Dec (解密)和LWR-ABFHE. Evaluate (同态评估)四部分组成。

$\text{LWR-ABFHE}\text{.Setup}\left(\lambda ,U,k\right)\to \left(PP,MSK\right)$ ：设置算法将输入：安全参数l，全部属性 $U=\left\{u_1,u_2,\cdots ,u_n\right\}$ 以及系统中参与计算的用户数量k。选择一个足够大的素数q使得 $q=1\mathrm{mod}\left(2\lambda \right)$ ，以及一个较小的正整数p，使得 $\gcd \left(p,q\right)=1$ 。设 $f\left(x\right)=\left(x^d+1\right)$ ，其中d是2的次幂。令 $R_q=Z_q\left[x\right]/\langle f\left(x\right)\rangle$ 是整数多项式f(x)和q模的环。选择一个均匀随机的主密钥 $K_0\leftarrow R_q$ 和选择t个随机元素 $a_t\leftarrow R_q$ (下标t表示第t个元素)，计算t个。接下来针对U中的每个属性 $\left\{u_1,u_2,\cdots ,u_n\right\}$ ，选择一对均匀随机元素 $\left(K_i,K_i^{-1}\right)\leftarrow R_q$ ，其中 $K_i^{-1}$ 是 $R_q$ 下 $S{K}_i$ 的倒数。计算，最后，输出如下公共参数PP和主密钥MSK。

$PP=\left\{a,P{K}_0,{\left\{P{K}_i\right\}}_{i=1}^n\right\}$

$MSK=\left\{K_0,{\left\{K_i\right\}}_{i=1}^n,{\left\{K_i^{-1}\right\}}_{i=1}^n\right\}$

$\text{LWR-ABFHE}\text{.KeyGen}\left(PP,MSK,D\right)\to \left(S{K}_D\right)$ ：秘钥生成算法将公共参数PP，一个主私钥MSK和一个在属性U范围内的访问结构D作为输入。它首先将访问结构D转换成LSSS矩阵 $\left(G,p\right)$ ，其中矩阵 $G\in R_q^{n\times m}$ ，行标签 $p\left(i\right)\in U$ ， $\forall i\in \left[n\right]$ 。然后，通过生成一个向量v来分配主密钥MSK的有效部分s，使得 $v=\left(s,r_2,\cdots ,r_m\right)$ ，其中 $r_2,\cdots ,r_m\leftarrow R_q$ 是随机选择的。 $Gv$ 表示根据访问结构D上线性秘密共享方案P的秘钥s的n个份额的向量。 ${\delta }_i=G_i\cdot v\in R_q$ ，其中 $G_i$ 表示矩阵G第i行的向量。下一步选择一个均匀随机数a和其对应的倒数 ${\alpha }^{-1}$ 使得 $\alpha ,{\alpha }^{-1}\leftarrow R_q$ 。该算法输出与 $\left(G,p\right)$ 的描述相关联的用户的秘密密钥 $S{K}_D=\left(S{K}_0,S{K}_i\right)$ ，其中：

$S{K}_0=K_0\cdot {\alpha }^{-1}\in R_q$

$S{K}_i=\alpha \cdot K_i^{-1}\cdot {\delta }_i\in R_q,\forall i\in A$

$\text{LWR-ABFHE}\text{.Encrypt}\left(M_1,\cdots ,M_t,PP,A\right)\to \left(C{T}_1,\cdots ,C{T}_t\right)$ ：加密算法采用主公钥参数PP，要加密的明文消息 $M\in \left\{0,1\right\}$ 以及一个授权属性集A作为输入。选取t个均匀随机的数 $r_t\in \left\{0,1\right\}$ ，令 $△p=\lfloor \frac{q_1}{p}\rfloor$ ，其中 $q_1$ 是明文模量，即 $△p=\frac{q_1}{p}-{\epsilon }_{q1}$ ， $0\le {\epsilon }_{q1}\le 1$ ，接下来计算密文。输出如下形式的密文 $C{T}_t=\left(C_t^0,C_t^i\right)$ ，其中：

$C_t^0=P{K}_0\cdot r_t+△p\cdot M_t\in R_p$

$C_t^i=a_t\cdot P{K}_i\cdot r_t\in R_q$

$\text{LWR-ABFHE}\text{.Evaluate}\left(PP,F,C_1^0,\cdots ,C_t^0\right)\to F\left(C_1^0,\cdots ,C_t^0\right)$ ：同态评估算法采用公开参数PP，多项式时间计算函数F和密文 $C_1^0,\cdots ,C_t^0$ 的第一分量作为输入。它在密文空间输出计算结果，使得 $C_t^{0\ast }=F\left(C_1^0,\cdots ,C_t^0\right)$ 。

$\text{LWR-ABFHE}\text{.Decrypt}\left(S{K}_D,C_t^0,C_t^i\right)\to \left(M^{\ast }or\perp \right)$ ：解密算法将密文空间中的计算结果 $C_t^{0\ast }=F\left(C_1^0,\cdots ,C_t^0\right)=F\left(M_1,\cdots ,M_t\right)$ 。利用LSSS的线性重构算法计算一组常量，如果等式 ${\displaystyle {\sum }_{i\in I}{\delta }_i{w}_i}=s$ 成立，接下来计算 $M^{\ast }=\frac{1}{△p}\left(C_t^0-S{K}_0{\displaystyle {\sum }_{i\in I}S{K}_i\cdot w_i\cdot C_t^i}\right)$ ，并将计算结果输出到明文空间中使得，否则输出解密失败符号 $\perp$ 。

3.2. 正确性分析

设，，由解密公式得出解密算法的正确性分析：

$\begin{array}{c}{M}^{\ast }=\frac{1}{△p}\left(C_t^0-S{K}_0{\displaystyle {\sum }_{i\in I}S{K}_i\cdot w_i\cdot C_t^i}\right)\\ =\frac{1}{△p}\left(C_t^0-S{K}_0{\displaystyle {\sum }_{i\in I}\alpha \cdot K_i^{-1}\cdot {\delta }_i\cdot w_i\cdot C_t^i}\right)\\ =\frac{1}{△p}\left(C_t^0-S{K}_0{\displaystyle {\sum }_{i\in I}\alpha \cdot K_i^{-1}\cdot s\cdot C_t^i}\right)\\ =\frac{1}{△p}\left(C_t^0-S{K}_0{\displaystyle {\sum }_{i\in I}\alpha \cdot K_i^{-1}\cdot s\cdot a_t\cdot P{K}_i\cdot r_t}\right)\\ =\frac{1}{△p}\left(\left(P{K}_0\cdot r_t\cdot s+△p\cdot M_t\right)-S{K}_0{\displaystyle {\sum }_{i\in I}\alpha \cdot K_i^{-1}\cdot s\cdot a_t\cdot P{K}_i\cdot r}\right)\end{array}$

$\begin{array}{l}=M_t+\frac{1}{△p}\left(\left(\frac{p}{q}{a}_t\cdot K_0+△k1\right)\cdot r_t\cdot s-{\displaystyle {\sum }_{i\in I}\left(\frac{p}{q}\cdot s\cdot a_t\cdot r_t+K_i^{-1}\cdot s\cdot a_t\cdot △k\cdot r_t\right)}\right)\\ =M_t+\frac{1}{△p}\left(△k1\cdot r_t\cdot s-{\displaystyle {\sum }_{i\in I}{K}_i^{-1}\cdot s\cdot a_t\cdot △k\cdot r_t}\right)\\ \le M_t+\frac{△k1}{△p}-\frac{△k}{△p}=M_t+\frac{△k1-△k}{△p}\end{array}$

因为 $r_t\in \left\{0,1\right\}$ ， $0<△k,△k1<\frac{1}{2}$ ，由以上公式可知当时，解密公式可以正确求出M。显然， $△k1-△k$ 的误差范围在 $\frac{△p}{2}$ 以内时，可以保密解密的正确性。故当满足 ${\Vert △k1-△k\Vert }_{\infty }^{can}\le △p/\left(2\cdot c_m\right)$ ， $c_m$ 表示环常数，详细解释见文献 [9] 。

同态运算包括同态加法和同态乘法运算，同态计算过程只计算密文的第一个分量，密文第二个分量用来区分该密文属性是否在信任区间。设 $C_1^0$ 和 $C_2^0$ 是两个新鲜密文的第一部分，即 $C_1^0=P{K}_1\cdot r_1+△p\cdot M_1$ ， $C_2^0=P{K}_2\cdot r_2+△p\cdot M_2$ 。

同态加法： $\begin{array}{c}{C}_{add}=F\left(C_1^0+C_2^0\right)=\left(P{K}_1\cdot r_1+△p\cdot M_1\right)+\left(P{K}_2\cdot r_2+△p\cdot M_2\right)\\ =△p\cdot \left(M_1+M_2\right)+P{K}_1\cdot r_1+P{K}_2\cdot r_2\end{array}$

同态乘法： $\begin{array}{c}{C}_{mult}=F\left(C_1^0\cdot C_2^0\right)=\frac{1}{△p}\left(P{K}_1\cdot r_1+△p\cdot M_1\right)\cdot \left(P{K}_2\cdot r_2+△p\cdot M_2\right)\\ =\frac{1}{△p}\left(△p^2\cdot M_1\cdot M_2+P{K}_1\cdot P{K}_2\cdot r_1{r}_2+△p\cdot \left(M_1\cdot P{K}_2\cdot r_2+M_2\cdot P{K}_1\cdot r_1\right)\right)\\ =△p\cdot \left(M_1\cdot M_2\right)+P{K}_2\cdot r_2\cdot \frac{M_1}{△p}+P{K}_1\cdot r_1\cdot \frac{M_2}{△p}+\frac{\left(P{K}_1\cdot r_1\right)\cdot \left(P{K}_2\cdot r_2\right)}{△p}\end{array}$

通过以上同态加法和同态乘法计算公式不难看出评估密文和新鲜密文形式一致，设 $C_1^0$ 和 $C_2^0$ 的计算误差分别为 $△k_1$ 、 $△k_2$ ，则同态加法后的密文误差为 $△k_{add}=△k_1+△k_2$ ，因为 ${\Vert △k_1+△k_2\Vert }_{\infty }^{\text{can}}\le {\Vert △k_1\Vert }_{\infty }^{\text{can}}\text{+}{\Vert △k_2\Vert }_{\infty }^{\text{can}}$ ，则同态加法可以正确计算。设同态乘法的计算误差为 $△k_{mult}$ ， $\delta =\frac{\left(P{K}_1\cdot r_1\right)\cdot \left(P{K}_2\cdot r_2\right)}{△p}$ ，则对于同态乘法的噪音分析如下： $\begin{array}{l}{\Vert △k_{mult}\Vert }_{\infty }^{can}\le {\Vert {\epsilon }_{q1}\cdot M_1\cdot M_2\Vert }_{\infty }^{can}+{\Vert △k_1\cdot M_1\Vert }_{\infty }^{can}+{\Vert △k_2\cdot M_2\Vert }_{\infty }^{can}\text{+}{\Vert \delta \Vert }_{\infty }^{can}\\ \le 4\cdot p^2\cdot \varphi \left(m\right)/3+6\cdot \left(B+B^{\prime }\right)\cdot p\cdot \sqrt{\varphi \left(m\right)/12}+B_{\delta }=F\left(B,B^{\prime }\right)\end{array}$ 。其中B(或者B')表示 $△k_1$ (或者 $△k_2$ )的标准范数的上界，那么 $△k_{mult}$ 的分类范数本质上增长为 $p\cdot B\cdot B^{\prime }/△p$ 。我们通过函数 $F\left(B,B^{\prime }\right)$ 绑定了 $△k_{mult}$ 的规范形式。所以当满足 ${\Vert △k_{mult}\Vert }_{\infty }^{can}\le F\left(B,B^{\prime }\right)$ ，可以保证同态乘法计算的正确性。

加密数据的细粒度访问控制：加密数据的访问控制由密文的第二部分 $C_t^i$ 实现。满足访问结构D的秘钥 $S{K}_D$ 的任何加密数据集A的超集能够恢复计算结果。如果一个属性子集S在访问结构D中，所有包含S作为子集的属性集合也是访问结构中的一部分。例如，一个访问结构为 $\text{D}=\left\{a_1\cap a_2\right\}$ ，如果集合 $\text{S}=\left\{a_1,a_2\right\}$ 满足访问结构D，则 $\text{A}=\left\{a_1,a_2,a_3\right\}$ 也满足访问结构D。

3.3. 安全性分析

本文提出的LWR-ABFHE方案的安全性是基于Ring-LWR问题的困难硬度构建起来的。本节证明了LWR-ABFHE方案满足IND-ID-CPA(选择明文和选择id攻击下的不可区分安全)安全。证明如下：

定理3. 如果LWR问题求解困难假设成立，则上节提出的LWR-ABFHE方案满足IND-ID-CPA(选择明文和选择id攻击下的不可区分安全)安全。

证明：下面我们通过下述随机预言模型游戏进行。令 ${\text{Adv}}_{\text{Gamei}}\left[{\rm A}\right]$ 表示攻击者A在游戏Gamei中的优势，B表示挑战者。

Game 0：这是一个关于我们LWR-ABFHE方案的标准IND-CPA游戏。依次通过下列步骤来刻画。

1) 初始化阶段：给出一个大小为u的属性集U，B声明他希望受到挑战的访问结构 $A^{\ast }$ 并向A公布他的意向。

2) B利用 $\text{LWR-ABFHE}\text{.Setup}\left(\lambda ,U,k\right)$ 算法生成 $\left(PP,MSK\right)$ ，并且将PP发送给A。

3) A向B发送属性列表 $B^{\ast }=\left\{B_1^{\ast },B_2^{\ast },\cdots ,B_j^{\ast }\right\}$ 的私钥查询，其中对于所有的i都有 $B^{\ast }\ne A^{\ast }$ 。B通过秘钥生成算法 $\text{LWR-ABFHE}\text{.KeyGen}\left(PP,MSK,D\right)$ 生成 $S{K}_D$ ，并且发送给A。

4) A发送属性 $B^{\ast }$ 和一对消息 $M_0$ 、 $M_1$ 给B，B随机产生在访问结构 $A^{\ast }$ 的密文CT。然后将CT发送给A。

5) A重复进行第三步中的任意多次秘钥询问。

6) A输出 $M^{\prime }\in \left\{0,1\right\}$ 。B接收到A对于密文CT的猜测 $C{T}^{\prime }$ ，如果 $CT=C{T}^{\prime }$ ，则成功；否则输出一个随机比特。在这个游戏中，A的优势是 $\left|\mathrm{Pr}\left[CT=C{T}^{\prime }\right]-\frac{1}{2}\right|$ 。

Game 1：与Game 0不同的是，Game 1改变了Setup算法，B随机均匀构造 $\left(K{1}_i,K{1}_i^{-1}\right)\leftarrow R_q$ ，由LWR问题的困难性知 $\left(K{1}_i,K{1}_i^{-1}\right)$ 和 $\left(K_i,K_i^{-1}\right)$ 是统计上不能区分的，因此攻击者A在Game 1中的优势为 $\left|{\text{Adv}}_{\text{Game0}}\left(\text{A}\right)-{\text{Adv}}_{\text{Game1}}\left(\text{A}\right)\right|\le negl\left(\lambda \right)$ 。

Game 2：与Game 1不同的是，Game 2改变了KeyGen算法中随机数a和其对应倒数a⁻¹的生成方式，因为 $R_q$ 上均匀随机选取到的a及a⁻¹在统计意义上是不可区分的，则 $\left|{\text{Adv}}_{\text{Game1}}\left(\text{A}\right)-{\text{Adv}}_{\text{Game2}}\left(\text{A}\right)\right|\le negl\left(\lambda \right)$ 。并且因为选值是随机均匀的，所以 ${\text{Adv}}_{\text{Game2}}\left(\text{A}\right)=\frac{1}{2}$ 。

综上所述，我们可以计算出Game 0中攻击者A获胜的概率为：

${\text{Adv}}_{\text{Game0}}\left(\text{A}\right)=\left|\text{Pr}\left(0\right)-\frac{1}{2}\right|\le {\displaystyle \underset{i=0,1}{\sum }\left|\mathrm{Pr}\left(i\right)-\mathrm{Pr}\left(i+1\right)\right|}+\left|\mathrm{Pr}\left(2\right)-\frac{1}{2}\right|\le negl(\lambda )$

所以，LWR-ABFHE全同态加密方案满足IND-ID-CPA安全，定理3得证。

4. 效率分析与对比

当数据接收方的属性列表满L足访问控制策略W时，接收方利用获得的用户私钥 $S{K}_L$ ，可以成功运行解密算法，从而获得数据的明文信息。下面从两个方面验证计算的正确性：

本文提出了基于Ring-LWR问题硬度的LWR-ABFHE方案的构建。为了支持多用户云环境下的端到端数据保护，本文将基于属性的加密方案扩展为同态加密方案。所提出的LWR-ABFHE方案能够在对加密数据进行细粒度访问控制的同时执行计算。在访问结构方面，所提出的LWR-ABFHE方案非常灵活，

表1. 效率分析对比

能够通过一组授权属性处理单调访问结构。在加密方面，所提出的LWR-ABFHE方案将密文分解为两个子分量，这进而改进了同态加密的计算能力。第一个组件承载用同态加密方案加密的数据;而第二个组件则负责通过使用基于属性的加密方案提供加密数据的细粒度访问。因此，能够扩展同态加密方案以支持多用户环境而不影响同态加密的计算能力。所提出的方案在Ring-LWR硬度的选择性设置模型下是安全的。

本文的LWR-IBFHE方案比传统的基于LWE问题构造的全同态加密方案具有更小的公、私钥尺寸和密文尺寸。而且消除了加密过程LWE进行高斯函数抽样的高昂时间开销，具有更快的高效的加解密效率。表1中列出了和文献 [5] (以下简称AB-GSW方案)在同态计算电路的深度为d时的效率对比，其中 $m=O\left(n\log q\right)$ ， $p\ge m^{\frac{3}{2}d+1}\omega \left({\log }^{2d}m\right)$ 并且 $q\ge 2mpB$ 。

5. 结语

近年来基于容错学习的全同态加密方案是研究的热点，但这类方案隐含的公钥尺寸过大和代价高昂的高斯噪声抽样，成为影响其效率的瓶颈。在本文中，我们基于R-LWR问题的困难性构造了一个更有效的LWR-ABFHE方案，并且演示了如何利用基于LSSS方案的单调访问结构编码密文以及密文的同态计算。带舍入学习问题的构造在保证安全性的基础上也降低了公钥尺寸，取得更快的计算效率。下一步工作将致力于研究非单调访问结构的访问策略构造全同态加密方案，以达到更高的效率和实现更广泛的应用场景。

基金项目

国家自然科学基金(10007016201201)。

文章引用

张兴兰,卢玉顺. 一种基于LWR的属性全同态加密方案
Attribute-Based Fully Homomorphic Encryption Based LWR[J]. 计算机科学与应用, 2018, 08(04): 503-511. https://doi.org/10.12677/CSA.2018.84056

参考文献