1.   引言

云存储可以为用户提供存储服务，而云计算可以通过整合用户上传到云中的资源来为用户提供各种计算服务。云计算在为用户提供服务的同时，也存在着各种安全风险，如用户的数据安全^[1]。1998年，Blaze等人^[2]提出了代理重加密的概念。代理重加密实现了非可信第3方在不解密的情况下，可以将一个用户的密文转化为其他用户的密文，保证了开放网络中数据的安全性和隐私性。这种特殊的转换性质使得代理重加密在云计算环境下的密文共享方面有着重要的应用。在一个代理重加密模型中，包含3个参与者，授权人，被授权人，代理人。授权人通过自己的私钥和被授权人的信息，产生一个秘密信息，作为代理人的代理私钥，代理人使用代理密钥把授权人的密文变换成被授权人的密文，而代理人并不能从代理密钥和用户密文中得到明文和用户的私钥的任何信息。文献[2]中提出了第1个代理重加密方案。Green等人^[3]提出了第1个单向的基于身份的代理重加密方案。之后，一系列基于身份的代理重加密方案被设计出来^[4,5]。然而，这些方案都是基于计算数论困难问题(如整数分解问题，离散对数问题)的，在量子计算环境下是不安全的。因此需要考虑抗量子计算能力的代理重加密方案的设计。格密码是设计抗量子攻击方案的一个很好的选择。Xagawa^[6]提出了第1个基于格的多次使用的双向代理重加密方案。接着基于格的代理重加密方案与特殊性质的方案陆续被提出^[7–12]。虽然基于格公钥的代理重加密方案取得了一些结果，但基于身份的方案却很少，并且都是随机预言机模型下的。因此，本文的目标是构造一个格上高效的标准模型下基于身份的代理重加密方案。

2.   基础知识

2.1   格

设${{B}} = \left\{ {{{{b}}_1}, {{{b}}_2}, ·\!·\!·, {{{b}}_m}} \right\} \in {\mathbb{Z}^{m \times m}}$是一个$m \times m$阶矩阵，且${{{b}}_1}, {{{b}}_2}, ·\!·\!· , {{{b}}_m} \in {\mathbb{Z}^m}$线性无关。则称向量${{{b}}_1}, {{{b}}_2}, ·\!·\!· , {{{b}}_m}$的所有整系数线性组合所构成的集合为一个$m$维格$\varLambda$，即

这里，${{{b}}_1}, {{{b}}_2}, ·\!·\!· , {{{b}}_m}$构成了格$\varLambda$的一组基。下面给出一类常用的整数格(正交格)。

定义 1　设q是一个素数，${{A}} \in \mathbb{Z}_q^{n \times m}$, ${{u}} \in \mathbb{Z}_q^n$，定义

引理 1^[13]　设$q \ge 3$是一个奇数且$m = \left\lceil {6n\log_2 q} \right\rceil$，则利用陷门生成算法${\rm{TrapGen}}\left( {{1^n}} \right)$，产生矩阵${{A}} \in \mathbb{Z}_q^{n \times m}$和${{T}} \in \mathbb{Z}_q^{m \times m}$，其中${{A}}$在$\mathbb{Z}_q^{n \times m}$上的分布与均匀分布是不可区分的，${{T}}$是格$\varLambda _q^ \bot \left( {{A}} \right)$的一组基，且满足$|\!\!\;| {\widetilde {{T}}} |\!\!\;| \!\le\! O\left( {\sqrt {n\log_2 q} } \right)$, $|\!\!\;| {{T}} |\!\!\;| \le O\left( {n\log_2 q} \right)$，这里$\widetilde {{T}}$是${{T}}$的施密特正交化矩阵，$|\!\!\;| {{T}}|\!\!\;|$是矩阵${{T}}$的欧几里得范数。

