基于循环加密链的高效动态可搜索对称加密方案*

陈海龙, 马昌社

华南师范大学计算机学院, 广州 510631

目前, 基于云服务器的数据外包技术是解决用户本地资源开销的重要技术. 数据外包不仅可以节省用户的本地存储资源开销, 而且可以让用户在任意时刻和任意地点都能从云服务器获取数据. 然而在大部分情况下云存储服务器是不可信的, 用户普遍的做法是将自己的数据进行标准加密处理后上传, 但是经过标准加密算法处理后的数据不支持高效查找. 为了解决加密数据的高效查找问题, 可搜索加密(searchable encryption, SE) 应运而生. 可搜索对称加密(searchable symmetric encryption, SSE) 方案一般采用分别加密索引和文档数据的方法实现. SSE 方案的查询流程如下: 用户使用查询令牌从加密索引数据表中查询获取指向加密文档数据的索引, 然后通过这个索引查询加密数据表以获取文档数据. SSE 方案不泄露真实文档数据的内容, 且尽可能少地泄露信息, 同时具有良好的搜索性能. 将大部分早期的静态SSE 方案简单地修改为支持动态更新的方案会导致额外的信息泄露. 为了减少动态更新带来的泄露, 前向安全成为动态可搜索对称加密(dynamic searchable symmetric encryption, DSSE) 方案必不可少的前提条件之一.

前向安全, 又称前向隐私, 下文统一称为前向安全, 是指新增文档不能泄露它所包含的关键字. 换句话说, 使用旧的查询令牌无法查询出在这个查询时间点后更新的所有文档, 只有用新生成的查询令牌才能关联最新的文档. 尽管在密码学领域, 前向安全并不是一个新概念, 但是早期的动态可搜索对称加密方案[1]没有实现前向安全. Islam 等人[2]和Cash 等人[3]研究了利用SSE 方案泄露的攻击, 并且他们的研究表明即使是很小的泄露也可以被攻击者所利用去恢复用户的查询. 他们的攻击不仅仅只是针对静态SSE 方案, 而且对DSSE 方案也有效, 在服务器可以添加新文档到数据库的情况下, 服务器能够获取更多信息, 使其在攻击中更具优势. 在2016 年的Usenix 安全会议上, Zhang 等人[4]提出了文档注入攻击, 在可以向数据库注入文档的场景(如邮件交互) 中, 该攻击通过利用SSE 方案的访问模式(access pattern) 泄露和返回的注入文档, 可以精确地恢复用户查询的关键字. 文献[4] 指出, 文档注入攻击是自适应的, 这表明该攻击对没有满足前向安全的方案非常有效, 只需注入少量文档(约小于100 个文档) 就可以精确恢复查询令牌所对应的明文关键字. SSE 方案的前向安全属性不仅仅能提升安全性, 还能提升初始化效率. 大多数静态SSE 方案需要在初始化阶段构建加密索引表, 这个阶段占用较多资源且无法提供搜索服务. 因为满足前向安全的DSSE 方案允许实时构建加密数据库, 从而避免低效率的初始化流程, 实现动态更新且不中断搜索服务.

现有的许多满足前向安全的DSSE 方案仍存在各种各样的缺陷. Song 等人[5]的方案通过在服务器缓存查询关键字在上一次查询后返回的结果集, 从而提升方案的搜索性能, 但是以明文形式存储搜索结果集可能泄露了更多信息, 比如直接泄露两个关键字的文档交集信息; Etemad 等人[6]的方案使用只含存储功能的服务器作为服务端, 所有的计算操作都在客户端处完成, 虽然满足前向安全, 但是引入较高的通信开销和客户端计算开销.

本文首先提出了一个新的密码学原语循环加密链, 并基于该原语设计了一个支持前向安全的高效动态可搜索对称加密方案ECDSSE (encrypted chain DSSE). 该方案的目标为在保证前向安全的前提条件下,提高搜索效率, 同时尽可能地减少客户端存储开销. 首先给出了循环加密链的形式化定义和通用构造方法,然后证明ECDSSE 方案在诚实且好奇的攻击模型下具有语义安全. 最后实现多个满足前向安全的DSSE方案并与ECDSSE 方案进行性能对比分析.

各方案的理论性能对比情况如表1 所示. 其中W表示所有关键字的集合,|W| 表示关键字集合中不重复关键字的个数, logM表示搜索令牌的比特长度, 按常见的AES 算法实现来计算, 该比特长度一般为128 个比特. logC和logD分别代表搜索次数和更新次数的计数器比特长度, 以C++ 的整型为例,在64 位计算机中整型大小占32 个比特.aw代表关键字w的总更新次数,nw代表关键字w的搜索结果集合中元素的数量. 虽然更新效率和搜索效率理论性能是总体一致的, 但是在具体算法中, FAST 方案使用了更多的加解密操作或哈希操作, 这导致了搜索和更新性能的下降. BESTIE 方案虽然在搜索效率和更新效率上与本文方案ECDSSE 不相上下, 但是在理论存储开销上比ECDSSE 方案多了50%.

表1 三种DSSE 方案的理论性能对比Table 1 Theoretical performance among three DSSE schemes

