云存储和计算以较大的存储容量、灵活的可访问性、和高效的数据管理等优势被引入来解决庞大数据的存储与计算需求. 通过将敏感数据外包给云服务器，个人和企业减轻了本地数据管理和维护的负担. 为了保证存储数据的隐私性和安全性，数据所有者在将共享数据外包给云服务器之前会进行加密处理. 然而，在此情境下，用户面临着在海量数据中难以执行关键字搜索的挑战，这在一定程度上阻碍了云环境下文件共享的灵活性. 因此，如何安全、高效地检索云数据变得尤为重要. 可搜索加密^[1-2]技术允许通过搜索某些关键字来检索目标加密文件. 在对称设置下，用户可以通过宋晓东等人^[1]提出的可搜索加密（searchable encryption，SE）方案检索加密数据. 在非对称设置下，Boneh等人^[2]提出了一种新的变体，称为公钥可搜索加密（public key encryption with keyword search， PEKS）.

PEKS在确保许多应用程序的隐私的同时，提供了搜索功能. 作为说明，本研究考虑在云计算中的1个示例，如图1所示. 自文献[2]引入PEKS方案以来，大多数PEKS格式都是使用双线性映射（例如文献[3-5]）和其他经典数论工具（例如文献[6-7]）构造的. 本研究选取周晓彤等人^[8]提出的基于计算Diffie-Hellman（computational Diffie-Hellman，CDH）问题的可搜索加密方案（ZHN+方案^[8]）作为典型代表. 然而，上述大多数方案容易受到量子攻击. 因此，研究人员陆续提出了一些基于格的PEKS方案（例如文献[9-12]）.

图  1  PEKS方案的示意图

Figure  1.  Illustration of PEKS scheme

下载: 全尺寸图片 幻灯片

在快速发展的云计算时代，PEKS是在保留可搜索功能的同时确保隐私的重要工具. 动态对称可搜索加密允许用户向服务器动态插入和删除文件. 但是，这些更新操作在搜索和更新查询期间会产生泄露. 具体来说，服务器可能会将新更新的文件与以前的搜索结果相关联，因此提出了前向安全^[13]的概念. 当新文件被加入数据库时，服务器能利用过往搜索记录中的关键字，来检查这些关键字是否与新文件相匹配. 这一机制使得服务器能够判断新添加的文件是否涵盖了之前搜索过的关键字. 文献[13]表明这种泄露可能导致严重的隐私问题. 另一方面，后向安全^[14]侧重于删除时搜索查询的泄露. 它确保服务器在后续搜索之前不会了解已删除文件的信息. 除了上述障碍之外，部署PEKS还将面临一些挑战. 随着移动智能终端设备的爆炸性使用，现有的大多数PEKS方案都存在密钥暴露问题^[15]. 一旦数据使用者的私钥被泄露，攻击者就可以泄露数据使用者之前提交的陷门的内容，外包数据的机密性因此被破坏. 另外，PEKS计算开销最大的部分是从整个数据库中检索目标数据，因为在搜索过程中，云服务器需要对每个关键字执行匹配. 由于代价高昂的公钥加密操作（如双线性配对和模幂运算），现有的PEKS方案引入了昂贵的计算和存储开销.

为了解决上述问题，本研究首先提供了一种具有低密钥和陷门存储开销、高计算效率的PEKS方案. 另外，本研究构建了一种具有前向安全和后向安全的扩展PEKS方案.

本文的主要贡献包括3个方面：

1）本文提出了一种优化的PEKS方案. 本文提出的方案基于环上错误学习问题，因此具有后量子安全性. 方案使用一种新的近似原像采样^[16-17]算法提高陷门的效率. 然后，本研究结合非球面高斯采样技术^[18]和理想可扩展输出函数来进一步降低密钥和陷门的存储开销.

2）本文提出了一种具有前向安全和后向安全的扩展PEKS方案. 本研究将每个私钥都连接到1个特定的时间段，通过定期更新密钥来实现前向安全. 本研究使用基于RLWE的同态加密方案^[19]对位图索引^[20]进行加密和更新，以实现后向安全.

3）理论分析和实验评估表明，与现有高效的PEKS方案相比，本文提出的PEKS方案降低了4.6%的公钥存储开销和50.1%的陷门存储开销，在加密、陷门生成和搜索上的效率分别提升了11.11%，2.5%，26.15%.

1.   相关工作

1.1   基于格的可搜索加密

构造基于格PEKS方案的一种一般方法是使用选择明文攻击下的不可区分性（indistinguishability under chosen plaintext attack，IND-CPA）安全的匿名基于身份的加密（identity-based encryption，IBE）方案. Boneh等人^[2]提出了从匿名IBE到PEKS方案的转换. 基于该框架，Abdalla等人^[15]进一步指出匿名IBE可以转换为PEKS方案，PEKS方案在计算上是一致的，并且满足IND-CPA的安全性. 在文献[15]的转换之后，Behnia等人^[21]提出了基于NTRU的PEKS方案（BOYa方案^[21]）和基于错误学习问题（learning with errors， LWE）的PEKS方案（BOYb方案^[21]）. 顾纯祥等人^[9]在标准模型下基于LWE问题设计了PEKS方案. 杨旸等人^[11]引入了一种基于LWE的语义关键字可搜索加密方案. 文献[22]基于环上错误学习问题^[23-24]提出了PEKS方案（QZ方案^[22]）. 该方案使用了满秩差分（full-rank differences，FRD）哈希函数^[25]、文献[26-27]中基于小工具的陷门构造等技术，具有更低的端到端延迟和更高的计算效率. 王鹏等人^[28]提出了一种基于格的具有访问控制的公钥搜索加密方案（WCX+方案^[28]）. 所有这些基于格的方案使得PEKS在云计算中发挥更大的潜力.

1.2   具有前向安全和后向安全的可搜索加密

在一些可搜索加密方案中，云服务器立即知道新添加的加密数据文件是否与先前的搜索查询匹配. 然而，文献[13]指出这会导致对可搜索加密的泄露滥用攻击，并可能进一步发现云服务器中加密数据文件的内容. 另外，现有的大多数PEKS方案都存在密钥暴露问题. 前向安全能够避免这些问题. 它意味着新更新的密文不能与以前的陷门匹配. 左聪等人^[29]利用一种改进的二进制树结构提出了前向安全的可搜索加密方案. 张晓均等人^[12]基于格基委托算法^[30]构造了一种基于LWE问题的前向安全PEKS方案（ZXW+方案^[12]）. 曾鸣等人^[31]和Emura^[32]都采用将搜索陷门、加密数据文件与其生成时间绑定在一起的方法实现前向安全的可搜索加密方案. 文献[33]引入了二叉树结构来实现具有前向安全的可搜索加密方案（XCC+方案^[33]）. 汤永利等人^[34]提出一种支持联合搜索的前向安全可搜索加密方案. 除了确保前向安全性外，还希望防止后续搜索泄露有关已删除文件的信息，即后向安全性. Bost等人^[14]基于约束伪随机函数和可穿刺加密方案等原语引入了几种实现前向安全和后向安全的可搜索加密方案，这些方案具有不同的效率和通信权衡. 甘庆晴等人^[35]研究了几种具有前向和后向隐私的对称可搜索加密方案. 张蓝蓝等人^[36]通过改进不经意交叉索引协议，提出了一种支持联合查询且满足前后向安全的可搜索加密方案. 黄一才等人^[37]设计了具有前向和后向隐私的向量数据存取结构，结合动态对称隐藏向量加密构造了支持连接查询的动态可搜索加密方案.

2.   预备知识

在本节中，本研究描述了在这项工作中使用的一些工具和定义.

2.1   基本定义

符号表示. 令粗体小写字母如$\boldsymbol{a},\boldsymbol{b},\boldsymbol{x},\boldsymbol{y}$等表示列向量，粗体大写字母如$\boldsymbol{A},\boldsymbol{B},\boldsymbol{T}$等表示矩阵. $\left\|\boldsymbol{a}\right\|$表示向量$\boldsymbol{a}$的欧氏范数，$\left\|\boldsymbol{A}\right\|=\underset{i}{\mathrm{max}}\left\|{\boldsymbol{a}}_{i}\right\|$表示矩阵$\boldsymbol{A}$的范数. 从分布$D$中采样$x$用$x\leftarrow D$表示，在集合$S$中均匀随机采样$x$用$x\leftarrow U\left(S\right)$表示. 令${\boldsymbol{b}}_{1},{\boldsymbol{b}}_{2},…,{\boldsymbol{b}}_{m}$为1组线性无关的向量，$\boldsymbol{B}=({\boldsymbol{b}}_{1},{\boldsymbol{b}}_{2},…,{\boldsymbol{b}}_{m})\in {\mathbb{R}}^{m\times m}$. 记满秩格

多项式环${\mathcal{R}}_{q}=\mathcal{R}/q\mathcal{R}={\mathbb{Z}}_{q}\left[x\right]/({x}^{n}+1)$ ，其中$q\equiv 1\;\mathrm{m}\mathrm{o}\mathrm{d}\;2n$.

定义1. 高斯分布. $n$维高斯函数定义为${\rho }_{\sigma ,{{\boldsymbol{z}}}}\left(\boldsymbol{x}\right) = \mathrm{e}\mathrm{x}\mathrm{p}(-{\text{π}}{\left\|\boldsymbol{x}-{{\boldsymbol{z}}}\right\|}^{2}/{\sigma }^{2})$，对于所有$\boldsymbol{x}\in {\mathbb{R}}^{n}$，其中${{\boldsymbol{z}}}\in {\mathbb{R}}^{n}$为中心，$\sigma \in \mathbb{R}$为宽度参数. ${D}_{\varLambda ,\sigma ,\boldsymbol{z}}={\rho }_{\sigma ,\boldsymbol{z}}\left(\boldsymbol{x}\right) /{\rho }_{\sigma ,\boldsymbol{z}}\left(\varLambda \right)$定义为格上的离散高斯分布，其中

定义2. 判定$\mathrm{R}\mathrm{L}\mathrm{W}\mathrm{E}$假设^[23-24]. 给定$\boldsymbol{z}={(\boldsymbol{z}}_{1},{\boldsymbol{z}}_{2},…, {\boldsymbol{z}}_{m})^{\mathrm{T}}\in {\mathcal{R}}_{q}^{m}，\beta \in \mathbb{R}$，且$\boldsymbol{b}=\boldsymbol{z}s+\boldsymbol{e}$，其中$s\leftarrow U({\mathcal{R}}_{q}),\;{\boldsymbol{e}}\leftarrow$ $D_{{\mathcal{R}}_{q}^{m},\beta }$. 判定$\mathrm{R}\mathrm{L}\mathrm{W}\mathrm{E}$（decision RLWE，D-RLWE）问题为给定实例$\boldsymbol{z}$和$\boldsymbol{b}$，区分$(\boldsymbol{z},\boldsymbol{b}=\boldsymbol{z}s+\boldsymbol{e})$和$(\boldsymbol{z},\boldsymbol{b})$在${\mathcal{R}}_{q}^{m}\times {\mathcal{R}}_{q}^{m}$上的均匀分布.

定义3. 哈希函数^[25]. 本研究使用满秩差分（full-rank differences，FRD）哈希函数^[25]$H:{\mathbb{Z}}_{q}^{n}\to {\mathcal{R}}_{q}$，将${\mathbb{Z}}_{q}^{n}$中的恒等式映射到${\mathcal{R}}_{q}$中的可逆元素. 设$n$为正整数，$q$为素数. 函数$H:{\mathbb{Z}}_{q}^{n}\to {\mathcal{R}}_{q}$是1个$\mathrm{F}\mathrm{R}\mathrm{D}$哈希函数，如果： 对于所有不同的$\boldsymbol{x},\boldsymbol{y}\in {\mathbb{Z}}_{q}^{n}$，元素$H\left(\boldsymbol{x}\right)-H\left(\boldsymbol{y}\right)\in {\mathcal{R}}_{q}$是可逆的; $H$可以在多项式时间内计算.