定义 2　${\rm{LW}}{{\rm{E}}_{q, \chi }}$判定问题：设q是一个素数，n是一个正整数。${A_{s, \chi }}$是变量为$({{a}}, {{{a}}^{\rm T}}{{s}} + {{x}})$的分布，这里${{a}} \leftarrow \mathbb{Z}_q^n$, ${{s}} \leftarrow \mathbb{Z}_q^n$是均匀随机选择的，$x \leftarrow \chi$, $\chi$是$\mathbb{Z}_q^{}$上的分布。${\rm{LW}}{{\rm{E}}_{q, \chi }}$判定问题是区分分布${A_{s, \chi }}$和$\; \mathbb{Z}_q^n \times {\mathbb{Z}_q}$上的均匀分布。

2.2   离散高斯

离散高斯分布与高斯抽样算法是在随机格上设计方案的重要定义与算法，下面简单介绍离散高斯分布的定义以及关于高斯抽样算法的几个相关引理。

对于${{c}} \in {\mathbb{Z}^m}$, $\sigma > 0$, m维格$\varLambda$上的离散高斯分布定义为

引理 2^[14]　设$q \ge 2$，矩阵${{A}} \in \mathbb{Z}_q^{n \times m}$, $m > n$。${{{T}}_{{A}}}$是格$\varLambda _q^ \bot \left( {{A}} \right)$的一组基，$\sigma \ge |\!\!\;| {{{\tilde {{T}}}_{{A}}}} |\!\!\;| \cdot \omega \left( {\sqrt {\log_2 m} } \right)$。那么，对于${{c}} \in {\mathbb{Z}^m}$, ${{u}} \in \mathbb{Z}_q^n$有：

(1) $\Pr \left[ {{{x}} \!\leftarrow\! {D_{\varLambda _q^ \bot \left( {{A}} \right), \sigma }}:\left\| {{x}} \right\| \!>\! \sigma \sqrt m } \right] \!\le\! {\rm{negl}}\left( n \right)$；

(2) 存在算法${\rm{SamplePre}}\left( {{{A}}, {{{T}}\!\!_{{A}}}, {{u}}, \sigma } \right)$，输出一个$\varLambda _q^u\left( {{A}} \right)$中的向量${{x}}$，且${{x}}$的分布与分布${D_{\varLambda _q^{{u}}\left( {{A}} \right), \sigma , {{c}}}}$是不可区分的。

引理 3^[14]　设$n$和$q$是正整数，且$q$是素数，$m \ge 2n\log_2 q$。那么对于${{A}} \in \mathbb{Z}_q^{n \times m}$, $\sigma \ge \omega \left( {\sqrt {\log_2 m} } \right)$, ${{e}} \leftarrow {D_{{\mathbb{Z}^m}, \sigma }}$，则${{u}} = {{Ae}}od q$的分布统计接近于$\mathbb{Z}_q^n$上的均匀分布。

引理 4^[15]　设$\varLambda \subseteq {\mathbb{Z}^m}$是一个格，$\sigma \in \mathbb{R}$。对于$i = 1, 2, ·\!·\!· , k, {{{v}}_i} \in {\mathbb{Z}^m}$。${X_i}$是从${D_{\varLambda + {{{v}}_i}, \sigma }}$中抽取的两两线性无关的随机变量。设${{c}} = \left( {{c_1}, {c_2}, ·\!·\!· , {c_k}} \right) \in {\mathbb{Z}^k}$，定义$g: = \gcd \left( {{c_1}, {c_2}, ·\!·\!· , {c_k}} \right)$, ${{v}}: = \displaystyle\sum\nolimits_{i = 1}^k {{c_i}{{{v}}_i}}$。对于可忽略的$\varepsilon$, $\sigma > \left\| {{c}} \right\| \cdot {\eta _\varepsilon}\left( \varLambda \right)$，那么$Z = \displaystyle\sum\nolimits_{i = 1}^k {{c_i}{X_i}}$的分布统计接近于${D_{g\varLambda + {{v}}, \left\| {{c}} \right\|\sigma }}$。

上述3个引理用在方案的安全性证明中，来说明模拟的系统与真实的系统是不可区分的。

3.   基于身份的代理重加密

3.1   方案介绍