在2000 年的S&P 安全会议上, Song 等人[8]首先提出实用可搜索加密的概念, 该文献指出可搜索加密方案的目标是在搜索效率、扩展性以及安全性上取得平衡, 并提出第一个基于流密码的可搜索加密方案SWP; 在2006 年的CCS 安全会议上, Curtmola 等人[9]提出了第一个基于倒排索引构造的SSE 方案的通用安全定义, 并设计了满足自适应IND2-CKA (indistinguishability against chosen-keyword attacks)安全定义的SSE 方案; Chase 等人[10]将SSE 方案的索引表结构抽象为一个多映射(multi-map, MM),并提出了结构化加密的概念; 为了拓展更多特性, Cash 等人[11]提出一个支持在大规模数据集上进行联合查询及布尔查询的静态SSE 方案OXT, 解决了在大规模数据集上进行高效多关键字查询的问题; Ma等人[12]在OXT 方案的基础上, 提出了子集成员查询的密码学原语及其通用构造方法, 并基于该原语来解决多关键字查询中存在的关键字对结果模式(keyword-pair result pattern, KPRP) 泄露问题; Sun 等人[13]根据RSA 函数的特点设计了一个支持非交互式和多用户特性的SSE 方案, 解决了多用户方案中数据拥有者与客户端用户交互的隐私泄露问题; 杨旸等人[14,15]使用Simhash 的方法实现一个支持模糊查询功能的可搜索加密方案, 并且将域加权评分、语义相似度和相关度分数三者结合构造更准确的多关键字语义排序搜索方案; 卢冰洁等人[16]使用名为状态链的数据结构来实现支持多用户特性的前向安全DSSE 方案; 刘翔宇等人[17]结合可搜索加密和属性加密算法, 提出一种多访问级别的动态云存储方案; 孙僖泽等人[18]提出一个基于可搜索加密机制的数据库加密方案, 将可搜索加密机制应用到现实数据库中.

然而, 静态SSE 方案不能满足现实用户动态更新数据的需求. 为了使SSE 方案更具实用性, Kamara 等人[1]首先提出了支持动态可搜索对称加密的方案, 虽然他们的方案实现了次线性级别的搜索效率, 但是删除和增加操作需要较高的复杂度; Stefanov 等人[19]首先提出了可搜索加密领域的前向安全的概念, 他们基于层次茫然随机访问内存[20](obilivious random acess memory, ORAM) 构造设计了一个满足前向安全的DSSE 方案, 该方案虽然满足前向安全的定义, 但是同时引入了较高的通信开销; 直到2016 年, Bost 等人[21]形式化定义前向安全的概念, 并提出了一个基于公钥密码学原语构造的高效DSSE 方案. 近年来, Bost 等人[22]提出一个基于受限伪随机函数(constraint pseudorandom function, CPRF) 构造的前向安全方案Diana, 使用对称密钥原语替代公钥密码学原语来实现前向安全;Song 等人[5]提出了基于缓存机制的前向安全方案FASTIO, 提高了DSSE 方案的I/O 效率; Etemad 等人[6]提出一个基于只作存储的服务器的前向安全方案, 减少了给服务器的信息泄露; He 等人[23]提出一个基于鱼骨链构造的前后向安全DSSE 方案, 该方案将客户端存储减少至常数级别, 但是引入了更新次数的限制, 实用性有限; Chen 等人[7]提出一个满足前后向安全的基于缓存机制的DSSE 方案BESTIE, 他们将缓存机制应用在后向安全的方案中, 提升删除操作的性能. 上述方案存在各种各样的缺陷, 与这些方案相比, 本文提出的基于循环加密链的ECDSSE 方案在满足前向安全的前提下, 具有更高的搜索效率.

本节给出DSSE 方案的定义以及本文用到的密码学原语, 并对文中使用的符号进行说明.

3.1 符号说明

在本节里, 本文将对所使用的符号进行说明. 将x$←X看作从一个集合X均匀随机采样获得一个样本x.x ←D代表从分布D中抽样出一个样本x. 设P(·) 为概率多项式时间(probabilistic polynominal time algorithm, PPT) 算法.p ←P(·) 表示算法P(·) 的输出赋值给变量p. 设S为集合或字符串,|S| 表示集合S的基数, 笛卡尔积Sn={(s1,s2,··· ,sn)|si ∈S,i= 1,2,··· ,n}. 对于向量、列表或链表v,v[i] 代表v的第i个分量. 假设a和b是正整数, 且a ＜b, 令[a,b] ={a,a+1,··· ,b}, [a] = [1,a].对于两个字符串S1和S2,S1||S2代表S1与S2进行拼接. 对于函数negl(λ) :Z →(0,1), 如果对于任意的正多项式p(·), 都存在正整数N0, 使得对于任意的λ ＞N0, 都有negl(λ)＜1/p(λ) 成立, 那么我们说negl(λ) 是可忽略函数. 令Ø表示空集或空字符串,⊥表示一个空值符号, poly(·) 代表一个多项式函数,代表该函数能在多项式时间内执行.

3.2 IND-CPA 安全的对称加密方案

(1) 挑战者C调用算法Gen(1λ) 生成一个随机密钥K.

(2) 敌手A选择两个相同大小的消息对m0和m1, 发送给挑战者C.

(3) 挑战者C选择一个随机比特b ←{0,1}, 计算密文c ←Enc(K,mb) 并将密文c返回给敌手A.(4) 敌手A根据返回的密文c, 输出判断值比特b′.

(5) 实验的输出定义为: 当b=b′时实验输出1, 否则输出0.

称对称加密方案Σ 具有IND-CPA 安全, 如果对任意PPT 敌手A, 存在一个可忽略函数negl(λ), 有以下不等式成立:

3.3 伪随机函数

定义2[25]令F:{0,1}λ×{0,1}n →{0,1}n表示一个函数族, 其中{0,1}λ表示密钥空间, 定义域和值域都是{0,1}n. 称F是一个伪随机函数(pseudorandom function, PRF), 如果对于任意PPT 区分器D, 存在一个可忽略函数negl(λ), 有以下不等式成立:

其中, 密钥k$←{0,1}λ, 函数f从映射n比特字符串到n字符串的函数集合中随机均匀选择.

3.4 动态可搜索对称加密

一般地, 动态可搜索对称加密方案由一个初始化算法Setup 和两个交互式协议Update、Search 组成.以下是DSSE 方案的形式化定义:

定义3[26]给定安全参数λ, DSSE 方案Π = (Setup,Update,Search) 由初始化算法Setup、更新协议Update 和搜索协议Search 组成. 方案的一般流程如下所示:

