-
摘要:
随着大模型技术的迅猛发展,大模型在自然语言处理和计算机视觉等领域表现出卓越的性能,成为解决复杂问题的重要工具,并在科研和产业界引发了广泛关注. 然而,当前基于云平台的大模型训练和推理方案面临诸多挑战,包括高昂的成本、有限的可扩展性和信息安全风险等. 随着模型参数规模的不断扩大,对于低成本、高效训练和推理的需求愈发迫切. 在端边侧进行大模型的协同训练和推理,可以显著降低延迟和带宽需求,同时增强数据隐私和操作效率,为大模型在多样化场景中的低成本应用提供关键技术支持,成为当前研究的热点之一. 全面调研了面向边缘智能的大模型相关研究,主要从大模型边缘训练和推理2个角度对当前相关研究进行了深入分析和讨论. 最后,提出了面向边缘智能的大模型技术发展所面临的挑战和未来展望. 希望能促进学术界和产业界对面向边缘智能的大模型技术有更深入了解和关注,并能够启发更多的学者开展深入研究.
Abstract:With the rapid development of large-scale model technology, these models have exhibited remarkable performance in fields such as natural language processing and computer vision, becoming essential tools for addressing complex issues and drawing significant interest from both the scientific community and the industry. Nonetheless, current cloud-platform-based schemes for training and inference of large models face multiple challenges, including high expenses, restricted scalability, and information security risks. As the scale of model parameters expands continually, the need for low-cost, efficient training and inference methods grows ever more pressing. Carrying out collaborative training and inference of large models on edge devices can dramatically decrease latency and bandwidth demands, concurrently reinforcing data privacy and operational efficiency. This strategy furnishes vital technological support for the economical deployment of large models across a variety of contexts, thereby evolving into one of the prominent research hotspots. This article conducts a thorough investigation of research pertinent to large models in the context of edge intelligence, with an in-depth analysis and discourse primarily focused on two aspects: edge-based training and inference of large models. Ultimately, it outlines the challenges confronted in the progression of large model technologies tailored for edge intelligence and delineates future prospects. The ambition is to stimulate a heightened comprehension and intensified attention from both academic and industrial sectors towards technologies involving large models for edge intelligence, thereby encouraging further scholarly exploration in this thriving domain.
-
云存储和计算以较大的存储容量、灵活的可访问性、和高效的数据管理等优势被引入来解决庞大数据的存储与计算需求. 通过将敏感数据外包给云服务器,个人和企业减轻了本地数据管理和维护的负担. 为了保证存储数据的隐私性和安全性,数据所有者在将共享数据外包给云服务器之前会进行加密处理. 然而,在此情境下,用户面临着在海量数据中难以执行关键字搜索的挑战,这在一定程度上阻碍了云环境下文件共享的灵活性. 因此,如何安全、高效地检索云数据变得尤为重要. 可搜索加密[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 不同微调方法的比较
Table 1 Comparison of Different Fine-Tuning Methods
表 2 大模型联邦高效微调框架总结
Table 2 Summary of Federated Efficient Fine-tuning Framework for Large Models
表 3 大模型压缩关键技术相关工作分类
Table 3 Classification of Related Work for Large Model Compression
参数剪枝 结构化剪枝 剪除冗余结构,降低模型大小和计算复杂度 文献[45−48] 非结构
化剪枝实现权重稀疏化,减小模型内存使用量和计算量,依赖特定软硬件加速模型张量运算 文献[49−51] 知识蒸馏 白盒蒸馏 产生特定领域下的小模型,减少模型尺寸和计算量,同时保持模型在特定任务下的性能 文献[52−60] 黑盒蒸馏 在不访问大模型内部结构的情况下,实现蒸馏过程,产生特定领域的小模型 文献[61−70] 模型量化 训练后
量化降低模型存储大小、节省存储、内存、带宽、计算量,同时保持模型精度 文献[71−81] 量化感
知训练降低模型量化误差,在降低模型存储、内存、带宽、计算量的前提下,进一步保持模型精度 文献[82−86] 低秩分解 — 减少模型参数量,实现推理加速 文献[87−91] “—”表示没有更细致的类别划分. 表 4 大模型推理加速技术相关工作分类
Table 4 Classification of Related Work for Large Model Inference Acceleration Technology
表 5 大模型边缘部署框架总结
Table 5 Summary of Edge Deployment Frameworks for Large Models
适用性 框架 特点 量化 多模
型支持跨平台支持 通用 TFLite[146] 在移动设备、嵌入式设备和loT设备上运行模型,支持多种开发语言和硬件加速 √ √ √ TorchExec[147] PyTorch平台下边缘部署工具,兼容多种计算平台并具有轻量级运行时 √ √ √ MNN[148] 轻量级的深度神经网络引擎,对模型格式、算子、设备、操作系统具有广泛的兼容性 √ √ √ NCNN[149] 适用于移动端的神经网络推理框架,无第三方依赖 √ √ √ 专用 MLC-LLM[150] 使用机器学习编译技术加速推理 √ √ √ llama.cpp[151] C/C++中LLM推理 √ √ √ llama2.c[152] 纯C语言环境执行Llama推理 √ Mllm[153] 适用于移动和边缘设备的多模态推理引擎 √ √ √ Intel Extension for Transformers[154] 在英特尔平台上提供LLM高效推理 √ √ InferLLM[155] 轻量级LLM推理框架,可部署至移动设备 √ √ TinyChatEngine[156] 支持多种设备上的多种量化方法 √ √ √ NanoLLM[157] 为NVIDIA Jetson设计的轻量级LLM推理引擎 √ -
[1] OpenAI. ChatGPT: Optimizing language models for dialogue[EB/OL]. (2022-12-30)[2024-02-10]. https://openai.com/blog/chatgpt/#rf2
[2] Achiam J, Adler S, Agarwal S, et al. GPT−4 technical report[J]. arXiv preprint, arXiv: 2303.08774, 2023
[3] Touvron H, Lavril T, Izacard G, et al. LLaMA: Open and efficient foundation language models[J]. arXiv preprint, arXiv: 2302.13971, 2023
[4] Liu Haotian, Li Chunyuan, Wu Qingyang, et al. Visual instruction tuning[J]. arXiv preprint, arXiv: 2304.08485, 2023
[5] Kirillov A, Mintun E, Ravi N, etc. Segment anything[J]. arXiv preprint, arXiv: 2304.02643, 2023
[6] Touvron H, Martin L, Stone K, el al. Llama 2: Open foundation and fine-tuned chat models[J]. arXiv preprint, arXiv: 2307.09288, 2023
[7] 王睿,齐建鹏,陈亮,等. 面向边缘智能的协同推理综述[J]. 计算机研究与发展,2021,60(2):398−414 Wang Rui, Qi Jianpeng, Chen Liang, et al. Survey of collaborative inference for edge intelligence[J]. Journal of Computer Research and Development, 2021, 60(2): 398−414 (in Chinese)
[8] Alizadeh K, Mirzadeh I, Belenko D, et al. LLM in a flash: Efficient large language model inference with limited memory[C]//Proc of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Stroudsburg, PA: ACL, 2024: 12562–12584
[9] Mcmahan H B, Moore E, Ramage D, et al. Communication-efficient learning of deep networks from decentralized data[C]//Proc of the 20th Int Conf on Artificial Intelligence and Statistics PMLR. New York: ACM, 2017: 1273−1282
[10] Custers B, Sears A M, Dechesne F, et al. EU Personal Data Protection in Policy and Practice[M]. The Hague, The Netherlands: TMC Asser Press, 2019
[11] Lambda. OpenAI’s GPT−3 language model: A technical overview[EB/OL]. (2020-06-03)[2024-01-08]. https://lambdalabs.com/blog/demystifying-gpt-3#1
[12] Ananthaswamy A. In AI, is bigger always better?[J]. Nature, 2023, 615(7951): 202−205 doi: 10.1038/d41586-023-00641-w
[13] Brown T, Mann B, Ryder N, et al. Language models are few-shot learners[C]//Proc of the 33rd Int Conf on Neural Information Processing Systems. New York: ACM, 2020: 1877−1901
[14] Lv Kai, Yang Yuqing, Liu Tengxiao, et al. Full parameter fine-tuning for large language models with limited resources[J]. arXiv preprint, arXiv: 2306.09782, 2023
[15] Lv Kai, Yan Hang, Guo Qipeng, et al. AdaLomo: Low-memory optimization with adaptive learning rate[J]. arXiv preprint, arXiv: 2310.10195, 2023
[16] Malladi S, Gao Tianyu, Nichani E, et al. Fine-tuning language models with just forward passes[J]. arXiv preprint, arXiv: 2305.17333, 2023
[17] Ding Ning, Qin Yujia, Yang Guang, et al. Parameter-efficient fine-tuning of large-scale pre-trained language models[J]. Nature Machine Intelligence, 2023, 5(3): 220−235 doi: 10.1038/s42256-023-00626-4
[18] Chen Chaochao, Feng Xiaohua, Zhou Jun, et al. Federated large language model: A position paper[J]. arXiv preprint, arXiv: 2307.08925, 2023
[19] Houlsby N, Giurgiu A, Jastrzebski S, et al. Parameter-efficient transfer learning for NLP[C]//Proc of the 36th Int Conf on Machine Learning PMLR. New York: ACM, 2019: 2790−2799
[20] Hu Zhiqiang, Lan Yihuai, Wang Lei, et al. LLM-adapters: An adapter family for parameter-efficient fine-tuning of large language models[J]. arXiv preprint, arXiv: 2304.01933, 2023
[21] Karimi M, Henderson J, Ruder S. Compacter: Efficient low-rank hypercomplex adapter layers[C]//Proc of the 34th Int Conf on Neural Information Processing Systems. New York: ACM, 2021: 1022−1035
[22] Li X, Liang P. Prefix-tuning: Optimizing continuous prompts for generation[J]. arXiv preprint, arXiv: 2101.00190, 2021
[23] Zhang Renrui, Han Jiaming, Zhou Aojun, et al. Llama-adapter: Efficient fine-tuning of language models with zero-init attention[J]. arXiv preprint, arXiv: 2303.16199, 2023
[24] Lester B, Al-Rfou R, Constant N. The power of scale for parameter-efficient prompt tuning[J]. arXiv preprint, arXiv: 2104.08691, 2021
[25] Sun Tianxiang, He Zhengfu, Zhu Qin, et al. Multitask pre-training of modular prompt for chinese few-shot learning[C]//Proc of the 61st Annual Meeting of the Association for Computational Linguistics. Stroudsburg, PA: ACL, 2023: 11156−11172
[26] Gu Yuxian, Han Xu, Liu Zhiyuan, et al. PPT: Pre-trained prompt tuning for few-shot learning[C]//Proc of the 60th Annual Meeting of the Association for Computational Linguistics. Stroudsburg, PA: ACL, 2022: 8410−8423
[27] Zhang Qingru, Chen Minshuo, Bukharin A, et al. Adaptive budget allocation for parameter-efficient fine-tuning[J]. arXiv preprint, arXiv: 2303.10512, 2023
[28] Chen Yukang, Qian Shengju, Tang Haotian, et al. Longlora: Efficient fine-tuning of long-context large language models[J]. arXiv preprint, arXiv: 2309.12307, 2023
[29] Chua T J, Yu Wenhan, Zhao Jun, et al. FedPEAT: Convergence of federated learning, parameter-efficient fine tuning, and emulator assisted tuning for artificial intelligence foundation models with mobile edge computing[J]. arXiv preprint, arXiv: 2310.17491, 2023
[30] Che Tianshi, Liu Ji, Zhou Yang, et al. Federated learning of large language models with parameter-efficient prompt tuning and adaptive optimization[J]. arXiv preprint, arXiv: 2310.15080, 2023
[31] Babakniya S, Elkordy A R, Ezzeldin Y H, et al. SLoRA: Federated parameter efficient fine-tuning of language models[J]. arXiv preprint, arXiv: 2308.06522, 2023
[32] Zhang Zhuo, Yang Yuanhang, Dai Yong, et al. FedPETuning: When federated learning meets the parameter-efficient tuning methods of pre-trained language models[C]//Proc of the 61st Annual Meeting of the Association for Computational Linguistics. Stroudsburg, PA: ACL, 2023: 9963−9977
[33] Kuang Weirui, Qian Bingchen, Li Zitao, et al. Federatedscope-llm: A comprehensive package for fine-tuning large language models in federated learning[J]. arXiv preprint, arxiv: 2309.00363, 2023
[34] Fan Tao, Kang Yan, Ma Guoqiang, et al. Fate-llm: A industrial grade federated learning framework for large language models[J]. arXiv preprint, arxiv: 2310.10049, 2023
[35] Chen Haokun, Zhang Yao, Krompass D, et al. FedDAT: An approach for foundation model finetuning in multi-modal heterogeneous federated Learning[J]. arXiv preprint, arXiv: 2308.12305, 2023
[36] Guo Tao, Guo Song, Wang Junxiao, et al. Promptfl: Let federated participants cooperatively learn prompts instead of models-federated learning in age of foundation model[J]. IEEE Transactions on Mobile Computing, 2023, 23(5): 5179−5194
[37] Xu Mengwei, Yin Wangsong, Cai Dongqi, et al. A survey of resource-efficient LLM and multimodal foundation models[J]. arXiv preprint, arXiv: 2401.08092, 2024
[38] Wan Zhongwei, Wang Xin, Liu Che, et al. Efficient large language models: A survey[J]. arXiv preprint, arXiv: 2312.03863, 2023
[39] Miao Xupeng, Oliaro G, Zhang Zhihao, et al. Towards efficient generative large language model serving: A survey from algorithms to systems[J]. arXiv preprint, arXiv: 2312.15234, 2023
[40] Kachris C. A survey on hardware accelerators for large language models[J]. arXiv preprint, arXiv: 2401.09890, 2024
[41] Zhong Juan, Liu Zheng, Chen Xi. Transformer-based models and hardware acceleration analysis in autonomous driving: A survey[J]. arXiv preprint, arXiv: 2304.10891, 2023
[42] Emani M, Foreman S, Sastry V, et al. A comprehensive performance study of large language models on novel AI accelerators[J]. arXiv preprint, arXiv: 2310.04607, 2023
[43] 张晓东,张朝昆,赵继军. 边缘智能研究进展[J]. 计算机研究与发展,2023,60(12):2749−2769 doi: 10.7544/issn1000-1239.202220192 Zhang Xiaodong, Zhang Chaokun, Zhao Jijun. State-of-the-Art survey on edge intelligence[J]. Journal of Computer Research and Development, 2023, 60(12): 2749−2769 (in Chinese) doi: 10.7544/issn1000-1239.202220192
[44] Zhu Xunyu, Li Jian, Liu Yong, et al. A survey on model compression for large language models[J]. arXiv preprint, arXiv: 2308.07633, 2023
[45] Ma Xinyin, Fang Gongfan, Wang Xinchao. LLM-Pruner: On the structural pruning of large language models[J]. arXiv preprint, arXiv: 2305.11627, 2023
[46] Xia Mengzhou, Gao Tianyu, Zeng Zhiyuan, et al. Sheared LLaMA: Accelerating language model pre-training via structured pruning[J]. arXiv preprint, arXiv: 2310.06694, 2023
[47] Wang Hanrui, Zhang Zhekai, Han Song. SpAtten: Efficient sparse attention architecture with cascade token and head pruning[C]//Proc of the 27th IEEE Int Symp on High-Performance Computer Architecture. Piscataway, NJ: IEEE, 2021: 97−110
[48] Zhang Mingyang, Chen Hao, Shen Chunhua, et al. LoRAPrune: Pruning meets low-rank parameter-efficient fine-tuning[J]. arXiv preprint, arXiv: 2305.18403, 2023
[49] Xia Haojun, Zheng Zhen, Li Yuchao, et al. Flash-LLM: Enabling cost-effective and highly-efficient large generative model inference with unstructured sparsity[J]. arXiv preprint, arXiv: 2309.10285, 2023
[50] Frantar E, Alistarh D. SparseGPT: Massive language models can be accurately pruned in one-shot[C]//Proc of the 40th Int Conf on Machine Learning PMLR. New York: ACM, 2023: 10323−10337
[51] Sun Mingjie, Liu Zhuang, Bair A, et al. A simple and effective pruning approach for large language models[J]. arXiv preprint, arXiv: 2306.11695, 2023
[52] Liang Chen, Zuo Simiao, Zhang Qingru, et al. Less is more: Task-aware layer-wise distillation for language model compression[C]//Proc of the 40th Int Conf on Machine Learning PMLR. New York: ACM, 2023: 20852−20867
[53] Zhang Chen, Song Dawei, Ye Zheyu, et al. Towards the law of capacity gap in distilling language models[J]. arXiv preprint, arXiv: 2311.07052, 2023
[54] Padmanabhan S, Onoe Y, Zhang M, et al. Propagating knowledge updates to LMs through distillation[J]. arXiv preprint, arXiv: 2306.09306, 2023
[55] Agarwal R, Vieillard N, Zhou Yongchao, et al. On-policy distillation of language models: Learning from self-generated mistakes[J]. arXiv preprint, arXiv: 2306.13649, 2024
[56] Gu Yuxian, Dong Li, Wei Furu, et al. Knowledge distillation of large language models[J]. arXiv preprint, arXiv: 2306.08543, 2023
[57] Timiryasov I, Tastet J L. Baby llama: Knowledge distillation from an ensemble of teachers trained on a small dataset with no performance penalty[J]. arXiv preprint, arXiv: 2308.02019, 2023
[58] Xiong Yunyang, Varadarajan B, Wu Lemeng, et al. EfficientSAM: Leveraged masked image pretraining for efficient segment anything[J]. arXiv preprint, arXiv: 2312.00863, 2023
[59] Yuan Jianlong, Phan M H, Liu Liyang, et al. FAKD: Feature augmented knowledge distillation for semantic segmentation[C]//Proc of the 2024 IEEE/CVF Winter Conf on Applications of Computer Vision. Piscataway, NJ: IEEE, 2024: 595−605
[60] Nasser S A, Gupte N, Sethi A. Reverse knowledge distillation: Training a large model using a small one for retinal image matching on limited data[C]//Proc of the 2024 IEEE/CVF Winter Conf on Applications of Computer Vision. Piscataway, NJ: IEEE, 2024: 7778−7787
[61] Zhu Xuekai, Qi Biqing, Zhang Kaiyan, et al. PaD: Program-aided distillation specializes large models in reasoning[J]. arXiv preprint, arXiv: 2305.13888, 2023
[62] Li L H, Hessel J, Yu Youngjae, et al. Symbolic chain-of-thought distillation: Small models can also “think” step-by-step[C]//Proc of the 61st Annual Meeting of the Association for Computational Linguistics. Stroudsburg, PA: ACL, 2023: 2665−2679
[63] Shridhar K, Stolfo A, Sachan M. Distilling reasoning capabilities into smaller language models[C]//Proc of the 61st Annual Meeting of the Association for Computational Linguistics. Stroudsburg, PA: ACL, 2023: 7059−7073
[64] Ho N, Schmid L, Yun S Y. Large language models are reasoning teachers[C]//Proc of the 61st Annual Meeting of the Association for Computational Linguistics. Stroudsburg, PA: ACL, 2023: 14852−14882
[65] Wang Peifeng, Wang Zhengyang, Li Zheng, et al. SCOTT: Self-consistent chain-of-thought distillation[C]//Proc of the 61st Annual Meeting of the Association for Computational Linguistics. Stroudsburg, PA: ACL, 2023: 5546−5558
[66] Hsieh C Y, Li C L, Yeh C K, et al. Distilling step-by-step! Outperforming larger language models with less training data and smaller model sizes[C]//Proc of the 61st Annual Meeting of the Association for Computational Linguistics. Stroudsburg, PA: ACL, 2023: 8003−8017
[67] Chen Zeming, Gao Qiyue, Bosselut A, et al. DISCO: Distilling counterfactuals with large language models[C]//Proc of the 61st Annual Meeting of the Association for Computational Linguistics. Stroudsburg, PA: ACL, 2023: 5514−5528
[68] Jiang Yuxin, Chan C, Chen Mingyang, et al. Lion: Adversarial distillation of proprietary large language models[C]//Proc of the 2023 Conf on Empirical Methods in Natural Language Processing. Stroudsburg, PA: ACL 2023: 3134−3154
[69] Fu Yao, Peng Hao, Ou Litu, et al. Specializing smaller language models towards multi-step reasoning[C]//Proc of the 40th Int Conf on Machine Learning PMLR. New York: ACM, 2023: 10421−10430
[70] Wu Minghao, Waheed A, Zhang Chiyu, et al. LaMini-LM: A diverse herd of distilled models from large-scale instructions[J]. arXiv preprint, arXiv: 2304.14402, 2024
[71] Lin Ji, Tang Jiaming, Tang Haotian, et al. AWQ: Activation-aware weight quantization for LLM compression and acceleration[J]. arXiv preprint, arXiv: 2306.00978, 2023
[72] Li Qingyuan, Zhang Yifan, Li Liang, et al. FPTQ: Fine-grained post-training quantization for large language models[J]. arXiv preprint, arXiv: 2308.15987, 2023
[73] Wei Xiuying, Zhang Yunchen, Zhang Xiangguo, et al. Outlier suppression: Pushing the limit of low-bit transformer language models[C]//Proc of the 36th Int Conf on Neural Information Processing Systems. New York: ACM, 2022: 17402−17414
[74] Wei Xiuying, Zhang Yunchen, Li Yuhang, et al. Outlier suppression+: Accurate quantization of large language models by equivalent and effective shifting and scaling[C]//Proc of the 2023 Conf on Empirical Methods in Natural Language Processing. Stroudsburg, PA: ACL, 2023: 1648−1665
[75] Guo Cong, Tang Jiaming, Hu Weiming, et al. OliVe: Accelerating large language models via hardware-friendly outlier-victim pair quantization[C/OL]//Proc of the 50th Annual Int Symp on Computer Architecture. New York: ACM, 2023[2024-9-10]. https: /doi.org/10.1145/3579371.3589038
[76] Yao Zhewei, Yazdani A R, Zhang Minjia, et al. ZeroQuant: Efficient and affordable post-training quantization for large-scale transformers[C]//Proc of the 36th Int Conf on Neural Information Processing Systems. New York: ACM, 2022: 27168−27183
[77] Dettmers T, Lewis M, Belkada Y, et al. LLM. int8(): 8-bit matrix multiplication for transformers at scale[C]//Proc of the 36th Int Conf on Neural Information Processing Systems. New York: ACM, 2022: 30318−30332
[78] Frantar E, Ashkboos S, Hoefler T, et al. GPTQ: Accurate quantization for generative pre-trained transformers[C/OL]//Proc of the 11th Int Conf on Learning Representations. OpenReview. net, 2023[2024-09-10]. https://openreview.net/forum?id=tcbBPnfwxS
[79] Xiao Guangxuan, Lin Ji, Seznec M, et al. SmoothQuant: Accurate and efficient post-training quantization for large language models[C]//Proc of the 40th Int Conf on Machine Learning PMLR. New York: ACM, 2023: 38087−38099
[80] Dettmers T, Svirschevski R, Egiazarian V, et al. SpQR: A sparse-quantized representation for near-lossless LLM weight compression[J]. arXiv preprint, arXiv: 2306.03078, 2023
[81] Lee Changhun, Jin Jungyu, Kim T, et al. OWQ: Outlier-aware weight quantization for efficient fine-tuning and inference of large language models[C]//Proc of the 38th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2024: 13355−13364
[82] Wang Hongyu, Ma Shuming, Dong Li, et al. BitNet: Scaling 1-bit transformers for large language models[J]. arXiv preprint, arXiv: 2310.11453, 2023
[83] Dettmers T, Pagnoni A, Holtzman A, et al. QLoRA: Efficient finetuning of quantized LLMs[C]//Proc of the 37th Advances in Neural Information Processing Systems. Cambridge, MA: MIT Press, 2023: 10088−10115
[84] Kim J, Lee J H, Kim S, et al. Memory-efficient fine-tuning of compressed large language models via sub−4-bit integer quantization[C]//Proc of the 36th Advances in Neural Information Processing Systems. Cambridge, MA: MIT Press, 2023: 36187−36207
[85] Liu Zechun, Oguz B, Zhao Changsheng, et al. LLM-QAT: Data-free quantization aware training for large language models[J]. arXiv preprint, arXiv: 2305.17888, 2023
[86] Liu Xinyu, Wang Tao, Yang Jiaming, et al. MPQ-YOLO: Ultra low mixed-precision quantization of YOLO for edge devices deployment[J]. Neurocomputing, 2024, 574: 127210 doi: 10.1016/j.neucom.2023.127210
[87] Kaushal A, Vaidhya T, Rish I. LORD: Low rank decomposition of monolingual code LLMs for one-shot compression[C/OL]//Proc of the 41st ICML 2024 Workshop on Foundation Models in the Wild. OpenReview. net, 2024[2024-09-10]. https://openreview.net/forum?id=br49PQvuMp
[88] Li Yixiao, Yu Yifan, Zhang Qingru, et al. LoSparse: Structured compression of large language models based on low-rank and sparse approximation[C]//Proc of the 40th Int Conf on Machine Learning. New York: PMLR, 2023: 20336−20350
[89] Xu Mingxue, Xu Yaolei, Mandic D P. TensorGPT: Efficient compression of the embedding layer in LLMs based on the tensor-train decomposition[J]. arXiv preprint, arXiv: 2307.00526, 2023
[90] Chang C C, Sung Y Y, Yu Shixing, et al. FLORA: Fine-grained low-rank architecture search for vision transformer[C]//Proc of the 2024 IEEE/CVF Winter Conf on Applications of Computer Vision. Piscataway, NJ: IEEE, 2024: 2482−2491
[91] Benedek N, Wolf L. PRILoRA: Pruned and rank-increasing low-rank adaptation[J]. arXiv preprint, arXiv: 2401.11316, 2024
[92] Cheng Hongrong, Zhang Miao, Shi J Q. A survey on deep neural network pruning-taxonomy, comparison, analysis, and recommendations[J]. arXiv preprint, arXiv: 2308.06767, 2023
[93] Xu Xiaohan, Li Ming, Tao Chongyang, et al. A survey on knowledge distillation of large language models[J]. arXiv preprint, arXiv: 2402.13116, 2024
[94] Zhu Xunyu, Li Jian, Liu Yong, et al. A survey on model compression for large language models[J]. arXiv preprint, arXiv: 2308.07633, 2023
[95] Hu E, Shen Yelong, Wallis P, et al. LoRA: Low-rank adaptation of large language models[C/OL]//Proc of the 10th Int Conf on Learning Representations. OpenReview. net, 2022[2024-09-10]. https://openreview.net/forum?id=nZeVKeeFYf9
[96] Liu Jing, Gong Ruihao, Wei Xiuying, et al. QLLM: Accurate and efficient low-bitwidth quantization for large language models[C/OL]//Proc of the 12th Int Conf on Learning Representations. OpenReview. net, 2024[2024-09-10]. https://openreview.net/forum?id=FIplmUWdm3
[97] Xiao Guangxuan, Tian Yuandong, Chen Beidi, et al. Efficient streaming language models with attention sinks[C/OL]//Proc of the 12th Int Conf on Learning Representations. OpenReview. net, 2024[2024-09-10]. https://openreview.net/forum?id=NG7sS51zVF
[98] Liu Zichang, Desai A, Liao Fangshuo, et al. Scissorhands: Exploiting the persistence of importance hypothesis for LLM KV cache compression at test time[C]//Proc of the 37th Advances in Neural Information Processing Systems. Cambridge, MA: MIT Press, 2023: 52342−52364
[99] Zhang Zhenyu, Sheng Ying, Zhou Tianyi, et al. H2O: Heavy-hitter oracle for efficient generative inference of large language models[C]//Proc of the 37th Advances in Neural Information Processing Systems. Cambridge, MA: MIT Press, 2023: 34661−34710
[100] Ge Suyu, Zhang Yunan, Liu Liyuan, et al. Model tells you what to discard: Adaptive KV cache compression for LLMs[C/OL]//Proc of the 12th Int Conf on Learning Representations. OpenReview. net, 2024[2024-09-10]. https://openreview.net/forum?id=uNrFpDPMyo
[101] Hooper C, Kim S, Mohammadzadeh H, et al. KVQuant: Towards 10 million context length LLM Inference with KV cache quantization[J]. arXiv preprint, arXiv: 2401.18079, 2024
[102] Kwon W, Li Zhuohan, Zhuang Siyuan, et al. Efficient memory management for large language model serving with pagedattention[C]//Proc of the 29th Symp on Operating Systems Principles. New York: ACM, 2023: 611−626
[103] Del C L, Del G A, Agarwal S, et al. SkipDecode: Autoregressive skip decoding with batching and caching for efficient LLM inference[J]. arXiv preprint, arXiv: 2307.02628, 2023
[104] Zeng Dewen, Du Nan, Wang Tao, et al. Learning to skip for language modeling[J]. arXiv preprint, arXiv: 2311.15436, 2023
[105] Schuster T, Fisch A, Gupta J, et al. Confident adaptive language modeling[C]//Proc of the 36th Advances in Neural Information Processing Systems. Cambridge, MA: MIT Press, 2022: 17456−17472
[106] Sun Tianxiang, Liu Xiangyang, Zhu Wei, et al. A simple hash-based early exiting approach for language understanding and generation[J]. arXiv preprint, arXiv: 2203.01670, 2022
[107] Liao Kaiyuan, Zhang Yi, Ren Xuancheng, et al. A global past-future early exit method for accelerating inference of pre-trained language models[C]//Proc of the 2021 Conf of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Stroudsburg, PA: ACL, 2021: 2013−2023
[108] Kong Jun, Wang Jin, Yu L C, et al. Accelerating inference for pretrained language models by unified multi-perspective early exiting[C]//Proc of the 29th Int Conf on Computational Linguistics. Stroudsburg, PA: ACL, 2022: 4677−4686
[109] Zeng Ziqian, Hong Yihuai, Dai Hongliang, et al. ConsistentEE: A consistent and hardness-guided early exiting method for accelerating language models inference[C]//Proc of the 38th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2024: 19506−19514
[110] Bae S, Ko J, Song H, et al. Fast and robust early-exiting framework for autoregressive language models with synchronized parallel decoding[C]//Proc of the 2023 Conf on Empirical Methods in Natural Language Processing. Stroudsburg, PA: ACL, 2023: 5910−5924
[111] Valmeekam C S K, Narayanan K K D, Kalathil D, et al. LLMZip: Lossless text compression using large language models[J]. arXiv preprint, arXiv: 2306.04050, 2023
[112] Chevalier A, Wettig A, Ajith A, et al. Adapting language models to compress contexts[C]//Proc of the 2023 Conf on Empirical Methods in Natural Language Processing. Stroudsburg, PA: ACL, 2023: 3829−3846
[113] Li Yucheng, Dong Bo, Guerin F, et al. Compressing context to enhance inference efficiency of large language models[C]//Proc of the 2023 Conf on Empirical Methods in Natural Language Processing. Stroudsburg, PA: ACL, 2023: 6342−6353
[114] Jiang Huiqiang, Wu Qianhui, Lin C Y, et al. LLMLingua: Compressing prompts for accelerated inference of large language models[C]//Proc of the 2023 Conf on Empirical Methods in Natural Language Processing. Stroudsburg, PA: ACL, 2023: 13358−13376
[115] Jiang Huiqiang, Wu Qianhui, Luo Xufang, et al. LongLLMLingua: Accelerating and enhancing LLMs in long context scenarios via prompt compression[C]//Proc of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Stroudsburg, PA: ACL, 2024: 1658−1677
[116] Fu Yichao, Bailis P, Stoica I, et al. Break the sequential dependency of LLM inference using lookahead decoding[C]//Proc of the 41st Int Conf on Machine Learning. New York: PMLR, 2024: 14060−14079
[117] Leviathan Y, Kalman M, Matias Y. Fast inference from transformers via speculative decoding[C]//Proc of the 40th int Conf on Machine Learning. New York: PMLR, 2023: 19274−19286
[118] Miao Xupeng, Oliaro G, Zhang Zhihao, et al. SpecInfer: Accelerating generative large language model serving with tree-based speculative inference and verification[C]//Proc of the 29th ACM Int Conf on Architectural Support for Programming Languages and Operating Systems, Volume 3. New York: ACM, 2024: 932–949
[119] Cai T, Li Yuhong, Geng Zhengyang, et al. Medusa: Simple LLM inference acceleration framework with multiple decoding heads[C]//Proc of the 41st int Conf on Machine Learning. New York: PMLR, 2024: 5209−5235
[120] Li Yuhui, Wei Fangyun, Zhang Chao, et al. EAGLE: Speculative sampling requires rethinking feature uncertainty[C]//Proc of the 41st int Conf on Machine Learning. New York: PMLR, 2024: 28935−28948
[121] Xu Daliang, Yin Wangsong, Jin Xin, et al. LLMCad: Fast and scalable on-device large language model inference[J]. arXiv preprint, arXiv: 2309.04255, 2023
[122] Shen Haihao, Chang Hanwen, Dong Bo, et al. Efficient llm inference on cpus[J]. arXiv preprint, arXiv: 2311.00502, 2023
[123] Dao T, Fu Dan, Ermon S, et al. FlashAttention: Fast and memory-efficient exact attention with IO-awareness[C]//Proc of the 36th Advances in Neural Information Processing Systems. Cambridge, MA: MIT Press, 2022: 16344−16359
[124] Dao T. FlashAttention−2: Faster attention with better parallelism and work partitioning[C/OL]//Proc of the 12th Int Conf on Learning Representations. OpenReview. net, 2024[2024-09-10]. https://openreview.net/forum?id=mZn2Xyh9Ec
[125] Dao T, Haziza D, Massa F, et al. Flash-Decoding for long-context inference[EB/OL]. 2023[2024-02-03]. https://pytorch.org/blog/flash-decoding/
[126] Hong Ke, Dai Guohao, Xu Jiaming, et al. FlashDecoding++: Faster large language model inference with asynchronization, flat GEMM optimization, and heuristics[C/OL]//Proc of Machine Learning and Systems. 2024: 148−161[2024-09-12]. https://proceedings.mlsys.org/paper_files/paper/2024/hash/5321b1dabcd2be188d796c21b733e8c7-Abstract-Conference. html
[127] Lai Ruihang, Shao Junru, Feng Siyuan, et al. Relax: Composable abstractions for end-to-end dynamic machine learning[J]. arXiv preprint, arXiv: 2311.02103, 2023
[128] Tillet P, Kung H T, Cox D. Triton: An intermediate language and compiler for tiled neural network computations[C]//Proc of the 3rd ACM SIGPLAN Int Workshop on Machine Learning and Programming Languages. New York: ACM, 2019: 10−19
[129] Feng Siyuan, Hou Bohan, Jin Hongyi, et al. TensorIR: An abstraction for automatic tensorized program optimization[C]//Proc of the 28th ACM Int Conf on Architectural Support for Programming Languages and Operating Systems: Volume 2. New York: ACM, 2023: 804−817
[130] Liu Zichang, Wang Jue, Dao T, et al. Deja Vu: Contextual sparsity for efficient LLMs at inference time[C]//Proc of the 40th Int Conf on Machine Learning. New York: PMLR, 2023: 22137−22176
[131] Sheng Ying, Zheng Lianmin, Yuan Binhang, et al. FlexGen: High-throughput generative inference of large language models with a single GPU[C]//Proc of the 40th Int Conf on Machine Learning. New York: PMLR, 2023: 31094−31116
[132] Song Yixin, Mi Zeyu, Xie Haotong, et al. PowerInfer: Fast large language model serving with a consumer-grade GPU[J]. arXiv preprint, arXiv: 2312.12456, 2023
[133] Yi Rongjie, Guo Liwei, Wei Shiyun, et al. EdgeMoE: Fast on-device inference of MoE-based large language models[J]. arXiv preprint, arXiv: 2308.14352, 2023
[134] Awais M, Naseer M, Khan S, et al. Foundational models defining a new era in vision: A survey and outlook[J]. arXiv preprint, arXiv: 2307.13721, 2023
[135] Tang Shengkun, Wang Yaqing, Kong Zhenglun, et al. You need multiple exiting: Dynamic early exiting for accelerating unified vision language model[C]//Proc of the 44th IEEE/CVF Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2023: 10781−10791
[136] Li Zi, Tian Lin, Mok C W, et al. Samconvex: Fast discrete optimization for ct registration using self-supervised anatomical embedding and correlation pyramid[G]//Proc of the 26th Medical Image Computing and Computer Assisted Intervention(MICCAI 2023). Berlin: Springer, 2023: 559−569
[137] Zhou Chong, Loy C C, Dai Bo. Extract free dense labels from CLIP[C]//Proc of the 17th Computer Vision(ECCV 2022). Berlin: Springer, 2022: 696−712
[138] Sanghi A, Chu Hang, Lambourn J G, et al. Clip-forge: Towards zero-shot text-to-shape generation[C]//Proc of the 2022 IEEE/CVF Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2022: 18603−18613
[139] Vaswani A, Shazeer N, Parmar N, et al. Attention is All you Need[C]//Proc of the 31st Advances in Neural Information Processing Systems. Cambridge, MA: MIT Press, 2017: 5999−6009
[140] InternLM. LMDeploy[EB/OL]. 2023[2024-02-04]. https://github.com/InternLM/lmdeploy
[141] Microsoft. DeepSpeed-MII[EB/OL]. 2022[2024-02-04]. https://github.com/microsoft/DeepSpeed-MII
[142] NVIDIA. TensorRT-LLM[EB/OL]. 2023[2024-02-04]. https://github.com/NVIDIA/TensorRT-LLM
[143] vLLM Team. vLLM[EB/OL]. 2023[2024-02-04]. https://github.com/vllm-project/vllm
[144] Lin Ji, Chen Weiming, Lin Yujun, et al. MCUNet: Tiny deep learning on IoT devices[C]//Proc of the 34th Advances in Neural Information Processing Systems. Cambridge, MA: MIT Press, 2020: 11711−11722
[145] Neuralmagic. DeepSparse[EB/OL]. 2021[2024-02-04]. https://github.com/neuralmagic/deepsparse
[146] 李双峰. TensorFlow Lite:端侧机器学习框架[J]. 计算机研究与发展,2020,57(9):1839−1853 doi: 10.7544/issn1000-1239.2020.20200291 Li Shuangfeng. TensorFlow lite: On-device machine learning framework[J]. Journal of Computer Research and Development, 2020, 57(9): 1839−1853 (in Chinese) doi: 10.7544/issn1000-1239.2020.20200291
[147] PyTorch Team. PyTorch ExecuTorch[EB/OL]. 2023[2024-05-28]. https://pytorch.org/executorch
[148] Alibaba. MNN[EB/OL]. 2019[2024-06-30]. https://github.com/alibaba/MNN
[149] Tencent. ncnn[EB/OL]. 2017[2024-05-30]. https://github.com/Tencent/ncnn
[150] MLC Team. MLC LLM[EB/OL]. 2023[2024-02-04]. https://github.com/mlc-ai/mlc-llm
[151] Gerganov G. llama. cpp[EB/OL]. 2023[2024-02-04]. https://github.com/ggerganov/llama.cpp
[152] Karpathy A. llama2. c[EB/OL]. 2023[2024-02-04]. https://github.com/karpathy/llama2.c
[153] Mllm Team. mllm[EB/OL]. 2023[2024-02-04]. https://github.com/UbiquitousLearning/mllm
[154] Intel. Intel Extension for Transformers[EB/OL]. 2022[2024-02-04]. https://github.com/intel/intel-extension-for-transformers
[155] Megvii Inc. InferLLM[EB/OL]. 2023[2024-02-04]. https://github.com/MegEngine/InferLLM
[156] MIT Han Lab. TinyChatEngine[EB/OL]. 2023[2024-02-04]. https://github.com/mit-han-lab/TinyChatEngine
[157] NVIDIA. NanoLLM[EB/OL]. 2024[2024-04-28]. https://github.com/dusty-nv/NanoLLM
[158] Shazeer N. Fast transformer decoding: One write-head is all you need[J]. arXiv preprint, arXiv: 1911.02150, 2019
[159] Ainslie J, Lee-Thorp J, de Jong M, et al. GQA: Training generalized multi-query transformer models from multi-head checkpoints[C]//Proc of the 2023 Conf on Empirical Methods in Natural Language Processing. Stroudsburg, PA: ACL, 2023: 4895−4901
[160] Choromanski K M, Likhosherstov V, Dohan D, et al. Rethinking attention with performers[C/OL]//Proc of the 9th Int Conf on Learning Representations. OpenReview. net, 2021[2024-09-10]. https://openreview.net/forum?id=Ua6zuk0WRH
[161] Shazeer N. Glu variants improve transformer[J]. arXiv preprint, arXiv: 2002.05202, 2020
[162] Lepikhin D, Lee H, Xu Yuanzhong, et al. GShard: Scaling giant models with conditional computation and automatic sharding[C/OL]//Proc of the 9th Int Conf on Learning Representations. OpenReview. net, 2021[2024-09-10]. https://openreview.net/forum?id=qrwe7XHTmYb
[163] Fedus W, Zoph B, Shazeer N. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity[J]. Journal of Machine Learning Research, 2022, 23(1): 120: 5232−120: 5270
[164] Gu A, Dao T. Mamba: Linear-time sequence modeling with selective state spaces[J]. arXiv preprint, arXiv: 2312.00752, 2023
[165] Peng Bo, Alcaide E, Anthony Q, et al. RWKV: Reinventing RNNs for the transformer era[C]//Proc of the Findings of the Association for Computational Linguistics(EMNLP 2023). Stroudsburg, PA: ACL, 2023: 14048−14077
[166] Sun Yutao, Dong Li, Huang Shaohan, et al. Retentive network: A successor to transformer for large language models[J]. arXiv preprint, arXiv: 2307.08621, 2023
[167] 徐志伟,曾琛,朝鲁,等. 面向控域的体系结构:一种智能万物互联的体系结构风格[J]. 计算机研究与发展,2019,56(1):90−102 doi: 10.7544/issn1000-1239.2019.20180775 Xu Zhiwei, Zeng Chen, Zhao Lu, et al. Domain oriented architecture: An architectural style of intelligent interconnection of all things[J]. Journal of Computer Research and Development, 2019, 56(1): 90−102 (in Chinese) doi: 10.7544/issn1000-1239.2019.20180775
[168] 李国杰. 对大数据的再认识[J]. 大数据,2015,1(1):8−16 doi: 10.11959/j.issn.2096-0271.2015.01.001 Li Guojie. Further understanding of big data[J]. Big Data, 2015, 1(1): 8−16 (in Chinese) doi: 10.11959/j.issn.2096-0271.2015.01.001
[169] Woisetschläger H, Isenko A, Wang Shiqiang, et al. Federated fine-tuning of llms on the very edge: The good, the bad, the ugly[C]//Proc of the 8th Workshop on Data Management for End-to-End Machine Learning. New York: ACM, 2024: 39−50
[170] Yang Chengxu, Xu Mengwei, Wang Qipeng, et al. Flash: Heterogeneity-aware federated learning at scale[J]. IEEE Transactions on Mobile Computing, 2024, 23(1): 483−500 doi: 10.1109/TMC.2022.3214234
[171] Lu Wang, Hu Xixu, Wang Jindong, et al. FedCLIP: Fast generalization and personalization for CLIP in federated learning[J]. IEEE Data Engineering Bulletin, 2023, 46(1): 52−66
[172] 矣晓沅,谢幸. 大模型道德价值观对齐问题剖析[J]. 计算机研究与发展,2023,60(9):1926−1945 doi: 10.7544/issn1000-1239.202330553 Yi Xiaoyuan, Xie Xing. An analysis of the alignment of moral values in the large model[J]. Journal of Computer Research and Development, 2023, 60(9): 1926−1945 (in Chinese) doi: 10.7544/issn1000-1239.202330553