(1)主密钥生成：输入安全参数${1^n}$，运行陷门生成算法${\rm{TrapGen}}\left( {{1^n}} \right)$产生一个随机的矩阵${{A}} \in \mathbb{Z}_q^{n \times m}$和格$\varLambda _q^ \bot \left( {{A}} \right)$的一个小范数矩阵${{T}} \in {\mathbb{Z}^{m \times m}}$作为格的陷门基，且$|\!\!\;| {\widetilde {{T}}} |\!\!\;| \le O\left( {\sqrt {n\log_2 q} } \right)$。函数${f\!\!_{A}}\left( {{x}} \right) = {{Ax}}od q$($f:{\mathbb{Z}^m} \to \mathbb{Z}_q^n$)。随机选择l+1个随机且线性无关的向量${{{u}}_0}, {{{u}}_1},·\!·\!· , {{{u}}_l} \in {\mathbb{Z}^n}$。那么主公钥为${\rm{MPK}} = ({{A}},{{{u}}_0},{{{u}}_1}, ·\!·\!· ,{{{u}}_l})$，主私钥为${\rm{MSK}} = {{T}}$。

(2)用户私钥提取：输入主公钥MPK、主私钥MSK和用户的身份${{id}} = ({\rm{id}}_1, {\rm{id}}_2, ·\!·\!·, {\rm{id}}_l) \in {\left\{ {0, 1} \right\}^l}$，提取用户私钥如下：(a)计算${{u}} = {{{u}}_0} + \displaystyle\sum\nolimits_{i = 1}^l {{\rm{id}}_i} {{{u}}_i}$; (b)给定高斯参数$\sigma \left(\left(1 + \displaystyle\sum\nolimits_{i = 1}^l {\rm{id}}_i\right)\biggr/(l + 1)\right)$，利用原像抽样算法产生一个向量${{e}}$满足${{Ae}} = {{u}} =$${{{u}}_0} \ + \ \displaystyle\sum\nolimits_{i = 1}^l {{\rm{id}}_i} {{{u}}_i}$且$|\!\!\;| {{e}} |\!\!\;| \le \sigma \left(\left(1 \ +\ \displaystyle\sum\nolimits_{i = 1}^l {\rm{id}}_i\right) \right.$$\Bigr/(l + 1)\biggr) \sqrt m {。}$因此，用户id的私钥为e。

(3)代理重加密密钥生成：对于用户${{id}}_1$与${{id}}_2$，其对应的私钥为${{{e}}_{{{id}}_1}}$与${{{e}}_{{{id}}_2}}$，计算${{\rm rk}_{{\bf{id}}_1 \leftrightarrow {{id}}_2}} = {{{e}}_{{{id}}_1}} - {{{e}}_{{{id}}_2}}$作为代理重加密密钥。

(4)加密：输入主公钥MPK，用户身份${{id}}_1 = ({\rm{id}}_{11}, {\rm{id}}_{12}, ·\!·\!· , {\rm{id}}_{1l})$和一个消息比特$\mu \in \left\{ {0, 1} \right\}$，加密如下：(a)计算${{u}} = {{{u}}_0} + \displaystyle\sum\nolimits_{i = 1}^l {{\rm{id}}_i} {{{u}}_i}$; (b)选择一个随机的向量${{s}}$，计算${{y}}={{{A}}^{\rm T}}{{s}}+{{x}}$, $c={{{u}}^{\rm{T}}}{{s}}+x +$$\mu \left\lfloor {q/2} \right\rfloor$，这里${{x}} \leftarrow \varPhi _\alpha\!\!\!^m$, $x \leftarrow {\varPhi _\alpha }$。(c)输出密文$\left( {{{y}}, c} \right)$。