(1) ((K,σ);EDB)←Setup((λ,DB);⊥): 系统初始化算法, 该算法主要在客户端处执行. 客户端输入一个明文数据库DB 和一个安全参数λ; 服务器端没有输入. 该算法输出一个主密钥K、状态σ以及一个加密后的密文数据库EDB, 其中客户端存储主密钥K和状态σ, 服务器存储密文数据库EDB.

(2) (σ′;EDB′)←Update((K,σ,op,w,id);EDB): 更新协议, 该协议在客户端和服务器之间交互进行. 客户端输入一个主密钥K、状态σ、一个文档id、关键字w以及更新操作符op; 服务器输入密文数据库EDB. 其中, 更新操作符op 从集合{add,del}中选择, 即客户端只能执行增加或删除(文档, 关键字) 键值对的操作. 更新协议结束后客户端更新状态σ为σ′, 服务器更新密文数据库EDB 为EDB′.

(3) ((σ′,DB(w));EDB′)←Search((K,σ,w);EDB): 搜索协议, 该协议在客户端和服务器之间交互进行. 客户端输入一个主密钥K、状态σ和要查询的关键字w; 服务器输入一个密文数据库EDB. 搜索协议结束后, 客户端输出关键字w的搜索结果集合DB(w) 并可能更新状态σ为σ′, 服务器可能更新密文数据库EDB 为EDB′.

DSSE 方案的安全性要求敌手尽可能少地了解数据库内容和查询信息, 更准确地说, 用户并不希望敌手能够获取除了方案允许的泄露之外的任何信息. 为了更好的描述DSSE 方案的安全性, 我们使用理想世界和真实世界的游戏对其进行形式化的描述.

定义4[26]给定DSSE 方案Π = (Setup,Update,Search),A为任意PPT 敌手,S为以泄露函数L=(LSetup,LUpdate,LSearch) 作输入的仿真器. 对于DSSE 方案Π 的证明通常需要定义两个游戏, 一个游戏RealΠA(λ) 代表协议的真实执行, 另一个游戏IdealΠA,S(λ) 由仿真器以泄露函数L作为输入模拟生成. 如果敌手无法区分自己是在哪个游戏中, 则表明敌手不掌握额外的知识, 即证明方案没有造成除了泄露函数描述之外的其他任何泄露, 具体地, 两个游戏的定义如图1 所示:

图1 DSSE 方案Π 的两个安全游戏Figure 1 Two secure games in DSSE scheme Π

其中, stA表示敌手A的状态, stS表示仿真器S的状态,K为DSSE 方案的主密钥,k表示查询次数, 是关于λ的多项式poly(λ), (ti)1≤i≤k表示第i次(更新/搜索) 查询时客户端发送给服务器的消息(t0=Ø), (EDBi)0≤i≤k表示第i次查询时的加密数据库, (σi)1≤i≤k表示第i次查询时客户端状态,(typei,idi,wi,DB(wi),opi)1≤i≤k分别表示第i次查询时的查询类型(更新/搜索)、文档标识符、关键字、关键字wi的查询结果和更新操作符,LSetup(DB)、LUpdate(op,w,id) 和LSearch(w) 分别表示Setup 算法、Update 协议和Search 协议的泄露函数.

如果对于任意PPT 敌手A, 存在一个PPT 仿真器S满足以下条件:

则称DSSE 方案Π 具有L-自适应安全.

3.5 前向安全

前向安全是指新添加一个文档后, 该新添加文档对应的关键字信息在下一次搜索查询前不会被泄露给敌手. 如果更新查询不会泄露正在更新的(关键字, 文档) 对中的关键字信息, 则DSSE 方案具有前向安全. 形式化定义如下:

定义5 本文使用文献[21] 的形式化定义. 如果方案Π 的更新泄露函数LUpdate可以写为如下形式:

则称DSSE 方案Π 具有前向安全, 其中input 表示更新操作的输入, 在方案中通常为(w,id) 键值对,op 表示更新操作符, idi代表第i个更新文档标识符,|Wid| 表示文档标识符id 匹配的所有关键字个数,L′是无状态函数.

本节提出循环加密链(circular encrypted chain, CEC) 的定义和安全性分析, 并给出通用的构造方法及一个基于哈希函数构造的CEC 方案的定义及安全性证明.

为了更好地理解循环加密链, 本节首先描述静态SSE 方案的基本流程, 简单的流程如下:

(1) 初始化算法Setup 主要由客户端执行. 算法输入数据集和安全参数, 输出加密数据集、加密索引集和密钥. 具体流程为: 客户端将明文数据集拆分成(w,id) 和(id,file) 两种键值对的形式, 即数据库可以分为索引和文档数据两部分, 分别加密后上传到服务器, 其中w表示关键字, id 表示文档标识符, file 表示真实文档.

(2) 搜索协议Search 由客户端和服务器交互进行. 算法输入关键字和密文数据集, 输出搜索结果集.具体流程为: 客户端根据需要查询的关键字w生成搜索令牌, 服务端使用该令牌检索键值对存储数据库, 将检索到的对应的加密文档标识符结果集返回给客户端, 客户端解密获得文档标识符集合, 最后通过文档标识符从服务器获取对应的加密文档集合.

简单地改动上述常见的静态SSE 方案为支持动态更新的SSE 方案会泄露更多信息, 因为在执行了搜索操作后, 服务器将拥有该查询关键字的搜索令牌, 如果数据拥有者基于该搜索令牌进行数据更新, 那么服务器将立刻得知该关键字对应的文档获得了更新, 在某些特定场景中服务器可利用该信息准确恢复该令牌对应的关键字. 以中秋节为例, 许多用户会在中秋节当天更新与中秋节相关的数据, 服务器可以根据统计数据准确推断出中秋节等关键字对应的搜索令牌和数据位置信息. 为了在减轻该类信息泄露影响的同时保证搜索效率, 前向安全成为DSSE 方案中必不可少的前提条件之一.