定义4. 格陷门结构. 非齐次SIS问题的陷门函数定义为${f}_{\boldsymbol{A}}\left(\boldsymbol{x}\right)\equiv \boldsymbol{A}\boldsymbol{x}\;\mathrm{m}\mathrm{o}\mathrm{d}\;q$. 格陷门由$m$维整数格${\varLambda }_{q}^{\perp }\left(\boldsymbol{A}\right) := \{\boldsymbol{x}\in {\mathbb{Z}}^{m}|\boldsymbol{A}\boldsymbol{x}\equiv 0\;\mathrm{m}\mathrm{o}\mathrm{d}\;q\}$的短基${\boldsymbol{T}}_{\boldsymbol{A}}\in {\mathbb{Z}}^{m\times m}$组成. 文献[22]的PEKS方案使用了文献[26-27]中基于小工具的陷门构造，本研究使用优化技术进行了改进，增强后的陷门效率更高.

定义5. 格基委托算法^[30]. 通过输入$\boldsymbol{A}\in {\mathbb{Z}}_{q}^{n\times m},\; \boldsymbol{R}\in {\mathbb{Z}}^{m\times m},\;\beta \in \mathbb{R}$，格基${\boldsymbol{T}}_{\boldsymbol{A}}\in {\mathbb{Z}}^{m\times m}$，格基委托算法$BasisDel$输出${\varLambda }_{q}^{\perp }\left(\boldsymbol{B}\right)$的格基${\boldsymbol{T}}_{\boldsymbol{B}}$，其中$\boldsymbol{B}=\boldsymbol{A}{\boldsymbol{R}}^{-1}$.

定义6. 位图索引^[20]. 位图索引是一种用长度为$j$的比特字符串$\eta$表示文件标识符的数据结构，其中$j$是可以支持的最大文件数，如果存在文件${f}_{i}$，则$\eta$的第 $i$位设置为$1$，否则设置为$0$. 注意，计数从“1”开始. 图2展示了1个$j=6$的实例. 假设存在文件${f}_{1}，{f}_{4}，{f}_{5}$，初始的比特字符串为${\eta }_{1}=100110$. 如果某用户希望添加文件${f}_{2}$，则需要生成比特字符串为${\eta }_{2}=010000$，并将其添加到${\eta }_{1}$中，如图2的①添加操作. 如果某用户要删除文件${f}_{2}$，该用户可以通过模加法来完成. 该用户转换${2}^{6}{-\eta }_{2}=110000={\eta }_{3}$，将${\eta }_{3}$添加到${\eta }_{2}$中，如图2的② 删除操作. 请注意，通过模加法可以对位图索引进行添加和删除操作.

图  2  位图索引

Figure  2.  Bitmap index

下载: 全尺寸图片 幻灯片

定义7. 基于RLWE的同态加密方案^[19]. 该方案（记为BFV）包含：密钥生成算法$KeyGen$、加密算法$Enc$、同态加法算法$Add$和解密算法$Dec\mathrm{这}$4个算法. BFV方案支持对密文的同态加法操作$\oplus$，即$Enc\left({m}_{1}\right) \oplus Enc\left({m}_{2}\right)$=Enc(${m}_{1}+{m}_{2})$.

1）密钥生成算法BFV. $KeyGen\left(\lambda \right)\to \left(PK,SK\right)$ ：采样${\boldsymbol{x}\leftarrow {\mathcal{R}}_{q}^{\partial },\;s\leftarrow D}_{{\mathcal{R}}_{q},\;\beta },\;{\boldsymbol{\varphi}\leftarrow D}_{{\mathcal{R}}_{q}^{\partial },\beta }$，计算$\boldsymbol{y}=\boldsymbol{x}s+\boldsymbol{\varphi }\;\mathrm{m}\mathrm{o}\mathrm{d}\;q$. 输出公钥$(\boldsymbol{x},\boldsymbol{y})\in {\mathcal{R}}_{q}^{2\partial }$，私钥$SK=s\in {\mathcal{R}}_{q}$.

2）加密算法BFV. $Enc(PK,m)\to \boldsymbol{t}$：为了加密消息$m\in {\mathcal{R}}_{q}$，算法采样$\boldsymbol{u}\leftarrow {\mathcal{R}}_{q}^{\partial }$，$\phi \leftarrow {D}_{{\mathcal{R}}_{q},\tau }$， $\psi \leftarrow {D}_{{\mathcal{R}}_{q},\tau }$. 计算${\mathscr{g}}_{1}={\boldsymbol{y}}^{\mathrm{T}}{\boldsymbol{u}}+\phi +\left\lfloor {q/2} \right\rfloor m\;\mathrm{m}\mathrm{o}\mathrm{d}\;q,\;{\mathscr{g}}_{2}={\boldsymbol{x}}^{\mathrm{T}}{\boldsymbol{u}}+\psi\; \mathrm{m}\mathrm{o}\mathrm{d}\;q$. 令$\boldsymbol{t}= ({\mathscr{g}}_{1},\;{\mathscr{g}}_{2})\in {\mathcal{R}}_{q}^{2}$.

3）同态加法算法BFV. $Add({\boldsymbol{t}}_{1},{\boldsymbol{t}}_{2})\to \boldsymbol{t}'$：给定密文${\boldsymbol{t}}_{1}$和密文${\boldsymbol{t}}_{2}，$计算并输出${\boldsymbol{t}}'={\boldsymbol{t}}_{1}+{\boldsymbol{t}}_{2}$.

4）解密算法$Dec(\boldsymbol{t},\boldsymbol{s})\to m$：令$\boldsymbol{t}=({\mathscr{g}}_{1},{\mathscr{g}}_{2})$，计算${m}'=\left({\mathscr{g}}_{1}-{\mathscr{g}}_{2}s\right)\mathrm{m}\mathrm{o}\mathrm{d}\;q，m=\left\lfloor {2m'/q} \right\rfloor \mathrm{m}\mathrm{o}\mathrm{d}\;2$.

2.2   系统模型和安全模型

本节将介绍PEKS系统模型，该模型具有3个实体：数据拥有者、数据使用者和云服务器.

1）数据拥有者. 被视为“诚实但好奇”的实体. 数据拥有者负责采集数据（如智能传感器采集的信息），将数据以及数据中包含的关键字进行加密，并上传到云服务器上.

2）数据使用者. 被视为“诚实但好奇”的实体. 数据接收方作为云用户，使用私钥生成与特定关键字关联的陷门，并将其发送给云服务器，以检索到预期加密的数据.

3）云服务器. 被视为“诚实但好奇”的实体. 云服务器负责系统中数据的计算和存储. 一旦从数据使用者接收到陷门，它就测试密文和陷门是否包含同一个关键字. 最终将所有匹配的加密文件发送给数据使用者.

本文主要考虑密文不可区分性（ciphertext indistinguishability），这为了避免敌手根据密文猜测出关键字的信息. 密文不可区分性是指如果攻击者没有获得关键字${w}_{0}$和${w}_{1}$的信息，攻击者很难将${w}_{0}$的密文与${w}_{1}$的密文区分开来. 密文不可区分性的定义通过挑战者$\mathcal{B}$和敌手$\mathcal{A}$之间的游戏给出：

1）初始化阶段. 给定安全参数$\lambda$，挑战者$\mathcal{B}$运行密钥生成算法输出接收方的公钥$PK$和私钥$SK.\mathcal{B}$将公钥$PK$发送给敌手，将私钥$SK$秘密保存.

2）问询阶段1. 敌手可以多项式次执行${O}_{T}$，${O}_{C}$这2个问询.

① 陷门问询${O}_{T}$. 给定关键字$\boldsymbol{w}$，问询${O}_{T}$根据接收方的公钥$PK$和私钥$SK$，运行陷门算法输出基于关键字$\boldsymbol{w}$的陷门${\boldsymbol{t}}_{\boldsymbol{w}}. {O}_{T}$将${\boldsymbol{t}}_{\boldsymbol{w}}\text{发送给}\mathcal{A}$.

② 密文问询${O}_{C}$. 给定关键字$\boldsymbol{w}$，问询${O}_{C}$根据接收方的公钥$PK$运行加密算法，输出基于关键字$\boldsymbol{w}$的密文${\boldsymbol{c}}_{\boldsymbol{w}}. {O}_{C}$将${\boldsymbol{c}}_{\boldsymbol{w}}$发送给$\mathcal{A}$.

3）挑战阶段. $\mathcal{A}$选取从未被问询过的挑战关键字$({\boldsymbol{w}}_{0}^{*},{\boldsymbol{w}}_{1}^{*})$，发送给$\mathcal{B}. \mathcal{B}$随机选取1个比特$b\in \left\{\mathrm{0,1}\right\}$，运行加密算法$Encrypt(PK,{\boldsymbol{w}}_{b}^{*})\to {\boldsymbol{c}}^{*}$，将挑战密文${\boldsymbol{c}}^{*}$发送给$\mathcal{A}$.

4）问询阶段2. 敌手可以多项式次执行${O}_{T},{O}_{C}$这2个问询，要求不能问询${\boldsymbol{w}}_{0}^{*},{\boldsymbol{w}}_{1}^{*}$.

5）猜测阶段. $\mathcal{A}$输出1个比特$b'\in \left\{\mathrm{0,1}\right\}$. 如果$b'=b$，$\mathcal{A}$赢得游戏；否则失败.

敌手$\mathcal{A}$在游戏中获胜的优势$Adv\left(\lambda \right)=$ $\left|Pr\left[b'=b\right]-\dfrac{1}{2}\right|$.

定义8. 如果任意概率多项式时间的敌手$\mathcal{A}$赢得游戏的优势$Adv\left(\lambda \right)$是可忽略的，那么方案满足密文不可区分性.

3.   公钥可搜索加密方案

本节提供了一种优化的公钥可搜索加密方案. 方案使用一种新的近似陷门采样算法^[16-17]提高陷门生成的效率，该算法能够输出1个近似的而不是精确的原像. 然后，本研究结合非球面高斯采样技术^[18]和理想可扩展输出函数来降低密钥和陷门的存储开销. 本研究首先给出上述提到的3种优化技术，然后结合这些优化技术进一步描述了本文的方案. 表1给出了方案用到的符号及定义.

表  1  符号及定义

Table  1.  Notations and Definitions

符号	定义
$\lambda$	安全参数
$l'$	种子长度
$p，l$	格陷门参数
$q$	模数$q=pl$
$b$	对数$\mathrm{l}\mathrm{o}\mathrm{g}$的底数
$\partial$	向量$\boldsymbol{f}$的维数，$\partial =\left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{b}q} \right\rceil$
$n$	2的次幂
$\sigma ，{\sigma }_{1}，{\sigma }_{2},$$\tau ，r，\bar{r}$	高斯参数
${\mathcal{R}}_{q}$	${\mathcal{R}}_{q}=\mathcal{R}/q\mathcal{R}={\mathbb{Z}}_{q}\left[x\right]/({x}^{n}+1)$
${D}_{{\mathcal{R}}_{q},\tau }$	在${\mathcal{R}}_{q}$上宽度参数为$\tau$的离散高斯分布

下载: 导出CSV 

| 显示表格

3.1   优化技术

优化技术包括采用一种新的近似陷门采样^[16-17]算法、非球面高斯采样^[18]、以及可扩展输出函数.

1）优化技术1. 采用一种新的近似陷门采样算法$ASampPre$. 给定$u\in {\mathcal{R}}_{q}$和$\bar{\boldsymbol{a}}\in {\mathcal{R}}^{\partial +2}，ASampPre$算法利用近似陷门采样方法得到近似原像$\boldsymbol{y}\in {\mathcal{R}}_{q}^{\partial +2}$，满足$\left\langle{\bar{\boldsymbol{a}},\boldsymbol{y}}\right\rangle= u-d\mathrm{m}\mathrm{o}\mathrm{d}q$，其中$d\in {\mathcal{R}}_{q}$. 算法主要包括以下步骤：