(5)重加密：输入重加密密钥${{\rm rk}_{{{id}}_1 \leftrightarrow {\bf{id}}_2}}\!\!=\! {{{e}}_{{{id}}_1}}\! \!-\! {{{e}}_{{{id}}_2}}$，用户${{id}}_1 = ({\rm{id}}_{11}, {\rm{id}}_{12}, ·\!·\!· , {\rm{id}}_{1l})$的密文$\left( {{{y}}, {c_{{{id}}_{{1}}}}} \right)$，代理者利用代理重加密密钥计算${c_{{{id}}_2}} = {c_{{{id}}_1}} - {\rm rk}_{{{id}}_1 \leftrightarrow {{id}}_2}^{\rm T}{{y}}$，输出用户${{id}}_2 = ({\rm{id}}_{21}, {\rm{id}}_{22}, ·\!·\!· , {\rm{id}}_{2l})$的密文$\left( {{{y}}, {c_{{{id}}_2}}} \right)$。

(6)解密：输入用户${{id}}_2 = ({\rm{id}}_{21}, {\rm{id}}_{22}, ·\!·\!· , {\rm{id}}_{2l})$的私钥${{{e}}_{{\bf{id}}_2}}$，计算${c_{{{id}}_2}} - {{e}}_{{{id}}_2}^{\rm T}{{y}}$，若结果接近0，则输出0，若结果接近$\left\lfloor {q/2} \right\rfloor$，则输出1。

3.2   正确性与参数设置

对于一个密文$\left( {{{y}}, c} \right)$，解密过程为

若$t$接近0，则输出0，若结果接近$\left\lfloor {q/2} \right\rfloor$，则输出1。

对于一个重加密密文$\left( {{{y}}, {c_{{\bf{id}}_2}}} \right)$，解密过程为

因此，若$t$接近0，则输出0，若结果接近$\left\lfloor {q/2} \right\rfloor$，则输出1。

对于方案的正确性，参数应该满足如下条件：

(1)为了满足陷门生成算法TrapGen的需要，我们设置$m > 6n\log_2 q$，并且$q = {\rm{ploy}}(n)$，这里ploy$(n)$表示$n$的多项式；

(2)为了满足私钥提取算法的需要，要求$\sigma \ge |\!\!\;|\widetilde {{T}}|\!\!\;| \cdot \omega (\sqrt {\log_2 n} )$；

(3)为满足文献[14]中对偶加密算法的正确性，要求$q > 5\sigma (m + 1)$且$\alpha < 1/\sigma \sqrt m \omega (\log_ 2{m})$；

(4)在陷门生成算法中，要求$\left\| {\tilde {{T}}} \right\| \le$$O\left( {\sqrt {n\log_2 q} } \right)$；

因此，设置参数如下：$m = 6n\left\lceil {\log _2q} \right\rceil$, $q = {n^3}$, $\sigma = m\cdot\omega (\log _2n)$, $\alpha = 1/(l + 1)\sigma m\omega (\log_2 m)$，这里$l < n$是用户身份的长度。

3.3   安全性分析

定理1(多次使用性)　该方案满足多次使用性。

证明　考虑$k$个用户$1, 2, ·\!·\!· , k$，假设$\left( {{{y}}, {c_1}} \right)$是用户1的密文，从$1-k$的重加密过程为

其中，$x'=x - {{e}}_1^{\rm T}{{x}} + {{e}}_k^{\rm T}{{x}}$。显然$\left( {{{y}}, {c_k}} \right)$是用户$k$的密文。由于${{{e}}_1}$, ${{{e}}_k}$, ${{x}}$是小范数向量，$x$是较小的整数，因此$x'$也是一个较小的整数，所以$\left( {{{y}}, {c_k}} \right)$可以正确解密。 证毕

定理2 (安全性)　假设参数设置为3.2节所示，并且LWE问题是困难的，则该代理重加密方案在标准模型下是IND-aID-CPA安全的。

证明　 在证明过程中，需要使用游戏的方式来证明一个多项式时间敌手攻击该方案的优势是可忽略的。下面需要证明3个游戏(Game)对于多项式时间敌手来说是不可区分的。

游戏1　该游戏是标准的适应性选择身份的选择明文攻击安全(IND-aID-CPA)的方案。