文献[21] 的前向安全定义表明, 查询之间发生的更新与前一个查询的查询陷门没有关联关系. 因此,满足前向安全的关键在于找到一个切断前后查询关联的方法, 以此实现客户端能根据旧状态生成新状态,而服务端无法从旧状态生成新状态的目标. 单向陷门置换函数是一种可以轻易进行正向计算, 但在缺少陷门信息的情况下很难求逆的函数, 这种函数能够满足前向安全的要求. Bost 等人[21]的方案使用基于公钥的单向陷门置换函数(如RSA 等) 来实现前向安全, 虽然该方案满足前向安全, 但是基于公钥密码学原语构造的方案存在计算开销较大的问题, 实用性较差. 随后Song 等人[5]和Etemad 等人[6]尝试基于对称密码学原语构造方案, 避免公钥体系的高计算开销, 提升方案搜索性能.

我们实现前向安全的想法来源于哈希链. 在密码学中, 哈希链是指重复使用同一个哈希函数对由该函数生成的哈希值进行哈希运算, 最终生成的一系列哈希值. 哈希函数具有单向性, 敌手无法在多项式时间内通过哈希函数的结果推导出哈希函数的原像. 只要DSSE 方案每次更新都从后往前使用前一个哈希值进行哈希运算, 由于哈希函数的单向性, 方案自然满足前向安全. 具体来说, 客户端选择一个初始化密钥K0←{0,1}λ, 然后通过安全哈希函数生成其他密钥, 即Ki+1←H(Ki),0≤i ＜L. 在客户端进行查询时, 客户端通过上传一个中间密钥Ki到服务器, 服务器可以从Ki开始一直计算哈希值Ki+1←H(Ki),直到获得最终的密钥Kn. 由于哈希函数的单向性, 服务器无法通过Ki计算出Ki-1, 因此哈希链满足前向安全. 然而, 哈希链方案有着致命的缺点, 它不仅需要客户端存储所有的更新状态, 还要在一开始就固定更新次数, 这对于现实数据库和有存储空间限制的用户设备来说都是不可接受的.

针对哈希链的缺点, 本文提出了对称循环加密链的新原语. 循环加密链将DSSE 的倒排索引表的每一行抽象成一个链表, 一个以头插法进行插入的链表. 循环加密链的思想可以用带钥匙的有锁盒子来解释.以Alice 和Bob 的交互进行举例说明, 假设每一个带锁的盒子都有它对应的一把钥匙, 最开始Alice 将信息存在第一个带锁的盒子里, 它继续添加新信息的时候, 需要再用一个新的带锁的盒子将新信息装进去,同时将第一个盒子的钥匙也放进去一起锁住, 以此类推, 最后将倒数第二个盒子的钥匙和新添加的信息放入最后一个盒子中, 使用最后一个盒子的钥匙锁起来, 把所有更新的盒子全交给Bob. 当Alice 需要查询信息时, 将这个最新的盒子的钥匙给了Bob, Bob 才能够依次解开每一个盒子, 拿出里面的信息给Alice,在此之前, Bob 并不知道每一个盒子间的关系, 也无法得知盒子内的钥匙和信息内容. 换句话说, 用户可以通过在客户端本地即时计算一个新的密钥Kn, 将这个密钥通过IND-KDM 安全的对称加密算法恢复旧的密钥Kn-1, 但是通过这个旧的密钥Kn-1是无法推导出新的密钥Kn的, 这样就满足了前向安全的定义. 如图2 所示, 循环加密链输入一系列密钥的集合K={K0,K1,··· ,Kn}, 使用IND-KDM 安全的对称加密方案(KG,E,D), 调用对称加密算法E, 用密钥K1加密密钥K0获得密文e1, 即e1=E(K1,K0),用密钥K2加密密钥K1获得密文e2, 以此类推, 最终获取一系列密文的集合E={e1,e2,··· ,en}. 对应的解密流程如图3 所示, 输入密文集合E, 使用一个最新的密钥Kn进行循环解密, 调用对称解密算法D,用密钥Kn解密密文en获得密钥Kn-1, 即Kn-1=D(Kn,en), 以此类推, 获得一系列解密的密钥集合K={K0,K1,··· ,Kn}. 同时, 因为循环加密链是一个从头部插入新结点的链表, 通过使用每次更新中本地计算的新密钥加密之前的密钥, 将加密的值插入到链表头部, 通过新密钥解密该值恢复之前的密钥结点. 只要密钥生成算法由用户执行, 用户就可以将更新次数扩展为无限次, 从而避免哈希链需要固定更新次数的缺点.

图2 循环加密链加密流程示意图Figure 2 Presentation of encryption in circular encrypted chain

图3 循环加密链解密流程示意图Figure 3 Presentation of decryption in circular encrypted chain

4.1 循环加密链及其安全的形式化定义

定义6 循环加密链方案ΠCEC= (KG,E,D,KGCEC,ECEC,DCEC) 由SKE 密钥生成算法KG、SKE 对称加密算法E、SKE 对称解密算法D、循环密钥生成算法KGCEC、循环密钥加密算法ECEC和循环密钥解密算法DCEC组成. 以下是方案的具体内容:

(1)K ←KG(λ): 密钥生成算法. 算法输入一个安全参数λ, 输出一个密钥K.

(2)C ←E(K,M): 对称加密算法. 算法输入一个密钥K和一个明文消息M, 输出一个密文C.

(3)M ←D(K,C): 对称解密算法. 算法输入一个密钥K和一个密文C, 输出一个明文M.

(4)K ←KGCEC(λ,n): 循环密钥生成算法. 算法输入安全参数λ和一个正整数n, 生成有n+1 个不同密钥的集合K={K0,K1,··· ,Kn}.

