格上基于累积器的可撤销的基于身份的加密方法

摘要

本发明公开了一种格上基于累积器的可撤销的基于身份的加密方法，具体按照以下步骤实施：步骤1、系统建立；步骤2、私钥生成；步骤3、更新密钥生成；步骤4、解密密钥生成；步骤5、加密；步骤6、解密；步骤7、撤销，本发明添加了用户身份撤销机制，可以有效地实现用户的身份管理；本发明基于格上的LWE困难问题，可以抵抗量子攻击，并具有较高的计算效率；本发明中用户的更新密钥的大小是常数，不会随着用户数量的增加而增加，本发明解决了现有技术中存在的用户私钥泄露、难以抵抗量子攻击的问题。

说明书

技术领域

本发明属于信息安全技术领域，具体涉及一种格上基于累积器的可撤销 的基于身份的加密方法。

背景技术

基于身份密码体制克服了传统的公钥密码体制中公钥证书的维护、更新 和撤销等问题。基于身份的密码体制从根本上改变了传统的公钥体制架构中 证书的管理和运作。基于身份的密码系统与普通的公钥系统相比不同之处在 于，基于身份的密码体制系统中实体公开身份信息是实体的唯一标识，用户 的公钥可以通过身份信息导出。这些方案在一些企事业单位中有良好的应用 前景，如个人与个人之间，个人与商家之间、商家与商家、企业与企业之间 的业务交流，或者是政府部门之间的电子政务来往等。

为了保证拥有大量用户的加密系统的安全性，身份撤销机制是很必要 的。系统用户公钥被撤销有多种原因：第一，用户的私钥泄露；第二，该用 户不再是一个合法的用户，这种情况下需要撤销该用户。比如在一个企业管 理系统中，某个员工从该企业辞职，则需要从该系统中撤销该用户，或者某 个员工篡改数据或者泄露企业隐私，违反了该企业的规章制度，也需要从该 系统中撤销该用户。

鉴于上述的实际问题，可撤销的基于身份的加密方法研究是很实用的。 在现实生活中，像这样的例子很多，比如像保密局、各类企业、商业、通信 等等领域。在这些情况下，撤销公钥-私钥对并且用新的密钥来代替是很重 要的。可撤销的基于身份加密在基于身份加密方案中提供了有效的撤销方 法，可信权威定期地发布非撤销用户的更新密钥，并且只有用户拥有最新的 更新密钥，他才可以正确的解密密文。因此，随着互联网产品的快速发展以 及广泛使用，研究可撤销的基于身份加密有很好的发展前景。

发明内容

本发明的目的是提供一种格上基于累积器的可撤销的基于身份的加密 方法，解决了现有技术中存在的用户私钥泄露、难以抵抗量子攻击的问题。

本发明所采用的技术方案是，格上基于累积器的可撤销的基于身份的加 密方法，具体按照以下步骤实施：

步骤1、系统建立；

步骤2、私钥生成；

步骤3、更新密钥生成；

步骤4、解密密钥生成；

步骤5、加密；

步骤6、解密；

步骤7、撤销。

本发明的特点还在于，

步骤1具体按照以下步骤实施：

步骤(1.1)、输入安全参数λ，以及用户的最大个数和时间周期个数之 和N，令用户身份这里时间段定义φ为一对一的映射φ(id)＝d,φ(t)＝l,d,l∈{1,…，N}，设置参数m＝2nlogq，$\alpha <\frac{1}{5}{\left(\right(O\left(2\sigma m\right)+1\left)\right(1+\omega \left(\sqrt{\log m}\right)\left)\right)}^{-1},q>10\sqrt{m}\left(O\right(2\sigma m)+1)(1+\omega (\sqrt{\log m}\left)\right);$

步骤(1.2)、使用基于格的陷门生成算法TrapGen(q,n)，生成一个随机均 匀的n×m维矩阵以及的基满足$\left|\right|{\tilde{T}}_{A_0}\left|\right|\le O\left(\sqrt{n\log q}\right);$