初始阶段：输入安全参数${1^n}$，运行陷门生成算法${\rm{TrapGen}}\left( {{1^n}} \right)$产生一个随机的矩阵${{A}} \in \mathbb{Z}_q^{n \times m}$和格$\varLambda _q^ \bot \left( {{A}} \right)$的一个小范数矩阵${{T}} \in {\mathbb{Z}^{m \times m}}$作为格的陷门基，且$|\!\!\;| {\widetilde {{T}}} |\!\!\;| \le O\left( {\sqrt {n\log_2 q} } \right)$。函数${f\!_{A}}\left( {{x}} \right) =$${{Ax}}od q$($f:{\mathbb{Z}^m} \to \mathbb{Z}_q^n$)。随机选择l+1个随机且线性无关的向量${{{u}}_0}, {{{u}}_1}, ·\!·\!·, {{{u}}_l} \in {\mathbb{Z}^n}$。最后把公开参数${{A}} \in \mathbb{Z}_q^{n \times m}$, ${{{u}}_0}, {{{u}}_1}, ·\!·\!· , {{{u}}_l} \in {\mathbb{Z}^n}$发送给敌手$\cal{A}$。

阶段1：在这个阶段，敌手$\cal{A}$在得到公开参数后，可以进行密钥提取询问、重加密密钥询问(敌手询问到重加密密钥后可自行进行重加密操作，因此不需要进行重加密询问)，真实系统回答提问如下：

密钥提取询问：敌手询问用户id的密钥，真实系统计算${{u}} = {{{u}}_0} + \displaystyle\sum\nolimits_{i = 1}^l {{{\rm id}}_i} {{{u}}_i}$；给定高斯参数$\sigma \left(\left(1 + \displaystyle\sum\nolimits_{i = 1}^l {{\rm id}}_i\right)\biggr/(l + 1)\right)$，利用原像抽样算法产生一个向量${{e}}$满足${{Ae}} = {{u}} = {{{u}}_0} + \displaystyle\sum\nolimits_{i = 1}^l {{{\rm id}}_i} {{{u}}_i}$且$|\!\!\;| {{e}} |\!\!\;| \le \sigma \left(\left(1 + \displaystyle\sum\nolimits_{i = 1}^l {{\rm id}}_i\right)\biggr/(l + 1)\right) \sqrt m$。发送${{e}}$给敌手$\cal{A}\,$作为用户id的私钥。

重加密密钥询问：敌手$\cal{A}$询问用户${{id}}_1$与${{id}}_2$之间的代理重加密密钥，系统查询其对应的私钥为${{{e}}_{{{id}}_1}}$与${{{e}}_{{{id}}_2}}$，计算${{\rm rk}_{{{id}}_1 \leftrightarrow {{id}}_2}} = {{{e}}_{{{id}}_1}} - {{{e}}_{{{id}}_2}}$作为代理重加密密钥发送给敌手$\cal{A}$。

挑战阶段：当挑战者收到$({{id}}^*, {\mu _0}, {\mu _1})$，挑战者选择一个随机的$b \in \left\{ {0, 1} \right\}$，计算${{y}}={{{A}}^{\rm T}}{{s}}+{{x}}$，${c^*}={{u}}_{{{id}}^*}^{\rm T}{{s}}+x + {\mu _b}\left\lfloor {q/2} \right\rfloor$，并发送${{{c}}^*} = ({{y}}, {c^*})$给敌手$\cal{A}$。最后$\cal{A}$给出猜测$b'$，若$b' = b$，则挑战者输出1，否则输出0。

游戏2　在这个游戏中，游戏2与游戏1的区别是矩阵${{A}}$与向量${{{u}}_0}, {{{u}}_1}, ·\!·\!· , {{{u}}_l}$的生成方法。在游戏2中挑战者$\cal{C}$要模拟真实的方案，并且需要回答攻击者$\cal{A}$的各种询问。首先挑战者模拟真实的方案如下：

初始阶段：挑战者$\cal{C}$随机选择一个随机矩阵${{A}} \leftarrow \mathbb{Z}_q^{n \times m}$，计算l+1个${{{u}}_0}, {{{u}}_1}, ·\!·\!· , {{{u}}_l} \in \mathbb{Z}_q^n$。计算步骤为：