(5)E ←ECEC(K): 循环密钥加密算法. 算法输入由算法KGCEC生成的有n+1 个不同密钥的集合K, 用密钥K1来加密密钥K0得到密文e1, 即e1=E(K1,K0), 接着继续用密钥K2来加密密钥K1得到密文e2, 以此类推, 直到用最后一个密钥Kn加密密钥Kn-1得到密文en, 最终输出一个密文集合E={e1,e2,··· ,en}.

(6)K ←DCEC(Kn,E): 循环密钥解密算法. 算法输入密钥Kn和密文集合E, 用密钥Kn来解密密文en得到密钥Kn-1, 即Kn-1=D(Kn,en), 接着继续用密钥Kn-1来解密密文en-1得到密钥Kn-2, 以此类推, 直到用最后一个密钥K1解密密文e1得到密钥K0, 最终输出一个密钥集合K={K0,K1,··· ,Kn}.

我们说ΠCEC方案具有计算正确性, 如果对于任意的安全参数λ和任意由密钥生成算法KGCEC生成的一系列密钥的集合K, 按顺序执行循环加密算法E ←ECEC(K), 然后执行循环解密算法K′←DCEC(Kn,E), 有K′=K, 否则K′/=K.

为了分析循环加密链方案的安全性, 对于方案ΠCEC= (KG,E,D,KGCEC,ECEC,DCEC), 用泄露函数LΠCEC表示PPT 敌手A能够从密钥集K的加密结果密文链集合E中获取到的信息.

接下来定义循环加密链方案的安全定义.

如果对于任意PPT 算法A, 存在

则称循环加密链方案ΠCEC在自适应攻击下具有IND-KDM 安全.

4.2 循环加密链方案

循环加密链是一种新的密码学原语, 它的构造方法并不唯一, 可以使用哈希函数、伪随机数发生器和伪随机函数等常见构造方法来构造循环加密链方案. 本节提出一个基于哈希函数构造的循环加密链方案(hash-based CEC, HCEC), 详见算法1, 该方案是循环加密链方案的一个特例.

为了更好地描述循环加密链方案, 将方案的主要过程抽象为六个算法. 这六个算法分别为对称密钥生成算法KG、对称加密算法E、对称解密算法D、循环密钥生成算法KGCEC、循环加密算法ECEC和循环解密算法DCEC. 其中, 前面三个算法满足IND-KDM 安全, 算法KG 输入安全参数λ, 输出一个密钥K; 算法E输入密钥K和明文M, 输出密文C; 算法D输入密钥K和密文C, 输出明文M; 算法KGCEC输入安全参数λ和一个正整数n, 输出一系列密钥的集合K. 具体地, 该算法首先调用对称密钥生成算法KG 生成一个密钥K, 通过安全哈希函数H和整数n, 生成一系列密钥的集合K. 而算法ECEC输入密钥集合K={K0,K1,··· ,Kn}, 调用对称加密算法E, 用密钥K1加密密钥K0获得密文e1, 即e1=E(K1,K0), 以此类推, 生成一系列密文的集合E={e1,··· ,en}. 算法DCEC输入最新的密钥Kn和一系列密文的集合E={e1,··· ,en}, 调用对称解密算法D, 用密钥Kn解密密文en获得密钥Kn-1, 以此类推, 最终输出一系列密钥的集合K={K0,K1,··· ,Kn}.

接下来为了分析HCEC 方案的计算正确性, 本文将构建方案的计算正确性实验. HCEC 方案的正确性实验流程如下: 实验首先执行算法KGCEC生成有n+1 个密钥的集合K={K0,K1,··· ,Kn}, 然后使用ECEC算法循环加密这一系列密钥, 获得一系列密文的集合E. 解密算法DCEC输入密钥Kn和上述一系列密文的集合, 输出一系列密钥的集合K′={K′0,K′1,··· ,K′n-1,Kn}. 若解密算法的输出结果K′与加密算法的输入K相等, 那么输出结果比特b=1, 否则b=0. 由于加密算法和解密算法都是确定性算法, 因此b=1 出现的可能性是确定的, HCEC 方案的计算正确性得证.

算法1 HCEC 方案算法KG Input: λ Output: K 1: K ←SKE.Gen(λ)2: Output K算法E Input: K,M Output: C 1: C ←SKE.E(K,M)2: Output C算法D Input: K,C Output: M 1: M ←SKE.D(K,C)2: Output M算法KGCEC Input: λ,n Output: K 1: K ←KG(λ)2: for i = 0 →n do 3: Ki ←H(K,i)4: K ←K ∪{Ki}5: end for 6: Output K算法ECEC Input: K Output: E 1: for i = 1 →n do 2: ei ←E(Ki,Ki-1)3: E ←E ∪{ei}4: end for 5: Output E算法DCEC Input: Kn, E Output: K 1: for i = n →1 do 2: Ki-1 ←D(Ki,ei)3: K ←K ∪{Ki-1}4: end for 5: Output K

下面分析HCEC 方案的安全性, 对于生成的密钥集合K, 定义以下泄露函数LHCEC(K)=(E,N). 其中N,K,E定义如下:

·N=|K| 是密钥集合的元素个数.

·K是一系列密钥的集合.

·E是一系列密文的集合.

定理1 令LHCEC如上所述. 在随机预言机模型下, 假设对称加密算法SKE 满足IND-KDM 安全,那么HCEC 方案在自适应攻击下具有IND-KDM 安全.

证明: 接下来使用混合论证的方法来对HCEC 方案进行安全性证明.

因此, HCEC 方案在自适应攻击下具有IND-KDM 安全.

基于循环加密链,本文提出一个满足前向安全的高效DSSE 方案ECDSSE(encrypted chain dynamic SSE), 它支持隐藏响应结果(response-hiding). 响应结果的隐藏与否与方案设计相关, 如果服务器返回的查询响应结果是加密的, 那么称方案支持隐藏响应结果, 否则称方案不支持隐藏响应结果. ECDSSE 方案的设计思想如下: 用Kn作为满足IND-KDM 安全的对称加密方案的新密钥, 对客户端本地计算的旧密钥Kn-1进行加密, 以此类推, 循环加密以前的密钥, 实现隐藏新密钥与旧密钥的关联. 用安全哈希函数切断新密钥和以前的搜索令牌的联系, 通过查询时发送最新的密钥关联更新文档.