步骤(1.3)、选取2个随机均匀矩阵以及2n-1个随机 均匀矩阵随机均匀选择一个n维向量

步骤(1.4)、令U表示被添加到累积器中的所有元素的索引构成的集合， 但是不必要包含在当前的累积器中，令设置累积器初始状态状态撤销列表RL初始设置为空，输出公共参数和主密钥： PP＝(A₀,A₁,A₂,C₁,C₂,B₁,…,B_n,u),

步骤2具体按照以下步骤实施：

步骤(2.1)、输入公共参数PP，主密钥MK，身份id，状态ST_U，令V表 示当前累积器中所有元素的索引构成的集合，因此给定i＝φ(id)∈[n]；

步骤(2.2)、首先计算矩阵

这里记号||表示级联运算；

步骤(2.3)、抽样向量同时满足分布使用私 钥过程如下：

$d_{B_i}\leftarrow sampleGaussian\left(BasisDel\right(T_{A_0},A_0,A_2+C_2·\underset{j\in V,j\ne i}{\Sigma }{B}_j),\sigma ,0),$

证据$w_i=d_{B_i};$

步骤(2.4)、更新累积器和状态如下：

Acc_V∪{i}＝Acc_V+B_i

ST_U∪{i}＝{U∪{i},B₁,…，B_n}

步骤(2.5)、抽样满足 其中H是满秩差分映射，令F_id:＝(A₀||A₁+H(id)C₁)，F_id·e_id＝u在上，e_id是均 匀分布在上，这里记号||表示级联运算；

步骤(2.6)、输出私钥

定义集合V_w表示当证据w_i被创建，包含在累积器中的元素，因此，V_w对 于每个用户是固定的，并且它是U的子集，密钥权威把私钥SK_id和集合V_W给 用户。

步骤3具体按照以下步骤实施：

步骤(3.1)、从集合V中删除和上一个时间段t′相关的l′＝φ(t′)；

步骤(3.2)、从集合V中删除所有在RL中对应于时间段t′的j＝φ(id)；

步骤(3.3)、更新累积器，即对于更新后的集合V，

步骤4具体按照以下步骤实施：

步骤(4.1)、用户对以下4点进行检测：

(a)、i＝φ(id),l＝φ(t)∈V，

(b)、$\left|\right|B_l\left|\right|\le \sigma \sqrt{2m},$

(c)、计算检测是否$F_{B_l}·w_l=0\mathrm{mod}q,$即$w_l\in A^{\perp }\left(F_{B_l}\right);$

(d)、验证w_l是否满足

步骤(4.2)、如果上述的4个验证其中一个失败，解密密钥生成输出终 止，否则，解密密钥用最新的累积器来替换当前的累积器，然后更新证据并 且计算最新解密密钥如下：

如果i∈V，并且计算：

$w_i^{\prime }\leftarrow \mathrm{sampleD}(\mathrm{BasisDel}(T_{A_0},A_0,A_2+C_2·(\underset{j\in V,j\ne i}{\Sigma }{B}_j+\underset{j\in V{V}_w}{\Sigma }{B}_j-\underset{i\in V_{w}V}{\Sigma }{B}_j)),\sigma ,0),$否则终止， 设置解密密钥DK_id,t＝(e_id,w_i′)。

步骤5具体按照以下步骤实施：

步骤(5.1)、给定消息M，包含当前时间的最新累积器Acc_V；

步骤(5.2)、令

这里记号||表示级联运算；

步骤(5.3)、随机均匀选择随机均匀选择m×m维矩阵 $R_i\stackrel{R}{\leftarrow }{\{-1,1\}}^{m\times m},i=1,2,$选择噪音向量和并且设置

步骤(5.4)、令$c_1\leftarrow {F_{id}}^{T}s+\left(\begin{array}{c}y\\ z_1\end{array}\right),c_2\leftarrow {F_{B_i}}^{T}s+\left(\begin{array}{c}y\\ z_2\end{array}\right),$输出密文

步骤6具体按照以下步骤实施：

步骤(6.1)、输入公共参数PP，解密密钥DK_id,t和密文CT_id,t＝(c₀,c₁,c₂)；