(1)挑战者首先按照高斯分布${D_{\sigma /(l + 1), 0}}$随机选择$l + 1$个矩阵${{{e}}_0}, {{{e}}_1}, ·\!·\!· , {{{e}}_l}$；

(2)挑战者计算${{A}}{{{e}}_i}\,(od q) = {{{u}}_i}$, $i \!=\! 0, 1, ·\!·\!· , l$；

(3)检查${{{u}}_i}$是否是线性无关的，如果不是，则重复步骤(1)。

挑战者$\cal{C}$将初始阶段产生的公开参数${{A}} \in \mathbb{Z}_q^{n \times m},$${{{u}}_0}, {{{u}}_1}, ·\!·\!· , {{{u}}_l} \in {\mathbb{Z}^m}$发送给攻击者$\cal{A}$。

阶段1：敌手$\cal{A}$在得到公开参数后，可以进行密钥提取询问、重加密密钥询问(敌手询问到重加密密钥后可自行进行重加密，因此不需要进行重加密询问)，挑战者$\cal{C}$回答敌手$\cal{A}$的询问如下：

(1)密钥提取询问：敌手$\cal{A}$发送身份${{id}}_i$给挑战者，挑战者计算${{{e}}_{\,{{\rm id}}_i}} \!\!=\! {{{e}}_0} \!+\!\! \displaystyle\sum\nolimits_{i = 1}^l \!\!\!{{{\rm id}}_i} {{{e}}_i}$, ${{{e}}_i} \!\leftarrow\!\!\! {D_{\sigma /(l \!+\! 1), 0}}$，由引理4可知，${{{e}}_{{{\rm id}}_i}} \!\!\leftarrow\!\! {D_{\sigma \cdot \sum\nolimits_{i = 0}^l {{{\rm id}}_i} /(l + 1), 0}}$。由于${{A}}{{{e}}_i}\,(\!od q)$$= {{{u}}_i}$，因此${{A}}{{{e}}_{{{id}}_i}}(od q) = {{{u}}_0} + \displaystyle\sum\nolimits_{i = 1}^l {{{\rm id}}_i} {{{u}}_i}$。挑战者发送${{{e}}_{{{id}}_i}} = {{{e}}_0} + \displaystyle\sum\nolimits_{i = 1}^l {{{\rm id}}_i} {{{e}}_i}$给敌手$\cal{A}$作为用户身份${{id}}_i$的私钥。

(2)重加密密钥询问：敌手$\cal{A}$发送$({{id}}_i, {{id}}_j)$给挑战者，则挑战者利用上述方法计算${{{e}}_{{{id}}_i}}$和${{{e}}_{{{id}}_j}}$，并计算${{\rm rk}_{{{id}}_i \leftrightarrow {{id}}_j}} = {{{e}}_{{{id}}_i}} - {{{e}}_{{{id}}_j}}$给敌手$\cal{A}$。

阶段2(挑战阶段)：当挑战者收到$({{id}}^*, {\mu _0}, {\mu _1})$，挑战者选择一个随机的$b \in \left\{ {0, 1} \right\}$，计算${{y}}={{{A}}^{\rm T}}{{s}}+$${{x}}$, ${c^*}={{u}}_{{{id}}^*}^{\rm T}{{s}} + x + {\mu _b}\left\lfloor {q/2} \right\rfloor$，并发送${{{c}}^*} = ({{y}}, {c^*})$给敌手$\cal{A}$。最后$\cal{A}$给出猜测$b'$，若$b' = b$，则挑战者输出1，否则输出0。

游戏3　在这个游戏中，与游戏2的区别是挑战密文的生成。在游戏2中，挑战密文${{{c}}^*} = ({{y}}, {c^*})$是使用加密算法产生的，即${{y}}={{{A}}^{\rm T}}{{s}}+{{x}}$, ${c^*}=$${{u}}_{{{id}}^*}^{\rm T}{{s }}+ x + {\mu _b}\left\lfloor {q/2} \right\rfloor$。在游戏3中，挑战密文${{{c}}^*}$是从$\mathbb{Z}_q^n \times {\mathbb{Z}_q}$中随机选取的。