ECDSSE 方案由系统初始化算法Setup、更新协议Update 和搜索协议Search 组成. 算法伪代码如算法2、算法3 和算法4 所示. 以下是Setup 算法、Update 协议和Search 协议的具体过程:

(1) Setup(λ,DB;⊥): 系统初始化算法, 该算法主要由客户端执行. 客户端输入安全参数λ和明文初始数据库DB, 从密钥空间{0,1}λ随机均匀抽样生成主密钥K并初始化本地缓存映射Σ、索引表T和删除表DT 为空映射; 服务器无输入. 如果初始数据库DB 不为空, 那么进行初始数据库的更新, 具体流程如下: 将数据库DB 解析成(w,IDw) 键值对的集合, 其中w代表关键字, IDw代表含有关键字w的文档标识符集合. 然后, 针对每一个关键字w对应的文档集合IDw调用循环密钥生成算法HCEC.KGCEC生成密钥集合K, 再调用循环密钥加密算法ECEC, 对上述生成的一系列密钥进行加密, 获得相对应的密文集合E, 同时对每一个文档id 都使用满足IND-CPA安全的对称加密算法进行加密, 且通过哈希函数H获取每一个密钥Ki的哈希键值Li, 将键值对{Li,(op+ed+ei)}添加到索引表T中. 初始化算法运行结束后, 客户端存储主密钥K和缓

存映射表Σ, 服务器存储索引表T和删除表DT.

算法2 Setup Input: λ,DB Output: K,Σ,T,DT 1: K$←{0,1}λ 2: Σ,T,DT ←empty map 3: while |DB|! = 0 do 4: key ←DB 5: (w,IDw) ←key 6: Σ[w] ←|IDw|7: Kw ←F(K,w)8: K ←HCEC.KGCEC(Kw,|IDw|)9: E ←HCEC.ECEC(K)10: for i = 1 →|IDw| do 11: Li ←H1(Ki)12: ei ←E 13: edi ←Enc(Kw,idi)14: T ←T ∪{Li,(op+edi +ei)}15: end for 16: DB.Remove(key)17: end while 18: Send (T,DT) to the Server

(2) Update(K,Σ,id,w,op;T): 更新协议, 该协议在客户端和服务器之间交互进行. 客户端输入主密钥K、本地状态缓存映射表Σ、需要更新的文档标识符id、文档中包含的关键字w以及更新操作符op; 服务器输入索引表T. 更新协议的具体流程如下:

(a) 对于键值对(w,id), 客户端初始化关键字w对应的状态缓存映射表Σ[w] 的更新次数n为0 或取出最新的更新次数n, 将该关键字的更新次数递增后重新存到状态缓存表Σ 中, 并使用伪随机函数计算对应的关键字密钥Kw.

(b) 使用这个关键字密钥Kw调用HCEC 方案的密钥生成算法生成密钥Kn+1和密钥Kn, 并对文档标识符id 使用IND-CPA 对称加密算法进行加密获得密文ed, 其中HCEC 方案的密钥生成算法中使用了抗碰撞的哈希函数H,主要目的是利用该函数的抗碰撞特性生成一系列不同密钥. 然后调用循环加密算法HCEC.E, 用密钥Kn+1加密密钥Kn获得密文en+1.

(c) 用安全哈希函数H1修饰密钥Kn+1获得一个哈希键值Ln+1, 断开新密钥与查询标签的联系,将更新操作符op、密文ed 以及加密联系密文en+1按顺序拼接,获得新密文En+1. 最后客户端存储更新后的本地状态缓存Σ, 服务器存储更新后的索引表T, 其中T[H1(Kn+1)]=En+1.

算法3 Update Input: (K,Σ,w,id,op);T Output: Σ′,T′Client:1: n ←Σ[w]2: if n == ⊥then 3: n ←0 4: end if 5: Kw ←F(K,w)6: Kn ←H(Kw,n)7: Kn+1 ←H(Kw,n+1)8: en+1 ←HCEC.E(Kn+1,Kn)9: Ln+1 ←H1(Kn+1)10: ed ←Enc(Kw,id)11: En+1 ←(op||ed||en+1)12: Σ[w] ←n+1 13: Send (Ln+1,En+1) to Server Server:14: T[Ln+1] ←En+1

值得注意的是, 客户端拥有主密钥K, 它能通过伪随机函数生成关键词w对应的子密钥Kw, 再结合计数器作为哈希函数的输入, 可生成关键词w在循环加密链上的一系列不关联的密钥. 此处伪随机函数的目标是为不同关键词w对应的循环加密链提供不同的随机子密钥Kw, 同时使得客户端在更新操作时, 可以利用主密钥重新计算出Kw, 免去了子密钥的存储开销. 在Update 协议步骤6 的密钥生成算法的选择取决于循环加密链的具体实例化, ECDSSE 方案使用了上文基于哈希函数的HCEC 实现前向安全, 因此步骤6 使用哈希函数生成密钥.

(3) Search(K,Σ,w;(DT,T)): 搜索协议, 该协议在客户端和服务器之间交互进行. 客户端输入主密钥K、本地状态缓存Σ 和待查询的关键字w; 服务器输入删除表DT 和索引表T. 具体流程如下:

(a) 客户端取出本地状态缓存Σ 中关键字w的更新次数n并使用哈希函数计算最新密钥Kn,发送密钥Kn和更新次数n给服务器.