步骤(6.2)、计算

步骤(6.3)、比较w和如果则输出1，否则，输出0。

步骤7具体为：

如果i＝φ(id)∈ST_U，则添加(id,t)到撤销列表RL。

本发明的有益效果是，格上基于累积器的可撤销的基于身份的加密方 法，基于格可以抵抗量子攻击，并且具有较高的计算效率，选择身份安全， 并且本发明的更新密钥的大小是常数，本发明添加了用户身份撤销机制，可 以有效地实现用户的身份管理，来保证整个加密系统的安全性。

具体实施方式

下面结合具体实施方式对本发明进行详细说明。

本发明格上基于累积器的可撤销的基于身份的加密方法，具体按照以下 步骤实施：

步骤1、系统建立：

具体按照以下步骤实施：

步骤(1.1)、输入安全参数λ，以及用户的最大个数和时间周期个数之 和N，令用户身份这里时间段定义φ为一对一的映射φ(id)＝d,φ(t)＝l,d,l∈{1,…,N}，设置参数m＝2nlogq，$\alpha <\frac{1}{5}{\left(\right(O\left(2\sigma m\right)+1\left)\right(1+\omega \left(\sqrt{\log m}\right)\left)\right)}^{-1},q>10\sqrt{m}\left(O\right(2\sigma m)+1)(1+\omega (\sqrt{\log m}\left)\right).$

步骤(1.2)、使用基于格的陷门生成算法TrapGen(q,n)，生成一个随机均 匀的n×m维矩阵以及的基满足$\left|\right|{\tilde{T}}_{A_0}\left|\right|\le O\left(\sqrt{n\log q}\right);$

步骤(1.3)、选取2个随机均匀矩阵以及2n-1个随机 均匀矩阵随机均匀选择一个n维向量

步骤(1.4)、令U表示被添加到累积器中的所有元素的索引构成的集合， 但是不必要包含在当前的累积器中，令设置累积器初始状态状态撤销列表RL初始设置为空，输出公共参数和主密钥： PP＝(A₀,A₁,A₂,C₁,C₂,B₁,…,B_n,u),

步骤2、私钥生成：

具体按照以下步骤实施：

步骤(2.1)、输入公共参数PP，主密钥MK，身份id，状态ST_U，令V表 示当前累积器中所有元素的索引构成的集合，因此给定i＝φ(id)∈[n]；

步骤(2.2)、首先计算矩阵

这里记号||表示级联运算；

步骤(2.3)、抽样向量同时满足分布使用私 钥过程如下：

$d_{B_i}\leftarrow sampleGaussian\left(BasisDel\right(T_{A_0},A_0,A_2+C_2·\underset{j\in V,j\ne i}{\Sigma }{B}_j),\sigma ,0),$

证据$w_i=d_{B_i};$

步骤(2.4)、更新累积器和状态如下：

Acc_V∪{i}＝Acc_V+B_i

ST_U∪{i}＝{U∪{i},B₁,…,B_n}

步骤(2.5)、抽样满足其 中H是满秩差分映射，令F_id:＝(A₀||A₁+H(id)C₁)，F_id·e_id＝u在上，e_id是均匀 分布在上，这里记号||表示级联运算；

步骤(2.6)、输出私钥

定义集合V_w表示当证据w_i被创建，包含在累积器中的元素，因此，V_w对 于每个用户是固定的，并且它是U的子集，密钥权威把私钥SK_id和集合V_W给 用户；

步骤3、更新密钥生成：

具体按照以下步骤实施：

步骤(3.1)、从集合V中删除和上一个时间段t′相关的l′＝φ(t′)；

步骤(3.2)、从集合V中删除所有在RL中对应于时间段t′的j＝φ(id)；

步骤(3.3)、更新累积器，即对于更新后的集合V，

步骤4、解密密钥生成：

具体按照以下步骤实施：

步骤(4.1)、用户对以下4点进行检测：

(a)、i＝φ(id),l＝φ(t)∈V，