若游戏2与游戏1不可区分，且游戏3与游戏2也是不可区分的，则该代理重加密方案在标准模型下是IND-aID-CPA安全的。 证毕

下面将通过两个引理来说明游戏2与游戏1是不可区分的，游戏3与游戏2是不可区分的。

引理 5　游戏2与游戏1是不可区分的，并且对于敌手的询问回答与真实的方案也是不可区分的。

(1)在游戏1中，矩阵${{A}} \in \mathbb{Z}_q^{n \times m}$是利用陷门生成算法${\rm{TrapGen}}\left( {{1^n}} \right)$生成的，并且是随机的。在游戏2中，${{A}}$是从$\mathbb{Z}_q^{n \times m}$中随机选取的。因此公开参数${{A}}$对于敌手看来是不可区分的。

(2)在游戏1中，公开参数${{{u}}_0}, {{{u}}_1}, ·\!·\!· , {{{u}}_l} \leftarrow \mathbb{Z}_q^n$是随机选择的；在游戏2中，${{{u}}_0}, {{{u}}_1},·\!·\!· , {{{u}}_l}$的生成是由算法${{A}}{{{e}}_i}\,(od q) = {{{u}}_i}$产生的，由引理3可知，${{A}}{{{e}}_i}\,(od q) = {{{u}}_i}$的分布统计接近于$\mathbb{Z}_q^n$上的均匀分布。因此公开参数${{{u}}_0}, {{{u}}_1}, ·\!·\!·, {{{u}}_l}$对于敌手看来也是不可区分的。

(3)对于密钥提取询问，在游戏1中，用户密钥${{{e}}_{{{id}}}}$是利用陷门使用原像抽样算法产生的，满足$A{{{e}}_{{{\rm id}}}} = {{u}} = {{{u}}_0} + \displaystyle\sum\nolimits_{i = 1}^l {{{\rm id}}_i} {{{u}}_i}$且$\left\| {{{{e}}_{{{id}}}}} \right\| \le$$\sigma\left(\left(1 + \displaystyle\sum\nolimits_{i = 1}^l {{\rm id}}_i\right)\!\biggr/(l + 1)\right) \sqrt m$。在游戏2中，用户密钥${{{e}}_0}, {{{e}}_1}, ·\!·\!· , {{{e}}_l}$是挑战者按照高斯分布${D_{\sigma /(l + 1), 0}}$抽取出来的，因此对于模拟的用户密钥${{{e}}_{{{\rm id}}}}$满足$\left\| {{{{e}}_{{id}}}} \right\| \le \sigma \left(\left(1 + \displaystyle\sum\nolimits_{i = 1}^l {{\rm id}}_i\right)\biggr/(l + 1)\right) \sqrt m$，且根据${{{u}}_0}, {{{u}}_1}, ·\!·\!· , {{{u}}_l}$的生成，满足${{A}}{{{e}}_i}\,(od q) = {{{u}}_i}$, $i = 0, 1, ·\!·\!· , l$。因此挑战者对于用户提取询问的回答对于敌手看来与游戏1中是不可区分的。

(4)对于重加密密钥询问，在游戏1中，代理重加密密钥的计算${{\rm rk}_{{{id}}_i \leftrightarrow {{id}}_j}} = {{{e}}_{{{id}}_i}} - {{{e}}_{{{id}}_j}}$。而在游戏1中也是以同样的方法计算的，因此挑战者对于重加密密钥的回答对于敌手看来与游戏1中是不可区分的。

因此，游戏1与游戏2对于攻击者是不可区分的。

引理 6　 游戏3与游戏2是不可区分的。

用反证法来证明游戏3与游戏2是不可区分的。假设敌手$\cal{A}$具有不可忽略的优势$\varepsilon$来区分游戏3与游戏2，则可以构造一个算法$\cal{B}$来解决LWE判定问题。