(b) 服务器获得(Kn,n) 后, 计算标签H1(Kn) 并用该标签从索引表T中获取对应的密文En,将密文En按顺序分离获取对应的更新操作符op、结果标识符密文ed 以及加密链值en, 根据更新操作符op 的类型(增加或删除), 分别添加到删除表DT 和加密结果集ER 中. 其中,服务器根据循环加密链方案, 调用循环解密算法HCEC.D, 用密钥Kn解密密文en获得密钥Kn-1, 以此类推, 循环解密直到获得最后的加密结果集ER, 服务器将结果集ER 发送给客户端.

(c) 客户端获得服务器返回的加密结果集ER 后, 用主密钥K计算查询关键字w对应的子密钥Kw. 客户端使用密钥Kw能够解密文档标识符密文集合ER, 获得明文文档标识符集合R,至此搜索协议结束.

算法4 Search Input: (K,Σ,w);(DT,T)Output: (Σ′,R)Client:1: n ←Σ[w]2: if n = ⊥ then 3: return Ø 4: end if 5: Kw ←F(K,w)6: Kn ←H(Kw,n)7: Send (Kn,n) to Server Server:8: ER, DT ←Ø 9: for i = n →1 do 10: Li ←H1(Ki)11: (op||ed||ei) ←T[Li]12: if op = del then 13: DT←DT ∪{ed}14: else 15: if ed ∈DT then 16: DT←DT-{ed}17: else 18: ER←ER∪{ed}19: end if 20: end if 21: Ki-1 ←HCEC.D(Ki,ei)22: end for 23: Send ER to Client Client:24: Kw ←F(K,w)25: for i = 1 →c do 26: idi ←Dec(Kw,ER[i])27: R ←R ∪{idi}28: end for 29: Output R

下面给出ECDSSE 方案的正确性定理与安全性定理.

定理2 假设H和H1是安全的抗碰撞哈希函数,F是安全的伪随机函数, (Gen,Enc,Dec) 是满足IND-CPA 安全的SKE 方案, HCEC 方案具有计算正确性, 如果对于任意PPT 敌手A, 均有以下不等式成立:

则称ECDSSE 方案具有计算正确性.

定理3 设H和H1是基于随机预言机建模的安全哈希函数, (Gen,Enc,Dec) 是满足IND-KDM 安全的SKE 方案,F是安全的伪随机函数, HCEC 方案具有计算正确性并且在自适应攻击下具有INDKDM 安全. 定义泄露函数L=(LSetup,LUpdate,LSearch), 它记录一个包含搜索请求和更新请求的请求列表Q, 如果泄露函数只泄露如下所示的信息:

也就是说, ECDSSE 方案具有前向安全和L-自适应安全, 其中|Widi| 表示更新文档idi对应的关键字集合的数量,N表示由初始化算法生成的加密数据库EDB′的键值对个数, sp(w) 代表关键字w的搜索模式, qp(w) 代表关键字w的查询模式, 具体细节如下:

由于篇幅问题, 定理2 和定理3 的证明在附录中给出, 此处不再赘述.

本节将从更新效率、搜索效率和存储开销等方面, 对ECDSSE 方案、FAST 方案[5]和BESTIE 方案[7]进行性能对比分析. 本文采用C++ 编程语言编写方案代码, 使用RocksDB 数据库存储键值对字典, 基于GRPC 框架实现客户端与服务器的网络数据传输. 此外, 本文使用Cryptopp 密码学开源库实现安全哈希函数H和H1、伪随机函数F和对称加密方案SKE. 本文修改了FAST 方案和BESTIE 方案的代码实现, 以便与本文方案进行对比, 其中BESTIE 方案修改为不使用缓存机制的支持前向安全的方案. 在所有方案中, 标识符长度都设置为64 位, 所有的关键字均经过哈希处理, 以防部分关键字长度过长造成对称加密的明文分组长度不同. 在广域网(wide area network, WAN) 的网络环境下, 服务端部署在具有4 核CPU、8 GB 内存、40 GB 存储空间的腾讯云服务器上, 而客户端部署在位于笔记本电脑上, 该电脑具有4 核CPU (英特尔酷睿i5-11300H, 3.10 Ghz)、16 GB 内存和500 GB 固态硬盘. 在本地局域网(local area network, LAN) 的网络环境下, 服务端和客户端同时部署在同一台笔记本电脑上, 笔记本电脑的配置同上.

6.1 更新效率

首先展示三个方案在更新操作上的性能情况. FAST、BESTIE 和ECDSSE 都是基于对称密码学原语构造的方案, 但是各方案更新协议中的操作有所区别. 更新实验测量的参数包括吞吐量和单个键值对更新时间, 其中吞吐量表示单位时间内方案执行键值对更新操作的数量, 单个键值对更新时间表示执行单个键值对更新操作所需的时间. 每个文档包含关键字个数范围有1000、5000、10 000 三种, 这是因为在实际的数据库中, 一个文档对应关键字个数普遍落在这三个数的范围内, 选择这三个数有利于分析在不同关键字个数的情况下方案的更新效率的情况. 实验首先测量了更新FAST、BESTIE 和ECDSSE 方案在LAN 中的更新效率, 即在同一计算机上运行客户端程序和服务端程序. 在LAN 环境中, 实验结果不包括网络传输导致的延迟误差, 更能体现方案本身的执行效率. 然后实验测量在WAN 环境中的方案更新效率, 其中服务器部署在腾讯云服务器, 客户端部署在笔记本电脑. 每个实验重复30 次, 取平均值, 避免偶然误差. 更新性能测试的结果如表2 所示, 在两种网络环境中, ECDSSE 方案的吞吐量都是FAST 方案的1.3 倍, 并且与BESTIE 方案的吞吐量几乎一致. 结果证实, ECDSSE 方案在更新效率方面比FAST 方案更胜一筹, 这是由于FAST 方案在更新过程中需要不断生成伪随机数, 而ECDSSE 方案的子密钥是通过安全哈希函数生成的, 更新效率的差距来源于哈希函数和伪随机数生成器的效率差. ECDSSE 方案与BESTIE 方案更新效率的差距不大的实验结果源于两者的客户端计算复杂度相当, 两者均执行相同数量的哈希操作或加解密操作.