(b)、$\left|\right|B_l\left|\right|\le \sigma \sqrt{2m},$

(c)、计算检测是否$F_{B_l}·w_l=0\mathrm{mod}q,$即$w_l\in {\Lambda }^{\perp }\left(F_{B_l}\right);$

(d)、最终验证w_l是否检测

步骤(4.2)、如果上述的4个验证其中一个失败，解密密钥生成输出终 止，否则，解密密钥用最新的累积器来替换当前的累积器，然后更新证据并 且计算最新解密密钥如下：

如果i∈V，并且计算：

$w_i^{\prime }\leftarrow \mathrm{sampleD}(\mathrm{BasisDel}(T_{A_0},A_0,A_2+C_2·(\underset{j\in V,j\ne i}{\Sigma }{B}_j+\underset{j\in V{V}_w}{\Sigma }{B}_j-\underset{i\in V_{w}V}{\Sigma }{B}_j)),\sigma ,0),$否则终止， 设置解密密钥DK_id,t＝(e_id,w_i′)；

步骤5、加密：

具体按照以下步骤实施：

步骤(5.1)、给定消息M，包含当前时间的最新累积器Acc_V；

步骤(5.2)、令

这里记号||表示级联运算

步骤(5.3)、随机均匀选择随机均匀选择m×m维矩阵 $R_i\stackrel{R}{\leftarrow }{\{-1,1\}}^{m\times m},i=1,2,$选择噪音向量和并且设置

步骤(5.4)、令$c_1\leftarrow {F_{id}}^{T}s+\left(\begin{array}{c}y\\ z_1\end{array}\right),c_2\leftarrow {F_{B_i}}^{T}s+\left(\begin{array}{c}y\\ z_2\end{array}\right),$输出密文

步骤6、解密：

具体按照以下步骤实施：

步骤(6.1)、输入公共参数PP，解密密钥DK_id,t和密文CT_id,t＝(c₀,c₁,c₂)；

步骤(6.2)、计算

步骤(6.3)、比较w和如果则输出1，否则，输出0；

步骤7、撤销：

具体为：

如果i＝φ(id)∈ST_U，则添加(id,t)到撤销列表RL。

下面对本发明格上基于累积器的可撤销的基于身份的加密方法的安全 性进行分析：

(1)、正确性证明：

本发明的正确性推导过程如下：

定理：上述正确性证明中的误差项$x-{e_{id}}^T\left(\begin{array}{c}y\\ z_1\end{array}\right)-{w_i}^{\prime T}\left(\begin{array}{c}y\\ z_2\end{array}\right)$的界限为 $\left(O\right(2\sigma m)+1)\left(\alpha q\right(1+\omega \left(\sqrt{\log m}\right)\left)\right).$

证明：为了证明误差项的界限，令e_id＝(e_id,1|e_id,2)，w_i'＝(w_i,1′,w_i,2′)其中 由左抽样算法得到：由高斯抽样算法得 到：$\left|\right|{w_i}^{\prime }\left|\right|\le \sigma ·\sqrt{2m},$则$e_{id,1},e_{id,2},{w_{i,1}}^{\prime },{w_{i,2}}^{\prime }\le \sigma \sqrt{m}$

$\left|\right|e_{id,1}+R_1{e}_{id,2}\left|\right|\le \left|\right|e_{id,1}\left|\right|+\left|\right|R_1{e}_{id,2}\left|\right|\le \sigma \sqrt{m}(1+O(\sqrt{m}\left)\right)\le O\left(\sigma m\right),$

$\left|\right|{w_{i,1}}^{\prime }+R_2{w_{i,2}}^{\prime }\left|\right|\le \left|\right|{w_{i,1}}^{\prime }\left|\right|+\left|\right|R_2{w_{i,2}}^{\prime }\left|\right|\le \sigma \sqrt{m}(1+O(\sqrt{m}\left)\right)\le O\left(\sigma m\right).$

利用引理1，引理1描述如下：

引理1：令e是中的向量，则的值为[0,q-1]中的整数，并且 以不可忽略的概率满足

