-
摘要:
目前数据中心规模迅速扩大和网络带宽大幅度提升,传统软件网络协议栈的处理器开销较大,并且难以满足众多数据中心应用程序在吞吐、延迟等方面的需求. 远程直接内存访问(remote direct memory access,RDMA)技术采用零拷贝、内核旁路和处理器功能卸载等思想,能够高带宽、低延迟地读写远端主机内存数据. 兼容以太网的RDMA技术正在数据中心领域展开应用,以太网RDMA网卡作为主要功能承载设备,对其部署发挥重要作用. 综述从架构、优化和实现评估3个方面进行分析:1)对以太网RDMA网卡的通用架构进行了总结,并对其关键功能部件进行了介绍;2)重点阐述了存储资源、可靠传输和应用相关3方面的优化技术,包括面向网卡缓存资源的连接可扩展性和面向主机内存资源的注册访问优化,面向有损以太网实现可靠传输的拥塞控制、流量控制和重传机制优化,面向分布式存储中不同存储类型、数据库系统、云存储系统以及面向数据中心应用的多租户性能隔离、安全性、可编程性等方面的优化工作;3)调研了不同实现方式、评估方式. 最后,给出总结和展望.
Abstract:With the rapid expansion of data center and the significant increase in network bandwidth, traditional software network protocol stack has high processor overhead and is difficult to meet the needs of many data center applications in terms of throughput, latency and other aspects. Remote direct memory access(RDMA)technology uses the ideas of zero copy, kernel bypass and processor function offloading to read and write remote host memory data with high bandwidth and low latency. Ethernet-compatible RDMA technology is being applied in data centers, and Ethernet RDMA NIC plays a crucial role in its deployment as the main functional bearer device. This overview analyzes from three aspects: architecture, optimization, and implementation evaluation. 1) We summarize the general architecture of Ethernet RDMA NIC and introduce the key functional components; 2) We focus on the optimization techniques in storage resources, reliable transmission and application-related aspects, including optimization of both connection scalability for NIC cache resources and registration access for host memory resources, optimization of congestion control, flow control and retransmission mechanism for lossy Ethernet to achieve reliable transmission, and optimization of different storage types in distributed storage, database system, cloud storage system, and multi-tenant performance isolation, security and programmability for data center applications; 3) Then we investigate different implementation and evaluation methods. Finally, the summary and outlook are given.
-
云存储和计算以较大的存储容量、灵活的可访问性、和高效的数据管理等优势被引入来解决庞大数据的存储与计算需求. 通过将敏感数据外包给云服务器,个人和企业减轻了本地数据管理和维护的负担. 为了保证存储数据的隐私性和安全性,数据所有者在将共享数据外包给云服务器之前会进行加密处理. 然而,在此情境下,用户面临着在海量数据中难以执行关键字搜索的挑战,这在一定程度上阻碍了云环境下文件共享的灵活性. 因此,如何安全、高效地检索云数据变得尤为重要. 可搜索加密[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]).
在快速发展的云计算时代,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} . 记满秩格
\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的② 删除操作. 请注意,通过模加法可以对位图索引进行添加和删除操作.
定义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 的离散高斯分布 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给出了方案的流程图.
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 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} 时的陷门匹配.
本研究通过基于格的委托机制来定期更新密钥. 每个私钥都连接到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} .
为了实现后向安全,本研究结合位图索引和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方案的安全特性比较.
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|发送方根据密钥为每个加密文件附加的关键字生成可搜索密文的过程为:根据接收方的公钥种子,计算实际的公钥参量;计算每个加密文件附加的关键字的哈希值;均匀随机选取多项式,再结合公钥参量,生成可搜索密文. 因此,加密算法需要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%的陷门存储开销.
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次时的平均运行时间.
用户每查询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%.
用户每提取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%.
对于每个搜索查询,服务器执行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%.
7. 结 论
针对抗量子公钥可搜索加密方案的高计算效率、低存储开销、以及前向和后向安全等问题,首先设计了一种基于RLWE的公钥可搜索加密方案. 通过使用一种新的近似陷门采样算法,并结合非球面高斯采样技术和理想可扩展输出函数,所提方案具有更低的密钥、陷门存储开销以及更高的计算效率. 其次,通过引入密钥更新、位图索引和格同态加密技术,提出了一种具有前向安全和后向安全的扩展方案来进一步提高实用性. 最后,理论分析和实验结果表明,所提方案不仅降低了密钥和陷门的存储开销,而且具有更高的搜索效率. 轻量级的可搜索加密方案以及具有丰富的搜索功能的可搜索加密方案仍值得进一步深入研究.
作者贡献声明:戚丽君负责方法调研,完成实验和数据分析,并撰写论文初稿;庄金成参与方案的实验设计,提出指导意见并参与论文修改.
-
表 1 RDMA常用传输方式对比
Table 1 Comparison of RDMA Common Transmission Modes
传输方式 通信原语 可靠性 可扩展性 消息大小/KB ① ② ③ ④ RC √ √ √ √* √ 一般 \le 221 UC √ × √ × × 一般 \le 221 UD √ × × × × 好 \le 4 注:①SEND (SEND with imm)/RECV;②READ;③WRITE (WRITE with imm);④ATOMIC. “*”表示对ATOMIC操作,消息大小仅支持8 B. 表 2 代表性RoCEv2网卡架构对比
Table 2 Comparison of Typical RoCEv2 NIC Architectures
发表或公布年份 会议/期刊/厂商 网卡 功能部件 通信原语 QP
数量报文处理逻辑 PCIe、DMA、
虚实地址转换可选部件 ① ② ③ ④ 拥塞控制 流量控制 2018 Xilinx ETRNIC*[79] 发送/
接收× √ × √ √ √ × 127 2019 SIGCOMM HPCC[39] √ √ √ × √ √ × 300 2020 EuroSys StRoM[36] √ — √ √ √ √ √ 16 000 2021 ICNP StaR[59] √ — — √ √ √ × 120 2021 Xilinx ERNIC[80] × √ √ √ √ √ √ 2 047 2022 TRETS Efficient[81] × — — √ √ √ × 1 2022 ICCD csRNA[58] 请求/
响应√ — — × √ √ × 15 000 2023 ISCAS ScalaRNIC**[57] √ — — — — √ — 320 2023 NSDI SRNIC[14] 发送/
接收√ √ √ √ √ √ × 10 000 2023 GLSVLSI Optimize TX[55] √ — — √ √ √ × 16 注:以上网卡均支持MAC、PHY、可靠传输基础功能. ①SEND/RECV;②READ;③WRITE;④SEND with imm|SEND with invalidate|WRITE with imm. “—”表示原文献未说明. “*”表示ETRNIC只支持发送READ和WRITE请求(不支持接收). “**”表示ScalaRNIC高优先级QP数量支持320个,一般优先级可支持大于25 600个. 表 3 网卡缓存资源优化方案总结
Table 3 Summary of NIC Cache Resource Optimization Schemes
表 4 主机内存资源优化方案总结
Table 4 Summary of Host Memory Resource Optimization Schemes
表 5 拥塞控制优化方案总结
Table 5 Summary of Congestion Control Optimization Schemes
表 6 流量控制优化方案总结
Table 6 Summary of Flow Control Optimization Schemes
表 7 重传机制优化方案总结
Table 7 Summary of Retransmission Mechanism Optimization Schemes
表 8 分布式存储优化方案总结
Table 8 Summary of Distributed Storage Optimization Schemes
表 9 性能隔离优化方案总结
Table 9 Summary of Performance Isolation Optimization Schemes
表 10 商用以太网RDMA网卡实现
Table 10 Implementation of Commercial Ethernet RDMA NIC
发布年份 实现方式 厂商 代表产品 支持协议 应用场景 2020 ASIC Intel 100GbE E810[15] RoCEv2,
iWARPHPC-AI、NFV、存储和混合云等高性能服务器
工作负载、
带宽密集型工作负载2021 ASIC NVIDIA Mellanox 400GbE ConnectX-7[16] InfiniBand,
RoCEv2超大规模数据中心、HPC、人工智能、科学计算 2021 ASIC MARVELL FastLinQ 100GbE
QL45000系列[17]RoCEv1,
RoCEv2,
iWARP企业级数据中心、共有和私有云、
托管服务提供商、电信2021 FPGA Xilinx 100GbE ERNIC[80] RoCEv2 传感器数据采集、视频和图像捕获和传输、
运行 RoCEv2的远程存储节点2022 ASIC Chelsio 400GbE Terminator7[19] RoCEv2,
iWARP数据中心网络、HPC、云计算、网络存储、
流媒体应用、边缘产品2022 NP-SoC Huawei,
Hisilicon基于Hi1822的
200GbE SP670[18]RoCEv2 OVS加速、DPI加速、虚拟化加速 2023 ASIC Broadcom 200GbE BCM957508-P1200G[20] RoCEv2 云和Web2. 0数据中心服务器、企业级数据中心、
HPC集群、机器学习集群、私有云、多节点容器平台、
NVMe存储分解(NVMe oF)数据库服务器2023 SoC AMD 200GbE Pensando
DSC2-200[130]RoCEv2 为大型云服务提供商和超大规模服务系统
(如Microsoft Azure,NetApp)提供计算、
网络、存储和安全服务2023 SoC NVIDIA Mellanox 400GbE BlueField-3DPU[131] RoCEv2 云网络、存储、安全、HPC/AI、电信与边缘计算 -
[1] Hoefler T, Roweth D, Underwood K, et al. Datacenter Ethernet and RDMA: Issues at hyperscale [J]. arXiv preprint, arXiv: 2302.03337, 2023
[2] 马潇潇,杨帆,王展,等. 智能网卡综述[J]. 计算机研究与发展,2022,59(1):1−21 doi: 10.7544/issn1000-1239.20200629 Ma Xiaoxiao, Yang Fan, Wang Zhan, et al. Survey on smart network interface card[J]. Journal of Computer Research and Development, 2022, 59(1): 1−21(in Chinese) doi: 10.7544/issn1000-1239.20200629
[3] Li Qiang, Xiang Qiao, Liu Derui, et al. From RDMA to RDCA: Toward high-speed last mile of data center networks using remote direct cache access [J]. arXiv preprint, arXiv: 2211.05975v2, 2023
[4] He Zhiqiang, Wang Dongyang, Fu Binzhang, et al. MasQ: RDMA for virtual private cloud [C/OL]//Proc of the 2020 ACM SIGCOMM Conf. New York: ACM, 2020 [2024-07-06]. https://dl.acm.org/doi/abs/10.1145/3387514.3405849
[5] Dragojevic A, Narayanan D, Hodson O, et al. FaRM: Fast remote memory [C]//Proc of the 11th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2014: 401−414
[6] Le Yanfang, Stephens B, Singhvi A, et al. RoGUE: RDMA over generic unconverged Ethernet [C]//Proc of the ACM Symp on Cloud Computing. New York: ACM, 2018: 225−236
[7] Mittal R, Shpiner A, Panda A, et al. Revisiting network support for RDMA [C]//Proc of the 2018 ACM SIGCOMM Conf. New York: ACM, 2018: 313−326
[8] Hoefler T, Girolamo S D, Taranov K, et al. sPIN: High-performance streaming processing in the network [C/OL]//Proc of the Int Conf for High Performance Computing, Networking, Storage and Analysis. New York: ACM, 2017 [2024-07-06]. https://ieeexplore.ieee.org/document/9926279
[9] Guo Chuanxiong, Wu Haitao, Deng Zhong, et al. RDMA over commodity Ethernet at scale [C]//Proc of the 2016 ACM SIGCOMM Conf. New York: ACM, 2016: 202−215
[10] IEEE 802.1 Working Group. 802.1Qbb – priority-based flow control [EB/OL]. [2024-07-06]. https://1.ieee802.org/dcb/802-1qbb/
[11] Internet Engineering Task Force. RFC3168: The addition of explicit congestion notification (ECN) to IP [EB/OL]. [2024-07-06]. https://dl.acm.org/doi/book/10.17487/RFC3168
[12] Kong Xinhao, Zhu Yibo, Zhou Huaping, et al. Collie: Finding performance anomalies in RDMA subsystems [C]//Proc of the 19th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2022: 287−305
[13] Tang Jian, Wang Xiaoliang, Dai Huichen. Scalable RDMA transport with efficient connection sharing [C/OL]//Proc of the IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2023 [2024-07-06]. https://ieeexplore.ieee.org/document/10228968
[14] Wang Zilong, Luo Layong, Ning Qingsong, et al. SRNIC: A scalable architecture for RDMA NICs [C/OL]//Proc of the 20th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2023 [2024-07-06]. https://www.usenix.org/ conference/nsdi 23/presentation/wang-zilong
[15] Intel. Intel E810 Ethernet network adapter [EB/OL]. [2024-07-06]. https://www.intel.cn/content/www/cn/zh/products/details/ethernet/800-network-adapters/e810-network-adapters/products.html
[16] NVIDIA. NVIDIA ConnectX−7 network adapter datasheet [EB/OL]. [2024-07-06]. https://nvdam.widen.net/s/csf8rmnqwl/infiniband-ethernet-datasheet-connectx-7-ds-nv-us-2544471
[17] MARVELL. MARVELL converged Ethernet network adapter[EB/OL]. [2024-07-06]. https://cn.marvell.com/products/ethernet-adapters-and-controllers/fastlinq-cna-adapters/documents.html
[18] Huawei Hisilicon. Huawei SP600 NIC [EB/OL]. [2024-07-06]. https://support.huawei.com/enterprise/zh/doc/EDOC1100309168?idPath=23710424%7C251364409%7C21782478%7C15791
[19] Chelsio. Chelsio T7 DPU products [EB/OL]. [2024-07-06]. https://www.chelsio.com/wp-content/uploads/resources/t7-dpu-asic.pdf
[20] Broadcom. Broadcom BCM957508-P1200G NIC datasheet [EB/OL]. [2024-07-06]. https://docs.broadcom.com/doc/957508-P1200G-DS1XX
[21] Singhvi A, Akella A, Gibson D, et al. 1RMA: Re-envisioning remote memory access for multi-tenant datacenters [C]//Proc of the 2020 ACM SIGCOMM Conf. New York: ACM, 2020: 708−721
[22] Vamanan B, Hasan J, Vijaykumar T N. Deadline-aware datacenter tcp (D2TCP)[J]. ACM SIGCOMM Computer Communication Review, 2012, 42(4): 115−126 doi: 10.1145/2377677.2377709
[23] Marty M, Kruijf M D, Adriaens J, et al. Snap: A microkernel approach to host networking [C]//Proc of the 27th ACM Symp on Operating Systems Principles. New York: ACM, 2019: 399−413
[24] Kumar G, Dukkipati N, Jang K, et al. Swift: Delay is simple and effective for congestion control in the datacenter [C]//Proc of the 2020 ACM SIGCOMM Conf. New York: ACM, 2020: 514−528
[25] Mittal R, Lam V T, Dukkipati N, et al. TIMELY: RTT-based congestion control for the datacenter [C]//Proc of the 2015 ACM SIGCOMM Conf. New York: ACM, 2015: 537−550
[26] Zhang Qizhen, Bernstein P A, Berger D S, et al. Redy: Remote dynamic memory cache [J]. Very Large Data Base Endowment, 2021, 15(4): 766−779
[27] Firestone D, Putnam A, Mundkur S, et al. Azure accelerated networking: SmartNICs in the public cloud [C]//Proc of the 15th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2018: 51−66
[28] Kandula S, Sengupta S, Greenberg A, et al. The nature of data center traffic: Measurements & analysis [C]//Proc of the 9th ACM SIGCOMM Conf on Internet Measurement. New York: ACM, 2009: 202−208
[29] Zhu Yibo, Ghobadi M, Misra V, et al. ECN or delay: Lessons learnt from analysis of DCQCN and TIMELY [C]//Proc of the 12th Int Conf on Emerging Networking Experiments and Technologies. New York: ACM, 2016: 313−327
[30] Lu Yuanwei, Chen Guo, Ruan Zhenyuan, et al. Memory efficient loss recovery for hardware-based transport in datacenter [C]//Proc of the 1st Asia-Pacific Workshop on Networking. New York: ACM, 2017: 22−28
[31] Dragojevic A, Narayanan D, Castro M. RDMA reads: To use or not to use[J]. IEEE Data Engineering Bulletin, 2017, 40(1): 3−14
[32] Bai Wei, Abdeen S S, Agrawal, et al. Empowering Azure storage with RDMA [C]//Proc of the 20th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2023: 49−67
[33] Li Bojie, Ruan Zhenyuan, Xiao Wencong, et al. KV-Direct: High-performance in-memory key-value store with programmable NIC [C]//Proc of the 26th Symp on Operating Systems Principles. New York: ACM, 2017: 137−152
[34] Lu Yuanwei, Chen Guo, Li Bojie, et al. Multi-path transport for RDMA in Datacenters [C]//Proc of the 15th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2018: 357−371
[35] Li Bojie, Cui Tianyi, Wang Zibo, et al. Socksdirect: Datacenter sockets can be fast and compatible [C]//Proc of the 2019 ACM SIGCOMM Conf. New York: ACM, 2019: 90−103
[36] Sidler D, Wang Z, Chiosa M, et al. StRoM: Smart remote memory[C/OL]//Proc of the 15th European Conf on Computer Systems. New York: ACM, 2020 [2024-07-06]. https://dl.acm.org/doi/abs/10.1145/3342195.3387519
[37] Li Qiang, Gao Yixiao, Wang Xiaoliang, et al. Flor: An open high performance RDMA framework over heterogeneous RNICs [C]//Proc of the 17th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2023: 931−948
[38] Gao Yixiao, Li Qiang, Tang Lingbo, et al. When cloud storage meets RDMA [C]//Proc of the 18th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2021: 519−533
[39] Li Yuliang, Miao Rui, Liu H H, et al. HPCC: High precision congestion control [C]//Proc of the 2019 ACM SIGCOMM Conf. New York: ACM, 2019: 44−58
[40] Liu Kefei, Jiang Zhuo, Zhang Jiao, et al. Hostping: Diagnosing intra-host network bottlenecks in RDMA servers [C]//Proc of the 20th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2023: 15−29
[41] Chen Youmin, Lu Youyou, Shu Jiwu. Scalable RDMA RPC on reliable connection with efficient resource sharing [C/OL]//Proc of the 14th EuroSys Conf. New York: ACM, 2019 [2024-07-06]. https://dl.acm.org/do i/10.1145/3302424.3303968
[42] Miao Mao, Ren Fengyuan, Luo Xiaohui, et al. SoftRDMA: Rekindling high performance software RDMA over commodity ethernet [C]//Proc of the 1st Asia-Pacific Workshop on Networking. New York: ACM, 2017: 43−49
[43] Ma Teng, Chen Kang, Ma Shaonan, et al. Thinking more about RDMA memory semantics [C]//Proc of the IEEE Int Conf on Cluster Computing. Piscataway, NJ: IEEE, 2021: 456−467
[44] Cheng Wenxue, Qian Kun, Jiang Wanchun, et al. Re-architecting congestion management in lossless Ethernet [C]//Proc of the 17th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2020: 19−36
[45] Ma Shaonan, Ma Teng, Chen Kang, et al. A survey of storage systems in the RDMA era[J]. IEEE Transactions on Parallel Distributed Systems, 2022, 33(12): 4395−4409 doi: 10.1109/TPDS.2022.3188656
[46] Lu Youyou, Shu Jiwu, Chen Youmin, et al. Octopus+: An RDMA-enabled distributed persistent memory file system[J]. ACM Transactions Storage, 2017, 17(3): 1−25
[47] Ma Tengyu, Ma Tao, Song Zhuo, et al. X-RDMA: Effective RDMA middleware in large-scale production environments [C/OL]//Proc of the IEEE Int Conf on Cluster Computing. Piscataway, NJ: IEEE, 2019 [2024-07-06]. https://ieeexplore.ieee.org/document/8891004
[48] Shen Dian, Luo Junzhou, Dong Fang, et al. Distributed and optimal RDMA resource scheduling in shared data center networks [C]//Proc of the IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2020: 606−615
[49] Wang Xiaoliang, Song Hexiang, Nguyen C, et al. Maximizing the benefit of RDMA at end hosts [C/OL]//Proc of the IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2021 [2024-07-06]. https://ieeexplore.ieee.org/document/9488875
[50] Qiu Haonan, Wang Xiaoliang, Jin Tianchen, et al. Toward effective and fair RDMA resource sharing [C]//Proc of the 2nd Asia-Pacific Workshop on Networking. New York: ACM, 2018: 8−14
[51] Yu Peiwen, Xue Feiyang, Tian Chen, et al. Bifrost: Extending RoCE for long distance inter-DC links[C/OL] //Proc of the 31st IEEE Int Conf on Network Protocols. Piscataway, NJ: IEEE, 2023 [2024-07-06]. https://ieeexplore.ieee.org/document/10355634
[52] He Zhiqiang, Chen Yuxin, Hua Bei. RoUD: Scalable RDMA over UD in lossy data center networks [C]//Proc of the 23rd IEEE/ACM Int Symp on Cluster, Cloud Internet Computing. Piscataway, NJ: IEEE, 2023: 36−46
[53] Wang Dongyang, Fu Binzhang, Lu Gang, et al. vSocket: Virtual socket interface for RDMA in public clouds [C]//Proc of the 15th ACM SIGPLAN/SIGOPS Int Conf on Virtual Execution Environments. New York: ACM, 2019: 179−192
[54] Zang Dawei, Cao Zheng, Liu Xiaoli, et al. PROP: Using PCIe-based RDMA to accelerate rack-scale communications in data centers [C]//Proc of the 21st IEEE Int Conf on Parallel Distributed Systems. Piscataway, NJ: IEEE, 2015: 465−472
[55] Liao Yunkun, Wu Jingya, Lu Wenyan, et al. Optimize the TX architecture of RDMA NIC for performance isolation in the cloud environment [C]// Proc of the Great Lakes Symp on VLSI. New York: ACM, 2023: 29−35
[56] Han Shukai, Zhang Mi, Jiang Dejun, et al. HiStore: Rethinking hybrid index in RDMA-based key-value store [J]. arXiv preprint, arXiv: 2208. 12987, 2022
[57] Ma Xiaoxiao, Yang Fan, Wang Zhan, et al. A scalable RDMA network interface card with efficient cache management [C/OL]//Proc of the IEEE Int Symp on Circuits Systems. Piscataway, NJ: IEEE, 2023 [2024-07-06]. https://ieeexplore.ieee.org/abstract/document/10181426
[58] Kang Ning, Wang Zhan, Yang Fan, et al. csRNA: Connection-scalable RDMA NIC architecture in datacenter environment [C]//Proc of the 40th IEEE Int Conf on Computer Design. Piscataway, NJ: IEEE, 2022: 398−406
[59] Wang Xizheng, Chen Guo, Yin Xijin, et al. StaR: Breaking the scalability limit for RDMA [C/OL]//Proc of the 29th IEEE Int Conf on Network Protocols. Piscataway, NJ: IEEE, 2021 [2024-07-06]. https://ieeexplore.ieee.org/document/9651935
[60] Wang Zilong, Wan Xinchen, Zeng Chaoliang, et al. Accurate and scalable rate limiter for RDMA NICs [C]//Proc of the 7th Asia-Pacific Workshop on Networking. New York: ACM, 2023: 15−20
[61] Rothenberger B, Taranov K, Perrig A, et al. ReDMArk: Bypassing RDMA security mechanisms [C]//Proc of the 30th USENIX Security Symp. Berkeley, CA: USENIX Association, 2021: 4277−4292
[62] Taranov K, Rothenberger B, Perrig A, et al. sRDMA-Efficient NIC-based authentication and encryption for remote direct memory access [C]//Proc of the USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2020: 691−704
[63] Barthels C, Alonso G, Hoefler T. Designing databases for future high-performance networks[J]. IEEE Data Engineering Bulletin, 2017, 40(1): 15−26
[64] Taranov K, Girolamo S D, Hoefler T. CoRM: Compactable remote memory over RDMA [C]//Proc of the Int Conf on Management of Data. New York: ACM, 2021: 1811−1824
[65] Xue Jiachen, Chaudhry M U, Vamanan B, et al. Dart: Divide and specialize for fast response to congestion in RDMA-based datacenter networks[J]. IEEE/ACM Transactions on Networking, 2018, 28(1): 322−335
[66] Tsai S Y, Zhang Yiying. LITE kernel RDMA support for datacenter applications [C]//Proc of the 26th Symp on Operating Systems Principles. New York: ACM, 2017: 306−324
[67] Xue Jiachen, Vijaykumar T N, Thottethodi M. Network interface architecture for remote indirect memory access (RIMA) in datacenters[J]. ACM Transactions on Architecture Code Optimization, 2020, 17(2): 1−22
[68] Taheri P, Menikkumbura D, Vanini E, et al. RoCC: Robust congestion control for RDMA [C]//Proc of the 16th Int Conf on Emerging Networking EXperiments Technologies. New York: ACM, 2020: 17−30
[69] Le Yanfang, Malekpourshahraki M, Stephens B, et al. On the impact of cluster configuration on RoCE application design [C]//Proc of the 3rd Asia-Pacific Workshop on Networking. New York: ACM, 2019: 64−70
[70] Kalia A, Kaminsky M, Andersen D G. FaSST: Fast, scalable and simple distributed transactions with two-sided (RDMA) datagram RPCs [C]//Proc of the 12th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2016: 185−201
[71] Kalia A, Kaminsky M, Andersen D G. Using RDMA efficiently for key-value services [C]//Proc of the 2014 ACM SIGCOMM Conf. New York: ACM, 2014: 295−306
[72] Kim D, Memaripour A, Badam A, et al. HyperLoop: Group-based NIC-offloading to accelerate replicated transactions in multi-tenant storage systems [C]//Proc of the 2018 ACM SIGCOMM Conf. New York: ACM, 2018: 297−312
[73] Kim D, Yu Tianlong, Liu H H, et al. FreeFlow: Software-based virtual RDMA networking for containerized clouds [C]//Proc of the 16th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2019: 113−126
[74] Kalia A, Kaminsky M, Andersen D G. Design guidelines for high performance RDMA systems [C]//Proc of the USENIX Conf on Usenix Annual Technical Conf. Berkeley, CA: USENIX Association, 2016: 437−450
[75] Openfabrics. Libibverbs release [EB/OL]. [2024-07-06]. https://www.openfabrics.org/downloads/libibverbs/
[76] Wei Xingda, Dong Zhiyuan, Chen Rong, et al. Deconstructing RDMA-enabled distributed transactions: Hybrid is better [C]//Proc of the 13th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2018: 233−251
[77] Zhang Yiwen, Gu Juncheng, Lee Youngmoon, et al. Performance isolation anomalies in RDMA [C]//Proc of the Workshop on Kernel-Bypass Networks. New York: ACM, 2017: 43−48
[78] Intel. Intel I350 Ethernet server adapter [EB/OL]. [2024-07-06]. https://www.intel.cn/content/www/cn/zh/products/details/ethernet/gigabit-network-adapters/i350-server-adapters.html
[79] Xilinx. Xilinx embedded target RDMA enabled v1.1 product guide [EB/OL]. [2024-07-06]. https://docs.xilinx.com/v/u/en-US/pg294-etrnic
[80] Xilinx. Xilinx embedded RDMA enabled NIC LogiCORE IP product guide [EB/OL]. [2024-07-06]. https://docs.xilinx.com/r/en-US/pg332-ernic
[81] Schelten N, Steinert F, Knapheide J, et al. A high-throughput, resource-efficient implementation of the RoCEv2 remote DMA protocol and its application[J]. ACM Transactions on Reconfigurable Technology, 2022, 16(1): 1−23
[82] Kong Xinhao, Chen Jingrong, Bai Wei, et al. Understanding RDMA microarchitecture resources for performance isolation [C]//Proc of the 20th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2023: 31−48
[83] IBTA. InfiniBand architecture specification [EB/OL]. [2024-07-06]. https://www.infinibandta.org/ibta-specification/
[84] Guo Zehua, Liu Sen, Zhang Zhili. Traffic control for RDMA-enabled data center networks: A survey[J]. IEEE Systems Journal, 2020, 14(1): 677−688 doi: 10.1109/JSYST.2019.2936519
[85] Ryser A, Lerner A, Forencich A, et al. D-RDMA: Bringing zero-copy RDMA to database systems [C/OL]//Proc of the 12th Annual Conf on Innovative Data Systems Research. Chaminade, CA: CIDR, 2022 [2024-07-06]. https://www.cidrdb.org/cidr2022/papers/p77-ryser.pdf
[86] Zhu Yibo, Eran H, Firestone D, et al. Congestion control for large-scale RDMA deployments [C]//Proc of the 2015 ACM SIGCOMM Conf. New York: ACM, 2015: 523−536
[87] Tang Jian, Xu Tingting, Nguyen C, et al. Tuning target delay for RTT-based congestion control [C/OL]//Proc of the 30th IEEE Int Conf on Network Protocols. Piscataway, NJ: IEEE, 2022 [2024-07-06]. https://ieeexplore.ieee.org/document/9940420
[88] Fuhrer B, Shpigelman Y, Tessler C, et al. Implementing reinforcement learning datacenter congestion control in NVIDIA NICs [C]//Proc of the 23rd IEEE/ACM Int Symp on Cluster, Cloud and Internet Computing. Piscataway, NJ: IEEE, 2023: 331−343
[89] Perry J, Ousterhout A, Balakrishnan H, et al. Fastpass: A centralized "zero-queue" datacenter network[J]. ACM SIGCOMM Computer Communication Review, 2014, 44(4): 307−318
[90] Cho I, Jang K, Han Dongsu. Credit-scheduled delay-bounded congestion control for datacenters [C]//Proc of the 2017 ACM SIGCOMM Conf. New York: ACM, 2017: 239−252
[91] NVIDIA. Introduction to resilient RoCE [EB/OL]. [2024-07-06]. https://enterprise-support.nvidia.com/s/article/introduction-to-resilient-roce---faq#jive_content_id_What_is_Resilient_RoCE
[92] Mitchell C, Geng Yifeng, Jinyang Li. Using one-sided RDMA reads to build a fast, CPU-efficient key-value store [C]//Proc of the USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2013: 103−114
[93] Yang Jian, Izraelevitz J, Swanson S. Orion: A distributed file system for non-volatile main memory and RDMA-capable networks [C]//Proc of the 17th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2019: 221−234
[94] Yang Jian, Izraelevitz J, Swanson S. FileMR: Rethinking RDMA networking for scalable persistent memory [C]//Proc of the 17th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2020: 111−125
[95] Zamanian E, Yu Xiangyao, Stonebraker M, et al. Rethinking database high availability with RDMA networks[J]. Very Large Data Base Endowment, 2019, 12(11): 1637−1650
[96] Miao Rui, Zhu Lingjun, Ma Shu, et al. From Luna to Solar: The evolutions of the compute-to-storage networks in Alibaba cloud [C]//Proc of the 2022 ACM SIGCOMM Conf. New York: ACM, 2022: 753−766
[97] Zhu Lingjun, Shen Yifan, Xu Erci, et al. Deploying user-space TCP at cloud scale with LUNA [C]//Proc of the USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2023: 673−687
[98] Broadcom VMware. VMware technical journal: Toward a paravirtual vRDMA device for VMware ESXi guests [R]. Palo Alto, CA: VMware, 2012: 22−27
[99] Pfefferle J, Stuedi P, Trivedi A K, et al. A hybrid I/O virtualization framework for RDMA-capable network interfaces [C]//Proc of the 11th ACM SIGPLAN/SIGOPS Int Conf on Virtual Execution Environments. New York: ACM, 2015: 17−30
[100] Zhang Yiwen, Tan Yue, Stephens B E, et al. Justitia: Software multi-tenancy in hardware kernel-bypass networks [C]//Proc of the 19th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2022: 1307−1326
[101] Amaro E, Luo Zhihong, Ousterhout A, et al. Remote memory calls [C]//Proc of the 19th ACM Workshop on Hot Topics in Networks. New York: ACM, 2020: 38−44
[102] Shalev L, Ayoub H, Bshara N, et al. A cloud-optimized transport protocol for elastic and scalable HPC[J]. IEEE Micro, 2020, 40(6): 67−73 doi: 10.1109/MM.2020.3016891
[103] Aliyun. eRDMA [EB/OL]. [2024-07-06]. https://github.com/alibaba/elastic-rdma-drivers
[104] Xing Jiarong, Hsu K, Qiu Yiming, et al. Bedrock: Programmable network support for secure RDMA systems [C]//Proc of the 31st USENIX Security Symp. Berkeley, CA: USENIX Association, 2022: 2585−2600
[105] Google. Falcon [EB/OL]. [2024-07-06]. https://cloud.google.com/blog/topics/systems/introducing-falcon-a-reliable-low-latency-hardware-transport
[106] Ultra Ethernet. UET [EB/OL]. [2024-07-06]. https://ultraethernet.org/wp-content/uploads/sites/20/2023/10/23.07.12-UEC-1.0-Overview-FINAL-WITH-LOGO.pdf
[107] 陈游旻,陆游游,罗圣美,等. 基于RDMA的分布式存储系统研究综述[J]. 计算机研究与发展,2019,56(2):227−239 Chen Youmin, Lu Youyou, Luo Shengmei, et al. Survey on RDMA-based distributed storage systems[J]. Journal of Computer Research and Development, 2019, 56(2): 227−239 (in Chinese)
[108] Openfabrics. Dynamically-connected transport service [EB/OL]. [2024-07-06]. https://www.openfabrics.org/images/eventpresos/workshops2014/DevWorkshop/presos/Monday/pdf/05_DC_Verbs.pdf
[109] Matthew J K, Jaidev K S, Dhabaleswar K P. Scalable MPI design over InfiniBand using extended reliable connection [C]//Proc of the IEEE Int Conf on Cluster Computing. Piscataway, NJ: IEEE, 2008: 203−212
[110] 杜鑫乐,徐恪,李彤,等. 数据中心网络的流量控制:研究现状与趋势[J]. 计算机学报,2021,44(7):1287−1309 Du Xinle, Xu Ke, Li Tong, et al. Traffic control for data center network: State of the art and future research[J]. Chinese Journal of Computers, 2021, 44(7): 1287−1309 (in Chinese)
[111] 刘敬玲,黄家玮,蒋万春,等. 数据中心负载均衡方法研究综述[J]. 软件学报,2021,32(2):300−326 Liu Jingling, Huang Jiawei, Jiang Wanchun, et al. Survey on load balancing mechanism in data center[J]. Journal of Software, 2021, 32(2): 300−326 (in Chinese)
[112] Xu Lisong, Harfoush K, Rhee Injong. Binary increase congestion control (BIC) for fast long-distance networks [C]//Proc of the IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2004: 2514−2524
[113] Ha Sangtae, Rhee Injong, Xu Lisong. CUBIC: A new TCP-friendly high-speed TCP variant[J]. ACM Special Interest Group on Operating Systems, 2008, 42(5): 64−74 doi: 10.1145/1400097.1400105
[114] Alizadeh M, Greenberg A G, Maltz D A, et al. Data center TCP (DCTCP)[J]. ACM SIGCOMM Computer Communication Review, 2010, 40(4): 63−74 doi: 10.1145/1851275.1851192
[115] IEEE 802.1 Working Group. 802.1Qau-congestion notification [EB/OL]. [2024-07-06]. https://1.ieee802.org/dcb/802-1qau/
[116] Tessler C, Shpigelman Y, Dalal G, et al. Reinforcement learning for datacenter congestion control[J]. ACM SIGMETRICS Performance Evaluation Review, 2021, 49(2): 43−46
[117] 章淼,吴建平,林闯. 互联网端到端拥塞控制综述[J]. 软件学报,2002,13(3):354−363 Zhang Miao, Wu Jianping, Lin Chuang. A review of research on end-to-end congestion control for the Internet[J]. Journal of Software, 2002, 13(3): 354−363 (in Chinese)
[118] Dally W J, Seitz C L. Deadlock-free message routing in multiprocessor interconnection networks[J]. IEEE Transactions on Computers, 1987, 36(5): 547−553
[119] Yu Zhuolong, Su BoWei, Bai Wei, et al. Understanding the micro-behaviors of hardware offloaded network stacks with Lumina [C]//Proc of the 2023 ACM SIGCOMM Conf. New York: ACM, 2023: 1074−1087
[120] RedHat. What is cloud storage? [EB/OL]. [2024-07-06]. https://www.redhat.com/zh/topics/data-storage/what-is-cloud-storage
[121] 陈思新. 分布式块存储系统中RDMA通信优化研究 [D]. 武汉:华中科技大学,2022 Chen Sixin. Optimization study of RDMA communication in distributed block storage systems [D]. Wuhan: Huazhong University of Science and Technology, 2022 (in Chinese)
[122] IBM. What is file storage? [EB/OL]. [2024-07-06]. https://www.ibm.com/cn-zh/topics/file-storage
[123] Azure. Azure blockchain service [EB/OL]. [2024-07-06]. https://azure.microsoft.com/en-us/services/blockchain-service/
[124] The Ohio State University. High-performance big data project [EB/OL]. [2024-07-06]. http://hibd:cse:ohio-state:edu/
[125] Carbone P, Katsifodimos A, Ewen S, et al. Apache Flink™: Stream and batch processing in a single engine[J]. IEEE Computer Society, 2015, 36(4): 28−33
[126] Li Hao, Kadav A, Kruus E, et al. Malt: Distributed data-parallelism for existing ml applications [C/OL]//Proc of the 10th European Conf on Computer Systems. New York: ACM, 2015 [2024-07-06]. https://dl.acm.org/doi/10.1145/2741948.2741965
[127] Abadi M, Barham P, Chen Jianmin, et al. Tensorflow: A system for large-scale machine learning [C]//Proc of the 12th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2016: 265−283
[128] Peripheral Component Interconnect Special Interest Group. SR-IOV [EB/OL]. [2024-07-06]. https://pcisig.com/specifications/iov/single_root/
[129] Ultra Ethernet. UEC [EB/OL]. [2024-07-06]. https://ultraethernet.org/
[130] AMD Pensando. DSC2−200 distributed services card [EB/OL]. [2024-07-06]. https://www.amd.com/system/files/documents/pensando-dsc-200-product-brief.pdf
[131] NVIDIA. BlueField−2DPU [EB/OL]. [2024-07-06]. https://www.nvidia.com/content/dam/en-zz/Solutions/Data-Center/documents/datasheet-nvidia-bluefield-3-dpu.pdf
[132] Aliyun. eRDMA [EB/OL]. [2024-07-06]. https://help.aliyun.com/zh/ecs/user-guide/erdma/?spm=a2c4g.11186623.0.0.52db44bbxNFCyy
[133] Amazon . ENA express: Improved network latency and per-flow performance on EC2 [EB/OL]. [2024-07-06]. https://aws.amazon.com/cn/blogs/aws/new-ena-express-improved-network-latency-and-per-flow-performance-on-ec2/
[134] Amazon. AWS Nitro system [EB/OL]. [2024-07-06]. https://aws.amazon.com/cn/ec2/nitro
[135] Pandey S M, Shashidhara R. SRoCE: Software RDMA over commodity Ethernet [EB/OL]. 2020 [2024-07-06]. https://homes.cs.washington.edu/~rajaths/sRoCE.pdf
[136] Liss L. The Linux softROCE driver [EB/OL]. [2024-07-06]. https://www.openfabrics.org/images/eventpresos/2017presentations/205_SoftRoCE_LLiss.pdf
[137] Linux. softiWARP [EB/OL]. [2024-07-06]. https://lxr.linux.no/linux+v5.15.91/drivers/infiniband/sw/siw/
[138] Chelsio. Chelsio T6 [EB/OL]. [2024-07-06]. https://www.chelsio.com/wp-content/uploads/resources/T6-Architecture.pdf
[139] The Transaction Processing Council. TPC-C benchmark v5.11 [EB/OL]. [2024-07-06]. http://www.tpc.org/tpcc/
[140] The H-Store Team. SmallBank benchmark [EB/OL]. [2024-07-06]. http://hstore.cs.brown.edu/documentation/deployment/benchmarks/smallbank/
[141] Huang Haoju, Ghandeharizadeh S. An evaluation of RDMA-based message passing protocols [C]//Proc of the IEEE Int Conf on Big Data. Piscataway, NJ: IEEE, 2019: 3340−3349
[142] Hong Yuju, Thottethodi M. Understanding and mitigating the impact of load imbalance in the memory caching tier [C/OL]//Proc of the 4th Annual Symp on Cloud Computing. New York: ACM, 2013 [2024-07-06]. https://dl.acm.org/doi/10.1145/2523616.2525970
[143] Redis. Redis open source in-memory data store [EB/OL]. [2024-07-06]. https://redis.io/
[144] CloudLab. CloudLab infrastructure for cloud computing [EB/OL]. [2024-07-06]. https://cloudlab.us/
[145] OFED. Linux perftest [EB/OL]. [2024-07-06]. https://github.com/linux-rdma/perftest
[146] NVIDIA Mellanox. NEO-Host [EB/OL]. [2024-07-06]. https://www.nvidia.cn/networking/management-software/
[147] Ohio Supercomputer Center. Linux qperf [EB/OL]. [2024-07-06]. https://github.com/linux-rdma/qperf
[148] Ohio State University. OSU benchmarks [EB/OL]. [2024-07-06]. https://mvapich.cse.ohio-state.edu/benchmarks/
[149] Carnegie Mellon University. rdma_bench [EB/OL]. [2024-07-06]. https://github.com/efficient/rdma_bench
[150] NS−3. The NS−3 discrete-event network simulator [EB/OL]. [2024-07-06]. http://www.nsnam.org
[151] OMNeT++. OMNeT++ discrete event simulator [EB/OL]. [2024-07-06]. https://omnetpp.org/
[152] Huang Bo, Jin Li, Lu Zhihui, et al. BoR: Toward high-performance permissioned blockchain in RDMA-enabled network[J]. IEEE Transactions on Services Computing, 2020, 13(2): 301−313 doi: 10.1109/TSC.2019.2948009
[153] Ren Yufei, Wu Xingbo, Zhang Li, et al. iRDMA: Efficient use of RDMA in distributed deep learning systems [C]//Proc of the 19th IEEE Int Conf on High Performance Computing and Communications. Los Alamitos, CA: IEEE Computer Society, 2017: 231−238
[154] Cossettini A, Taranov K, Vogt C, et al. A RDMA interface for ultra-fast ultrasound data-streaming over an optical link [C]//Proc of the Design, Automation & Test in Europe Conf & Exhibition. Leuven, BEL: European Design and Automation Association, 2022: 80−83
[155] De Laat W. The application of RDMA over converged Ethernet data transport for radio-astronomy systems [D]. Delft, Netherlands: Delft University of Technology, 2022