表2 FAST、BESTIE 和ECDSSE 方案的更新效率Table 2 Update efficiency among FAST、BESTIE and ECDSSE

6.2 搜索效率

对于FAST、BESTIE 和ECDSSE 方案, 服务器端的搜索操作需要处理加密索引条目列表以查找匹配的文档. 因此, 搜索效率关键取决于处理索引的效率. 图4 和图5 展示了三种方案在不同网络环境中的搜索效率情况. 使用三个不同数量级大小的数据库106、107和108进行了实验. 每个实验测量了服务器端搜索具有10—105个匹配文档的关键字的总时间(即不计算客户端的网络延迟和令牌生成时间). 实验重复了1000 次, 取平均值, 然后除以匹配文档的数量, 得到搜索单个条目的时间. 从图中可以看到, 随着更新文档数量的增加, 处理单个更新文档的时间会减少. 这是因为初始化搜索有一个固定的成本, 它被分摊到每个更新文档的处理时间中. 随着条目数量的增加, 摊销的初始化成本变得不那么重要.

图4 LAN 环境下106、107、108 的数据集的方案搜索性能对比Figure 4 Search performance comparison in 106、107 and 108 size dataset at LAN

图5 WAN 环境下106、107、108 的数据集的方案搜索性能对比Figure 5 Search performance comparison in 106、107 and 108 size dataset at WAN

根据图4 和图5 的实验数据可以发现, 随着数据库的容量增大, 对应的DSSE 方案的搜索效率都有一定程度的下降, 但整体的搜索效率趋势是大体一致的. 无论是在WAN 还是在LAN 的网络环境下,ECDSSE 方案的搜索效率都稳定优于FAST 方案. 根据具体的实验数据对比, 除了搜索匹配文档数量级为10 的关键字的搜索效率提升约为10%, 针对其他数量级的关键字的搜索效率提升均超过20%. 方案间的搜索效率差是由于本文算法在服务器端进行搜索时进行更少的加解密以及哈希操作. 在WAN 环境下,ECDSSE 方案和BESTIE 方案依然比FAST 方案的搜索效率更高, 但是由于存在网络延迟等其他原因,实际的性能表现比在LAN 环境中稍差. 在WAN 和LAN 环境中, ECDSSE 方案与BESTIE 方案的搜索效率差距均不大, 原因在于两个方案的服务端计算复杂度是一样的, 两者都有相同数量的耗时操作, 比如加解密操作以及哈希操作.

6.3 存储开销

表1 展示了ECDSSE、FAST 和BESTIE 方案的理论存储性能, 本小节将用实验数据展示并分析三者的存储开销.

在实验中, 我们采用RocksDB 键值对数据库来存储客户端的状态表, 即在本地以RocksDB 数据库的数据文件格式存储状态表. 实验选择的数据库有不同的数量级: 106、107和108, 它们分别包含约10 万个关键字、50 万个关键字和200 万个关键字. 实验数据如表3 所示, 在106级别的数据库中,ECDSSE 方案的存储开销相对于BESTIE 和FAST 方案分别减少12.5% 和61.1%; 在107级别的数据库中, ECDSSE 方案的存储开销相对于BESTIE 和FAST 方案分别减少16.1% 和54.0%; 在108级别的数据库中, ECDSSE 方案的存储开销相对于BESTIE 和FAST 方案分别减少13.0% 和60.4%. 由上述数据可知, BESTIE 方案的存储开销并没有比ECDSSE 少多少, 这是因为在编程实现中, 计数器按整型变量计算, 存储一个数需要4 个字节的存储空间, 但是在存入文件时可以转换为字符串, 在更新次数较少的情况下, 所需客户端存储空间小于4 个字节, 比如计数器的值为1, 按整型计算需要4 个字节, 转换为字符串存储只需要1 个字节, 因而在数据量不大的情况下, 差距不明显. 理论上, ECDSSE 方案相比BESTIE 方案在客户端存储开销上最多可以减少50%, 这是因为BESTIE 方案有2 个计数器, 而ECDSSE 方案只有1 个计数器, 在关键字个数一样的情况下, 存储开销由计数器的数量决定. 而FAST 方案的客户端存储开销比ECDSSE 方案高, 因为它除了在本地存有一个关键字更新次数的计数器之外, 还存有一个固定大小的随机字符串, 这导致了FAST 方案比ECDSSE 方案多(关键字个数* 随机字符串) 的数值大小的客户端存储开销.

表3 三种DSSE 方案的实际存储开销对比Table 3 Realistic storage cost among three DSSE schemes

本文提出了一种新的密码学原语循环加密链, 并基于该密码学原语及其通用构造提出了一种满足前向安全的高效DSSE 方案ECDSSE. 与FAST[5]方案相比较, ECDSSE 方案在保证安全性的情况下, 使用哈希函数实现密钥的生成, 避免了不必要的生成伪随机密钥的计算, 提高了更新效率, 并且通过提前加密文档标识符, 减少了不必要的异或加密操作, 提升了搜索效率, 并且将客户端的存储开销明显降低, 同时相对于FAST 方案将更新效率和搜索效率提高了约35% 和20%. 与BESTIE[7]方案相比, ECDSSE 方案在减少客户端存储开销上取得优势, 相比于BESTIE 方案可减少至少12.5% 的客户端存储开销.

满足前向安全的DSSE 方案具有实用性, 但是此类方案仍然不足以应对未来可能出现的因删除文档导致的信息泄露攻击. 为了应对这种挑战, 需要进一步研究后向安全的概念. 目前已有一些研究着力于实现满足后向安全的方案[22,23,29,30], 如何实现满足后向安全的DSSE 方案可作为进一步的研究方向.