$\left|e^{T}y\right|\le \left|\right|e\left|\right|q\alpha w\left(\sqrt{\log m}\right)+\left|\right|e\left|\right|\sqrt{m/2}$

误差项被界定为

$\left(\begin{array}{c}\left|x-{e_{id}}^T\left(\begin{array}{c}y\\ z_1\end{array}\right)-{e_t}^T\left(\begin{array}{c}y\\ z_2\end{array}\right)\right|\le \left|x\right|+\left|{(e_{id,1}+R_1{e}_{id,2})}^{T}y\right|+\left|{({w_{i,1}}^{\prime }+R_2{w_{i,2}}^{\prime })}^{T}y\right|\\ \le \frac{1}{2}q\alpha \omega \left(\sqrt{\log m}\right)+\left|\right|\left(e_{id,1}+R_1{e}_{id,2}\right)\left|\right|·(\frac{\sqrt{m}}{2}+q\alpha \omega (\sqrt{\log m}\left)\right)+\left|\right|{w_{i,1}}^{\prime }+R_2{w_{i,2}}^{\prime }\left|\right|·(\frac{\sqrt{m}}{2}+q\alpha \omega (\sqrt{\log m}\left)\right)\\ =\frac{1}{2}+q\alpha \omega \left(\sqrt{\log m}\right)+\left(\right|\left|\right(e_{id,1}+R_1{e}_{id,2}\left)\right||+||{w_{i,1}}^{\prime }+R_2{w_{i,2}}^{\prime }|\left|\right)(\frac{\sqrt{m}}{2}+q\alpha \omega (\sqrt{\log m}\left)\right)\\ \le (1+|\left|\right(e_{id,1}+R_1{e}_{id,2}\left)\right||+||{w_{i,1}}^{\prime }+R_2{w_{i,2}}^{\prime }|\left|\right)(\frac{\sqrt{m}}{2}+q\alpha \omega (\sqrt{\log m}\left)\right)\\ \le \left(O\right(2\sigma m)+1)(\frac{\alpha q}{4}+q\alpha \omega (\sqrt{\log m}))\\ <\left(O\right(2\sigma m)+1)\left(\alpha q\right(1+\omega \left(\sqrt{\log m}\right)\left)\right)\end{array}\right)$

上述的误差项的界限为

为了保证方案的正确性，通过设置参数q,n,m,σ,α，确保误差项是小于 q/5，方案中的参数估计过程如下：

(a)误差项小于q/5，也就是说$\alpha <\frac{1}{5}{\left(\right(O\left(2\sigma m\right)+1\left)\right(1+\omega \left(\sqrt{\log m}\right)\left)\right)}^{-1},$

(b)陷门生成算法需满足m>2nlogq，

(c)对于左抽样算法和高斯抽样算法，σ要保证是足够大的，即 $\sigma >\left|\right|{\tilde{T}}_A\left|\right|\sqrt{m}w\left(\sqrt{\log m}\right)=m\omega \left(\sqrt{\log m}\right),$

(d)根据学者Regev的约减过程，参数需满足

为了满足上述的要求，设置参数如下：

(a)m＝2nlogq，

(b)$\sigma =m\omega \left(\sqrt{\log m}\right),$

(c)噪声参数$\alpha <\frac{1}{5}{\left(\right(O\left(2\sigma m\right)+1\left)\right(1+\omega \left(\sqrt{\log m}\right)\left)\right)}^{-1},$

(d)模数q是一个素数并且满足

$q>10\sqrt{m}\left(O\right(2\sigma m)+1\left)(1+\omega (\sqrt{\log m})\right).$

(2)、安全性证明：

定理：如果存在一个概率多项式时间算法A在IND-sID-CPA下以优势 ε>0攻破RIBE方案，则存在概率多项式时间算法B以ε的优势判定 问题。

证明：如果敌手A以不可忽略的优势攻破方案，则挑战者B可以借助敌 手A来判定问题。证明过程是在一系列游戏之间进行的，第 一个游戏和安全模型中的IND-sID-CPA游戏相同，在最后一个游戏中，敌手 的优势A是0，只要证明一个概率多项式时间敌手A是不能区分任意两个游 戏的，即证明了敌手以可忽略的优势赢得原始的IND-sID-CPA游戏。

