-
摘要:
隐私审计是数据治理中的关键问题，旨在判断数据的隐私是否得到了有效保护. 通常，学者们通过对数据添加噪声或扰动实现差分隐私，从而保护个人隐私. 特别在机器学习场景下，出现越来越多的差分隐私算法, 并且这些算法均声称自己可以达到较为严格的隐私保护水平. 然而，即使这些算法在发布之前会经过严格的数学证明，其实际应用中的隐私保护程度亦难以确定. 鉴于差分隐私理论本身的复杂性，隐私算法中证明的错误和编程实现的错误时有发生，使得这些算法无法达到其声称的隐私保护水平，导致隐私泄露. 为了解决这一问题，隐私审计应运而生. 隐私审计可以获取隐私算法的真实隐私保护水平，有助于算法设计者对算法进行改进. 将综述隐私审计相关算法，从数据构建、数据测算、结果量化3个维度进行总结，并对隐私审计算法进行实验说明，最终提出隐私审计面临的挑战以及未来研究方向.
Abstract:Privacy auditing is a crucial issue of data governance, aiming to detect whether data privacy has been protected effectively. Typically, scholars would protect personal private data to meet differential privacy guarantees by perturbing data or adding noise to them. Especially in scenarios of machine learning, an increasing number of differential privacy algorithms have emerged, claiming a relatively stringent level of privacy protection. Although rigorous mathematical proofs of privacy have been conducted before the algorithms’ release, the actual effect on privacy in practice is hardly assured. Due to the complexity of the theory of differential privacy, the correctness of their proofs may not have been thoroughly examined, and imperceptible errors may occur during programming. All of these can undermine the extent of privacy protection to the claimed degree, leaking additional privacy. To tackle this issue, privacy auditing for differential privacy algorithms has emerged. This technique aims to obtain the actual degree of privacy-preserving of differential privacy algorithms, facilitating the discovery of mistakes and improving existing differential privacy algorithms. This paper surveys the scenarios and methods of privacy auditing, summarizing the methods from three aspects―data construction, data measurement, and result quantification, and evaluating them through experiments. Finally, this work presents the challenges of privacy auditing and its future direction.
-
Keywords:
- data governance /
- privacy preserving /
- machine learning /
- privacy auditing /
- differential privacy
-
当前，移动互联、万物互联以及数字化转型所带动的海量数据流量致使人们对存储的需求呈现爆发式增长. 伴随海量数据所增长的储存和处理需求直接拉动云环境下外包数据存储市场高增. 然而，在人们享受云存储带来的便利的同时，数据安全性的问题随之而来. 为了防止云服务提供商和黑客未经授权访问用户的外包数据，用户可以将敏感和隐私数据进行加密再外包至云服务器. 然而，传统加密方法会改变数据的原始特征，云服务器无法对密文进行搜索和处理，严重影响外包数据的可用性. 为了解决上述问题，研究者们提出了可搜索加密技术——在保障用户安全方便地使用外包数据存储服务的同时，使云服务器端能够在不解密数据的前提下对密文进行搜索，从而保证了外包数据的机密性与可用性. 近年来，可搜索加密技术得到了广泛且深入的研究，但仍面临许多挑战.
首先是动态更新方面. 现实场景中，企业及个人用户外包数据很少是一成不变的，经常需要频繁定期更新. 已有可搜索加密方案中利用前向索引构造的方案[1]支持直接文件更新，动态性较好，易于实际开发应用，但是前向索引结构泄露了和明文相关的信息，容易被敌手进行统计攻击，而且搜索效率不尽如人意. 倒排索引结构是实现关键字到文件映射关系的最佳方式，能够实现高效搜索[2]，然而，倒排索引动态更新过程较为复杂，添加或删除文件时必须对索引中的所有条目进行线性扫描. 现有基于倒排索引的可搜索加密方案的动态更新过程大多需要额外更新结构进行辅助，这些更新结构通常过于复杂，导致更新效率非常低，并且只能允许有限的更新操作. 除此之外，已有的动态更新方法在更新过程中往往会向服务器泄露较多信息，例如关于更新关键字的关联信息等，即敌手可将更新的文件与之前的历史搜索结果建立联系，进而使方案无法抵抗文件注入攻击.
其次，为了更好地提高用户的搜索体验，可搜索加密一个重要的研究方向是提高搜索语句表达性，例如支持多关键字布尔搜索[3]. 严格意义上的布尔搜索是指利用布尔逻辑运算符连接各个搜索关键字，然后由计算机进行相应逻辑运算，以找出所需信息的方法. 布尔搜索在所有搜索功能中使用面最广、使用频率最高. 但是，布尔搜索不仅需要云服务器进行关键字密文搜索，还需要对搜索结果进行布尔运算，过程中更容易由于节点崩溃或外部攻击而返回不正确的布尔搜索结果. 因此为了应对上述问题，亟需引入搜索结果验证机制来保证搜索结果的正确性. 一些可搜索加密方案通过数据认证技术，如MAC认证结构[4]、Merkle哈希树[5]和布隆滤波器[6]等，实现对搜索结果的验证. 然而上述验证方法仅能验证搜索语句表达性较差的搜索请求，甚至单一关键字搜索请求. 对于多关键词布尔搜索，目前的验证方法主要使用基于数据持有性证明技术中随机抽取的思想来实现[7]，面临误差较大以及结果验证计算负载较大等缺陷，不能适应实际广泛的应用场景.
最近几年，随着加密货币和去中心化应用的流行，区块链技术受到了各行业极大的关注. 区块链数据存储成为构建分布式存储平台的关键技术. 例如Bigchain DB[8]和Bluzelle[9]，其通过共识协议确保数据存储的一致性和不可篡改性，为解决上述这些问题提供了可能. 近年来，很多方法将密码学加密技术与区块链结构相融合，一定程度上实现了链上数据的隐私保护[10-11]. 一些可搜索加密方案以智能合约代替传统的可信第三方来提供搜索公平性的保证[12-14]. 然而，上述方案中安全索引仍然部署于服务器端，而且受制于区块链固有的分叉问题导致方案的可用性受到了影响，并未发挥出区块链数据存储固有的防篡改和增量更新性等优势.
本文针对上述问题展开研究，提出基于区块链索引的可验证布尔搜索加密方案VBSE-BI.方案将可搜索加密中的安全索引结构与区块链数据存储进行深度融合，限制服务器由于单点故障原因对索引结构进行破坏，实现索引的存储机密性、动态更新性以及搜索正确性. 同时方案在支持对多关键字布尔搜索的同时，保证了布尔搜索结果的不可伪造性. 本文主要工作如下：
1）提出基于区块链存储结构的增量链式安全索引构造方法. 首先构建“关键字-文件”链式索引结构，将索引拆分为数据块的形式存储在区块链结构的交易信息中，利用指针进行链接，并引入同态加密机制代替标准加密方法来加密索引信息，在不解密索引的情况下实现高效搜索. 此方法以区块链的不可篡改性来提供搜索正确性和可靠性，并且避免了构建辅助更新索引结构导致的索引存储及更新开销大的问题.
2）提出针对布尔搜索结果的完整性验证方法. 针对服务器端布尔运算完整性验证需求，给出VBSE-BI的搜索结果不可伪造性定义，基于双线性映射累加器和扩展欧几里德算法设计面向布尔搜索的完整性证明以及验证方法，并且，基于双线性q阶强Diffie-Hellman假设，对该方法的不可伪造性进行了严格的安全性证明.
3）对VBSE-BI方案每个算法和协议进行详细构建，并从存储开销、计算开销以及通信开销3个维度对比分析方案性能；对VBSE-BI方案进行了编程实现，并通过对算法的性能测试来分析方案在实际应用中的性能表现. 性能分析结果显示，本方案降低了服务器端存储以及搜索开销的同时，降低了用户计算复杂度，满足实际云环境下资源受限本地设备的应用需求.
1. 相关工作
近几年，学者们对可搜索加密方案的各方面问题进行了深入的研究. 针对可搜索加密的动态更新问题，2012年，Kamara等人[2]提出了基于正反双链表结构的动态可搜索加密方案，但是在更新文件的时候会造成较大信息泄露，无法抵抗文件注入攻击. 为了降低更新泄露，Hahn等人[15]中提出一种新的动态可搜索加密方案，主要思想是根据用户的搜索历史构造前向索引和倒排索引2个索引结构，云服务器不会得到除了搜索令牌之外的任何用户信息，但是该方案仅在文件数据庞大而关键字数目不多的场景下具有高的搜索效率.2016年，Bost[1]构造了一个满足向前安全性的动态可搜索加密方案，向前安全性保证了更新文件时敌手无法将其关键字信息与之前的搜索历史进行匹配.2018年，Zuo等人[16]基于二进制树和同态加密算法构建了2个动态可搜索加密方案，并支持范围查询，第1个方案拥有前向安全，第2个方案拥有前向安全和部分后向安全，但对加密文档的数量有限制.
在搜索结果的可验证性方面，2013年，Chai等人[17]首先提出并研究了支持搜索结果验证可搜索加密问题. 2015年，Wang等人[18]提出了一种在混合云中支持容错性和可验证性的可搜索加密方案，通过基于字典的索引构建方法，生成模糊关键字字典，实现搜索结果的动态排序和可验证性. Kurosawa等人[19]利用RSA累加器生成搜索标签，从而实现搜索结果的验证并支持对文件的动态更新. 2015年，Ameri等人[20]利用布隆过滤器和多层级访问控制略构造了一种通用的多层级可验证关键字搜索方案. 2017年，Jiang等人[21]基于特殊倒排索引结构QSet、二进制矢量以及MAC函数设计了支持多关键字排序的可验证可搜索加密方案. 2018年，Wang等人[22]基于OXT的连接关键词检索方法，采用聚合器和采样检测技术提出了公开可验证的连接关键词检索方案. 已有的支持搜索结果验证的方案或多或少会牺牲搜索性能. 2020年，闫玺玺等人[23]提出了一种可验证属性基搜索加密方案，方案结合区块链技术解决半诚实且好奇的云服务器模型下返回搜索结果不正确的问题. 2021年，Najafi等人[24]针对实际应用场景中对多关键字可搜索加密的需求，提出多关键字动态可搜索加密及搜索结果完整性验证方法. 2024年，Xie等人[25]提出了一种新的可验证中文多关键字模糊排序可搜索加密方案，使用认证标签和概率陷门提高安全性、准确性和效率，解决了现有模糊关键词搜索方法的存储和计算资源消耗问题.
基于上述研究现状可以看出，现有的支持验证的可搜索加密方法中，数据拥有者端通常需要存储庞大的辅助结构，导致本地存储负载较大，而且大多可验证算法包含复杂的通信与计算代价，在实际应用中具有局限性. 考虑到资源受限的移动设备数量急剧增加，用户端的结果验证代价应尽可能小，否则将没有实用价值. 因此，提高搜索语句的表达性并且降低用户验证代价是可验证可搜索加密中亟待解决的关键问题.
2. VBSE-BI模型
VBSE-BI方案主要考虑2类实体：用户U和云服务器S.方案模型架构如图1所示. 用户U通过对本地文件集合进行信息提取来构建搜索索引，将索引利用密码学算法进行结构化加密，生成安全链式索引，并将链式索引拆分为交易值的形式存储于区块链索引中，根据对应的交易地址以及附加辅助验证元素生成以关键字为键的查找表，将查找表同样利用密码学算法进行结构化加密，生成密态查找表发送给云服务器S.区块链的增量存储特性使得索引能够满足文件的动态更新需求，即用户U可以随时添加或删除文件，并同时更新索引和查找表结构. 随后，用户发起生成布尔搜索请求，利用密码学工具将布尔表达式中的关键字信息进行加密，生成搜索令牌并发送给云服务器S.云服务器S在收到搜索令牌后，在密态查找表中定位到区块链索引中的搜索关键字对应的链式索引交易地址，进而在区块链安全索引中进行搜索并对搜索结果进行布尔运算. 随后，云服务器S将搜索结果以及对于布尔搜索结果正确性的证明返回给用户U. 用户U在收到搜索结果和相关的证明之后，在本地验证搜索结果的正确性，验证通过则可判定云服务器S正确执行了布尔搜索请求. 值得说明的是，区块链只负责存储链式索引结构，而真实的数据以加密的形式存储在云服务器S中.
2.1 符号描述
本节列出了论文中涉及的符号及其对应的含义，如表1所示.
表 1 符号描述Table 1. Symbols Description符号 含义 1k 安全参数 f 文件集合 fwi 包含关键字wi的文件集合 BC 区块链索引 T 密态查找表 ϕ(W) 关键字W布尔表达式 Rϕ(W) 搜索结果 L 泄露函数 π 证据 τ 搜索/更新令牌 F，G，P 伪随机函数 K1，K2，K3 伪随机函数F，G，P的密钥 K 用户密钥 Lw=(N1,…,N#fw) BC中关键字w对应的虚拟链表 addr(N) 节点N在BC中的地址 acc(fwi) fwi的双线性累加值 I/U/D 交/并/差集 flag 添加/删除标志 2.2 形式化定义
定义1. VBSE-BI方案主要由5个多项式时间算法和协议组成，即KeyGen，Setup，Search，Verify，Update，具体描述如下：
1）(K,PP)←KeyGen(1k). 密钥生成算法，由用户U执行. 输入安全参数1k，输出密钥K和公共参数PP.
2）(T,BC)←Setup(K,f). 初始化算法，由用户U执行. 输入密钥K，文件集合f，输出区块链索引BC以及密态查找表T.
3）(Rϕ(W),π;⊥)←Search(U(K,ϕ(W));S(T,BC)). 搜索协议，由用户U和云服务器S交互执行. 用于搜索文件. 用户输入密钥K、布尔表达式ϕ(W)，云服务器S输入密态查找表T和区块链索引BC，输出布尔搜索结果Rϕ(W)以及正确性证明π.
4）b←Verify(K,Rϕ(W),π). 验证算法，由用户U执行. 输入密钥K、搜索结果Rϕ(W)以及证明π，输出输入1或者0表示接受或拒绝.
5）(⊥;(T′,BC′))←Update(U(K,f);S(T,BC)). 更新协议，由用户U和云服务器S交互执行. 用户输入密钥K、更新文件f，云服务器输入密态查找表T和区块链索引BC，输出更新后的区块链索引BC′以及密态查找表T′.
定义2. VBSE-BI正确性.VBSE-BI方案的正确性包括搜索正确性以及更新正确性：
1）搜索正确性. 对于所有的安全参数k、所有的由KeyGen(1k)生成的K、所有的文件f以及所有由Setup(K,f)输出的(T, BC)和Update(U(K,f);S(T,BC))即任意顺序的更新操作，用户U与云服务器S交互执行的搜索协议Search(U(K,f);S(T,BC))总会得到正确的结果Rϕ(W). 即用户端的验证算法Verify(K,Rϕ(W),π)输出为1.
2）更新正确性. 用户U利用更新协议Update(U(K,f);S(T,BC))与云服务器S交互添加或删除包含关键字信息的文件f时，协议执行后服务器端的更新的密态查找表T′和区块链索引BC′会正确添加或删除文件f的相关信息，且二者仍然保持一致性且完整性.
2.3 安全性定义
在VBSE-BI方案的威胁模型中，假设云服务器为恶意敌手，即可能伪造搜索结果的布尔运算过程. 在这种威胁存在的情况下，VBSE-BI方案应该满足以下安全性定义：
定义3. 动态IND-CKA2安全性. 设A为敌手，Sim为模拟器，L1，L2，L3分别为初始化、搜索、更新文件阶段的泄露函数. 定义如下2个实验：
1）RealA(1k). 为敌手A和挑战者C之间的交互式实验，使用真实的方案算法. 在该实验中，挑战者C运行KeyGen(1k)生成密钥K和公共参数PP. 敌手A输出文件集合f给挑战者C，挑战者C运行初始化算法Setup(K,f)，输出(T,BC)给敌手. 敌手A可以向挑战者发起多项式次自适应质询{ϕ(Wi),fi}1⩽i⩽q. 对于每次质询{ϕ(Wi),fi}，挑战者C为敌手A生成搜索令牌τs,i. 或者更新令牌τu,i. 由于A是自适应敌手，所以其每次质询的结果都可以作为输入来产生下一次质询. 在所有q次质询结束后，敌手A输出一个比特值b作为该实验的输出.
2）IdealA,S(1k). 为敌手A和模拟器Sim之间的交互式实验. 敌手A输出索引结构δ. 根据泄露函数L1，模拟器Sim生成模拟的(˜T,~BC)并发送给敌手A. 敌手A可以向模拟器Sim发起多项式次自适应质询{ϕ(Wi),δfi}1⩽i⩽q. 对于每次质询(ϕ(Wi),δfi)，模拟器可以访问泄露函数L2和L3其中之一，并返回给敌手对应的模拟搜索令牌˜τS. 最终，敌手A返回一个比特值b作为该实验的输出.
VBSE-BI方案满足动态IND-CKA2安全性，当且仅当对于所有满足概率多项式时间计算能力的敌手A，存在多项式时间计算能力的模拟器Sim，使得
|Pr[RealA(1k)=1]−Pr[IdealA,S(1k)=1]|⩽negl(1k)， 其中negl(1k)为以1k为输入的可忽略函数.
定义4. 不可伪造性. 设A为一个有状态的敌手，C为挑战者，L1，L2，L3分别为初始化、搜索、更新文件阶段的泄露函数. 考虑游戏ForgeA(1k)中，敌手A输出文件集合f给挑战者C，挑战者C运行初始化算法(T,BC)←Setup(K,f)，输出区块链索引BC以及密态查找表T给敌手. 敌手A可以向挑战者发起多项式次自适应质询[{ϕ(Wi),fi}]q. 在所有q次质询结束后，敌手输出包含一组关键字的布尔表达式ϕ(W)、一个针对该表达式的错误搜索结果˜Rϕ(W)和针对这一错误结果的证明π. 如果证明可以通过验证算法的验证，即Verify(K,˜Rϕ(W),π)=1，那么实验输出1，否则输出0.
VBSE-BI方案满足不可伪造性，当且仅当对于所有满足多项式时间计算能力的敌手A，使得：Pr[ForgeA(1k)=1]⩽negl(1k)，其中negl(1k)为以1k为输入的可忽略函数.
3. VBSE-BI方案
本节给出VBSE-BI方案的设计思路与具体构建方法. 首先通过构建基于区块链数据存储的增量安全索引结构来实现对密文的搜索以及高效更新，然后设计布尔搜索结果完整性验证方法来实现布尔搜索结果的完整性验证；最后根据设计思路完成方案中每个算法和协议的详细构建.
3.1 设计思路
3.1.1 基于区块链的安全索引构建方法
VBSE-BI的主要搜索结构包含存储于区块链结构中的增量链式安全索引(简称区块链索引BC)以及存储于云服务器的密态查找表T. 令F，G，P为3个伪随机函数，用户U随机选择3个长度k 比特的比特串K1，K2，K3作为伪随机函数F，G，P的密钥. 用户首先在文件集合f=(f1,f2,…,f#f)中提取到关键字信息W=(w1,w2,…,w#W)，构建以关键字为引导的进行组织的#W条虚拟链表(L1,L2,…,L#W)，每个链表都由#fw个节点(N1,N2,…,N#fw)构成，每个节点都存储一个唯一的“文件/关键字”对，所有链表共同构成链式索引结构. 随后，用户将链式索引结构以数据条目的形式上传到区块链中，每个节点存储在BC中的一条交易中. 为了能够将区块链索引中一条虚拟链表中的不同节点进行连接，在每个节点Ni内额外添加指针信息addr(Ni−1)，指向链表内上一个节点Ni−1的交易地址，从而实现整条链表的高效定位与查找. 定义节点Ni的结构为Ni=⟨fi,addr(Ni−1),flag⟩，其中fi为文件的唯一标识， addr(Ni−1)表示链表内上一个节点Ni−1的交易地址，flag为增删标识位. 链表Lw中的所有节点都使用PK3(w)进行异或加密从而对索引的真实索引信息进行隐私保护，其中K3为伪随机函数P的密钥. 除此之外，用户构建查找表T，包含了系统中的所有关键字信息，对于每个关键字w，查找表T中的对应元素以FK1(w)为键，以指向指向区块链索引中链表Lw的末节点地址addr(N#fw)为值，其中K1为伪随机函数F的密钥，addr(N#fw)使用GK2(w)进行异或加密，其中K2是伪随机函数G的密钥.
搜索关键字wi∈W包含的文件时，服务器S使用FK1(wi)作为键来在密态查找表T中定位到到密态地址，使用GK2(wi)来解密得到Lwi的末节点地址明文，并链接到区块链索引BC中的相关交易，最后使用PK3(wi)来解密交易信息，获得文件标识和前一个节点的地址信息，进而在区块链索引BC中提取到链表Lwi中所有节点(N1,N2,…,N#fwi)的信息，得到针对关键字wi的文件标识符集合fwi.
图2为索引结构示意图. 为了更好地说明方案的索引结构间的关系和搜索过程，图2中索引结构均以明文形式阐述. 在区块链结构中，一定数量的新数据条目作为交易的形式封装到一个新的块中，块头包含当前链的最后一个块的哈希值、随机数、交易的Merkle哈希根以及时间戳等信息，块体包含了所有的交易信息，即存储索引BC. 例如，对于关键字w2，在查找表中键w2对应的值为402，即指向了区块链中地址为402的交易. 地址为402的交易信息中存储了一个指向地址为101的交易的指针，地址为101的交易中存储的指针指向了地址0，然后结束遍历. 通过对关键字w2的虚拟链表的遍历，所有包含关键字w2的文件都可以被找到. 上述过程实现搜索正确性的思想是，由于区块链结构对网络中的所有对等点都是可审计的，一旦挖掘出一个块并达成一致意见，就不再在该块中进一步执行修改操作. 因此区块链索引凭借着安全不可篡改的特性， 能防止已经确认的交易记录被更改，能够保证每个得到有效性验证的区块数据和交易记录中的节点信息的完整性，因此其保证了索引存储以及搜索的正确性.
3.1.2 布尔搜索完整性验证方法
为了搜索针对关键字集合W={w1,w2,…,wn}的某个布尔表达式ϕ(W)，服务器S需要通过查找表对每个关键字wi∈W在区块链中定位链表Lwi的末节点N#fwi的地址addr(N#fwi)，并分别在区块链索引中进行搜索，得到结果R = (fw1,fw2,…,fw\# W)后进行针对布尔表达式ϕ(W)的运算. 根据类型不同，布尔运算正确性满足如下性质：
1）交集. 如果I={f1,f2,…,fm}为fw1,fw2,…,fwn正确交集，当且仅当下列2个条件成立：①子集条件. 作为集合的交集，集合I一定为每一个集合fwi的子集，即(I⊆fw1)∩…∩(I⊆fwn)；② 完备性条件. 集合I必须包含集合fw1,fw2,…,fwn的所有共同关键字，即(fw1−I)∩…∩(fwn−I)=fwm.
2）并集. 直观上，U={f1,f2,…,fm}为fw1,fw2,…,fwm正确并集，当且仅当下列2个条件成立：①成员条件. 作为集合的并集，集合U中的任何文件一定包含于某个集合fwi，即∀fk∈U,∃i∈{1,2,…,n}:fk∈fwn；②超集条件. 任何集合fwi一定是集合U的子集，即(U⊇fw1)∧(U⊇fw2)∧…∧(U⊇fwn).
3）差集. 给定集合D和2个集合fwi,fwj，D为fwi,fwj正确差集当且仅当差集条件成立：集合D中的文件包含所有包含关键字wi但不包含关键字wj中的文件，即D=fwi−fwj⇔fwi−(fwi−D)=fwi∩fwj. 如果Iwi∧wj为集合fwi和fwj的交集，即Iwi∧wj=fwi∩fwj，则集合D和Iwi∧wj的并集与集合fwi相等：D∪Iwi∧wj=fwi. 因此，证明D=fwi−fwj等价于证明fwi=D∪Iwi∧wj，即证明fwi为D和Iwi∧wj的并集.
本文设计融合双线性映射累加器和扩展欧几里德算法的集合运算正确性证明方法.
具体来讲，为了证明并集搜索结果I的子集条件，对于所有w∈W，首先用户分别为fw1,fw2,…,fwn计算累加值acc(fwi)，然后便可以为每一个集合fwi生成对应的子集包含证据(I,WI,fwi). 用户利用acc(fwi)和(I,WI,fwi)验证集合I和集合Si之间的子集包含关系了. 除此之外，若集合I是完备的，当且仅当存在多项式q1(s),q2(s),…,qn(s)，使得q1(s)P1(s)+q2(s)P2(s)+…+qn(s)Pn(s)=1，其中
Pi(s)=∏f∈Si−I(s+id(f)). 因此假设I并不是完备的集合，那么在多项式P1(s),P2(s),…,Pn(s)中至少存在一个公因式. 在这种情况下，便不存在多项式q1(s),q2(s),…,qn(s)使得q1(s)P1(s)+q2(s)P2(s)+…+qn(s)Pn(s)=1. 因此如果能找到符合要求的q1(s),q2(s),…,qn(s)，那么就说明P1(s),P2(s),…,Pn(s)中一定不存在公因式.
为了证明并集搜索结果U的成员条件，需要为集合U中的每个文件fj生成针对文件集合fwi的成员证据Mj,i. 验证时，验证成员条件通过验证下列等式是否成立：e(Mj,i,gfjgs)=e(acc(fwi),g). 需要注意的是，对于集合U中的每个文件fj，只有当对于每个集合fwi上述等式都不成立时，才表示元素fj不属于任意集合fwi，此时认为验证失败. 证明超集条件时，需要为fw1,fw2,…,fwn构造超集证据：对于1⩽i⩽n，计算
Pi=∏f∈U−fwi(s+f)， 令S={Si}1⩽i⩽n={gPi}1⩽i⩽n为超集证据. 验证时，通过验证下列等式是否成立，验证
e(Si,acc(fwi))=e(gd∏k=1(s+fk),g)， 其中Si为超集证据S中元素. 如果所有的验证过程都通过，那么就可以认为U是正确的，即的确是由fw1,fw2,…,fwn通过并集运算得到的结果. 由于差集证明方法可规约为并集证明，因此不再过多赘述.
3.1.3 安全索引的动态更新机制
用户U可以随时在方案中添加或删除包含Wf=(w1,w2,…,wn)关键字的文件f. 对于Wf中的任意关键字wi，首先用户U和服务器S交互获取密态查找表T中与wi对应的链表Lwi的末节点N#fwi在区块链索引BC中的交易地址addr(N#fwi)以及相关累加值acc(fwi)，并且利用此地址addr(N#fwi)更新链表Lwi——增加文件f对应的新的末节点N′#fwi. 之后用户将N′#fwi作为交易的形式更新到区块链索引BC中，得到N′#fwi的交易地址addr(N′#fwi). 除此之外，用户需要利用原有fwi对应的累加值acc(fwi)和更新的文件f计算新的累加值acc(fwi)′. 最后用户将addr(N′#fwi)以及累加值acc(fwi)′更新到查找表中wi键对应的值中，至此完成安全索引结构的更新. 由于区块链结构为增量数据结构，且具有防篡改性，因此无法修改或删除已有交易值信息，针对上述情况，将添加和删除文件过程均利用添加节点至区块链来进行，通过在每个节点内区分标flag标志位的值来区分添加和删除操作，flag = 1则表示f为增加的文件，flag = 0则表示f为删除的文件. 上述动态更新过程中服务器S可以在无需对查找表进行解密的情况下，使用用户发送的更新令牌中的密文信息直接对密态查找表直接进行更新.
3.2 详细算法及协议
令F:{0,1}k×{0,1}∗→{0,1}k，G:{0,1}k×{0,1}∗→{0,1}∗，P:{0,1}k×{0,1}∗→{0,1}k 为3个固定长度伪随机函数，∑BC(Init,Put,Get)为区块链数据存储结构，具体的算法及协议描述如下：
3.2.1 密钥生成算法
(K,PP)←KeyGen(1k)：进行用户端密钥的生成. 主要步骤如下：
1）随机选择3个长度为k比特的比特串K1,K2,K3.
2）选择双线性配对的参数(p,G,G,e,g).
3）选择s∈Z∗p作为一个随机的秘密陷门.
4）计算(g,gs,gs2,…gsq)作为公开参数.
5）输出密钥K=(K1,K2,K3,s)，并输出公开参数PP=(g,gs,gs2,…,gsq).
3.2.2 初始化算法
(T,BC)←Setup(K,f)：用户U初始化索引结构. 主要步骤如下：
1）初始化长度为#W的查找表T.
2）调用∑BC·Init(k)算法，输入安全参数k，初始化区块链索引BC.
3）对于每个关键字w∈W：
① 构建一个由#fw个节点(N1,N2…,N#fw)构成的链表L，节点的结构定义为
Ni=⟨fi,addr(Ni−1),flag⟩⊕PK2(w)， 其中fi为文件标识，addr(Ni−1)表示节点Ni−1的交易地址，addr(N1)=⊥，flag为增删标识位；
② 对于链表Lw的所有节点(N1,N2,…,N#fw)，依次调用∑BC·Put(Ni)算法，将节点Ni作为交易值封装进区块链索引BC的区块上并获取交易地址addr(Ni)，最终返回addr(N#fw).
4）对于每个关键字w∈W：
① 计算fw的累加值，即
acc(fw)=g∏f∈fw(s+id(f)). ② 输出区块链索引BC和密态查找表T共同作为安全索引结构，即
T[FK1(w)]=⟨θ1,θ2⟩=⟨addr(N#fw)⊕GK3(w),acc(fw)⟩. 3.2.3 搜索协议
(Rϕ(W),π;⊥)←Search(U(K,ϕ(W));S(T,BC))：用户U和云服务器S交互执行针对关键字集合W={w1,…,wn}的布尔表达式ϕ(W)的搜索过程，服务器针对搜索结果生成相应布尔运算证明. 主要步骤如下：
1）用户U.
① 针对每个搜索关键字wi∈W：生成搜索令牌τi=(τi,1,τi,2,τi,3)=(FK1(wi),GK2(wi),PK3(wi)).
② 发送搜索令牌τs=(ϕ(W),{τi}i∈W)给服务器S.
2）服务器S.
对于每个关键字wi∈W，执行以下步骤：
① 使用τi,1作为键检索密态查找表T中的值θ1←T[τi,1].
② 计算链表头节点在索引BC中的交易地址α1←θ1⊕τi,2.
③ 在BC中获取地址addr(N#fwi)的交易值tx1←∑BC·Get(addrN#fw).
④ 计算a1||a2||a3←tx1⊕τi,3.
⑤ 如果a3=1，则更新Rwi←Rwi∪{a1}，如果a3=0，则更新Rwi←Rwi/{a1}.
⑥ 如果a2≠⊥，则重复过程③④，继续查找BC中地址为a2的交易值，直到a2=⊥. 对于所有关键字 wi∈W搜索完毕后，得到搜索结果R=(Rw1,Rw2,…,Rw#W).
对于布尔表达式ϕ(W)，云服务器S进行如下步骤完整集合运算的证明：
1）交集证明.
步骤1. 计算交集RI=Rw1∩Rw2∩…∩Rwn，其中RI={f1,f2,…,fm}.
步骤2. 对于每个集合Rwi，1⩽i⩽n，执行如下：
①计算多项式Pi=∏f∈Rwi−RI(s+f).
②计算集合RI对于Rwi的子集包含证据IRI,Rwi=gPi.
③计算子集证据I={Ii}={II,fwi}1⩽i⩽n.
④使用公开参数(g,gs,…,gsq)来计算gPi的值.
⑤给定{P1,P2,…,Pn}，使用扩展欧几里德算法找到多项式{q1,q2,…,qn}，满足q1P1+q2P2+…+qnPn=1. 整合C={gq1,gq2,…,gqn}为完备性证据.
步骤3. 整合交集证据πI={I,C}.
2）并集证明.
步骤1. 计算并集RU=Rw1∪Rw2∪…∪Rwn，其中RU={f1,f2,…,fm}.
步骤2. 对于每个集合Rwi，1⩽i⩽n，执行如下：
①对于RU中每个文件fk，计算多项式
Fk,i=∏f∈Rwi−fk(s+f). ②使用公开参数(g,gs,…,gsq)计算Mk,i=gFk,i.
步骤3. 计算多项式Pi=∏f∈RU−Ri(s+f).
步骤4. 计算成员证据M={Mi,j}1⩽i⩽n,1⩽k⩽m，超集证据S={Si}1⩽i⩽n={gPi}1⩽i⩽n.
步骤5. 整合并集证据πU={M,S}.
3）差集证明.
设差集搜索令牌τs=(D(wi,wj),τi,τj) ，计算差集RD=Rwi−Rwj，其中RD={f1,f2,…,fm}. 之后服务器按照如下方式计算证据πD={M,S}以完成证明：
步骤1. 对于RD中每个文件fk，1⩽k⩽m：
①计算多项式
F1=∏f∈RD−fk(f+s)，F2,1=∏f∈Rwi−fk(f+s)，以及F2,2=∏f∈Rwj−fk(f+s).
②使用公开参数(g,gs,…,gsq)来计算
M={M1,M2,M3}， 其中M1=gF1，M2=gF2,1，M3=gF2,2.
步骤2. 计算交集Iwi∧wj=Rwi∩Rwj.
步骤3. 计算acc(Iwi∧wj)=g∏f∈Iwi∧wj(f+s).
步骤4. 对于集合RD和Iwi∧wj，计算
P1=∏f∈Rwi−RD(f+s)， P2=∏f∈Rwi−Iwi∧wj(f+s)， P3=∏f∈RD(f+s), P4=∏f∈Iwi∧wj(f+s). 步骤5. 计算超集证据：
S=(S1,S2,S3,S4)=(gP1,gP2,gP3,gP4). 步骤6. 整合差集证据πD={M,S}.
随后，云服务器S将搜索结果集合Rϕ(W)和针对该集合的证明π返回给用户U.
3.2.4 验证算法
b←Verify(K,Rϕ(W),π)：用户U验证布尔搜索结果的完整性. 主要步骤如下：
1）交集验证.
步骤1. 对于τs中的每个τi，1⩽i⩽n，使用θ2通过以下等式来验证子集条件：
e(gm∏k=1(s+fk),Si)=e(θ2,g)， 其中(f1,f2,…,fm)为交集中的元素，Si=gPi为子集证据S中元素.
步骤2. 通过以下等式来验证完备性条件：
m∏i=1e(Si,Ci)=e(g,g)， 其中Si = gPi为子集证据S中元素，Ci=gqi为完备性证据C中对应元素.
步骤3. 如果上述验证过程都通过，则输出1代表验证成功；否则输出0代表验证失败.
2）并集验证.
步骤1. 对于每个文件fk∈U，1⩽k⩽m，使用θ2通过以下等式来验证验证成员条件：
e(Mk,i,gfkgs)=e(θ2,g)， 其中Mk,i = gFk,i为M中的元素.
步骤2. 对于每个集合Rwi,1⩽i⩽n，通过以下等式来验证超集条件：
e(Si,acc(fwi))=e(gd∏k=1(s+fk),g)， 其中Si为超集证据S中元素.
只有RU中的存在文件对于任意集合fwi的成员条件均不成立时，认为验证失败.
步骤3. 如果上述验证过程都通过，则输出1代表验证成功；否则输出0代表验证失败.
3）差集验证.
步骤1. 对于每个文件标识fk∈Rwi,1⩽k⩽m，通过以下等式来验证成员条件：
e(M1,gfkgs)=e(acc(RD),g)，e(M2,gfkgs)=e(acc(Rwi),g)，e(M3,gfkgs)=e(acc(Rwj),g)， 其中(M1,M2,M3)=(gF1,gF2,1,gF2,2)为成员证据M中的元素.
步骤2. 对于集合R和Iwi∧wj，通过以下等式来验证超集条件：
e(S1,S3)=e(gd∏k=1(s+fk),g)， e(S2,S4)=e(gd∏k=1(s+fk),g)， 其中(S1,S2,S3,S4)=(gP1,gP2,gP3,gP4)为超集证据S中元素.
步骤3. 当步骤1中成员条件3个等式都不成立时，判定验证失败. 如果上述验证过程都通过，则输出1代表验证成功；否则输出0代表验证失败.
3.2.5 更新协议
(⊥;T′;BC′)←Update(U(K,f);S(T);BC)：用于用户U添加或删除包含Wf=(w1,w2,…,wd)关键字的文件f时索引结构的更新. 主要步骤如下：
用户U计算(FkF(w1),FkF(w2),…,FkF(wd))发送至服务器S.
服务器S对于每一个tju，在查找表中获取T[tju]，将(θ1,θ2,…,θd)按序发送回用户U.
1）用户U对于每一个θi，执行以下步骤：
步骤1. 计算addrN#fwi−1=θi⊕GkG(wi).
步骤2. 如添加文件，计算
N#fwi=⟨f,addrN#fwi−1,1⟩⊕PKP(wi)， 如删除文件，计算
N#fwi=⟨f,addrN#fwi−1,0⟩⊕PKP(wi). 步骤3. 调用∑BC·Put(N#fwi)，将N#fwi作为交易值封装进区块链索引BC的区块上并获取交易地址addr(N#fwi).
步骤4. 计算更新后fwi对应的相关累加值
τ3u,i←θ2s+f. 步骤5. 计算τ2i←GKG(wi)⊕addr(N#fwi).
步骤6. 如果为添加操作，计算τ3i←θ2s+f.如果为删除操作，计算τ3u,i←θ21/(s+f).
步骤7. 计算τi=(τ1i,τ2i,τ3i).
步骤8. 对于所有θi执行完步骤1～6后，将τu=(τ1,τ2,…,τd)作为更新令牌发送给服务器.
2）服务器S对于每个τi，执行以下步骤：
步骤1. 获取(θ1,θ2)←T[τi,1].
步骤2. 使用τ2u,i对θ1进行更新θ′1←τ1u,i.
步骤3. 使用τ3u,i对θ2进行更新θ′2←τ3u,i.
步骤4. 更新查找表T：(θ1′,θ2′)←T[τi,1].
步骤5. 输出更新后的索引结构T′;BC′.
4. 安全性分析
4.1 动态IND-CKA2安全性
首先定义3个泄露函数L1(T,I)，L2(f,ϕ(W))，L3(f)来描述初始化、搜索和更新文件执行期间向服务器泄露的信息. 接下来的定理表明，给定以上泄露函数的情况下，VBSE-BI方案在随机预言模型下满足动态自适应CKA安全性.
定理1. 若F,G,P为伪随机函数，则VBSE-BI方案在随机预言模型下针对自适应选择关键字攻击是(L1,L2,L3)安全的，即满足动态IND-CKA2安全性.
证明. 在IdealA,S(k)中，通过L1的信息，模拟器可以确定可以获知查找表T的大小#T、字典大小集合#W以及集合[id(w)]w∈W. 随后，它可以使用随机值来构建搜索结构，并输出作为模拟值(˜T,~BC). 由于真实索引是使用伪随机函数F,G,P产生的，而模拟索引是由随机比特填充的，因此，如果函数F,G,P的伪随机性成立，则对于所有PPT敌手A，无法在多项式时间内区分真实索引和模拟索引.
为了响应敌手的质询，模拟器需要使用L2和L3来构建模拟搜索令牌和更新令牌，使其与真实令牌是无法区分的. 具体来说，泄露函数L2(δ,f,ϕ(W))向服务器泄露了所有关键字w∈W的标识id(w)，以及每个关键字标识id(w)和包含关键字w的文件标识之间的关联. 因为˜τs=(˜τ1,˜τ2,…,˜τn)，˜τi=(γ(id(wi))，T[γ(id(wi))]⊕iT(id(wi)),Kid(wi))，而˜τs=(˜τ1,˜τ2,…,˜τn)，τi=(FK1(wi),GK2(wi), PK3(wi))，根据函数F,G,P的伪随机性，对于所有概率多项式计算能力敌手A，不能区分搜索令牌和模拟搜索令牌τs和˜τs. 同理，泄露函数L3(f)泄露了更新协议中更新文件所包含的关键字的标识符集合. [id(w)]w∈Wf. 以及关键字w是否是一个新的关键字[apprs(w)]w∈Wf，其中apprs(w)为一个1 b的标志位，值为1表示关键字w已经存在于索引中；值为0表示w是一个新关键字. 因此，基于函数F,G,P的伪随机性，敌手同样不能区分更新令牌τu和模拟更新令牌.
综上所述，对于所有PPT敌手A来说，实验RealA(k)与IdealA,S(k)的输出是一致的，除了以可忽略的概率negl(k)，即
|Pr[RealA(k)=1]−Pr[IdealA,S(k)=1]|⩽negl(k). 因此，VBSE-BI方案在在随机预言模型下满足动态IND-CKA2安全性. 证毕.
4.2 不可伪造性
VBSE-BI方案的不可伪造性指对于所有概率多项式计算能力敌手A，针对伪造的布尔搜索结果，无法生成正确有效的证据.
定理2. 如果双线性q-SDH假设成立，那么VBSE-BI方案满足不可伪造性.
证明. 如果存在一个概率多项式计算能力敌手A使得实验ForgeA(1k)的输出为1，那么就存在一个模拟器Sim，有能力攻破双线性q-SDH假设. 证明主要针对交集布尔搜索场景的不可伪造性，并集以及差集证明方法与交集不可伪造性证明方法过程类似，不再赘述.
假设A在执行针对集合W的搜索算法Search后，输出一个文件标识符集合˜Rϕ(W)≠Rϕ(W)和一个有效的证明π. 这意味着该证明π通过了验证算法Verify中的所有验证，即敌手A成功的进行了伪造. 证明π={S,C}中的伪造可以分为伪造S和伪造C这2种情况. 通过以下分析，我们能够得出，模拟器Sim能够通过伪造S和伪造C来攻破双线性q-SDH假设.
给定模拟器Sim双线性q-SDH实例：(p,G,G,e,g)以及一个(q+1)元组(g,gs,…,gsq)，模拟器Sim和敌手A在实验VeriA(1k)中交互.
首先，由于模拟器Sim不知道给定实例中的s值，他需要对实验VeriA(1k)进行修改，重新构造和s值相关的算法：
1）KeyGen算法中，模拟器Sim在不知情s的情况下直接使用(g,gs,gs2,…,gsq)作为公开参数并发送给敌手A.
2）Setup算法中，模拟器Sim利用(g,gs,gs2,…,gsq)计算acc(fwi)=g∏f∈fw(s+f). 为了模拟更新令牌，模拟器Sim需要构造一个额外辅助结构N，为每个acc(fwi)存储一个多项式nw=∏f∈fw(s+f).
3）Update协议中，模拟器Sim不能直接生成更新令牌τu，首先找到结构N中与θi,2相等的多项式ni，然后利用(g,gs,gs2,…,gsq)计算gni(s+f)，生成新的θ2=gni(s+f).
模拟器Sim将和s值相关的数值通过上述方式计算，然而由于修改的实验中算法的输出和实验VeriA(1k)算法的输出是不可区分的，所以在敌手A的视角中，新计算的数值仍然有效. 那么如果敌手A赢得了游戏，那么意味着敌手A攻破了双线性q-SDH假设，即成功伪造了伪造子集证据S或者成功伪造了完备性证据C.
1）伪造子集证据S：敌手输出错误的搜索结果I′={f1,f2,…,fm}和伪造的子集证据Si=⌢gPi. 令Si={f1,f2,…,fq}为包含关键字wi的文件标识符集合，如果I′⊄，那么一定存在某个1 \leqslant j \leqslant m，使得{f_j} \notin {S_i}. 通过验证意味着
e( {{g^{\prod\limits_{f \in I'} {(s + f)} }},{\mathcal{S}}} ) = e\left( {{g^{(s + {f_1})(s + {f_2}) … (s + {f_q})}},g} \right) \text{，} 因为{f_j} \notin {S_i}，因此(s + {f_j})并不能整除 (s + {f_1}) (s + {f_2}) … (s + {f_q}) . 所以存在一个次为q - 1的多项式Q(s)和一个常数c \ne 0，使得 (s + {f_1})(s + {f_2}) … (s + {f_q}) = Q(s)(s + {f_j}) + c . 因此
e{( {g,\stackrel{\frown}{g}^{{P_i}}} )^{(s + {f_j})\prod\limits_{f \in I' - {f_j}} {(s + f)} }} = e{\left( {g,g} \right)^{Q(s)(s + {f_j}) + c}} 经过变形后，最终可以得到
e{\left( {g,g} \right)^{\frac{1}{{s + {f_j}}}}} = {\left( {e{{( {g,{\stackrel{\frown}{g}^{{P_i}}}} )}^{\prod\limits_{f \in I' - {f_j}} {(s + f)} }}e{{\left( {g,g} \right)}^{ - Q(s)}}} \right)^{1/c}} \text{，} 这说明模拟器\mathcal{S}im可以借在多项式时间内解决双线性q-SDH问题的一个实例. 这违反了双线性q-SDH假设.
2）伪造完备性证据 \mathcal{C} ：这种情况下，敌手输出错误的交集搜索 {\widetilde R_{\phi ({\mathcal{W}})}} = \{ {f_1},{f_2}, … ,{f_m}\} 和一个完备性证据 \stackrel{\frown}{\cal C}. 因为 {\widetilde R_{\phi ({\mathcal{W}})}} 是 R 的真子集，那么多项式{P_1},{P_2}, … ,{P_n}至少存在一个公因式. 令(s + f)为{P_1},{P_2}, … ,{P_n}的一个公因式，其中f \notin I'. 通过验证算法意味着 \prod\limits_{i = 1}^m {e( {\cal S},\stackrel{\frown}{\cal C} )} = e\left( {g,g} \right)成立. 通过计算{g^{{{P'}_i}}} = {({g^{{P_i}}})^{1/(s + f)}}，将(s + f)从每个{P_i}中提取出来，即
\begin{split} \prod\limits_{i = 1}^n {e\left( {{g^{{P_i}}},{g^{{q_i}}}} \right)} =\;& \prod\limits_{i = 1}^n {e( {{{( {{g^{{{P'}_i}}}} )}^{s + f}},{g^{{q_i}}}} )}= \\ &{\left( {\prod\limits_{i = 1}^n {e\left( {{g^{{{P'}_i}}},{g^{{q_i}}}} \right)} } \right)^{s + f}} =e(g,g) \end{split} 因此模拟器\mathcal{S}im可以很容易的计算 e{\left( {g,g} \right)^{1/(s + f)}} = \prod\limits_{i = 1}^n {e\left( {{g^{{{P'}_i}}},{g^{{q_i}}}} \right)} ，从而找到双线性q-SDH问题的一个实例的解，这同样违反了双线性q-SDH假设.
综上所述，如果敌手可以伪造出一个有效的证据，那么就存在一个模拟器\mathcal{S}im，可以攻破哈希函数{H_3}的抗碰撞性和双线性q-SDH假设的至少一个. 因此，对于所有概率多项式计算能力敌手\mathcal{A}来说，赢得实验 Ver{i_{\mathcal{A}}}({1^k}) 概率为：
Pr{\text{[}}Forg{e_{\mathcal{A}}}({1^k}) = {\text{1}}] \leqslant negl({1^k}) \text{，} 其中 negl({1^k}) 是一个以安全参数 {1^k} 为输入的可忽略函数. 因此VBSE-BI方案具有不可伪造性.
5. 性能分析与实验
本节主要分析提出VBSE-BI方案的性能，. 首先从理论层面对方案的各个阶段的性能进行综合对比评估，之后通过设计实验方案的原型系统，来对不同阶段的性能进行测试，得到实验结果.
5.1 代价分析
针对模型构建过程中的存储代价、计算代价以及通信代价3个维度分析方案性能. 设N表示关键字集合的大小，M为文件总个数，n为布尔搜索请求中包含的关键字个数，m为搜索结果中文件个数，d为更新文件包含的关键字个数. 方案的代价分析如表2所示.
表 2 代价分析Table 2. Cost Analysis复杂度类别 VBSE-BI方案 文献[23]方案 用户端 服务器端 用户端 服务器端 {\text{Sto}}{{\text{r}}_{{\text{Index}}}} {\mathcal{O}}(1) {\mathcal{O}}(N) {\mathcal{O}}(1) {\mathcal{O}}(NM){\text{ + }}{\mathcal{O}}(N){\text{ + }}{\mathcal{O}}(M) {\text{Com}}{{\text{p}}_{{\text{Search}}}} {\mathcal{O}}(n) {\mathcal{O}}(mn) {\mathcal{O}}(n) {\mathcal{O}}(n + mn) {\text{Com}}{{\text{p}}_{{\text{ProveI}}}} - {\mathcal{O}}(N{\log ^2}N\log \log N) - {\mathcal{O}}(N{\log ^2}N\log \log N) {\text{Com}}{{\text{p}}_{{\text{ProveU}}}} - {\mathcal{O}}(N\log N) - - {\text{Com}}{{\text{p}}_{{\text{ProveD}}}} - {\mathcal{O}}(N\log N) - - {\text{Com}}{{\text{m}}_{{\text{Search}}}} {\mathcal{O}}(n + m) {\mathcal{O}}(n + m) {\mathcal{O}}(n) {\mathcal{O}}(n\log n + m) {\text{Com}}{{\text{p}}_{{\text{Verify}}}} {\mathcal{O}}(n + m) - {\mathcal{O}}(n\log n + m) - {\text{Com}}{{\text{p}}_{{\text{Update}}}} {\mathcal{O}}(d) {\mathcal{O}}(d) {\mathcal{O}}(\log N + d) {\mathcal{O}}(d) {\text{Com}}{{\text{m}}_{{\text{Update}}}} {\mathcal{O}}(d) {\mathcal{O}}(d) {\mathcal{O}}(d) {\mathcal{O}}(d) 注：{\text{Sto}}{{\text{r}}_{{\text{Index}}}}—存储空间复杂度；{\text{Com}}{{\text{p}}_{{\text{Search}}}}—搜索计算复杂度；{\text{Com}}{{\text{p}}_{{\text{ProveI}}}}—交集证明计算复杂度；{\text{Com}}{{\text{p}}_{{\text{ProveU}}}}—并集证明计算复杂度；{\text{Com}}{{\text{p}}_{{\text{ProveD}}}}—差集证明计算复杂度；{\text{Com}}{{\text{p}}_{{\text{Verify}}}}—验证计算复杂度；{\text{Com}}{{\text{m}}_{{\text{Search}}}}—搜索通信复杂度；{\text{Com}}{{\text{p}}_{{\text{Update}}}}—更新计算复杂度；{\text{Com}}{{\text{m}}_{{\text{Update}}}}—更新通信复杂度；-：无复杂度体现. 存储代价主要考虑云服务器的安全索引存储代价，设T为长度为N的查找表，索引的空间复杂度为\mathcal{O}(N). 在计算代价方面，构建搜索令牌的计算代价与搜索关键字个数有关，时间复杂度为\mathcal{O}(n). 服务器对搜索令牌进行搜索操作时的计算复杂度为\mathcal{O}(mn)，进行交集运算的渐近运行时间为\mathcal{O}(N{\log ^2}N\log \log N)，并集和差集云服务器的渐近运行时间复杂度为\mathcal{O}(N\log N)，用户端完成验证操作的渐近运行时间复杂度为\mathcal{O}(n) + \mathcal{O}(m). 搜索通信代价主要由搜索关键字个数以及搜索结果中文件个数决定. 当用户想要搜索n个关键字的布尔集合时，和服务器交互一次，发送搜索令牌的通信复杂度为\mathcal{O}(n)，云服务器返回搜索结果的通信复杂度为\mathcal{O}(m)，因此通信的数据规模为的通信复杂度为\mathcal{O}(n + m). 与同类型的文献[23]方案相比，本方案在支持更丰富的布尔查询语句的同时，降低了服务器端索引的存储代价以及搜索、验证以及更新的计算代价.
5.2 实验分析
本文对提出的方案进行了编程实现，然后通过对算法的性能测试来分析方案在实际应用中的表现. 方案部署一个远程服务器来模拟云服务器，处理器为Intel Core i7-
2600 Quad-Core Processor 3.4 GHz，内存为8 GB；同时部署多台主机模拟用户端，每台主机模拟为一个和云服务器交互的用户. 此外，方案利用Ethereum仿真平台Ropsten Testnets模拟区块链存储平台，具体来说，利用Ethereum的web3 API包[26]来构建区块链索引，调用Metamask[27]创建本地钱包来实例化 {\sum }_{BC}{}_{·}Init\text{()} 算法，调用signTransaction函数实例化 {\sum }_{BC}{}_{·}Put\text{()} 算法来存储链式索引结构中的节点信息；调用sendRawTransaction函数接受已签名的交易同时输出交易的地址；搜索时，调用getTransaction函数来实例化 {\sum }_{BC}{}_{·}Get\text{()} 算法将交易的地址作为输入并输出关联的交易内容，然后读取数据字段以检索链式索引中的节点信息. 方案调用OpenSSL_SHA256-HMAC[28]算法实现伪随机函数F，G，P. 使用Enron邮件数据集[29]来进行性能的评估，从邮件集合中随机选择1 000个文件作为测试用的文件集.根据系统实现的功能，测试系统执行不同操作时的云服务器端和用户端的计算开销及通信开销，其中服务器计算开销主要测试的内容包括搜索时间、生成证明时间，用户的计算开销主要测试验证时间，通信开销主要测试云服务器返回搜索结果的数据量. 实验中每个数据均为实验重复50 次并取平均值后得到的结果.
1）计算开销. 计算开销可以分为区块链索引搜索开销、服务器本地证明开销以及用户端本地验证开销，如图3所示. 当搜索关键字数量为（2，4，6，8，10）时，搜索区块链索引的时间开销与关键字个数大致呈线性关系（1.817～5.755 s）. 证明过程耗时较搜索过程大，原因为包含较多指数运算和双线性配对运算，尽管关键字数量变化，时间开销相对稳定，维持在6.1～6.8 s之间，与理论分析一致. 由于这些计算的效率与所选用的曲线参数和配对算法有很大关系，通过多线程计算和预先计算，可以显著降低证明阶段的计算时间. 因此随着参数和算法的不断优化，其效率可以进一步得到提升. 此外，服务端的算法还可以进行一些实现方面的优化，从而可以大大降低证明阶段所花费的时间. 例如对集合证据使用多线程来计算，以及使用预先计算好的{P_i}和{g^{{P_i}}}等. 用户计算开销主要测试在不同数目关键字情况下进行搜索时用户完成验证操作的时间，开销与关键字个数无关，维持在1.0～1.8 s之间. 验证过程中耗时最多的操作为双线性配对过程，与服务器端的搜索和证明时间相比，用户端计算开销为服务器端计算开销的9.98%～14.03%. 因此，VBSE-BI方案在用户端的计算开销相对较低，验证操作高效快速，极大地减少了用户端的计算负担. 这使得方案在实际应用中具有较好的用户体验，特别是在资源受限的移动设备上，表现尤为突出.
![]()
图 3 计算开销与关键字数量之间的关系Figure 3. The relationship between computational cost and the number of keywords2）通信开销. 通信开销主要包含搜索结果的数据量和额外证明的数据量. 图4表明了通信开销与搜索时布尔表达式中的关键字数量之间的关系. 当搜索时使用的关键字数量为（2，4，6，8，10）递增时，通信开销中搜索结果的数据量从758 B减少至201 B这是因为符合多个关键字布尔表达式的搜索结果减少，传输的数据量也相应减少. 证明数据量从502B增加至1 896 B，因为更多的关键字需要更多的证明数据来保证搜索结果的正确性和完整性，占总数据量的36.97%～76.54%. 因此，额外证明的数据量是影响通信开销的主要因素，与理论分析一致. 因此，对于频繁查询的关键字，预先生成并存储其证明数据，减少实时计算和传输的开销，可以显著减少VBSE-BI方案中的通信开销，提高整体性能. 特别是在处理较多关键字的搜索时，通过优化证明算法和减少冗余数据，可以有效地控制通信开销的增长，从而提高方案在实际应用中的效率和可扩展性.
![]()
图 4 通信开销与关键字数量之间的关系Figure 4. The relationship between communication cost and the number of keywords6. 总 结
本文提出一种基于区块链索引的可验证布尔搜索加密方案. 设计基于区块链的索引构建算法和索引动态更新算法，并利用可证安全的对称加密和同态加密机制对索引进行加密，实现多关键字布尔搜索. 针对布尔搜索的完整性验证需求，给出布尔搜索结果不可伪造性定义，并提出基于双线性映射累加器和扩展欧几里德算法的布尔运算完整性验证算法. 安全性分析表明，本方案在随机预言模型下能够抵抗动态选择关键字攻击，并且在双线性阶强Diffie-Hellman 假设下满足不可伪造性. 性能分析表明，本方案有效地降低了搜索时的通信代价以及用户端计算复杂度. 本方案提升可搜索加密的可用性和确保用户享受的合法权益不受损害具有重要意义. 本文搜索协议在进行搜索结果证明时的计算代价具有提升空间，因此在未来的研究中重点关注此方面效率的提高. 除此之外，未来考虑使方案满足有隐私保护需求的更多密文搜索场景，例如基于兴趣的推荐服务以及云边协同隐私保护查询等.
作者贡献声明：李宇溪负责模型设计，方案设计，算法设计，方案分析，论文撰写及修改；陈晶晶负责安全性分析，实验环境部署，论文撰写及修改；周福才负责模型设计，技术路线可行性分析；徐剑负责理论基础，整体思路确定；纪东负责实验分析，论文修改.
-
![]()
图 1 不同差分隐私数据处理框架对比
Figure 1. Comparison of framework for different differential privacy data processing
攻击者 数据构建者 攻击目标 辨别信息 攻击者1 {D}'=D-(x,y) 最终模型 点(x,y)在最终模型上的的损失函数值 攻击者2 利用影子模型梯度生成对抗样本 最终模型 攻击者3 利用影子模型梯度生成对抗样本 所有中间模型 点(x,y)在中间模型的损失函数值 攻击者4 构建投毒点 特殊数据点 攻击者5 在模型参数中加入水印信息 中间模型的所有参数 模型参数的距离 攻击者6 构建有毒数据集 模型梯度 
下载: 导出CSV
攻击者 数据构建者 辨别者 黑盒 白盒 攻击者1 无处理 黑盒辨别者1 白盒辨别方法 攻击者2 利用FSGM[39]图像梯度 黑盒辨别者2 白盒辨别方法 攻击者3 生成大梯度值 {\boldsymbol{g}}_{1}=\nabla f({x}_{1},{\boldsymbol{\theta }}_{t}) ; {\boldsymbol{g}}_{2}=\nabla f({x}_{1},{\boldsymbol{\theta }}_{t}') {\boldsymbol{\theta }}_{t}'={\boldsymbol{\theta }}_{t}+\alpha \nabla f\left({x}_{1};{\boldsymbol{\theta }}_{t}\right) 黑盒辨别者2 白盒辨别方法 攻击者4 {\boldsymbol{g}}_{1}=\nabla f({x}_{1},{\boldsymbol{\theta }}_{t}){;\boldsymbol{g}}_{2}=-{\boldsymbol{g}}_{1} 黑盒辨别者2 白盒辨别方法 攻击者5 {\boldsymbol{g}}_{1}=\nabla f\left({x}_{1},\tilde{{\boldsymbol{\theta }}_{t}}\right) ; {\boldsymbol{g}}_{2}=-{\boldsymbol{g}}_{1} 黑盒辨别者2 白盒辨别方法 攻击者6 {\boldsymbol{g}}_{1}=\left(\lambda ,\lambda ,… ,\lambda \right);{\boldsymbol{g}}_{2}=-{\boldsymbol{g}}_{1} 黑盒辨别者3 白盒辨别方法
下载: 导出CSV
下载: 导出CSV
表 7 隐私审计的结果量化方法小结
Table 7 7 Summary of Methods for Quantifying of Privacy Auditing
类别 方法 审计对象 优点 缺点 基于差分隐私变体的量化 基于f-DP的量化 DP-SGD 审计所得经验隐私下界严格 审计构建过程复杂 基于LiDP的量化 DP-SGD 所需样本数量少 加入的告密点较多 基于RKRDP的量化 高斯机制 适用于高维数据 仅能审计高斯机制 基于Renyi散度的量化 PID框架方法 审计所需训练模型数量少 仅针对于隐私预测接算法 基于贝叶斯的量化 基于差分可辨的量化 DP-SGD 审计所得经验 \mathrm{隐}\mathrm{私}\mathrm{下}\mathrm{界} 最严格 中间结果空间代价大 基于贝叶斯变量的量化 DP-SGD 所需样本数量最少 需要选择数据点进行审计
下载: 导出CSV
表 8 隐私审计方法分析
Table 8 8 Analysis of Privacy Auditing Methods
方法 文献来源 应用场景 审计对象 数据集 训练模型 代码 开源 可用性 Jagielski等人[30] 2020NeurlPS CML DP-SGD FMNIST；P100 LR; FNN 是 可运行 Lu等人[31] 2022NeurlPS CML LR；NB；RF；DP-SGD Iris；FMNIST等 SmallCNN 是 可完整运行 Nasr等人[36] 2021SP CML DP-SGD MNIST；P100等 CNN 否 ― Matsumoto等人[37] 2022Arxiv DDC LDP-SGD MNIST；SVHN等 CNN 否 — Arcolezi等人[40] 2023TPDP DDC 8种频数估计算法 — — 否 — Tramer等人[6] 2022Arxiv CML DP-SGD MNIST CNN 否 — CANIFE[46] 2023ICLR DFL DP-FedAvg CelebA ResNet18 是 需手动调大量参数文件 Sent140等 2-layerLSTM Steinke等人[47] 2023NeurlPS CML DP-SGD CIFAR-10 WideResNet 否 — one_shot_eps[48] 2023Arxiv DFL DP-FedSGD word prediction data LSTM 是 需调整代码 Nasr等人[49] 2023USENIX CML DP-SGD CIFAR-10；P100 WRN-16;ConvNet 否 — Pillutla等人[28] 2023NeurlPS CML DP-SGD FMNIST；P100 MLP等 否 — Domingo-Enrich等人[29] 2023Arxiv CML DP-SGD 生成数据 — 否 — Chadha等人[50] 2024Arxiv CML PDI框架方法 MNIST；SST2等 ViT-L/16等 否 — Bernau等人[58] 2021PVLDB CML DP-SGD MNIST；Adult等 NN 是 缺少函数 Zanella等人[61] 2023PLMR CML DP-SGD CIFAR-10；SST2 CNN 否 — 注：―对应部分为空缺.
下载: 导出CSV
表 9 实验数据集
Table 9 9 Datasets of Experiments
数据集 维度 训练集 测试集 标签数 FMNIST 28 \times 28 60 000 10 000 10 CIFAR10 32 \times 32 \times 3 50 000 10 000 10
下载: 导出CSV
-
[1] Archer D W, Pigem B B, Bogdanov D, et al. UN handbook on privacy-preserving computation techniques[J]. arXiv preprint, arXiv: 2301.06167, 2023
[2] Dwork C. Differential privacy: A survey of results [C/OL] //Proc of the 5th Int Conf on Theory and Applications of Models of Computation, Berlin: Springer , 2008[2024-01-24]. https://web.cs.ucdavis.edu/~franklin/ecs289/2010/dwork_2008.pdf
[3] Dwork C, Lei J. Differential privacy and robust statistics[C]//Proc of the 41st Annual ACM Symp on Theory of Computing. New York: ACM, 2009. 371–380
[4] Smith A. Privacy-preserving statistical estimation with optimal convergence rates[C]//Proc of the 43rd Annual ACM Symp on Theory of Computing. New York: ACM, 2011: 813−822
[5] Stevens T, Ngong I C, Darais D, et al. Backpropagation clipping for deep learning with differential privacy[J]. arXiv preprint, arXiv: 2202.05089, 2022
[6] Tramer F, Terzis A, Steinke T, et al. Debugging differential privacy: A case study for privacy auditing[J]. arXiv preprint, arXiv: 2202.12219, 2022
[7] Baldoni R, Coppa E, D’elia D C, et al. A survey of symbolic execution techniques[J]. ACM Computing Surveys (CSUR), 2018, 51(3): 1−39
[8] 陈若曦,金海波,陈晋音,等. 面向深度学习模型的可靠性测试综述[J]. 信息安全学报,2024,9(1):33−55 Chen Ruoxi, Jin Haibo, Chen Jinyin, et al. Deep learning testing for reliability: A survey[J]. Journal of Cyber Security, 2024, 9(1): 33−55(in Chinese)
[9] Barthe G, Gaboardi M, Arias E J G, et al. Proving differential privacy in Hoare logic[C]//Proc of the 27th Computer Security Foundations Symp. Piscataway, NJ: IEEE, 2014: 411−424
[10] Barthe G, Danezis G, Grégoire B, et al. Verified computational differential privacy with applications to smart metering[C]// Proc of the 26th Computer Security Foundations Symposium. Piscataway, NJ: IEEE, 2013: 287−30
[11] Barthe G, Fong N, Gaboardi M, et al. Advanced probabilistic couplings for differential privacy [C] //Proc of the 23rd ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2016: 55−67
[12] Barthe G, Gaboardi M, Grégoire B, et al. Proving differential privacy via probabilistic couplings[C]//Proc of the 31st Annual ACM/IEEE Symp on Logic in Computer Science. New York: ACM, 2016: 749−758
[13] Barthe G, Köpf B, Olmedo F, et al. Probabilistic relational reasoning for differential privacy[C]//Proc of the 39th Annual ACM SIGPLAN-SIGACT Symp on Principles of Programming Languages. New York: ACM, 2012: 97−110
[14] Barthe G, Olmedo F. Beyond differential privacy: Composition theorems and relational logic for f-divergences between probabilistic programs[C]//Proc of the 40th Int Colloquium on Automata, Languages, and Programming. Berlin: Springer, 2013: 49−60
[15] Gaboardi M, Haeberlen A, Hsu J, et al. Linear dependent types for differential privacy[C]//Proc of the 40th Annual ACM SIGPLAN-SIGACT Symp on Principles of Programming Languages. New York: ACM, 2013: 357−370
[16] Ding Zeyu, Wang Yuxin, Wang Guanhong, et al. Detecting violations of differential privacy[C]//Proc of the 25th ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2018: 475−489
[17] Bichsel B, Gehr T, Drachsler-Cohen D, et al. Dp-finder: Finding differential privacy violations by sampling and optimization[C]//Proc of the 25th ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2018: 508−524
[18] McSherry F D. Privacy integrated queries: an extensible platform for privacy-preserving data analysis[C]//Proc of the 34th ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2009: 19−30
[19] Roy I, Setty S T V, Kilzer A, et al. Airavat: Security and privacy for MapReduce[C]// Proc of the 7th USENIX Conf on Networked Systems Design and Implementation. New York: ACM, 2010: 297−312
[20] Mohan P, Thakurta A, Shi E, et al. GUPT: Privacy preserving data analysis made easy[C]// Proc of the 12th ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2012: 349−360
[21] Abadi M , Chu A, Goodfellow I , et al. Deep learning with differential privacy[C]// Proc of the 23rd ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2016: 308–318
[22] McMahan H B, Daniel R, Kunal T, et al. Learning differentially private recurrent language models. [J]. arXiv preprint, arXiv: 1710.06963, 2017
[23] 叶青青,孟小峰,朱敏杰,等. 本地化差分隐私研究综述[J]. 软件学报,2018,29(7):159−183 Ye Qingqing, Meng Xiaofeng, Zhu Minjie, et al. Survey on local differential privacy[J]. Journal of Software, 2018, 29(7): 159−183 (in Chinese)
[24] McMahan 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. New York: PMLR, 2017: 1273−1282
[25] Wang Tianhao, Blocki J, Li N, et al. Locally differentially private protocols for frequency estimation[C]// Proc of the 26th USENIX Conf on Security Symp. Berkeley, CA: USENIX Association, 2017: 729−745
[26] Shokri R, Stronati M, Song C, et al. Membership inference attacks against machine learning models[C]// Proc of the 37th IEEE Symp on Security and Privacy (SP). Piscataway, NJ: IEEE, 2017: 3−18
[27] Dong Jinshuo, Aaron R, Su W J, Gaussian differential privacy. [J]Journal of the Royal Statistical Society Series B : Statistical Methodology 2022: 84(1): 3−37
[28] Pillutla K, Andrew G, Kairouz P, et al. Unleashing the power of randomization in auditing differentially private ML[C]//Proc of the 36th Advances in Neural Information Processing Systems. New York: Curran Associates, 2023: 66201−66238
[29] Domingo-Enrich C, Mroueh Y. Auditing differential privacy in high dimensions with the kernel quantum R\'enyi divergence[J]. arXiv preprint, arXiv: 2205.13941, 2022
[30] Jagielski M, Ullman J, Oprea A. Auditing differentially private machine learning: How private is private sgd?[C]//Proc of the 33rd Int Conf on Neural Information Processing Systems. New York: Curran Associates, 2020: 22205−22216
[31] Lu Fred, Munoz J, Fuchs M, et al. A general framework for auditing differentially private machine learning[C]//Proc of the 35th Int Conf on Neural Information Processing Systems. New York: Curran Associates, 2022: 4165−4176
[32] Chaudhuri K, Monteleoni C. Privacy-preserving logistic regression[C]//Proc of the 21st Advances in Neural Information Processing Systems. New York: Curran Associates, 2008, 21: 289−296
[33] Chaudhuri K, Monteleoni C, Sarwate A D. Differentially private empirical risk minimization[J]. Journal of Machine Learning Research, 2011, 12(3): 1069−1109
[34] Vaidya J, Shafiq B, Basu A, et al. Differentially private naive bayes classification[C]//Proc of the 10th IEEE/WIC/ACM Int Joint Conf on Web Intelligence (WI) and Intelligent Agent Technologies (IAT). Piscataway, NJ: IEEE, 2013: 571−576
[35] Fletcher S, Islam M Z. Differentially private random decision forests using smooth sensitivity[J]. Expert Systems with Applications, 2017, 78: 16−31 doi: 10.1016/j.eswa.2017.01.034
[36] Nasr M, Songi S, Thakurta A, et al. Adversary instantiation: Lower bounds for differentially private machine learning[C]//Proc of the 42nd IEEE Symp on Security and Privacy (SP). Piscataway, NJ: IEEE, 2021: 866−882
[37] Matsumoto M, Takahashi T, Liew S P, et al. Measuring lower bounds of local differential privacy via adversary instantiations in federated learning. [J]arXiv preprint, arXiv: 2206.09122, 2022
[38] Erlingsson Ú, Feldman V, Mironov I, et al. Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation[J]. arXiv preprint, arXiv: 2001.03618, 2020
[39] Ian J G, Jonathon S, Christian S. Explaining and harnessing adversarial examples[J]. arXiv preprint, arXiv: 1412.6572, 2014
[40] Arcolezi H H, Gambs S. Revealing the true cost of local privacy: An auditing perspective[J]. arXiv preprint, arXiv: 2309.01597, 2023
[41] Kairouz P, Bonawitz K, Ramage D. Discrete distribution estimation under local privacy[C]// Proc of the 33rd Int Conf on Int Conf on Machine Learning. New York: PMLR, 2016: 2436−2444
[42] Wang Shaowei, Huang Liusheng, Wang Pengzhan, et al. Mutual information optimally local private discrete distribution estimation[J]. arXiv preprint, arXiv: 1607.08025, 2016
[43] Ye Min, Barg A. Optimal schemes for discrete distribution estimation under locally differential privacy[J]. IEEE Transaction on Infomation Theory, 2018, 64(8): 5662−5676 doi: 10.1109/TIT.2018.2809790
[44] Erlingsson Ú, Pihur V, Korolova A. Rappor: Randomized aggregatable privacy-preserving ordinal response[C]//Proc of the 21st ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2014: 1054−1067
[45] Bassily R, Smith A. Local, private, efficient protocols for succinct histograms[C]//Proc of the 47th Annual ACM Symp on Theory of Computing. New York: ACM, 2015: 127−135
[46] Maddock S, Sablayrolles A, Stock P. CANIFE: Crafting canaries for empirical privacy measurement in federated learning[J]. arXiv preprint, arXiv: 2210.02912, 2022
[47] Steinke T, Nasr M, Jagielski M. Privacy auditing with one (1) training run[C]//Proc of the 36th Advances in Neural Information Processing Systems. New York: Curran Associates, 2023: 49268−49280
[48] Andrew G, Kairouz P, Oh S, et al. One-shot empirical privacy estimation for federated learning[J]. arXiv preprint, arXiv: 2302.03098, 2023
[49] Nasr M, Hayes J, Steinke T, et al. Tight auditing of differentially private machine learning[C]// Proc of the 32nd USENIX Conf on Security Symp. Berkeley, CA: USENIX Association, 2023: 1631−1648
[50] Chadha K, Jagielski M, Papernot N, et al. Auditing private prediction[J]. arXiv preprint, arXiv: 2402.09403, 2024
[51] Papernot N, Abadi M, Erlingsson U, et al. Semi-supervised knowledge transfer for deep learning from private training data[J]. arXiv preprint, arXiv: 1610.05755, 2016
[52] Papernot N, Song Shuang, Mironov I, et al. Scalable private learning with pate[J]. arXiv preprint, arXiv: 1802.08908, 2018
[53] Choquette-Choo C A, Dullerud N, Dziedzic A, et al. Capc learning: Confidential and private collaborative learning[J]. arXiv preprint, arXiv: 2102.05188, 2021
[54] Duan H, Dziedzic A, Papernot N, et al. Flocks of stochastic parrots: Differentially private prompt learning for large language models[C]//Proc of the 36th Advances in Neural Information Processing Systems. New York: Curran Associates, 2024: 76852−76871
[55] Zhu Yuqing, Yu Xiang, Chandraker M, et al. Private-kNN: Practical differential privacy for computer vision[C]//Proc of the 43rd IEEE/CVF Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2020: 11854−11862
[56] Dwork C, Feldman V. Privacy-preserving prediction[C] //Proc of the 31st Conf on Learning Theory. New York: Curran Associates, 2018: 1693−1702
[57] Mironov I. Rényi differential privacy[C]// Proc of the 30th IEEE Computer Security Foundations Symp (CSF). Piscataway, NJ: IEEE, 2017: 263−275
[58] Bernau D, Eibl G, Grassal P W, et al. Quantifying identifiability to choose and audit \varepsilon in differentially private deep learning[C]//Proceedings of the VLDB Endowment, 2022, 14(13): 3335–3347
[59] Lee J, Clifton C. How much is enough? Choosing ε for differential privacy[C]//Proc of the 14th Int Conf on Information Security, Berlin: Springer, 2011: 325−340
[60] Yeom S, Giacomelli I, Fredrikson M, et al. Privacy risk in machine learning: Analyzing the connection to overfitting[C]// Proc of the 31st IEEE Computer Security Foundations Symp (CSF). Piscataway, NJ: IEEE, 2018: 268−282
[61] Zanella-Béguelin S, Wutschitz L, Tople S, et al. Bayesian estimation of differential privacy[C]// Proc of the 40th Int Conf on Machine Learning. New York: PMLR, 2023: 40624−40636
[62] Krizhevsky A , Hinton G . Learning multiple layers of features from tiny images[J/OL]. Handbook of Systemic Autoimmune Diseases, 2009, 1(4): [2025-01-23]. https://www.cs.utoronto.ca/~kriz/learning-features-2009-TR.pdf
[63] Liu Ziwei, Luo Peng, Wang Xiaogang, et al. Deep learning face attributes in the wild[C]//Proc of the 15th IEEE Int Conf on Computer Vision. Piscataway, NJ: IEEE, 2015: 3730−3738
[64] Go A, Bhayani R, Huang Lei. Twitter sentiment classification using distant supervision[R/OL]. 2009[2025-01-23]. https://www-cs.stanford.edu/people/alecmgo/papers/TwitterDistantSupervision09.pdf
[65] Cun Y L , Boser B , Denker J , et al. Handwritten digit recognition with a backpropogation network[C]//Proc of the 2nd Advances in Neural Information Processing Systems. New York: Curran Associates, 1989: 396−404
[66] He Kaiming, Zhang Xiangyu, Ren Shaoqing, et al. Deep residual learning for image recognition [C] //Proc of the 29th IEEE Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2016: 770−778
[67] Zagoruyko S, Nikos K. Wide residual networks[J]. arXiv preprint, arXiv: 1605.07146
[68] Ye Qingqing , Hu Haibo , Meng Xiaofeng , et al. PrivKV: Key-value data collection with local differential privacy[C]// Proc of the 40th IEEE Symp on Security and Privacy (SP). Piscataway, NJ: IEEE, 2019: 317−331
[69] Ye Qinging , Hu Haibo, Li Ninghui , et al. Beyond value perturbation: local differential privacy in the temporal setting[C/OL]//Proc of the IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, 2021[2025-01-23]. https://drive.google.com/file/d/1ODzRtejolFnKHoZr_cGjQr6E6lMBJeFL/view
[70] Ghazi B, Golowich N, Kumar R, et al. Deep learning with label differential privacy[C]//Proc of the 34th Advances in Neural Information Processing Systems. New York: Curran Associates, 2021: 27131−27145
[71] Malek Esmaeili M, Mironov I, Prasad K, et al. Antipodes of label differential privacy: Pate and alibi[C]//Proc of the 34th Advances in Neural Information Processing Systems. New York: Curran Associates, 2021: 6934−6945
[72] Ghazi B, Kamath P, Kumar R, et al. Regression with label differential privacy[J]. arXiv preprint, arXiv: 2212.06074, 2022
[73] Busa-Fekete R I, Syed U, Vassilvitskii S. On the pitfalls of label differential privacy[EB/OL]. 2021[2025-01-20]. https://openreview.net/forum?id=2sWidqliCDG
[74] Brahmbhatt A, Saket R, Havaldar S, et al. Label differential privacy via aggregation[J]. arXiv preprint, arXiv: 2310.10092, 2023
[75] Esfandiari H, Mirrokni V, Syed U, et al. Label differential privacy via clustering[C/OL]//Proc of the 25th Int Conf on Artificial Intelligence and Statistics. New York: PMLR, 2022: 7055−7075
[76] Bitau A, Erlingssonú, Maniatis P, et al. Prochlo: Strong privacy for analytics in the crowd [C]//Proc of the 17th ACM Symp on Operating Systems Principles. New York: ACM, 2017: 441−459
[77] Wu Ruihan, Zhou Jinpeng, Weinberger K Q, et al. Does label differential privacy prevent label inference attacks?[C]//Proc of the 26th Int Conf on Artificial Intelligence and Statistics. New York: PMLR, 2023: 4336−4347
计量
- 文章访问数: 14
- HTML全文浏览量: 2
- PDF下载量: 7