① 先构造一种新的工具向量$\boldsymbol{f}=\left\langle{p,\boldsymbol{g}}\right\rangle\in {\mathcal{R}}^{\partial }$，$\boldsymbol{b}=\boldsymbol{f}-[1,a]\boldsymbol{R}\in {\mathcal{R}}^{\partial }$. 令向量$\bar{\boldsymbol{a}}=[1,a,\boldsymbol{b}]$，有$\bar{\boldsymbol{a}}\left[\begin{array}{c}\boldsymbol{R}\\ \boldsymbol{I}\end{array}\right]= \boldsymbol{f}\;\mathrm{m}\mathrm{o}\mathrm{d}\;q$. 在这里，向量$\bar{\boldsymbol{a}}$的格陷门为$\boldsymbol{T}=\left[\begin{array}{c}\boldsymbol{R}\\ \boldsymbol{I}\end{array}\right]$.

② 采样向量$\boldsymbol{p}\leftarrow {D}_{{\mathcal{R}}_{q}^{2+\partial },{\boldsymbol{\Sigma }}_{p}}$，其中${D}_{{\mathcal{R}}_{q}^{2+\partial },{\boldsymbol{\varSigma }}_{p}}$为在${\mathcal{R}}_{q}^{2+\partial }$上协方差矩阵${\boldsymbol{\varSigma }}_{p}={\boldsymbol{\varSigma }}_{1}-{r}^{2}\left[\begin{array}{c}\boldsymbol{R}\\ \boldsymbol{I}\end{array}\right]\left[\begin{array}{cc}{\boldsymbol{R}}^{\mathrm{T}}& \boldsymbol{I}\end{array}\right]= {\sigma }^{2}\boldsymbol{I}- {r}^{2}\left[\begin{array}{c}\boldsymbol{R}\\ \boldsymbol{I}\end{array}\right]\left[\begin{array}{cc}{\boldsymbol{R}}^{\mathrm{T}}& \boldsymbol{I}\end{array}\right]$的离散高斯分布.

③ 计算$v=u-\left\langle{\bar{\boldsymbol{a}},\boldsymbol{p}}\right\rangle$. 利用一种新的半随机原像采样算法$SampleGadget$采样$\boldsymbol{x}$. 通过输入多项式$v$，$SampleGadget$算法输出的多项式$\boldsymbol{x}\leftarrow {D}_{{\mathcal{R}}_{q}^{\partial },r}$，使得$\left\langle{\boldsymbol{f},\boldsymbol{x}}\right\rangle=v-d\mathrm{m}\mathrm{o}\mathrm{d}q$，其中${D}_{{\mathcal{R}}_{q}^{\partial },r}$为在${\mathcal{R}}_{q}^{\partial }$上宽度参数为$r$的离散高斯分布，$d\in {\mathcal{R}}_{q}$.

④ 计算$\boldsymbol{y}=\boldsymbol{p}+\left[\begin{array}{c}\boldsymbol{R}\\ \boldsymbol{I}\end{array}\right]\boldsymbol{x}$，其中$\boldsymbol{y}\leftarrow {D}_{{\mathcal{R}}_{q}^{2+\partial },r}$，满足$\left\langle{\bar{\boldsymbol{a}},\boldsymbol{y}}\right\rangle= u-d\mathrm{m}\mathrm{o}\mathrm{d}q$，其中${D}_{{\mathcal{R}}_{q}^{2+\partial },r}$是在${\mathcal{R}}_{q}^{2+\partial }$上宽度参数为$\sigma$的离散高斯分布，其协方差矩阵为${r}^{2}\boldsymbol{I}$.

2）优化技术2.采用非球面高斯采样^[18]. 基于上述近似陷门采样算法，本研究得到了1个近似原像$\boldsymbol{y}$. 本研究计算该近似原像的${l}_{2}$范数上界为${\varPhi }_{1}= \sigma \sqrt{(\partial +2)n}$，存储该近似原像所需的最大比特数上界为${\varPsi }_{1}=(\partial +2)n(1 +\left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{b}\sigma} \right\rceil )$，其中$\sigma \ge r{s}_{1}\left(\left[\begin{array}{c}\boldsymbol{R}\\ \boldsymbol{I}\end{array}\right]\right)$. 为了进一步地降低$\boldsymbol{y}$的存储开销，本研究选择在非球面高斯上采样，即在${\mathcal{R}}_{q}^{2+\partial }$上协方差矩阵${\boldsymbol{\Sigma }}_{2}=$ $\left[\begin{array}{cc}{\sigma }_{1}^{2}{\boldsymbol{I}}_{2n}& 0\\ 0& {\sigma }_{2}^{2}{\boldsymbol{I}}_{\partial n}\end{array}\right]$的离散高斯分布上采样$\boldsymbol{y}$，其中${\sigma }_{1}\gg {\sigma }_{2}$. 计算$\boldsymbol{y}$的${l}_{2}$范数上界为$\sqrt{{2n\sigma }_{1}^{2}+{\partial n\sigma }_{2}^{2}}$，存储$\boldsymbol{y}$所需的最大比特数上界为$2n(1 +\left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{b}{\sigma }_{1}} \right\rceil ) +\partial n(1 +\left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{b}{\sigma }_{2}} \right\rceil )$.

3）优化技术3.采用可扩展输出函数. 在优化技术1的步骤1中，本文得到了向量$\bar{\boldsymbol{a}}=[1,a,\boldsymbol{b}]$及其格陷门$\boldsymbol{T}=\left[\begin{array}{c}\boldsymbol{R}\\ \boldsymbol{I}\end{array}\right]$. 本研究选择用1个${l}'$的随机种子$\mathcal{H}$来代替$a$，这一步使得公钥$\bar{\boldsymbol{a}}$的存储开销由$5\mathrm{ }120$b降为$256$b，降低了$95\mathrm{\%}$的公钥内存开销.

3.2   方案构造

本文提出的公钥可搜索加密方案包括下面4个算法. 图3给出了方案的流程图.

图  3  PEKS方案的流程图

Figure  3.  Workflow of PEKS scheme

下载: 全尺寸图片 幻灯片

1）密钥生成算法$KeyGen\left(\lambda \right)\to \left(PK,SK\right)$：该算法输入安全参数$\lambda$，输出接收方的公钥$PK$和私钥$SK$. 接收方初始化运行环境，并运行该算法生成接收方的公钥和私钥. 本研究将优化技术1中的向量$\bar{\boldsymbol{a}}$作为公钥，格陷门$\boldsymbol{R}$作为私钥. 为了降低公钥的存储开销，本研究选择用1个${l}'$比特的随机种子$\mathcal{H}$来代替$a$，并且使用优化技术3的可扩展输出函数来生成$a$.

① 采样1个${l}'$比特的随机种子$\mathcal{H}\leftarrow {\left\{\mathrm{0,1}\right\}}^{{l}'}$， 得到$a\leftarrow XOF\left(\mathcal{H}\right)$， 其中$a\in {\mathcal{R}}_{q}，XOF$是1个理想的可扩展输出函数.

② 采样$\boldsymbol{R}\leftarrow {D}_{{\mathcal{R}}_{q}^{2\times \partial },\sigma }$. 令$\boldsymbol{f}=\left\langle{p,\boldsymbol{g}}\right\rangle\in {\mathcal{R}}^{\partial }$，$\boldsymbol{b}=\boldsymbol{f}- [1, a]\boldsymbol{R}\in {\mathcal{R}}^{\partial }$. 令$\bar{\boldsymbol{a}}=\left[1,a,\boldsymbol{b}\right]，\boldsymbol{T}=\left[\begin{array}{c}\boldsymbol{R}\\ \boldsymbol{I}\end{array}\right]$，有$\bar{\boldsymbol{a}}\boldsymbol{T}=\boldsymbol{f}\;\mathrm{m}\mathrm{o}\mathrm{d}\;q$.

③ 算法输出$(\mathcal{H},\boldsymbol{b})$作为公钥$，\boldsymbol{T}$作为私钥.

2）陷门生成算法$Tradoor(PK,SK,\boldsymbol{w})\to {\boldsymbol{t}}_{\boldsymbol{w}}$：输入接收方的公钥$PK$，私钥$SK$，和关键字$\boldsymbol{w}\in {\mathbb{Z}}_{q}^{n}$，算法输出基于关键字$\boldsymbol{w}$的陷门${\boldsymbol{t}}_{\boldsymbol{w}}$. 接收方基于预先设定搜索的关键字，生成检索陷门并提交给服务器. 在该步骤中，本研究结合优化技术1的近似陷门采样方法$ASampPre$和优化技术2的非球面高斯采样，在提高效率的同时进一步压缩了陷门的大小.

① 采样$\boldsymbol{p}\leftarrow SampleP\left(SK\right)$，使得$\boldsymbol{p}\leftarrow {D}_{{\mathcal{R}}_{q}^{2+\partial },{\boldsymbol{\Sigma }}_{p}}$，其中${\boldsymbol{\varSigma }}_{p}=\left[\begin{array}{cc}{\sigma }_{1}^{2}{\boldsymbol{I}}_{2n}& 0\\ 0& {\sigma }_{2}^{2}{\boldsymbol{I}}_{\partial n}\end{array}\right]-{r}^{2}\left[\begin{array}{c}\boldsymbol{R}\\ \boldsymbol{I}\end{array}\right]\left[\begin{array}{cc}{\boldsymbol{R}}^{\mathrm{T}}& \boldsymbol{I}\end{array}\right]\succ {\bar{r}}^{2}$. 本研究使用非球面高斯采样技术，改变参数${\boldsymbol{\varSigma }}_{p}$，使得原像$\boldsymbol{y}\leftarrow {D}_{{\mathcal{R}}_{q}^{2+\partial },{\boldsymbol{\varSigma }}_{2}}$.

② 计算$a\leftarrow XOF\left(\mathcal{H}\right)$，$u=H\left(\boldsymbol{w}\right)$. 其中函数$H:{\mathbb{Z}}_{q}^{n}\to {\mathcal{R}}_{q}$是1个满秩差分编码函数，它可以将${\mathbb{Z}}_{q}^{n}$中的元素映射到${\mathcal{R}}_{q}$中的可逆元素.

③ 令$\bar{\boldsymbol{a}}=[1,a,\boldsymbol{b}]$，计算$v=u-\left\langle{\bar{\boldsymbol{a}},\boldsymbol{p}}\right\rangle$. 采样${\boldsymbol{x}}\leftarrow$ $SampleGadget\left(v\right)$. 其中，$SampleGadget$算法如优化技术1所述.

④ 计算$\boldsymbol{y}=\boldsymbol{p}+\left[\begin{array}{c}\boldsymbol{R}\\ \boldsymbol{I}\end{array}\right]\boldsymbol{x}$.

⑤ 算法输出${\boldsymbol{t}}_{\boldsymbol{w}}=\boldsymbol{y}\in {\mathcal{R}}_{q}^{2+\partial }$.

