Processing math: 0%
  • 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
高级检索

基三众核架构中基于同步哈密顿环的无死锁策略

李春峰, Karim Soliman, 计卫星, 石峰

李春峰, Karim Soliman, 计卫星, 石峰. 基三众核架构中基于同步哈密顿环的无死锁策略[J]. 计算机研究与发展, 2025, 62(4): 930-949. DOI: 10.7544/issn1000-1239.202331042
引用本文: 李春峰, Karim Soliman, 计卫星, 石峰. 基三众核架构中基于同步哈密顿环的无死锁策略[J]. 计算机研究与发展, 2025, 62(4): 930-949. DOI: 10.7544/issn1000-1239.202331042
Li Chunfeng, Karim Soliman, Ji Weixing, Shi Feng. Deadlock-Free Strategies Based on Synchronized Hamiltonian Ring in Triplet-Based Many-Core Architecture[J]. Journal of Computer Research and Development, 2025, 62(4): 930-949. DOI: 10.7544/issn1000-1239.202331042
Citation: Li Chunfeng, Karim Soliman, Ji Weixing, Shi Feng. Deadlock-Free Strategies Based on Synchronized Hamiltonian Ring in Triplet-Based Many-Core Architecture[J]. Journal of Computer Research and Development, 2025, 62(4): 930-949. DOI: 10.7544/issn1000-1239.202331042
李春峰, Karim Soliman, 计卫星, 石峰. 基三众核架构中基于同步哈密顿环的无死锁策略[J]. 计算机研究与发展, 2025, 62(4): 930-949. CSTR: 32373.14.issn1000-1239.202331042
引用本文: 李春峰, Karim Soliman, 计卫星, 石峰. 基三众核架构中基于同步哈密顿环的无死锁策略[J]. 计算机研究与发展, 2025, 62(4): 930-949. CSTR: 32373.14.issn1000-1239.202331042
Li Chunfeng, Karim Soliman, Ji Weixing, Shi Feng. Deadlock-Free Strategies Based on Synchronized Hamiltonian Ring in Triplet-Based Many-Core Architecture[J]. Journal of Computer Research and Development, 2025, 62(4): 930-949. CSTR: 32373.14.issn1000-1239.202331042
Citation: Li Chunfeng, Karim Soliman, Ji Weixing, Shi Feng. Deadlock-Free Strategies Based on Synchronized Hamiltonian Ring in Triplet-Based Many-Core Architecture[J]. Journal of Computer Research and Development, 2025, 62(4): 930-949. CSTR: 32373.14.issn1000-1239.202331042

基三众核架构中基于同步哈密顿环的无死锁策略