游戏0：该游戏的安全模型是选择明文攻击及选择身份攻击下的不可区分 的安全模型(IND-sID-CPA)。挑战者B选择n+4个随机矩阵 生成公共参数PP和主密钥MK。在挑战阶段， 挑战者生成挑战密文CT^*。令对于i＝1,2，表示创建密文CT^*时 使用的2个短暂的随机矩阵。

游戏1：在游戏1中，挑战者改变生成公共参数矩阵A₁,A₂的方式，令(id^*,t^*) 是A要挑战的身份时间对，φ(id^*)＝i^*,φ(t^*)＝l^*，挑战者B在建立阶段选择随机 矩阵并且构造矩阵A₁,A₂如下：

游戏中剩余的参数不变。注意到是在建立阶段提前选 择的，并且关于挑战身份id^*和挑战时间t^*的知识是不需要的。

引理2：假设m>(n+1)logq+w(logn)，q是素数。令是均匀选择的， 令R是m×m维的矩阵，在{-1,1}^m×mmodq上均匀选择的。接着，对于所有的向 量分布(A,AR,R^Tw)是统计接近于分布(A,B,R^Tw)的。

通过使用引理2，证明游戏0和游戏1是不可区分的。观察在游戏1中， 矩阵仅仅被用来构造矩阵A₁,A₂以及构造挑战密文CT^*中用到的 误差向量通过使用引理3，分布(A₀,A₀R₁^*,z₁)和(A₀,C₁′,z₁) 是统计接近的，分布(A₀,A₀R₂^*,z₂)和(A₀,C₂′,z₁)是统计接近的，其中C₁′,C₂′是上的均匀随机矩阵。因此，从敌手的角度来看，矩阵A₀R_i^*是接近于均匀的， 并且独立于z，所以上面定义的A₁,A₂是接近于均匀的。因此，A₁,A₂在游戏1 和游戏2中是不可区分的。

游戏2：在游戏2中，我们改变改变参数中u的选择方式，并且挑战者 生成id＝id^*,t＝t^*分别对应的私钥和更新密钥如下：

为了约减方便，我们把敌手分为两种类型：

类型1：敌手选择询问挑战身份id^*的私钥，但是id^*在t^*时刻之前已经被撤销。

类型2：敌手在任意时间都不对挑战身份id^*的私钥进行询问。

如果挑战者面对的是第一种类型中的敌手，则生成 并且令u←F_id·e_id，接着令其中l＝φ(t),i＝φ(id)。因为id^*在询问t^*更新密钥之前 已经撤销，我们知道，在最新的累积器中，已没有id^*的记录。挑战者用(e_id,w_i) 作为关于id^*的私钥询问的回答，用(w_l)作为关于挑战时间t^*的更新密钥询问 的回答。

如果挑战者面对的是第二种类型的敌手，则生成其中l＝φ(t)。因为id^*的私钥从不被询问，挑战者用(w_l)作为关于挑战时间t^*的 更新密钥询问的回答。

由引理1知，上述的e_id,w_i,w_l是从上抽样的，它是统计接近于真实 方案中的特别地，我们有$e_{{\mathrm{id}}^{*}}\in D_{{\Lambda }_q^u\left(F_{{\mathrm{id}}^{*}}\right),\sigma },w_{i^{*}}\in D_{{\Lambda }_q^{\perp }\left(F_{{B_i}^{*}}\right),\sigma },$因为可以看成是在是随机选取的矩阵，由引理2知， u是统计接近于上的均匀分布。因此，敌手不能区分挑战者模拟的是哪种 类型的敌手，并且有的概率模拟正确的游戏。因此，如果正确的游戏被模 拟的话，游戏1和游戏2是不可区分的。