3）加密算法$Encrypt(PK,\boldsymbol{w}')\to {\boldsymbol{c}}_{\boldsymbol{w}'}$：输入接收方的公钥$PK$和关键字$\boldsymbol{w}'\in {\mathbb{Z}}_{q}^{n}$，算法输出基于关键字$\boldsymbol{w}'$的密文${\boldsymbol{c}}_{\boldsymbol{w}'}$. 发送方根据接收方的公钥为每个加密文件附加的关键字生成可搜索密文，并将生成的可搜索密文和密文文件一起上传到服务器.

①计算$a\leftarrow XOF\left(\mathcal{H}\right)$，$u=H\left(\boldsymbol{w}'\right)$. 其中函数$H:{\mathbb{Z}}_{q}^{n}\to {\mathcal{R}}_{q}$是1个满秩差分编码函数，它可以将${\mathbb{Z}}_{q}^{n}$中的元素映射到${\mathcal{R}}_{q}$中的可逆元素.

② 采样$\upsilon \leftarrow \left\{\mathrm{0,1}\right\}$，$s\leftarrow {D}_{{\mathcal{R}}_{q},\tau }{，\boldsymbol{\varpi }\leftarrow D}_{{\mathcal{R}}_{q}^{\partial +2},\tau }$，$\xi \leftarrow {D}_{{\mathcal{R}}_{q},\tau }$.

③ 令$\bar{\boldsymbol{a}}=[1,a,\boldsymbol{b}]$，计算$\boldsymbol{\varrho }=\bar{\boldsymbol{a}}s+\boldsymbol{\varpi }，\varsigma =us+ \xi + \left\lfloor {q/2} \right\rfloor \upsilon \;\mathrm{m}\mathrm{o}\mathrm{d}\;q$，其中$\left\lfloor {q/2} \right\rfloor$表示对$q/2$的下取整函数；本研究将关键字的哈希值作为密文的一部分，而不是附加到接收方的公钥上.

④ 算法输出${\boldsymbol{c}}_{\boldsymbol{w}'}=(\upsilon ,\boldsymbol{\varrho },\varsigma )\in {\mathcal{R}}_{q}^{4+\partial }$.

4）测试算法$Test({\boldsymbol{t}}_{\boldsymbol{w}},{\boldsymbol{c}}_{\boldsymbol{w}'})\to 0/1$：输入陷门${\boldsymbol{t}}_{\boldsymbol{w}}$和密文${\boldsymbol{c}}_{\boldsymbol{w}'}$，如果$\boldsymbol{w}=\boldsymbol{w}'$， 算法输出1；否则，输出0. 服务器根据检索陷门来检索所有可搜索密文，返回所有匹配的可搜索密文的密文文件并将其发送给接收方.

① 计算$\bar{c}=\varsigma -{\boldsymbol{\varrho }}^{\mathrm{T}}{\boldsymbol{t}}_{\boldsymbol{w}}$.

② 对于$1\le i\le n$，如果$q/4\le {\bar{c}}_{i}\le 3q/4$， 则${\bar{c}}_{i}=1$；否则，${\bar{c}}_{i}=0$.

③ 如果$\bar{c}=\upsilon$， 算法输出1；否则，输出0.

正确性：如果$\boldsymbol{w}=\boldsymbol{w}'$，$\bar{c}=\varsigma -{\boldsymbol{\varrho }}^{\mathrm{T}}{\boldsymbol{t}}_{\boldsymbol{w}}=\xi -{\boldsymbol{\varpi }}^{\mathrm{T}}\boldsymbol{y}-ds+ \left\lfloor {q/2} \right\rfloor \upsilon$. 令错误项$\bar{e}=\xi -{\boldsymbol{\varpi }}^{\mathrm{T}}\boldsymbol{y}-ds$. 在参数的选取下，错误项需满足：$\left\|\bar{e}\right\|\le q/4$. 因此，如果$\boldsymbol{w}=\boldsymbol{w}'，\bar{c}=\upsilon$，算法输出1；否则，输出0.

参数集. 为了保证方案能够正确解密和达到$\lambda$比特的具体安全性，方案需要满足如下条件：

1）错误项需满足$\left\|\bar{e}\right\|\le q/4$.

2）参数$n，q，r$需保证RLWE实例是困难的.

3）由于NFLlib库的使用，模数$q$的大小需为14，30，62 b.

4）参数${\sigma }_{1}$和${\sigma }_{2}$需满足${\sigma }_{1}^{2}\ge ({r}^{2}+{\bar{r}}^{2})\left({{s}_{1}\left(\boldsymbol{R}\right)}^{2}\right)+ 2{r}^{2}+ 4{\bar{r}}^{2}， {\boldsymbol{\varSigma }}_{p}= \left[\begin{array}{cc}{\sigma }_{1}^{2}{\boldsymbol{I}}_{2n}& 0\\ 0& {\sigma }_{2}^{2}{\boldsymbol{I}}_{\partial n}\end{array}\right]-{r}^{2}\left[\begin{array}{c}\boldsymbol{R}\\ \boldsymbol{I}\end{array}\right]\left[\begin{array}{cc}{\boldsymbol{R}}^{\mathrm{T}}& \boldsymbol{I}\end{array}\right]\succ {\bar{r}}^{2}$.

评估主要利用 BKZ 格约化算法来评估coreSVP困难性. 重点考虑2个BKZ攻击，称为原始攻击和对偶攻击. 关于 BKZ 格约化算法的渐近成本存在不同的模型. 令$T={2}^{c\beta }$表示使用筛分算法来计算coreSVP的复杂度的近似下界. 根据常数$c$，考虑3种情况，$c= 0.292$ 表示经典安全性，$c= 0.265$表示量子安全性，$c= 0.207 5$ 表示常数$c$的悲观下界.表2给出了方案的建议参数.

表  2  PEKS方案的参数集

Table  2.  Parameters Set of PEKS Scheme

参数	取值
	经典安全	量子安全	悲观下界
$\lambda$	80	80	80
$n$	512	1 024	1 024
${\mathrm{l}\mathrm{o}\mathrm{g}}_{b}q$	62	62	62
${\mathrm{l}\mathrm{o}\mathrm{g}}_{b}p$	32	32	32
${\mathrm{l}\mathrm{o}\mathrm{g}}_{b}l$	30	30	30
$l'$	256	256	256
$r$	6.5	3	4.2
$\partial$	62	62	62
$\tau$	6.7	6.3	6.2
${\sigma }_{1}$	11 902.21	10 523.46	10 192.64
${\sigma }_{2}$	43.61	9.29	18.21

下载: 导出CSV 

| 显示表格

4.   前向安全和后向安全的扩展方案

前向安全性是动态可搜索加密方案的1个重要特性，这意味着新更新的密文无法与以前的陷门匹配. 图4给了具有前向安全的可搜索加密方案的1个示例. 假设${t}_{1} < {t}_{2} < {t}_{3} < {t}_{4}$，数据拥有者在时间${t}_{1}$上传具有关键字$\boldsymbol{w}$的密文文件${f}_{1}$，并且数据使用者在$\mathrm{时}\mathrm{间}{t}_{2}$时执行关键字$\boldsymbol{w}$的查询. 然后，数据拥有者在时间${t}_{3}$上传具有关键字$\boldsymbol{w}$的密文文件${f}_{2}$，并且数据使用者在$\mathrm{时}\mathrm{间}{t}_{4}$时又一次执行关键字$\boldsymbol{w}$的查询. 前向安全性意味着${t}_{3}$时上传的密文无法与${t}_{2}$时的陷门匹配，但允许与${t}_{4}$时的陷门匹配.

图  4  前向安全的PEKS方案的1个示例

Figure  4.  An example of a forward secure PEKS scheme

下载: 全尺寸图片 幻灯片

本研究通过基于格的委托机制来定期更新密钥. 每个私钥都连接到1个特定的时间段. 每个时间段结束时都需要更新私钥. 因此，实现PEKS的前向安全性. 具体地，除了前面提到的4种算法外，本研究还添加了1个密钥更新算法，该算法由接收方执行. 它以当前时间$j$和前一个时间$i(i < j)$的私钥${\boldsymbol{T}}_{i}$作为输入，输出时间$j$的私钥${\boldsymbol{T}}_{j}$. 作为对应的公钥可以由任何实体基于初始公钥和相应的哈希函数计算，本文提出的方案不需要用户在每个时间段更新相应的公钥. 在加密算法中，发送方利用接收方的身份、当前时间$j$和关键字$\boldsymbol{w}$生成密文. 在陷门生成算法中，接收方利用私钥${\boldsymbol{T}}_{j}$生成与所选关键字$\boldsymbol{w}$对应的陷门${\boldsymbol{T}}_{\boldsymbol{w},j}$. 然后将生成的陷门提交给云服务器，云服务器执行$Test$算法. 从数据接收方的角度来看，当传输从时间段$i$变为时间段$j(i < j)$时，数据接收方从本地存储撤销私钥${\boldsymbol{T}}_{i}$. 从这个时间段开始，任何外部攻击者都无法成功搜索到之前时间段的PEKS密文，即使私钥${\boldsymbol{T}}_{j}$暴露.

除了确保前向安全性外，还希望防止后续搜索泄露有关已删除文件的信息，即后向安全性.图5给了具有后向安全的可搜索加密方案的1个示例. 假设数据拥有者在时间${t}_{1}$上传具有关键字$\boldsymbol{w}$的密文文件${f}_{1}$，并且数据使用者在$\mathrm{时}\mathrm{间}{t}_{2}$时执行关键字$\boldsymbol{w}$的查询. 然后，数据拥有者在时间${t}_{3}$删除具有关键字$\boldsymbol{w}$的密文文件${f}_{1}$，并且数据使用者在$\mathrm{时}\mathrm{间}{t}_{4}$时又一次执行关键字$\boldsymbol{w}$的查询. 后向安全意味着${t}_{4}$时提交的陷门无法检索${t}_{3}$已删除的文件${f}_{1}$.

图  5  后向安全的PEKS方案的1个示例

Figure  5.  An example of a backward secure PEKS scheme

下载: 全尺寸图片 幻灯片

为了实现后向安全，本研究结合位图索引和BFV同态加密方案实现文件标识符的添加和删除. 在位图索引中，所有文件标识符都由单个比特表示. 要添加或删除文件标识符，可以通过1个模加法来修改比特字符串. 为了安全地更新加密数据库，本文提出的方案使用同态加密方案作为底层加密原语. 因此，本文提出的方案不会泄露更新类型，因为添加和删除都是通过1个模加法完成的.

前向安全和后向安全的扩展方案包括以下7个算法：密钥生成$KeyGen$、密钥更新算法$KeyUpdate$、陷门生成算法$Trapdoor$、加密算法$Encrypt$、更新算法$Update$、测试算法$Test$以及解密算法$Decrypt$. 给定公钥可搜索加密方案为$PEKS=(PEKS.KeyGen,$

$PEKS.Trapdoor,PEKS.Encrypt,PEKS.Test)$和同态加密$BFV=(BFV.KeyGen,BFV.Enc,BFV.Add,$

$BFV.Dec)$. 下面主要描述扩展方案的关键部分.

1）密钥生成$KeyGen\left(\lambda \right)\to ({PK}_{1},{SK}_{1},{PK}_{2},{SK}_{2})$： 该算法输入安全参数$\lambda$，运行$PEKS.KeyGen\left(\lambda \right)\to ({PK}_{1},{SK}_{1})$用于生成关键字密文、陷门和搜索；运行$BFV.KeyGen\left(\lambda \right)\to \left({PK}_{2},{SK}_{2}\right)$用于加密和解密文件标识符.

2）密钥更新算法$KeyUpdate({\boldsymbol{T}}_{i},j)\to {\boldsymbol{T}}_{j}$：输入时间段$i$时接收方的私钥${\boldsymbol{T}}_{i}$和当前时间段$j(j > i)$，算法输出时间段$j$时接收方的私钥${\boldsymbol{T}}_{j}$.

① 计算${h}_{i}={H}_{1}\left(\bar{\boldsymbol{a}}||i\right){H}_{1}(\bar{\boldsymbol{a}}||i-1)… {H}_{1}\left(\bar{\boldsymbol{a}}||1\right)$，${h}_{i-j}= {H}_{1}\left(\bar{\boldsymbol{a}}\right|\left|j\right){H}_{1}\left(\bar{\boldsymbol{a}}\right|\left|j+1\right)… {H}_{1}\left(\bar{\boldsymbol{a}}\right||i+1)$，${\boldsymbol{a}}_{i}=\bar{\boldsymbol{a}}{h}_{i}^{-1}$.

② 运行算法$BasisDel({\boldsymbol{a}}_{i},{h}_{i-j},\beta ,{\boldsymbol{T}}_{i})\to {\boldsymbol{T}}_{j}$，其中${\boldsymbol{a}}_{j}={\boldsymbol{a}}_{i}{h}_{i-j}^{-1}=\bar{\boldsymbol{a}}{h}_{j}^{-1}$.

③ 算法输出${\boldsymbol{T}}_{j}$.

3）陷门生成算法$Tradoor({PK}_{1},{SK}_{1},w,j)\to {\boldsymbol{t}}_{\boldsymbol{w}}$：输入数据使用者的公钥${PK}_{1}$，私钥${SK}_{1}$，关键字$\boldsymbol{w}\in {\mathbb{Z}}_{q}^{n}$，和当前时间段$j$，算法输出基于关键字$\boldsymbol{w}$的陷门${\boldsymbol{t}}_{\boldsymbol{w},j}$.

① 计算${h}_{j}={H}_{1}\left(\bar{\boldsymbol{a}}\right|\left|j\right){H}_{1}\left(\bar{\boldsymbol{a}}\right||j-1)… {H}_{1}\left(\bar{\boldsymbol{a}}\right|\left|1\right)$，${\boldsymbol{a}}_{j}= \bar{\boldsymbol{a}}{h}_{j}^{-1}，{h}_{\boldsymbol{w}\left|\right|j}={H}_{2}\left(\boldsymbol{w}\right|\left|j\right)$，运行$BasisDel({\boldsymbol{a}}_{j},$ ${h}_{\boldsymbol{w}\left|\right|j},\beta ,{\boldsymbol{T}}_{j}) \to {\boldsymbol{T}}_{\boldsymbol{w}\left|\right|j}$，其中${\boldsymbol{a}}_{\boldsymbol{w}\left|\right|j}={\boldsymbol{a}}_{j}{h}_{\boldsymbol{w}\left|\right|j}^{-1}$.

② 运行$PEKS.Tradoor\left({PK}_{1},{SK}_{1},\boldsymbol{w}\right)\to {\boldsymbol{t}}_{\boldsymbol{w}}$，将基础可搜索加案陷门算法中的$\bar{\boldsymbol{a}}$替换为${\boldsymbol{a}}_{\boldsymbol{w}\left|\right|j}$.

4）加密算法$Encrypt({PK}_{1},{PK}_{2},\boldsymbol{w}',j,\eta )\to {\boldsymbol{c}}_{\boldsymbol{w}',j,\eta }$：输入数据使用者的公钥${PK}_{1}，{PK}_{2}$，关键字$\boldsymbol{w}'\in {\mathbb{Z}}_{q}^{n}$，用于表示文件标识符的位图索引$\eta$和当前时间段$j$，算法输出密文${\boldsymbol{c}}_{\boldsymbol{w}',j,\eta }$.

① 计算${h}_{j}={H}_{1}\left(\bar{\boldsymbol{a}}\right|\left|j\right){H}_{1}\left(\bar{\boldsymbol{a}}\right||j-1)… {H}_{1}\left(\bar{\boldsymbol{a}}\right|\left|1\right)$，${\boldsymbol{a}}_{j}= \bar{\boldsymbol{a}}{h}_{j}^{-1}，{h}_{\boldsymbol{w}\left|\right|j}={H}_{2}\left(\boldsymbol{w}'\right|\left|j\right)$，运行$PEKS.Encrypt$$({PK}_{1},\boldsymbol{w}')\to {\boldsymbol{c}}_{\boldsymbol{w}'}$将基础方案加密算法中的$\bar{\boldsymbol{a}}$替换为${\boldsymbol{a}}_{j}$.

② 运行$BFV.Enc(PK,\eta )\to \boldsymbol{t}$，其中$\eta \in {\mathcal{R}}_{q}$. 请注意，1次$BFV.Enc$加密算法最多表示$n$个文件. 对于$m(m > n)$个文件，本研究选择将其拆分成$\left\lceil {m/n} \right\rceil$个位图索引，并按顺序分别加密.

③ 算法输出${\boldsymbol{c}}_{\boldsymbol{w}',j,\eta }=({\boldsymbol{c}}_{\boldsymbol{w}'},\boldsymbol{t})$.

5）更新$Update({PK}_{1},{PK}_{2},\boldsymbol{w}',j,\eta ,op)\to {\boldsymbol{c}}_{\boldsymbol{w}',j,\eta }$：输入数据使用者的公钥${PK}_{1},{PK}_{2}$，关键字$\boldsymbol{w}\boldsymbol{'}\in {\mathbb{Z}}_{q}^{n}$，用于更新文件的位图索引$\eta$，当前时间段$j$和更新操作$op\in \{\mathrm{a}\mathrm{d}\mathrm{d},\mathrm{d}\mathrm{e}\mathrm{l}\}$，算法输出更新密文${\boldsymbol{c}}_{\boldsymbol{w}',j,\eta }$.

① 如果$op=\mathrm{a}\mathrm{d}\mathrm{d}$，这表示添加文件，令$\eta '=\eta$；如果$op=\mathrm{d}\mathrm{e}\mathrm{l}$，这表示删除文件，令${\eta }'={2}^{n}-\eta \;\mathrm{m}\mathrm{o}\mathrm{d}\;{2}^{n}$.

② 运行加密算法$Encrypt({PK}_{1},{PK}_{2},\boldsymbol{w}',j,\eta ')\to {\boldsymbol{c}}_{\boldsymbol{w}',j,\eta }$，并输出${\boldsymbol{c}}_{\boldsymbol{w}',j,\eta }$.

6）测试算法$Test\left({\boldsymbol{t}}_{\boldsymbol{w}},{\boldsymbol{c}}_{{\boldsymbol{w}}',j,\eta }\right)\to \boldsymbol{t}/0$：输入陷门${\boldsymbol{t}}_{\boldsymbol{w}}$和密文${\boldsymbol{c}}_{\boldsymbol{w}',j,\eta }=({\boldsymbol{c}}_{\boldsymbol{w}'},\boldsymbol{t})$，运行$PEKS.Test\left({\boldsymbol{t}}_{\boldsymbol{w}},{\boldsymbol{c}}_{{\boldsymbol{w}}'}\right)\to 0/1$. 如果$\boldsymbol{w}=\boldsymbol{w}'$，$PEKS.Test$算法输出1；否则，$PEKS.Test$算法输出0，算法终止. 对于所有输出1的密文${\boldsymbol{c}}_{\boldsymbol{w}',j,\eta }$，运行$BFV.Add$，同态计算位图索引的模加法，并将最终结果输出.

7）解密算法$Decrypt(\boldsymbol{t},{SK}_{2})\to \eta$：输入数据使用者的私钥${SK}_{2}$，加密后的位图索引$\boldsymbol{t}$，算法运行$BFV.Dec(\boldsymbol{t},{SK}_{2}) \to \eta$，并输出位图索引$\eta$.

请注意，基础方案的正确性和参数集适用于扩展方案.

5.   安全性分析

5.1   基础方案的安全性分析

定理1. 如果RLWE问题是困难的，那么本文提出的方案满足密文不可区分性.

证明. 本研究通过归约来证明该定理. 如果存在1个敌手$\mathcal{A}$以不可忽略的概率$\epsilon$打破方案的密文不可区分性，那么本研究能构造1个挑战者$\mathcal{B}$具有不可忽略概率利用$\mathcal{A}$解决RLWE问题. 挑战者$\mathcal{B}$构造如下：

1）初始化阶段. 给定$w+2$个RLWE实例$({p}_{i},{q}_{i})$，其中${q}_{i}={p}_{i}s+{e}_{i},1\le i\le \partial +2$. $\mathcal{B}$维护1个哈希表$L$. 设${Q}_{H}$为$\mathcal{A}$执行哈希问询$H$的最大次数. $\mathcal{B}$设置$\boldsymbol{p}= ({p}_{1},{p}_{2},… ,{p}_{\partial +1}){，h}_{{\boldsymbol{w}}^{\boldsymbol{*}}}={p}_{0}$，随机选取${i}^{*}\in [1,{Q}_{H}]$.

2）问询阶段. 敌手$\mathcal{A}$可以执行${O}_{H}，{O}_{T}$这2个问询.

① 哈希问询${O}_{H}$. 对于$\mathcal{A}$执行的第$j$次问询${\boldsymbol{w}}_{j}$，$\mathcal{B}$首先检查哈希表中是否已经存在$({\boldsymbol{w}}_{j},\mathrm{*},\mathrm{*},\mathrm{*})$. 如果不存在并且$j\ne {i}^{*}$，$\mathcal{B}$将$\left({\boldsymbol{w}}_{j},{p}_{0},\perp ,\perp \right)$存到哈希表中；如果不存在并且$j={i}^{*}$ $\mathcal{B}$采样$\boldsymbol{y}\leftarrow {D}_{{\mathcal{R}}_{q}^{2+\partial },{\boldsymbol{\varSigma }}_{2}},\omega \leftarrow U\left({\mathcal{R}}_{q}\right)$，并计算${h}_{{\boldsymbol{w}}_{j}}=\left[1,\boldsymbol{p}\right]\boldsymbol{y}-\omega . \mathcal{B}$将$({\boldsymbol{w}}_{j},{h}_{{\boldsymbol{w}}_{j}},$$\boldsymbol{y},\omega )$存到哈希表中.

② 陷门问询${O}_{T}$. 当$\mathcal{A}$问询$\boldsymbol{w}$的陷门时，$\mathcal{B}$从哈希表中检索$(\boldsymbol{w},{h}_{\boldsymbol{w}},\boldsymbol{y},\omega )$，并将$\boldsymbol{y}$发送给$\mathcal{A}$.如果表中不存在元素$\boldsymbol{y}$和$\omega$，$\mathcal{B}$输出1个随机比特并终止.

3）挑战阶段. 当$\mathcal{A}$输出挑战关键字$({\boldsymbol{w}}_{0}^{*},{\boldsymbol{w}}_{1}^{*})$时，$\mathcal{B}$从哈希表中检索${(\boldsymbol{w}}_{0}^{*},\mathrm{*},\mathrm{*},\mathrm{*})$和$({\boldsymbol{w}}_{1}^{*},\mathrm{*},\mathrm{*},\mathrm{*})$. 如果$\boldsymbol{y}=\perp$，$\mathcal{B}$输出1个随机比特，并终止游戏. 否则，$\mathcal{B}$令$\boldsymbol{a}'= ({p}_{1},{p}_{2},… ,{p}_{\partial +1})，\boldsymbol{b}'=({q}_{1},{q}_{2},… ,{q}_{\partial +1})$，采样$\upsilon \leftarrow \left\{\mathrm{0,1}\right\}$，设置挑战密文${\boldsymbol{c}}^{*}=(\upsilon ,\boldsymbol{b}',{q}_{\partial +2}+\left\lfloor {q/2} \right\rfloor \upsilon )$.

4）猜测阶段.$\mathcal{B}$将$\mathcal{A}$的输出作为输出.

在陷门问询阶段，$\mathcal{B}$首先从哈希表中检索$({\boldsymbol{w}}_{j}, {h}_{{\boldsymbol{w}}_{j}}, \boldsymbol{y},\omega )$，只有元素$\boldsymbol{y}$和$\omega$不存在时$\mathcal{B}$终止游戏. 而$\mathcal{A}$可以执行哈希问询$H$的次数为${Q}_{H}$，只有当哈希表中不存在${\boldsymbol{w}}_{j}$且$j\ne {i}^{*}$时，${\boldsymbol{w}}_{j}$对应的元素$\boldsymbol{y}$和$\omega$在哈希表中为$\perp$. 因此，$\mathcal{B}$在游戏中不发生终止的概率为$1/{Q}_{H}$. 在$\mathcal{B}$不终止时，根据文献[17]中的定理2，分布$(\bar{\boldsymbol{a}}, \boldsymbol{y},u, \omega '): u\leftarrow U\left({\mathcal{R}}_{q}\right),\boldsymbol{y}\leftarrow ASampPre\left(\bar{\boldsymbol{a}},u\right),\omega '=u-\left\langle{\bar{\boldsymbol{a}},\boldsymbol{y}}\right\rangle\mathrm{m}\mathrm{o}\mathrm{d}\;q$与$\{\left(\bar{\boldsymbol{a}},\boldsymbol{y},u,\omega '\right):\boldsymbol{y} \leftarrow {D}_{{\mathcal{R}}_{q}^{2+\partial },\sqrt{\boldsymbol{\varSigma }}}$, $\omega ' \leftarrow U({\mathcal{R}}_{q})$, $u = \left\langle{\bar{\boldsymbol{a}},\boldsymbol{y}}\right\rangle+ \omega '\mathrm{m}\mathrm{o}\mathrm{d}\;q\}$在统计上是无法区分的. 因此，$\mathcal{B}$在哈希问询阶段采样的$\boldsymbol{y}\leftarrow {D}_{{\mathcal{R}}_{q}^{2+\partial },\sqrt{\boldsymbol{\varSigma }}},\omega '\leftarrow U\left({\mathcal{R}}_{q}\right)$与方案运行$ASampPre$得到的$\boldsymbol{y}$和$\omega '$在统计上不可区分. 在$\mathcal{A}$的视角中，在挑战阶段生成的挑战密文与密文不可区分性游戏中的挑战密文具有同样的形式. 因此，在该游戏中$\mathcal{B}$提供给$\mathcal{A}$的视角等同于密文不可区分性中的视角. $\mathcal{B}$解决RLWE的优势为可忽略的$\epsilon /{Q}_{H}$.

5.2   扩展方案的安全性分析

扩展方案的安全性分别用理想世界${Ideal}_{\mathcal{A},\mathcal{S}}\left(\lambda \right)$和现实世界${Real}_{\mathcal{A},\mathcal{S}}\left(\lambda \right)$这2个世界来建模^[35]. 现实世界和理想世界是$\mathcal{A}$和$\mathcal{S}$之间交互的游戏，区别在于$\mathcal{S}$所获取的信息. 现实世界中的$\mathcal{S}$诚实地运行扩展方案，理想世界中的$\mathcal{S}$可以访问扩展方案的泄露函数$\mathcal{L}= ({\mathcal{L}}_{KeyGen},{\mathcal{L}}_{KeyUpdate},{\mathcal{L}}_{Trapdoor},{\mathcal{L}}_{Encrypt},{\mathcal{L}}_{Update},{\mathcal{L}}_{Test},$${\mathcal{L}}_{Decrypt})$. 该函数描述了扩展方案在密钥生成、密钥更新、陷门生成、加密、更新、测试以及解密算法阶段的泄露. 如果$\mathcal{A}$区分理想世界${Ideal}_{\mathcal{A},\mathcal{S}}\left(\lambda \right)$和现实世界${Real}_{\mathcal{A},\mathcal{S}}\left(\lambda \right)$的优势可以忽略不计，那么本文提出的扩展方案是$\mathcal{L}-$自适应安全的.

在进行安全分析之前，本研究首先定义了扩展方案的泄露函数$\mathcal{L}$. 令$TList=\{{t}_{1},{t}_{2},… \}$为时间段列表，$R\left(\boldsymbol{w}\right)$为对关键字$w$的搜索次数，$\underset{m}{\mathrm{max}}$为文件数量$m$的最大值，$U\left(\boldsymbol{w}\right)$为对关键字$\boldsymbol{w}$的更新次数，$A\left(\boldsymbol{w}\right)$为对关键字$\boldsymbol{w}$的操作（添加和删除）次数，$TimeDB\left(\boldsymbol{w}\right)= \left\{\right({t}_{1},{b}_{1},\boldsymbol{w}),({t}_{1},{b}_{2},\boldsymbol{w}),… \}$为与$\boldsymbol{w}$匹配的所有加密位图索引及时间段列表. 本文提出的扩展方案的泄露函数$\mathcal{L}=({\mathcal{L}}_{KeyGen},{\mathcal{L}}_{KeyUpdate},{\mathcal{L}}_{Trapdoor},{\mathcal{L}}_{Encrypt},{\mathcal{L}}_{Update},$${\mathcal{L}}_{Test}, {\mathcal{L}}_{Decrypt})$定义如下：

1）${\mathcal{L}}_{KeyGen}=\perp$；

2）${\mathcal{L}}_{KeyUpdate}=TList$；

3）${\mathcal{L}}_{Trapdoor}=\{TList,R(\boldsymbol{w}\left)\right\}$;7）

4）${\mathcal{L}}_{Encrypt}=\{TList,\underset{m}{\mathrm{max}},R(\boldsymbol{w}\left)\right\}$；

5）${\mathcal{L}}_{Update}= \{TList,U(\boldsymbol{w}\left)\right\}$；

6）${\mathcal{L}}_{Test}=\left\{TimeDB\right(\boldsymbol{w}),A(\boldsymbol{w}\left)\right\}$；

7）${\mathcal{L}}_{Decrypt}=b$.

给定安全参数$\lambda$，$KeyGen$算法仅输出方案所需要的2组公钥和私钥对，泄露函数${\mathcal{L}}_{KeyGen}=\perp$. 给定当前时间段$j(j > i)$，$KeyUpdate$算法用于将时间段$i$时的私钥${\boldsymbol{T}}_{i}$更新为时间段$j$时的私钥${\boldsymbol{T}}_{j}$，因此${\mathcal{L}}_{KeyUpdate}$泄露每次密钥更新的时间，即，$TList.Tradoor$算法为当前时间段$j$的关键字$\boldsymbol{w}$生成搜索陷门，该算法泄露生成陷门的所有时间段和总次数. 因此，${\mathcal{L}}_{Trapdoor}= \{TList,R(\boldsymbol{w}\left)\right\}.Encrypt$算法加密当前时间段$j$的关键字${\boldsymbol{w}}'$和位图索引$\eta$，对于方案包含的$m$个文件，本研究选择将其拆分成$\left\lceil {m/n} \right\rceil$个位图索引，并按顺序分别加密. 因此，该算法不仅泄露生成密文的所有时间段和总次数，而且暴露文件数量$m$的最大值. 对于要更新的包含关键字$\boldsymbol{w}'$的文件，本研究构造位图索引$\eta$，用$Update$算法生成更新密文. 由于本研究使用同态加密方案通过1个模加法来修改位图索引，本文提出的方案不会泄露更新类型. 该算法泄露更新的所有时间段和次数，即，${\mathcal{L}}_{Update}= \{TList,U(\boldsymbol{w}\left)\right\}.Test$算法用于判断关键字密文与陷门是否匹配，并同态计算所有匹配的位图索引. 因此，泄露与$\boldsymbol{w}$匹配的所有加密位图索引，时间段和对关键字$\boldsymbol{w}$的操作总次数，即，${\mathcal{L}}_{Test}=\left\{TimeDB\right(\boldsymbol{w}),A(\boldsymbol{w}\left)\right\}$. 对于加密的位图索引，$Decrypt$算法解密并输出位图索引. 因此，该算法会泄露与$\boldsymbol{w}$匹配的位图索引，即， ${\mathcal{L}}_{Decrypt}=\eta$. 证毕.

定理2. 设扩展可搜索加密方案为$\Pi = (KeyGen, KeyUpdate,Trapdoor,Encrypt,Update,Test,Decrypt)$. 泄露函数$\mathcal{L}=({\mathcal{L}}_{KeyGen},{\mathcal{L}}_{KeyUpdate},{\mathcal{L}}_{Trapdoor},{\mathcal{L}}_{Encrypt},{\mathcal{L}}_{Update}, {\mathcal{L}}_{Test},{\mathcal{L}}_{Decrypt})$如前所述. 如果RLWE问题是困难的，那么本文提出的扩展方案具有$\mathcal{L}-$自适应安全.

证明. 本研究通过归约来证明扩展方案的理想世界${Ideal}_{\mathcal{A},\mathcal{S}}\left(\lambda \right)$和现实世界${Real}_{\mathcal{A},\mathcal{S}}\left(\lambda \right)$的不可区分性. 假设存在1个具有不可忽略概率$\epsilon$的区分理想世界${Ideal}_{\mathcal{A},\mathcal{S}}\left(\lambda \right)$和现实世界${Real}_{\mathcal{A},\mathcal{S}}\left(\lambda \right)$的敌手$\mathcal{A}$，那么本研究能构造1个具有不可忽略概率的挑战者$\mathcal{S}$利用$\mathcal{A}$解决RLWE问题. 挑战者$\mathcal{S}$构造如下：

1）初始化阶段. 给定$w+2$个RLWE实例$\left({p}_{i},{q}_{i}\right)$，其中${q}_{i}={p}_{i}s+{e}_{i}，1\le i\le \partial +4$. 挑战者$\mathcal{S}$随机设置${j}^{*}$为$\mathcal{A}$区分理想世界${Ideal}_{\mathcal{A},\mathcal{S}}\left(\lambda \right)$和现实世界${Real}_{\mathcal{A},\mathcal{S}}\left(\lambda \right)$的时间段. 同时，$\mathcal{S}$维护2个表${L}_{1}$和${L}_{2}$. 令${\boldsymbol{a}}'=\left({p}_{1},{p}_{2},…,{p}_{\partial +1}\right)，{\boldsymbol{b}}'=\left({q}_{1},{q}_{2},… ,{q}_{\partial +1}\right).$设$Q$为$\mathcal{A}$问询${H}_{2}$的最大次数. $\mathcal{S}$选择1个随机数${J}^{*}\in Q.\mathcal{S}$随机采样${j}^{*}+1$个多项式${\boldsymbol{r}}^{*},{\boldsymbol{r}}_{1}^{*},…{\boldsymbol{r}}_{{j}^{*}}^{*}$. 令$\bar{\boldsymbol{a}}={{\boldsymbol{a}}'\left({\boldsymbol{r}}_{{j}^{*}}^{*}{{\boldsymbol{r}}_{{j}^{*}-1}^{*}…\boldsymbol{r}}_{1}^{*}{\boldsymbol{r}}^{*}\right)}^{-1}. \mathcal{S}$将$\bar{\boldsymbol{a}}，{H}_{1}，{H}_{2}$发送给敌手$\mathcal{A}$.

2）问询阶段. 敌手$\mathcal{A}$可以执行${O}_{{H}_{1}},{O}_{{H}_{2}},{O}_{T},{O}_{K}$问询.

① 哈希问询${O}_{{H}_{1}}$. 若$\mathcal{A}$对$\bar{\boldsymbol{a}}\left|\right|j$执行${H}_{1}$问询，本研究假设它已经问询了时间段$i < j$的相应哈希值. 对于$\bar{\boldsymbol{a}}\left|\right|j,j=\mathrm{1,2},\cdots ,{j}^{*}+1$的每个问询， $\mathcal{S}$设置${H}_{1}\left(\bar{\boldsymbol{a}}\right|\left|j\right) ={\boldsymbol{r}}_{j}^{*}$，并将${\boldsymbol{r}}_{j}^{*}$返回给$\mathcal{A}$. 如果$j={j}^{*}+ 1$，$\mathcal{S}$计算${\boldsymbol{a}}_{j-1}= \bar{\boldsymbol{a}}{\left({\boldsymbol{r}}_{{j}^{*}}^{*}{{\boldsymbol{r}}_{{j}^{*}-1}^{*}… \boldsymbol{r}}_{1}^{*}{\boldsymbol{r}}^{*}\right)}^{-1}$，运行$BasisDel$算法获取1个随机${\boldsymbol{r}}_{j}$和短随机格基${\boldsymbol{T}}_{j}$，其中${\boldsymbol{a}}_{j}={\boldsymbol{a}}_{j-1}{{\boldsymbol{r}}_{j}}^{-1}$，并将$\left(\bar{\boldsymbol{a}}\right||j,{\boldsymbol{a}}_{j},{\boldsymbol{r}}_{j},{\boldsymbol{T}}_{j})$加入列表${L}_{1}$，最后将${\boldsymbol{r}}_{j}$返回给$\mathcal{A}$. 如果$j > {j}^{*}+ 1$，$\mathcal{S}$从列表${L}_{1}$中找到$\left(\bar{\boldsymbol{a}}\right||j-1,{\boldsymbol{a}}_{j-1},{\boldsymbol{r}}_{j-1},{\boldsymbol{T}}_{j-1})$，采样${\boldsymbol{r}}_{j}\leftarrow {D}_{{\mathcal{R}}_{q},\tau }$，运行$BasisDel({\boldsymbol{a}}_{j-1},{\boldsymbol{r}}_{j},\beta ,{\boldsymbol{T}}_{j-1})\to {\boldsymbol{T}}_{j}$，将$\left(\bar{\boldsymbol{a}}\right||j,{\boldsymbol{a}}_{j},{\boldsymbol{r}}_{j},{\boldsymbol{T}}_{j})$加入列表${L}_{1}$，最后将${\boldsymbol{r}}_{j}$返回给$\mathcal{A}$.

② 哈希问询${O}_{{H}_{2}}$. 对于第${Q}_{{H}_{2}}\in [1,Q]$次查询，$\mathcal{A}$在时间段j对$\boldsymbol{w}\left|\right|j$执行${H}_{2}$问询，$\mathcal{S}$做如下回复. 如果${Q}_{{H}_{2}}={J}^{*}$使得$\boldsymbol{w}={\boldsymbol{w}}^{*},j={j}^{*}$，则$\mathcal{S}$设置${H}_{2}\left(\boldsymbol{w}\right|\left|j\right) ={\boldsymbol{r}}^{*}$，并将${\boldsymbol{r}}^{*}$返回给$\mathcal{A}$. 否则，$\mathcal{S}$在列表${L}_{1}$中查找$\left(\bar{\boldsymbol{a}}\right||j,{\boldsymbol{a}}_{j},{\boldsymbol{r}}_{j},{\boldsymbol{T}}_{j})$，采样${\boldsymbol{r}}_{\boldsymbol{w}\left|\right|j}\leftarrow {D}_{{\mathcal{R}}_{q},\tau }$，运行$BasisDel({\boldsymbol{a}}_{j},{\boldsymbol{r}}_{\boldsymbol{w}\left|\right|j},\beta ,{\boldsymbol{T}}_{j})\to {\boldsymbol{T}}_{\boldsymbol{w}\left|\right|j}. \mathcal{S}$将$\left(\boldsymbol{w}\right||j,{\boldsymbol{a}}_{j}{{\boldsymbol{r}}_{\boldsymbol{w}\left|\right|j}}^{-1},{\boldsymbol{r}}_{\boldsymbol{w}\left|\right|j},{\boldsymbol{T}}_{\boldsymbol{w}\left|\right|j})$加入列表${L}_{2}$，最后将${\boldsymbol{r}}_{\boldsymbol{w}\left|\right|j}$返回给$\mathcal{A}$.

③ 陷门问询${O}_{T}$. 当从$\mathcal{A}$接收到时间段$j$的关键字$\boldsymbol{w}$的查询时，$\mathcal{S}$首先查找列表${L}_{2}$，如果$\left(\boldsymbol{w}\right||j,{\boldsymbol{a}}_{j}{{\boldsymbol{r}}_{\boldsymbol{w}\left|\right|j}}^{-1}, {\boldsymbol{r}}_{\boldsymbol{w}\left|\right|j},{\mathbf{T}}_{\boldsymbol{w}\left|\right|j})$在列表${L}_{2}$中，运行$ASampPre({\boldsymbol{a}}_{j}{{\boldsymbol{r}}_{\boldsymbol{w}\left|\right|j}}^{-1},{\boldsymbol{T}}_{\boldsymbol{w}\left|\right|j},u, \sigma )\to {\boldsymbol{t}}_{\boldsymbol{w}\left|\right|j}$，将${\boldsymbol{t}}_{\boldsymbol{w}\left|\right|j}$返回给$\mathcal{A}$.

④ 私钥问询${O}_{T}$. 若$\mathcal{A}$在某个时间段内进行私钥问询，本研究假设它已经执行了所有相关的${H}_{1}$问询.$\mathcal{A}$查询时间段$j > {j}^{*}$的数据使用者的私钥，$\mathcal{S}$可以向$\mathcal{A}$提供相应的私钥${\boldsymbol{T}}_{j}$，如下所示. 对于前一个时间段$i={j}^{*}+ 1$的问询，$\mathcal{S}$在列表${L}_{1}$中查找$\left(\bar{\boldsymbol{a}}\right||i,{\boldsymbol{a}}_{i},{\boldsymbol{r}}_{i},{\boldsymbol{T}}_{i}). \mathcal{S}$计算${h}_{i-j}={H}_{1}\left(\bar{\boldsymbol{a}}\right|\left|j\right){H}_{1}\left(\bar{\boldsymbol{a}}\right||j-1) … {H}_{1}\left(\bar{\boldsymbol{a}}\right|\left|i+1\right)$，并运行算法$BasisDel({\boldsymbol{a}}_{i},{h}_{i-j},\beta ,{\boldsymbol{T}}_{i})\to {\boldsymbol{T}}_{j}$，将${\boldsymbol{T}}_{j}$返回给$\mathcal{A}$.

3）挑战阶段. $\mathcal{A}$将时间段${j}^{*}$的挑战关键字$({\boldsymbol{w}}_{0}^{*},{\boldsymbol{w}}_{1}^{*})$ 和挑战位图索引$({\eta }_{0}^{*},{\eta }_{1}^{*})$发送给$\mathcal{S}. \mathcal{S}$随机选择1个比特$x\leftarrow \left\{\mathrm{0,1}\right\}$. 如果$x=0$，则$\mathcal{S}$返回与关键字${\boldsymbol{w}}_{0}^{*}$关联的随机密文${\boldsymbol{c}}_{{\boldsymbol{w}}_{x}^{*},{j}^{*},{\eta }_{x}^{*}}$给$\mathcal{A}$. 否则，$\mathcal{S}$执行如下操作. 采样$\upsilon \leftarrow$ $\left\{\mathrm{0,1}\right\}$，设置挑战密文${\boldsymbol{c}}^{*}=(\upsilon ,\boldsymbol{b}',{q}_{\partial +2}+\left\lfloor {q/}\upsilon \right\rfloor )$和${\boldsymbol{c}\boldsymbol{'}}^{*}=({q}_{\partial +3}+ \left\lfloor {q/2} \right\rfloor \upsilon ,{q}_{\partial +4})$. 最后，$\mathcal{S}$将${\boldsymbol{c}}_{{\boldsymbol{w}}_{x}^{*},{j}^{*},{\eta }_{x}^{*}}=({\boldsymbol{c}}^{*},{\boldsymbol{c}\boldsymbol{'}}^{*})$返回给$\mathcal{A}$.

4）猜测阶段. $\mathcal{S}$将$\mathcal{A}$的输出作为输出.

根据上述设置，$\bar{\boldsymbol{a}}={\boldsymbol{a}'\left({\boldsymbol{r}}_{{j}^{*}}^{*}{{\boldsymbol{r}}_{{j}^{*}-1}^{*}… \boldsymbol{r}}_{1}^{*}{\boldsymbol{r}}^{*}\right)}^{-1}$，有${\boldsymbol{a}}_{j}= \bar{\boldsymbol{a}}{h}_{j}^{-1}=\boldsymbol{a}'$，$\boldsymbol{b}\boldsymbol{'}=\boldsymbol{a}\boldsymbol{'}s+\boldsymbol{e}$，${q}_{\partial +2}+\left\lfloor {q/2} \right\rfloor \upsilon ={p}_{\partial +2}s+{e}_{\partial +2}+\left\lfloor {q/2} \right\rfloor \upsilon , {q}_{\partial +3}+ \left\lfloor {q/2} \right\rfloor\upsilon = {p}_{\partial +3}s+{e}_{\partial +3}+\left\lfloor {q/2} \right\rfloor\upsilon ,{q}_{\partial +4}={p}_{\partial +4}s+{e}_{\partial +4}$. 假设$\mathcal{A}$能够以不可忽略的概率$\mathrm{\epsilon }$区分理想世界${Ideal}_{\mathcal{A},\mathcal{S}}\left(\lambda \right)$和现实世界${Real}_{\mathcal{A},\mathcal{S}}\left(\lambda \right)$，那么$\mathcal{A}$便有概率$\epsilon$成功地猜出与关键字${\boldsymbol{w}}_{1}^{*}$相关的PEKS密文. 若此时关键字${\boldsymbol{w}}_{1}^{*}$恰好是第${J}^{*}$次${H}_{2}$问询，这种情况发生的概率是$1/Q$. 对于时间段$j\in [1,\vartheta ]$，$\mathcal{A}$能够以$1/\vartheta$的概率成功猜出时间段$j={j}^{*}$的私钥. 因此，如果$\mathcal{A}$能够以不可忽略的概率$\epsilon$区分理想世界${Ideal}_{\mathcal{A},\mathcal{S}}\left(\lambda \right)$和现实世界${Real}_{\mathcal{A},\mathcal{S}}\left(\lambda \right)$，则$\mathcal{S}$具有至少为$\epsilon /\vartheta Q$的不可忽略概率解决RLWE问题. 证毕.

6.   性能分析

本节对构造的基于RLWE的公钥可搜索方案与现有PEKS方案（QZ方案^[22]、BOYa方案^[21]、BOYb方案^[21]、ZXW+方案^[12]、XCC+方案^[33]、WCX+方案^[28]和ZHN+方案^[8]）进行了安全特性、计算复杂度、存储复杂度以及计算效率等方面的分析和比较. 表3展示了本文提出的方案与现有PEKS方案的安全特性比较.

表  3  与PEKS方案的安全特性比较

Table  3.  Security Properties Compared with PEKS Scheme

方案	后量子安全	前向安全	后向安全	安全性假设
QZ方案[22]	是	否	否	RLWE
BOYa方案[21]	是	否	否	LWE
BOYb方案[21]	是	否	否	NTRU
ZXW+方案[12]	是	是	否	LWE
XCC+方案[33]	是	是	否	LWE
WCX+方案[28]	是	否	否	LWE
ZHN+方案[8]	否	否	否	CDH
本文方案	是	否	否	RLWE
本文扩展方案	是	是	是	RLWE

下载: 导出CSV 

| 显示表格

6.1   计算复杂度分析

本文提出的PEKS方案的计算复杂度如表4所示. 设${T}_{H}{，T}_{M}，{T}_{SP}$，${T}_{SL}，{T}_{ASP}$，${T}_{XOF}$，${T}_{NBD}$分别表示通用乘法、通用哈希函数、$SamplePre$算法^[20]、$SampleLeft$算法^[21]、$ASampPre$算法、可扩展输出函数XOF和格基委托算法$NewBasisDel$^[30]的运行时间. 令$l$为关键字的长度，$\rho ，\kappa$与安全参数有关的参数，$\xi$为执行$SamplePre$算法^[20]的次数. 在本文提出的PEKS方案中，可扩展输出函数XOF的操作可离线计算. 方案生成检索陷门的过程为：根据接收方的公钥种子，计算实际的公钥参量；计算预先设定搜索的关键字的哈希值；基于近似陷门采样$ASampPre$算法，生成多项式，该多项式作为生成检索陷门. 因此，陷门生成算法仅需要1次XOF操作、1次哈希操作和1次$ASampPre$算法. 即，陷门生成算法的计算复杂度为${T}_{H}+{T}_{XOF}+{T}_{ASP}$.

表  4  基于格的PEKS方案的计算复杂度和存储复杂度

Table  4.  Computational Complexity and Storage Complexity of Lattice-Based PEKS scheme

方案	计算复杂度				存储复杂度
	陷门生成算法	加密算法	测试算法		公钥	私钥	陷门	密文
QZ方案[22]	${T}_{H}+{T}_{SP}+kn{T}_{M}$	${T}_{H}+(kn+mn+n){T}_{M}$	$mn{T}_{M}$		$n\left|q\right|\left(\right|q|+3)$	$2n\left|q\right|$	$n\left|q\right|(1+\left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{b}\sigma} \right\rceil )$	$n\left|q\right|\left(\right|q|+4)$
BOYa方案[21]	${T}_{H}+{T}_{SP}$	${2T}_{H}+2n{T}_{M}$	${2T}_{H}+n{T}_{M}$		$n\left|q\right|$	$4{n}^{2}\left|q\right|$	$3n\left|q\right|$	$n\left|q\right|$
BOYb方案[21]	${T}_{SL}+l{T}_{M}$	${\rho }^{2}({n}^{2}+2mn+m+l+1)n{T}_{M}$	$2\rho n{T}_{M}$		$m\left|q\right|\left(\right(\mu +2)n+1)$	${n}^{2}\left|q\right|$	$\epsilon \left(\right|q|+2n|q|+1)$	$2n\left|q\right|$
ZXW+方案[12]	${T}_{NBD}+{T}_{SP}+{T}_{SL}$	$({mn}^{2}+m\rho +nm\rho ){T}_{M}$	$n\rho {T}_{M}$		$(2nm+m+2{n}^{2})\left|q\right|$	${n}^{2}\left|q\right|$	$n\left|q\right|$	$\left(1+n\right)$ $\rho \left|q\right|$
XCC+方案[33]	$2{T}_{H}+{T}_{SL}+{T}_{SP}+$ $(\kappa n+\kappa m+\kappa +l){T}_{M}$	$(\rho +1){T}_{H}+{T}_{SL}+{T}_{SP}+$ $(\kappa n+\kappa m+\kappa +4\rho {n}^{2}+$ $3\rho nm+2\rho n+\rho l){T}_{M}$	$4\rho n{T}_{M}$		$2n\left|q\right|+m\kappa \left|q\right|+$ $nm(l+2)\left|q\right|$	$m\left|q\right|+n\kappa \left|q\right|$	$4n\left|q\right|$	$\rho \left(\right|q|+4n|q|+1)$
WCX+方案[28]	${\xi T}_{SP}$	$(\xi m+\xi +nm+nm\rho ){T}_{M}$	$2n\xi {T}_{M}$		$(nm\rho +2nm+m+{n}^{2})\left|q\right|$	(${n}^{2}+2n\left)\right|q|$	$2n\xi \left|q\right|$	$(\xi +1+n+n\rho )\left|q\right|$
本文方案	${T}_{H}+{T}_{XOF}+{T}_{ASP}$	${T}_{H}+{T}_{XOF}+(\partial n+3n){T}_{M}$	$(\partial n+2n){T}_{M}$		${l}'+\partial n\left|q\right|$	$2n\left|q\right|$	$2n\left(1+\left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{b}{\sigma }_{1}} \right\rceil \right)+$ $\partial n\left(1+\left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{b}{\sigma }_{2}} \right\rceil \right)$	$\left(\partial +4\right)$ $n\left|q\right|$

下载: 导出CSV 

| 显示表格

发送方根据密钥为每个加密文件附加的关键字生成可搜索密文的过程为：根据接收方的公钥种子，计算实际的公钥参量；计算每个加密文件附加的关键字的哈希值；均匀随机选取多项式，再结合公钥参量，生成可搜索密文. 因此，加密算法需要1次$XOF$操作、1次哈希操作和$\partial n+3n$次乘法. 即，加密算法的计算复杂度为${T}_{H}+{T}_{XOF}+(\partial n+3n){T}_{M}$. 在测试算法中，服务器根据检索陷门来检索所有可搜索密文的过程为：根据检索陷门和可搜索密文，计算判断参量$\bar{c}$. 测试算法仅需要$\partial n+2n$次乘法. 即，测试算法的计算复杂度为$(\partial n+ 2n){T}_{M}.$

6.2   存储复杂度分析

表4描述了基于格的PEKS方案的存储复杂度，其中，$n$是维数，$\left|q\right|$是模数$q$的比特长度，${l}'$是种子长度，$\partial$是向量f的维数，$\epsilon ，\mu$是与安全参数有关的参数. 在本文提出的PEKS方案中，公钥$\left(\mathcal{H},b\right)$

$\in {l\mathcal{'}+\mathcal{R}}^{\partial }$，则公钥的大小为$l'+\partial n\left|q\right|$. 方案的私钥为$\boldsymbol{R}\in {\mathcal{R}}_{q}^{2\times \partial }$，那么私钥的大小为$2n\left|q\right|$. 陷门为近似陷门采样$ASampPre$算法生成的多项式${\boldsymbol{t}}_{\boldsymbol{w}}\in {\mathcal{R}}_{q}^{2+\partial }$. 因此，陷门的大小为$2n(1 +\left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{b}\;{\sigma }_{1}} \right\rceil )+\partial n(1 +\left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{b}\;{\sigma }_{2}} \right\rceil )$. 密文的大小为$(\partial +4)n\left|q\right|$.

对于80 b的具体安全性，表5列出了基于格的PEKS方案的存储需求. 在本文提出的方案中，设置$n=512，q=62，l'=256，{\sigma }_{1}=11 902.21，{\sigma }_{2}=43.61，\partial =62$. 在QZ方案^[22]中，设置$n=512，\left|q\right|=62，\sigma =11 902.21$. 在BOYa方案^[21]中，设置$n=512，\left|q\right|=23$. 在其余的4个方案BOYb方案^[21]、ZXW+方案^[12]、XCC+方案^[33]、WCX+方案^[28]中，设置$m=256，n=9 753， \epsilon =\rho =\kappa = \xi =10$，$q=12，\mu =10$. 由表5可知， BOYa方案^[21]的密钥、陷门和密文存储开销最小. 与基于RLWE的PEKS方案相比，本文提出的PEKS方案比QZ方案^[22]降低了4.6%的公钥存储开销和50.1%的陷门存储开销. 与基于LWE的PEKS方案相比，本文提出的PEKS方案比BOYb方案^[21]降低了99.5%的公钥存储开销，99.9%的私钥存储开销和89.9%的陷门存储开销；本文提出的PEKS方案比ZXW+方案^[12]降低了99.9%的公钥存储开销和99.9%的私钥存储开销；本文提出的PEKS方案比XCC+方案^[33]降低了99.4%的公钥存储开销，94.5%的私钥存储开销，49.2%的陷门存储开销和55.2%的密文存储开销；本文提出的PEKS方案比WCX+方案^[28]降低了99.8%的公钥存储开销，99.9%的私钥存储开销和89.9%的陷门存储开销.

表  5  基于格的PEKS方案的存储需求

Table  5.  Storage Requirements of Lattice-Based PEKS Scheme Kb

方案	公钥	私钥	陷门	密文
QZ方案[22]	2 015	62	465	2 046
BOYa方案[21]	12	23 552	35	12
BOYb方案[21]	351 111	1 114 699	2 286	229
ZXW+方案[12]	2 287 919	1 114 699	114	1 143
XCC+方案[33]	351 366	1146	457	4 572
WCX+方案[28]	1 465 810	1 114 927	2 286	1 257
本文方案	1 922	62	232	2 046

下载: 导出CSV 

| 显示表格

6.3   计算效率评估

本文提出的PEKS方案的性能评估是用C++实现的，并在AMD Ryzen 7 4700U笔记本电脑上执行，该笔记本电脑配有Radeon Graphics 2.0 GHz CPU和16 GB RAM. 为了全面的对比效率，将本文提出的PEKS方案与基于双线性对的ZHN+方案^[8]，基于NTRU的BOYa方案^[21]，基于LWE的WCX+方案^[28]和基于RLWE的QZ方案^[22]这4种方案进行对比. 本研究在密钥生成$KeyGen$、陷门生成算法$Trapdoor$、加密算法$Encrypt$、测试算法$Test$这4个方面进行了比较. 图6给出了这5种PEKS方案的陷门生成算法$Trapdoor$、加密算法$Encrypt$、测试算法$Test$被运行10 000次时的平均运行时间.

图  6  每个算法的平均运行时间

Figure  6.  Average running time of each algorithm

下载: 全尺寸图片 幻灯片

用户每查询1个关键字执行1次陷门生成算法. 随着关键字数量的增加，陷门生成时间呈线性增长，如图7所示. 结果表明，BOYa方案^[21]、 QZ方案^[22]和本文提出的PEKS方案具有较低的陷门生成耗时. 这3种PEKS方案都采用了高效的高斯采样算法. 由于有效的基于小工具的格陷门，QZ方案^[22]和本文提出的PEKS方案的陷门生成耗时少于BOYa方案^[21]. QZ方案^[22]和本文提出的PEKS方案的高斯原像采样算法需要这包括结合2个阶段：使用$SampleP$算法生成扰动向量；使用$SampleGadget$从特定格采样. 相比于QZ方案^[22]，本文提出的近似陷门采样算法需要较少的乘法运算，这使得本文提出的陷门生成耗时比QZ方案^[22]的低. 当为1 000个关键字生成陷门时，本文提出的PEKS方案的耗时为7.8s，而BOYa方案^[21]， QZ方案^[22]，WCX+方案^[28]和ZHN+方案^[8]的耗时分别为9.71 s，8 s，511 s，35 s. 本文提出的PEKS方案在$Trapdoor$算法中的耗时分别比BOYa方案^[21] 、QZ方案^[22] 、WCX+方案^[28] 、ZHN+方案^[8]方案低约19.67%，2.5%，98.47%，77.71%.

图  7  陷门生成的时间

Figure  7.  Time of trapdoor generation

下载: 全尺寸图片 幻灯片

用户每提取1个关键字，就执行1次加密算法. 因此，密文生成时间随着关键字数量的增加呈线性增加，如图8所示. 另外，随着文件数量的增加（平均每个文件包含10个关键字），密文生成时间呈线性增长，如图9所示. 结果表明，QZ方案^[22]和本文提出的PEKS方案具有较低的密文生成耗时. 本文提出的PEKS方案和QZ方案^[22]都需要计算每个加密文件附加的关键字的哈希值；均匀随机选取多项式，再结合公钥参量，生成可搜索密文. 区别在于QZ方案^[22]需要将哈希值附加在用户的公钥上. 这需要额外的模乘运算. 因此，本文提出的PEKS方案的效率高于QZ方案^[22]. 当搜索1 000个关键字时，本文提出的PEKS方案的耗时为4 s，而QZ方案^[22]，WCX+方案^[28]和ZHN+方案^[8]的耗时分别为4.5 s，95 s，105 s. 本文提出的PEKS方案在$Encrypt$算法中的耗时分别比QZ方案^[22] 、WCX+方案^[28] 、ZHN+方案^[8]低约11.11%，95.78%，96.19%.

图  8  随关键字数量变化密文生成的时间

Figure  8.  Time of ciphertext generation changes with the number of keywords

下载: 全尺寸图片 幻灯片

图  9  随文件数量变化密文生成的时间

Figure  9.  Time of ciphertext generation changes with the number of files

下载: 全尺寸图片 幻灯片

对于每个搜索查询，服务器执行1次测试算法. 因此，测试算法的效率尤为重要. 请注意，测试时间取决于安全级别、关键字的平均长度和硬件. 在本文的环境中，以平均关键字长度为10个字母，安全级别为80b为例，采集结果如图10所示. 结果表明，BOYa方案^[21]、 QZ方案^[22]和本文提出的PEKS方案具有较低的搜索耗时. 由于多项式环上快速傅里叶变换，本文提出的PEKS方案和QZ方案^[22]的测试算法都比BOYa方案^[21]更高效. 当搜索1 000个关键字时，本文提出的PEKS测试耗时为0.48 s，而BOYa方案^[21]，QZ方案^[22]、 WCX+方案^[28] 、ZHN+方案^[8]的耗时分别为0.65 s，0.48 s，27 s，35 s. 本文提出的PEKS方案在Encrypt算法中的耗时分别比BOYa方案^[21] 、WCX+方案^[28] 、ZHN+方案^[8]低约26.15%，98.22%，98.62%.

图  10  测试时间

Figure  10.  Time of testing

下载: 全尺寸图片 幻灯片

7.   结　　论

针对抗量子公钥可搜索加密方案的高计算效率、低存储开销、以及前向和后向安全等问题，首先设计了一种基于RLWE的公钥可搜索加密方案. 通过使用一种新的近似陷门采样算法，并结合非球面高斯采样技术和理想可扩展输出函数，所提方案具有更低的密钥、陷门存储开销以及更高的计算效率. 其次，通过引入密钥更新、位图索引和格同态加密技术，提出了一种具有前向安全和后向安全的扩展方案来进一步提高实用性. 最后，理论分析和实验结果表明，所提方案不仅降低了密钥和陷门的存储开销，而且具有更高的搜索效率. 轻量级的可搜索加密方案以及具有丰富的搜索功能的可搜索加密方案仍值得进一步深入研究.

作者贡献声明：戚丽君负责方法调研，完成实验和数据分析，并撰写论文初稿；庄金成参与方案的实验设计，提出指导意见并参与论文修改.