$\cal{B}$收到m个随机实例$({{{a}}_i}, {y_i}) \in \mathbb{Z}_q^n \times {\mathbb{Z}_q}$，令${{A}} = ({{{a}}_1}, {{{a}}_2}, ·\!·\!· {{{a}}_m})$, ${{y}} = ({y_1}, {y_2}, ·\!·\!· {y_m})$。计算${c^*} =$${\left( {{{{e}}_0} + \displaystyle\sum\nolimits_{i = 1}^l {{\rm{id}}_i{{{e}}_i}} } \right)^{\rm{T}}}{{{A}}^{\rm{T}}}{{y}} + x + {\mu _b}\left\lfloor {q/2} \right\rfloor$，令${{{c}}^*} =$$\left( {{{y}}, {c^*}} \right)$。如果敌手$\cal{A}$猜测了正确的b，则挑战者输出1，否则输出0。

如果随机实例$({{{a}}_i}, {y_i}) \in \mathbb{Z}_q^n \times {\mathbb{Z}_q}$是均匀随机生成的，则挑战密文${{c}^*}$也是均匀随机的，因此$\cal{B}$输出1的概率至多为1/2。

如果随机实例$({{{a}}_i}, {y_i}) \in \mathbb{Z}_q^n \times {\mathbb{Z}_q}$是LWE实例，即${{y}} = ({y_1}, {y_2}, ·\!·\!· {y_m}) = ({{{A}}^{\rm T}}{{s}} + {{x}})od q$，则挑战密文${{{c}}^*}$也是均匀随机的。这和采用加密算法得到的密文分布是相同的。在这种情况下，敌手$\cal{A}$猜测正确的b的概率为$(1 + \varepsilon )/2$，其中，$\varepsilon$是一个不可忽略的量。即$\cal{B}$输出1的概率也是$(1 + \varepsilon )/2$。

综上可知，$\cal{B}$至少以$\varepsilon ' = (1 + \varepsilon )/2 - 1/2 = \varepsilon /2$的概率求解LWE判定问题。

由于LWE判定问题是一个困难问题，因此游戏3与游戏2是不可区分的。

因此，由引理5和引理6可知，该方案在标准模型下是IND-aID-CPA安全的。

4.   安全与效率分析

该方案将用户的身份直接映射到一个向量，使得方案的主公钥、用户私钥与密文尺寸较短，存储空间较小。下面将该方案与格上其他相关方案的安全性、运行效率和存储空间进行比较，表1为存储空间与安全模型的比较结果，表2为计算效率的比较结果。

表 1  存储空间及安全模型比较

	主公钥尺寸	用户私钥尺寸	密文尺寸	安全模型
本文方案	O((m+l)nlog2q)	O(mlog2q)	O(mlog2q)	标准模型
文献[9]	O(nmlog2q)	O(mlog2q)	O(mlog2q)	随机预言机模型
文献[10]	O(nmlog2q)	O(nmlog2q)	O(mlog2q)	随机预言机模型

下载: 导出CSV 

| 显示表格

表 2  计算效率比较

	私钥生成	加密	重加密	解密
本文方案	O(n2)	O(n2)	O(n)	O(n)
文献[9]	O(n2)	O(n2)	O(n)	O(n)
文献[10]	O(n2)	O(n2)	O(n2)	O(n3)

下载: 导出CSV 

| 显示表格

通过表1与表2的比较可以发现，本方案在标准模型下的主公钥、用户私钥与密文尺寸和随机预言机模型下的主公钥、用户私钥、密文尺寸相当，而在计算效率上却没有降低。

5.   结束语

本文采用原像抽样技术提出了一个标准模型下高效的格上基于身份的代理重加密方案。在方案中，用户的身份被编码为一个向量，与传统的格上基于身份的方案中用户私钥的提取技术相比，效率较高。该方案具有双向性，多次使用性等性质。最后证明了在LWE困难假设下是适应性选择身份的选择明文安全的。