基金项目: 国家自然科学基金项目(60973010)
详细信息
    作者简介:

    李春峰: 1995年生. 博士研究生. CCF学生会员. 主要研究方向为计算机体系结构、高性能计算

    Karim Soliman: 1991年生. 博士研究生. CCF学生会员. 主要研究方向为计算机体系结构、高性能计算

    计卫星: 1980年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为计算机体系结构、高性能计算、代码检测与分析

    石峰: 1961年生. 博士,教授,博士生导师. 主要研究方向为计算机体系结构、高性能计算

    通讯作者:

    石峰(bitsf@bit.edu.cn

  • 中图分类号: TP302

Deadlock-Free Strategies Based on Synchronized Hamiltonian Ring in Triplet-Based Many-Core Architecture

Funds: This work was supported by the National Natural Science Foundation of China (60973010).
More Information
    Author Bio:

    Li Chunfeng: born in 1995. PhD candidate. Student member of CCF. His main research interests include computer architecture and high-performance computing

    Karim Soliman: born in 1991. PhD candidate. Student member of CCF. His main research interests include computer architecture and high-performance computing

    Ji Weixing: born in 1980. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include computer architecture, high-performance computing, and code detection and analysis

    Shi Feng: born in 1961. PhD, professor, PhD supervisor. His main research interests include computer architecture and high-performance computing

  • 摘要:

    确保片上网络(network-on-chip,NoC)中的数据传输无死锁,是NoC为多处理器片上系统(multi-processor system-on-chip,MPSoC)提供可靠通信服务的前提,决定了NoC甚至MPSoC的可用性. 现有的通用防死锁策略难以发挥出特定拓扑结构的自身特点和优势,甚至可能会增加网络延迟、功耗以及硬件复杂性. 另外,由于路由级和协议级死锁存在显著差异,现有无死锁方案较难同时解决这2类死锁问题,影响了MPSoC的可靠性. 利用基三众核架构(triplet-based many-core architecture,TriBA)中拓扑结构自身具有的哈密顿特性提出了基于同步哈密顿环的无死锁策略,该策略依据拓扑结构自身的对称轴和哈密顿边对数据传输进行分类,预防了协议级死锁并提高了数据传输速度;同时使用循环链表技术判断同一缓冲区内数据同步传输方向,消除了路由级死锁并降低了数据传输延迟. 在优化前瞻路由算法基础上,设计了基于同步哈密顿环的无死锁路由机制HamSPR(Hamiltonian shortest path routing). GEM5仿真结果表明,与TriBA现有方法相比,HamSPR在合成流量下的平均数据包延迟和功耗分别降低了8.78% ~ 65.40% 和6.94% ~ 34.15%,吞吐量提高了8.00% ~ 59.17%;在PARSEC测试集下的应用运行时间和平均数据包延迟分别最高实现了16.51%和42.75%的降低. 与2D-Mesh架构相比,TriBA在PARSEC测试集下的应用性能实现了1% ~ 10%的提升.

    Abstract:

    Ensuring deadlock-free data transmission in the network-on-chip (NoC) is a prerequisite for providing reliable communication services for multi-processor system-on-chip (MPSoC), directly determining the availability of NoC and even MPSoC. Existing general-purpose deadlock-free strategies are oriented to arbitrary topologies, making it challenging to utilize the features and advantages of a specific topology. Moreover, these strategies may even increase network latency, power consumption, and hardware complexity. In addition, due to significant differences in the regular network between routing-level and protocol-level deadlocks, existing solutions struggle to simultaneously address both types of deadlock issues, affecting MPSoC reliability. We propose a deadlock-free strategy with synchronous Hamiltonian rings based on the inherent Hamiltonian characteristics of the triplet-based many-core architecture (TriBA). This method uses the topology’s symmetric axes and Hamiltonian edge to allocate independent store-and-forward buffers for data transmission, preventing protocol-level deadlocks and improving data transfer speed. Additionally, we design a directional determination method for data transmission within the same buffer using cyclic linked-list technology. This method ensures data independence and synchronous forward transmission, eliminates routing-level deadlocks, and reduces data transfer latency. Based on optimizing redundant calculations in look-ahead routing algorithms, we propose a deadlock-free routing mechanism called Hamiltonian shortest path routing (HamSPR) based on a synchronous Hamiltonian ring. GEM5 simulation results show that, compared with existing solutions in the TriBA, HamSPR reduces average packet latency and power consumption in synthetic traffic patterns by 18.78%−65.40% and 6.94%−34.15%, respectively, while improving throughput by 8.00%−59.17%. In the PARSEC benchmark, HamSPR achieves maximum reductions of 16.51% in application runtime and 42.75% in average packet latency, respectively. Moreover, compared with 2D-Mesh, TriBA demonstrates an application performance improvement of 1%−10% in PARSEC benchmark.

  • 云存储和计算以较大的存储容量、灵活的可访问性、和高效的数据管理等优势被引入来解决庞大数据的存储与计算需求. 通过将敏感数据外包给云服务器,个人和企业减轻了本地数据管理和维护的负担. 为了保证存储数据的隐私性和安全性,数据所有者在将共享数据外包给云服务器之前会进行加密处理. 然而,在此情境下,用户面临着在海量数据中难以执行关键字搜索的挑战,这在一定程度上阻碍了云环境下文件共享的灵活性. 因此,如何安全、高效地检索云数据变得尤为重要. 可搜索加密[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%.

    构造基于格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在云计算中发挥更大的潜力.

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

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

    符号表示. 令粗体小写字母如 \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} . 记满秩格

    \varLambda \left(\boldsymbol{B}\right)=\sum _{i=1}^{m}{{\boldsymbol{x}}_{i}\boldsymbol{b}}_{i},{\boldsymbol{x}}_{i}\in \mathbb{Z}.

    多项式环 {\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) 定义为格上的离散高斯分布,其中

    {\rho }_{\sigma ,\boldsymbol{z}}\left(\varLambda \right)=\sum _{\boldsymbol{x}\in \varLambda }{\rho }_{\sigma ,\boldsymbol{z}}\left(\boldsymbol{x}\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 .

    本节将介绍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) 是可忽略的,那么方案满足密文不可区分性.

    本节提供了一种优化的公钥可搜索加密方案. 方案使用一种新的近似陷门采样算法[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 
    | 显示表格

    优化技术包括采用一种新的近似陷门采样[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{\%} 的公钥内存开销.

    本文提出的公钥可搜索加密方案包括下面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 808080
    n 5121 0241 024
    {\mathrm{l}\mathrm{o}\mathrm{g}}_{b}q 626262
    {\mathrm{l}\mathrm{o}\mathrm{g}}_{b}p 323232
    {\mathrm{l}\mathrm{o}\mathrm{g}}_{b}l 303030
    l' 256256256
    r 6.534.2
    \partial 626262
    \tau 6.76.36.2
    {\sigma }_{1} 11 902.2110 523.4610 192.64
    {\sigma }_{2} 43.619.2918.21
    下载: 导出CSV 
    | 显示表格

    前向安全性是动态可搜索加密方案的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 .

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

    定理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} .

    扩展方案的安全性分别用理想世界 {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问题. 证毕.

    本节对构造的基于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 
    | 显示表格

    本文提出的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}.

    表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 015624652 046
    BOYa方案[21]1223 5523512
    BOYb方案[21]351 1111 114 6992 286229
    ZXW+方案[12]2 287 9191 114 6991141 143
    XCC+方案[33]351 36611464574 572
    WCX+方案[28]1 465 8101 114 9272 2861 257
    本文方案1 922622322 046
    下载: 导出CSV 
    | 显示表格

    本文提出的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

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

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

  • 图  1   NoC中路由级和协议级死锁产生示意图

    Figure  1.   Illustration of routing-level and protocol-level deadlocks generation in NoC

    图  2   基于同步哈密顿环的无死锁策略示意图

    Figure  2.   Illustration of deadlock-free strategy based on synchronized Hamiltonian rings

    图  3   TriBA-NoC的拓扑结构示意图

    注:ε表示占位符,可由不同的数字取代.

    Figure  3.   Illustration of TriBA-NoC topology structure

    图  4   TriBA-NoC的布局布线示意图[7]

    Figure  4.   Illustration of layout and wiring for TriBA-NoC[7]

    图  5   {TC}^{F} 中不同的路由子图及传输模式和路径示意图

    Figure  5.   Illustration of the different routing subgraphs in {TC}^{F} , as well as the transmission modes and paths

    图  6   {TC}^{F} 尖端 {1}^{F} {2}^{F} 之间的H-路径(以 {TC}^{3} 为例)

    Figure  6.   H-path between apex {1}^{F} and {2}^{F} (taking TC^3 for example)

    图  7   {TC}^{F} 尖端之间的哈密顿环(以TC^{3} 为例)

    Figure  7.   H-cycle between apex of {TC}^{F} (taking TC^3 for example)

    图  8   {TC}^{3} 中的虚拟哈密顿环流

    Figure  8.   Virtual Hamiltonian ring flow in {TC}^{3}

    图  9   {TC}^{f} 尖端 {1}^{f} {2}^{f} 之间的 \mathrm{H} -路径及其相关对称轴

    Figure  9.   H-path betwee 1f and 2f in apex TCf and its associated symmetry axis

    图  10   基于同步哈密顿环的无死锁策略中对称轴选择和最大边判断示例

    Figure  10.   Example of symmetry axis selection and maximum edge determination in a deadlock-free strategy based on synchronous Hamiltonian rings

    图  11   路由计算流水线硬件实现模块图

    Figure  11.   Block diagram of the pipeline hardware implementation for routing computation

    图  12   HamSPR在GEM5中路由器微架构的实现

    Figure  12.   Router microarchitecture implemented in GEM5 for HamSPR

    图  13   {TC}^{3} 中不同路由算法在合成流量模式下的平均数据包延迟和吞吐量

    Figure  13.   Average data packet latency and throughput of different routing algorithms in {TC}^{3} under synthetic traffic patterns

    图  14   {TC}^{3} 中不同路由算法在PARSEC应用程序下的归一化运行时间和平均数据包延迟

    Figure  14.   Normalized runtime and average data packet latency of different routing algorithms in {TC}^{3} under PARSEC applications

    图  15   {TC}^{3} 中不同路由算法在PARSEC应用程序下的平均数据包跳数

    Figure  15.   Average data packet hops of different routing algorithms in {TC}^{3} under PARSEC applications

    图  16   不同架构的路由算法在PARSEC应用程序下的运行时间和平均数据包延迟

    Figure  16.   Runtime and average data packet latency of routing algorithms with different architectures under PARSEC applications

    图  17   {TC}^{3} 中不同路由算法在合成流量和PARSEC应用程序下的归一化平均数据包功耗

    Figure  17.   Normalized average data packet power consumption of different routing algorithms in {TC}^{3} under the synthetic traffic and PARSEC applications

    表  1   TriBA架构下的路由解决方案

    Table  1   Routing Solutions Schemes Under TriBA Architecture

    算法 对比方法 延迟
    \downarrow
    吞吐量
    \uparrow
    功耗
    \downarrow
    路由级
    死锁
    协议级
    死锁
    Look-up Table[11] 2D-Mesh × ×
    DDRA[35] × ×
    Min-DDRA[36] DDRA × ×
    DM4T[27] DDRA × ×
    SPORT[37] DDRA和
    Min-DDRA
    × ×
    SPR4T[3] SPORT × ×
    LA4T[38] DDRA和SPORT ×
    HamSPR(本文) SPR4T和LA4T
    注: \downarrow 表示降低; \uparrow 表示提升;√ 表示满足;× 表示不满足.
    下载: 导出CSV

    表  2   SE模式和FS模式下的仿真参数

    Table  2   Simulation Parameters in SE and FS Modes

    模式 参数 数值
    SE 节点数 27
    仿真和预热/周期 400001000
    虚拟网络和通道 3,4
    路由器延迟/周期 4
    线路延迟/周期 1
    死锁阈值/周期 150
    缓存一致性协议 Garnet Standalone
    数据包交换 Wormhole
    Flit大小/b 128
    SA分配策略 Round-Robin
    CPU频率/GHz 1.0
    FS ISA x86
    系统内核 x86-Linux-kernel-4.19.83
    CPU类型 x86KVMCPU,2.0 GHz
    L1 cache Private, 16 KB, 2-way associative,
    64 B block size
    L2 cache Shared, 2 MB, 8-way associative,
    64 B block size
    内存类型 SimpleMemory,3 GB
    缓存一致性协议 MESI Two Level
    基准测试集规模 simsmall
    下载: 导出CSV

    表  3   HamSPR在不同网络规模下相比其他算法的性能差异

    Table  3   Performance Variation of HamSPR Compared with Other Algorithms with Different Network Scales

    网络规模 平均数据包延迟降低/% 吞吐量提升/%
    Table SPR4T LA4T Table SPR4T LA4T
    9 46.67 43.84 40.75 27.29 26.29 21.21
    27 48.28 45.78 39.46 27.35 27.35 19.69
    81 45.35 43.94 37.64 25.86 26.56 18.74
    243 45.95 42.98 37.17 26.08 26.44 19.22
    方差 1.2053 1.0422 2.0631 0.4662 0.1691 0.8597
    下载: 导出CSV
  • [1]

    Yazdanpanah F, Afsharmazayejani R. A systematic analysis of power saving techniques for wireless network-on-chip architectures[J]. Journal of Systems Architecture, 2022, 126: 102485 doi: 10.1016/j.sysarc.2022.102485

    [2]

    Della Vecchia G, Sanges C. A recursively scalable network VLSI implementation[J]. Future Generation Computer Systems, 1988, 4(3): 235−243 doi: 10.1016/0167-739X(88)90007-6

    [3] 石峰,陈旭,尹飞,等. 基于 S3 变换的 TriBA-Net 最短路径路由机制[J]. 中国科学:信息科学,2018,48(1):100−114 doi: 10.1360/N112017-00065

    Shi Feng, Chen Xu, Yin Fei, et al. A shortest path routing mechanism based on S3 for TriBA-Net[J]. SCIENTIA SINICA Informationis, 2018, 48(1): 100−114 (in Chinese) doi: 10.1360/N112017-00065

    [4] 张洋,王达,叶笑春,等. 众核处理器片上网络的层次化全局自适应路由机制[J]. 计算机研究与发展,2016,53(6):1211−1220 doi: 10.7544/issn1000-1239.2016.20150149

    Zhang Yang, Wang Da, Ye Xiaochun, et al. A global hierarchical adaptive routing mechanism in many-core processor network-on-chip[J]. Journal of Computer Research and Development, 2016, 53(6): 1211−1220 (in Chinese) doi: 10.7544/issn1000-1239.2016.20150149

    [5]

    Feng Yinxiao, Xiang Dong, Ma Kaisheng. Heterogeneous die-to-die interfaces: Enabling more flexible chiplet interconnection systems[C]//Proc of the 56th Annual IEEE/ACM Int Symp on Microarchitecture. New York: ACM, 2023: 930−943

    [6]

    Bakhouya M, Suboh S, Gaber J, et al. Analytical performance comparison of 2D mesh, wk-recursive, and spidergon nocs [C/OL]//Proc of the 19th IEEE Int Symp on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW). Piscataway, NJ: IEEE, 2010[2024-05-22]. https://ieeexplore.ieee.org/abstract/document/5470784

    [7] 石峰,魏增辉,王一拙,等. 一种多/众核架构TriBA-CMPs的布局布线方案tMesh:中国,CN107526894A[P]. 2017-12-29

    Shi Feng, Wei Zenghui, Wang Yizhuo, et al. A layout and routing scheme named tMesh for a multi/many-core architecture TriBA-CMPs: China, CN107526894A[P]. 2017-12-29 (in Chinese)

    [8]

    Braham C C, Ji Weixinga, Zhang Lingyu. The design and implementation of a hierarchical network on chip[J]. Procedia Engineering, 2012, 29: 2966−2974

    [9]

    Feng Shi, Yang Zhang. Design and evaluation of low-latency and shortest-path routing algorithm for triplet-based hierarchical interconnection network[J]. Journal of Testing and Evaluation, 2013, 41(4): 541−550 doi: 10.1520/JTE20120212

    [10]

    Khan HUR, Shi Feng, Ji Weixing, et al. Computationally efficient locality-aware interconnection topology for multi-processor system-on-chip (MP-SoC)[J]. Chinese Science Bulletin, 2010, 55(29): 3363−3371 doi: 10.1007/s11434-010-4118-z

    [11]

    Wang Zuo, Zuo Qi, Li Jiaxin. Triplet-based topology for on-chip networks[J]. WSEAS Transactions on Computers, 2009, 8(3): 516−525

    [12]

    Xue Licheng, Shi Feng, Ji Weixing. 3D floorplanning of low-power and area-efficient network-on-chip architecture[J]. Microprocessors and Microsystems, 2011, 35(5): 484−495 doi: 10.1016/j.micpro.2011.04.001

    [13]

    Zhang Yang, Shi Feng, Zuo Qi, et al. Express router microarchitecture for triplet-based hierarchical interconnection network[C]//Proc of the 14th IEEE Int Conf on High Performance Computing and Communication & 9th IEEE Int Conf on Embedded Software and Systems. Piscataway, NJ: IEEE, 2012: 295−302

    [14]

    Wang Xiaojun, Shi Feng, Zhang Hong. KLSAT: An application mapping algorithm based on Kernighan–Lin partition and simulated annealing for a specific WK-recursive NoC architecture[C]//Proc of the 16th IFIP WG 10.3 Int Conf on Network and Parallel Computing. Berlin: Springer, 2019: 31−42

    [15]

    Zhang Hong, Wang Xiaojun. KGT: An application mapping algorithm based on Kernighan–Lin partition and genetic algorithm for WK-recursive NoC architecture[C]//Proc of the 17th Int Conf on Intelligent Computing Theories and Application (ICIC). Berlin: Springer, 2021: 86−101

    [16]

    Shi Feng, Li Jiaxin, Bai Ziru. Performance of triplet-based interconnection strategy for multi-core on-chip processors[C]//Proc of the 11th IEEE Int Conf on High Performance Computing and Communications. Piscataway, NJ: IEEE, 2009: 163−170

    [17]

    Wang Xiaojun, Shi Feng, Zhang Hong. A novel speedup evaluation for multicore architecture based topology of on-chip memory[C]//Proc of the 10th Int Symp on Parallel Architectures, Algorithms and Programming. Berlin: Springer, 2019: 35−47

    [18]

    Feng Yinxiao, Xiang Dong, Ma Kaishen. A scalable methodology for designing efficient interconnection network of chiplets [C]//Proc of the 2023 IEEE Int Symp on High-Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2023: 1059−1071

    [19]

    Kasan H, Kim J. VVQ: Virtualizing virtual channel for cost-efficient protocol deadlock avoidance[C]//Proc of the 2023 IEEE Int Symp on High-Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2023: 1072−1084

    [20]

    Romanov A Y, Myachin N M, Lezhnev E V, et al. Ring-Split: Deadlock-free routing algorithm for circulant networks on chip[J]. Micromachines, 2023, 14(1): 141 doi: 10.3390/mi14010141

    [21]

    Kwauk G, Kang S, Kasan H, et al. Boomgate: Deadlock avoidance in non-minimal routing for high-radix networks[C]//Proc of the 2021 IEEE Int Sym on High-Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2021: 696−708

    [22]

    Flich J, Skeie T, Mejia A, et al. A survey and evaluation of topology-agnostic deterministic routing algorithms[J]. IEEE Transactions on Parallel and Distributed Systems, 2011, 23(3): 405−425

    [23]

    Wu Yibo, Wang Liang, Wang Xiaohang, et al. A deflection-based deadlock recovery framework to achieve high throughput for faulty NoCs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 40(10): 2170−2183

    [24]

    Razavi S, Sarbazi-Azad H. The triangular pyramid: Routing and topological properties[J]. Information Sciences, 2010, 180(11): 2328−2339 doi: 10.1016/j.ins.2010.02.016

    [25]

    Wang Nengchung, Yen Chengpang, Chu Chihping. Multicast communication in wormhole-routed symmetric networks with Hamiltonian cycle model[J]. Journal of Systems Architecture, 2005, 51(3): 165−183 doi: 10.1016/j.sysarc.2004.11.001

    [26]

    El-Obaid A. Three-dimension Hamiltonian broadcast wormhole-routing[J]. International Journal of Computer Networks & Communications, 2015, 7(3): 31−46

    [27]

    Chen Xu, Shi Feng, Yin Fei, et al. An efficient distributed minimal routing algorithm for triplet-based WK-recursive network[C]//Proc of the 20th IEEE Int Conf on High Performance Computing and Communications; 16th IEEE Int Conf on Smart City; 4th IEEE Int Conf on Data Science and Systems (HPCC/SmartCity/DSS). Piscataway, NJ: IEEE, 2018: 547−554

    [28]

    Fan Dongrui, Zhang Hao, Wang Da, et al. Godson-T: An efficient many-core processor exploring thread-level parallelism[J]. IEEE Micro, 2012, 32(2): 38−47 doi: 10.1109/MM.2012.32

    [29]

    Parasar M, Farrokhbakht H, Jerger N E, et al. DRAIN: Deadlock removal for arbitrary irregular networks[C]//Proc of the 2020 IEEE Int Symp on High Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2020: 447−460

    [30]

    Dally W J, Towles B P. Principles and Practices of Interconnection Networks[M]. Amsterdam: Elsevier, 2004

    [31]

    Ramey C. Tile-GX100 manycore processor: Acceleration interfaces and architecture[C/OL]//Proc of the 23rd IEEE on Hot Chips Symp. Piscataway, NJ: IEEE, 2011[2024-05-22]. https://ieeexplore.ieee.org/abstract/document/7477491

    [32]

    Wentzlaff D, Griffin P, Hoffmann H, et al. On-chip interconnection architecture of the tile processor[J]. IEEE Micro, 2007, 27(5): 15−31 doi: 10.1109/MM.2007.4378780

    [33]

    Sodani A, Gramunt R, Corbal J, et al. Knights landing: Second-generation intel Xeon Phi product[J]. IEEE Micro, 2016, 36(2): 34−46 doi: 10.1109/MM.2016.25

    [34]

    Rahman R. Intel Xeon Phi Coprocessor Architecture and Tools: The Guide for Application Developers[M]. Berlin: Springer, 2013

    [35]

    Qiao Baojun, Shi Feng, Ji Weixing. A new hierarchical interconnection network for multi-core processor[C]//Proc of the 2nd IEEE Conf on Industrial Electronics and Applications. Piscataway, NJ: IEEE, 2007: 246−250

    [36]

    Wang Zuo, Shi Feng. A shortest path routing algorithm in triplet-based network[J]. Transactions of Beijing Institute of Technology, 2009, 29(5): 410−414

    [37]

    Zhang Yang, Shi Feng, Ji Weixing, et al. SPORT: A shortest path routing algorithm for triplet-based hierarchical interconnection[J]. Transactions of Beijing institute of Technology, 2013, 33(1): 57−61

    [38]

    Chen Xu, Shi Feng, Yin Fei, et al. A novel look-ahead routing algorithm based on graph theory for triplet-based network-on-chip router[J]. IEICE Electronics Express, 2018, 15(8): 1−12

    [39] 石峰,阮生强,尹飞,等. 基于尖端子图分类传输数据的基三核间网络防死锁方法:中国,CN112698960B[P]. 2022-08-09

    Shi Feng, Ruan Shenqiang, Yin Fei, et al. A deadlock prevention method for inter-core networks based on apex-subgraph classification for data transmission in triplet-based architecture: China, CN112698960B[P]. 2022-08-09 (in Chinese)

    [40]

    Tutte W T. Graph Theory[M]. Cambridge, UK: Cambridge University Press, 2001

    [41]

    Levine G N. The classification of deadlock prevention and avoidance is erroneous[J]. ACM SIGOPS Operating Systems Review, 2005, 39(2): 47−50 doi: 10.1145/1055218.1055221

    [42]

    Binkert N, Beckmann B, Black G, et al. The GEM5 simulator[J]. ACM SIGARCH Computer Architecture News, 2011, 39(2): 1−7 doi: 10.1145/2024716.2024718

    [43]

    Bharadwaj S, Yin J, Beckmann B, et al. Kite: A family of heterogeneous interposer topologies enabled via accurate interconnect modeling[C/OL]//Proc of the 57th ACM/IEEE Design Automation Conf (DAC). Piscataway, NJ: IEEE, 2020[2024-05-22]. https://ieeexplore.ieee.org/abstract/document/9218539

    [44]

    Sun Cheng, Chen C H O, Kurian G, et al. DSENT―A tool connecting emerging photonics with electronics for opto-electronic networks-on-chip modeling[C]//Proc of the 6th IEEE/ACM Int Symp on Networks-on-Chip. Piscataway, NJ: IEEE, 2012: 201−210

    [45]

    Zhan Xusheng, Bao Yungang, Bienia C, et al. PARSEC3.0: A multicore benchmark suite with network stacks and SPLASH-2X[J]. ACM SIGARCH Computer Architecture News, 2017, 44(5): 1−16

    [46]

    Parasar M, Jerger N E, Gratz P V, et al. SWAP: Synchronized weaving of adjacent packets for network deadlock resolution[C]//Proc of the 52nd Annual IEEE/ACM Int Symp on Microarchitecture. New York: ACM, 2019: 873−885

    [47]

    Joshi B, Thakur M K. Genetic algorithm-and cuckoo search algorithm-based routing optimizations in network-on-chip[J]. Arabian Journal for Science and Engineering, 2023, 48(8): 9635−9644 doi: 10.1007/s13369-022-07272-9

    [48]

    Luo Yaoying, Meyer M C, Jiang Xin, et al. A hotspot-pattern-aware routing algorithm for networks-on-chip[C]//Proc of the 13th IEEE Int Symp on Embedded Multicore/Many-core Systems-on-Chip (MCSoC). Piscataway, NJ: IEEE, 2019: 229−235

图(17)  /  表(3)
计量
  • 文章访问数:  121
  • HTML全文浏览量:  27
  • PDF下载量:  25
  • 被引次数: 0
出版历程
  • 收稿日期:  2023-12-24
  • 修回日期:  2024-08-11
  • 录用日期:  2024-09-02
  • 网络出版日期:  2024-09-08
  • 刊出日期:  2025-03-31

目录

/

返回文章
返回