游戏3：现在，挑战者改变游戏2中的A₀,C₁,C₂的选择方式，在游戏3 中，生成矩阵A₀是一个上的随机矩阵，而生成矩阵C₁,C₂是使用TrapGen算 法，满足C₁,C₂是上的随机矩阵，并且挑战者拥有的陷门和 的陷门对于矩阵A₁,A₂的构造和游戏1中一样。

为了回答私钥和更新密钥的询问，其中id≠id^*,t≠t^*，我们用陷门来代替陷门令

$F_{id}=\left(A_0\right|A_1+H\left(id\right)·C_1)=\left(A_0\right|{\mathrm{LR}}_1^{*}+\left(H\right(id)-H\left({\mathrm{id}}^{*}\right))·C_1)$

$F_{B_i}=\left(A_0\right|A_2+C_2·\underset{j\in V,j\ne i}{\Sigma }{B}_i)=\left(A_0\right|A_0{R}_2^{*}+\left(\underset{j\in V,j\ne l^{*}}{\Sigma }{B}_j-\underset{j\in V,j\ne l^{*}}{\Sigma }{B}_j\right)·C_2)$

因为[H(id)-H(id^*)]和是非奇异的，所以，陷门也 是对应的陷门，其中 ${C_1}^{\prime }=\left(H\right(id)-H(id*\left)\right)C_1,{C_2}^{\prime }=\left(\right(\underset{j\in V,j\ne i}{\Sigma }{B}_j-\underset{j\in V,j\ne l^{*}}{\Sigma }{B}_j\left)\right)C_2.$

现在挑战者回答所有id≠id^*的私钥询问如下：

$w_i\leftarrow sampleRight(T_{c_2},{C_2}^{\prime },R_2^{*},0,\sigma )$

$e_{id}\leftarrow sampleRight(T_{c_1},{C_1}^{\prime },R_1^{*},u,\sigma )$

其中φ(id)＝i。

现在挑战者回答所有t≠t^*的更新密钥询问如下：

$w_l\leftarrow sampleRight(T_{c_2},{C_2}^{\prime },R_2^{*},0,\sigma )$

其中φ(t)＝l。

因为在加密系统中使用的σ是足够大的，模拟出来的私钥中的部分e_id是 统计接近于w_i是统计接近于模拟出来的更新密钥的部分w_l是统计接近于挑战者回答id^*的私钥询问和t^*的更新密钥询问和游戏 2中是一样的。否则的话，游戏3和游戏2是一样的。在游戏3中，为了回 答私钥询问和更新密钥询问，构造的矩阵A₀,C₁,C₂是统计接近于游戏2中的 原矩阵的，因此，敌手在游戏3中的优势至多可忽略的不同于游戏2中的优 势，也就是说，游戏2和游戏3是不可区分的。

游戏4：游戏4是等同于游戏3的，除了挑战密文(c₀^*,c₁^*,c₂^*)是在 上随机选取的元素。因为挑战密文总是在密文空间上的新的随机 元素，因此在这个游戏中敌手的优势为0。留下来的任务就是证明游戏3和 游戏4是计算不可区分的，通过使用一个LWE问题的规约。

LearnwithError(LWE)问题的规约：假设敌手有不可忽略的优势来区分游 戏3和游戏4，通过使用敌手来构造一个LWE算法，记为B。回顾LWE问题 的实例是通过一个抽样预言机O提供的，该预言机要么是完全随机的预言机 O_$，要么是带噪音的伪随机预言机O_s。挑战者B使用敌手来区分两个游戏， 其过程如下：

实例化：B询问预言机O，得到回答。对于i＝0,…,m，一个新的对 建立：B构造系统的公共参数PP如下：

1、利用先前给出的LWE问题的m个实例，令的第i列是LWE问题 实例中的n维向量u_i，对于i＝1,…,m。

2、指定LWE实例的第0个抽样成为随机n维向量

3、构造公共参数的剩余项，即就是A₁,A₂,C₁,C₂的构造像游戏3中的一样， 通过使用id^*,t^*,

4、发送公共参数PP＝(A₀,A₁,A₂,C₁,C₂,B₁,…,B_n)给敌手。

询问：挑战者像游戏3中一样回答私钥询问和更新密钥询问。

挑战：当敌手给出一个消息比特b^*∈{0,1}，构造一个对应于目标(id^*,t^*)的挑战 密文，如下：

1、令v₀,…,v_m是来自LWE实例的分量，设置

2、盲化消息比特，通过令

3、令

4、选择一个随机比特r∈{0,1}，如果r＝0，则发送密文CT^*＝(c₀^*,c₁^*,c^*₂)给 敌手，如果r＝0，则发送一个随机密文给敌手。

接下来讨论，当LWE预言机是伪随机预言机的时候，即O＝O_s，则有CT^*的分布和游戏3中的分布是一致的。首先，我们观察得到

$F_{{\mathrm{id}}^{*}}=\left(A_0\right|A_1+H\left({\mathrm{id}}^{*}\right)C_1)=\left(A_0\right|A_0{R}_1^{*}+\left(H\right({\mathrm{id}}^{*})-H\left({\mathrm{id}}^{*}\right))C_1)=\left(A_0\right|A_0{R}_1^{*})$

$F_{B_{l^{*}}}=\left(A_0\right|A_2+\left(\underset{j\in V,j\ne l^{*}}{\Sigma }{B}_j\right)C_1)=\left(A_0\right|A_0{R}_2^{*}+\left(\underset{j\in V,j\ne l^{*}}{\Sigma }{B}_j-\underset{j\in V,j\ne l^{*}}{\Sigma }{B}_j\right)C_2)=\left(A_0\right|A_0{R}_2^{*})$

其次，通过O_s的定义，知道对于一些随机噪音向量分布在 因此，在第3步中定义的满足

${c_1}^{*}\left(\begin{array}{c}{v}^{*}\\ {\left(R_1^{*}\right)}^T{v}^{*}\end{array}\right)=\left(\begin{array}{c}{A}_0^{T}s+y\\ {\left(R_1^{*}\right)}^T{A}_0^{T}s+{\left(R_1^{*}\right)}^{T}y\end{array}\right)=\left(\begin{array}{c}{A}_0^{T}s+y\\ {\left(A_0{R}_1^{*}\right)}^{T}s+{\left(R_1^{*}\right)}^{T}y\end{array}\right)={\left(F_{{\mathrm{id}}^{*}}\right)}^{T}s+\left(\begin{array}{c}y\\ {\left(R_1^{*}\right)}^{T}y\end{array}\right)$

${c_2}^{*}=\left(\begin{array}{c}{v}^{*}\\ {\left(R_2^{*}\right)}^T{v}^{*}\end{array}\right)=\left(\begin{array}{c}{A}_0^{T}s+y\\ {\left(R_2^{*}\right)}^T{A}_0^{T}s+{\left(R_2^{*}\right)}^{T}y\end{array}\right)=\left(\begin{array}{c}{A}_0^{T}s+y\\ {\left(A_0{R}_2^{*}\right)}^{T}s+{\left(R_2^T\right)}^{T}y\end{array}\right)={\left(F_{B_{l^{*}}}\right)}^{T}s+\left(\begin{array}{c}y\\ {\left(R_2^{*}\right)}^{T}y\end{array}\right)$

并且等式的右边是游戏3中有效的挑战密文的c₁，c₂部分。我们也注意到， 这恰好是游戏3中挑战密文的c₀部分。

当O＝O_$，v₀是均匀分布在上的，v^*是均匀分布在上的。因此，上 述步骤3中定义的是均匀且独立分布在是均匀且独立分布在因此，挑战密文总是均匀分布在上的，和游戏4中的一样。

猜测：之后允许进行额外的询问，敌手进行猜测。如果敌手赢得游戏，则挑 战者借助敌手解决了LWE问难问题。

我们已经讨论过，当O＝O_$，敌手的角度和游戏4一样，当O＝O_s，敌手的角 度和游戏3一样。因此，解决LWE问题的挑战者的优势和敌手区分游戏3和 游戏4的优势是一样的。这就完成了算法B的描述，并且完成了我们的证明。