FSMS:具有最小本地存储开销的前向安全可搜索加密方案

FSMS:具有最小本地存储开销的前向安全可搜索加密方案 FSMS:A Forward Secure SSE Scheme with Minimal Client Storage Cost 1 2 first-author 周钦曦, 女, 硕士生, 现从事应用密码学可搜索加密方面的研究。E-mail：zhouqinxi@whu.edu.cn 周钦曦, 女, 硕士生, 现从事应用密码学可搜索加密方面的研究。E-mail： zhouqinxi@whu.edu.cn zhouqinxi@whu.edu.cn 1 2 corresp 何琨, E-mail：milloglobe@gmail.com 何琨, E-mail：milloglobe@gmail.com milloglobe@gmail.com 1 3 1 2 武汉大学 国家网络安全学院, 湖北 武汉 430072 武汉大学 国家网络安全学院, 湖北 武汉 430072 School of Cyber Science and Engineering, Wuhan University, Wuhan 430072, Hubei, China School of Cyber Science and Engineering, Wuhan University, Wuhan 430072, Hubei, China 武汉大学深圳研究院, 广东 深圳 518000 武汉大学深圳研究院, 广东 深圳 518000 Shenzhen Institute of Wuhan University, Shenzhen 518057, Guangdong, China Shenzhen Institute of Wuhan University, Shenzhen 518057, Guangdong, China 武汉大学 地球空间信息技术协同创新中心, 湖北 武汉 430079 武汉大学 地球空间信息技术协同创新中心, 湖北 武汉 430079 Collaborative Innovation Center of Geospatial Technology, Wuhan University, Wuhan 430079, Hubei, China Collaborative Innovation Center of Geospatial Technology, Wuhan University, Wuhan 430079, Hubei, China 提出了一种具有最小本地存储开销的前向安全高效可搜索加密方案FSMS, 设计了一个双层的加密存储结构, 利用该结构构造可搜索加密方案将逆向索引的存储开销转移到服务端。双层加密存储结构中的第一层结构是根据全局状态生成搜索令牌的逻辑结构, 这一结构代替了原来逆向索引的作用, 减少了本地的存储开销; 第二层结构优化了计算开销。利用双层加密存储结构设计的动态可搜索加密方案达到了前向安全属性, 并且没有增加额外的计算和通信开销。将本文方案与三个现有方案进行对比, 结果表明, 本文方案虽然减少了本地的存储开销, 但依旧具备较高的搜索效率。 In this paper, we propose the efficient and forward secure SSE(symmetric searchable encryption)scheme with minimal client storage cost, called FSMS. We propose a two-level structure for an SSE scheme to transfer the cost of inverted index structures on the user side to the server side. The first level of the two-level structure is a logic structure which generates the search token based on the global state. With the structure, we can replace the role of inverted index and reduce client storage cost. The second level optimizes the computational cost. The dynamic SSE scheme which is designed by the two-level structure achieves forward security and adds no extra computational and communicational cost. Compared with the existing three methods, Extensive experiments show that the efficiency of FSMS is as well as the state-of-the-art solution, while the storage cost on the user side is reduced. 可搜索加密 前向安全 本地存储 searchable encryption forward security client storage 引言 1 随着云服务的兴起和大数据时代的到来, 企业和个人都习惯于将重要的数据存储在云上, 为保证隐私数据的安全, 云服务的客户需要将敏感数据加密后存储。但是, 加密操作在保护数据安全的同时, 也限制了云服务端进行有效操作(如搜索、计算)的能力。如果需要对加密数据进行操作, 则需将所有加密文件下载到本地, 解密后进行相关操作, 这种方式消耗大量的通信和计算开销。为了解决这一问题, 可搜索加密 [ 1 1 ~ 3 3 1~3 ] (searchable encryption, SE)技术应运而生。SE实现了在加密数据上直接进行关键词搜索的功能。SE主要包含对称可搜索加密(symmetric searchable encryption, SSE)和非对称可搜索加密(asymmetric searchable encryption, ASE) [ 4 4 , 5 5 ] 两种类型, 这两种类型根据不同的需求解决不同的现实问题, 本文研究的方案围绕SSE, 设计的方案也属于SSE类型。 早期的SSE研究工作集中在静态方案上, 即静态对称可搜索加密(static symmetric searchable encryption)。这类方案在用户将私有数据上传到半可信(semitrusted)服务端后, 只会进行关键词搜索, 而不会再对加密数据集进行任何操作 [ 6 6 ~ 10 10 6~10 ] 。显然, 静态SSE方案在实际中是不适用的, 因此动态SSE(dynamic SSE, DSSE)方案被提出。DSSE方案允许进行文件更新操作, 如添加和/或删除文件 [ 11 11 ~ 18 18 11~18 ] 。 然而, 现有的DSSE方案在实际应用中仍然面临严峻的考验。为了在更新和搜索过程中提供更优的计算复杂度 [ 11 11 , 12 12 ] , 许多方案使用了逆向索引(inverted index)的结构, 但其中一些方案无法保证前向安全(forward security) [ 14 14 , 18 18 ] 。前向安全是动态可搜索加密中的一个安全概念, 保证前向安全的可搜索加密方案在进行更新操作后, 服务端无法判断新添加的文件中是否包含搜索过的关键词。为了实现前向安全, 一些研究人员使用了复杂的密码学原语, 如ORAM(oblivious RAM) [ 19 19 ~ 22 22 19~22 ] 来实现方案, 这些复杂的密码技术会在搜索和/或更新过程中造成沉重的计算和通信开销负担 [ 13 13 , 18 18 ] 。目前, 已有方案中存在同时达到前向安全和理论最优计算复杂度的方案 [ 14 14 , 15 15 ] (关于“最优”, 将在第4. 1节说明), 但这些方案在实际应用中表现欠佳, 此外还存在文件更新数量受限问题。尤其, 当前没有任何高效方案在客户端达到固定的存储开销。 针对上述问题, 本文提出了采用双层加密存储结构的FSMS方案。第一层结构减少了存储开销, 增加了客户端的计算开销; 第二层结构优化了计算开销。双层加密存储结构的设计达到了前向安全属性。 基础概念 1 符号 2 对于一个有限集合 X , http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465545&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465545&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465545&type=middle 表示 x 是从集合 X 中随机抽取出来的。| X |表示集合 X 中的元素个数。操作||表示字符串的连接。{0, 1} l 表示长度为 l 的二进制字符串集合, {0, 1} * 表示任意有限长度的二进制字符串集合。 如果对于所有正多项式 p (·)和所有足够大的参数 k , 函数 g ( k )＜1/ p ( k )都成立, 则称函数 g : http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465522&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465522&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465522&type=middle 是在参数 k 上可忽略的。用 f ( k )=neg l ( k )表示存在一个可忽略函数 g (·)对于所有足够大的 k 都有 f ( k )≤ g ( k )。 λ ∈ http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465525&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465525&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465525&type=middle 表示安全参数。除非特别说明, 本文中的对称密钥都是比特长度为 λ 的字符串, 并且密钥生成函数是从{0, 1} λ 中随机生成密钥的。 本文仅考虑在安全参数 λ 下运行时间为概率多项式时间(probabilistic polynomial time, PPT)的算法和协议。特别地, 敌手是概率多项式时间算法。 客户端和服务端之间的两方协议 P 表示为 P (cin; sin) → (cout; sout), 客户端将cin作为输入并输出cout, 服务端将sin作为输入并输出sout。 动态对称可搜索加密(DSSE) 2 一个文件doc=(ind, W ind )用ind∈{0, 1} * 进行标记, ind表示文件标识符, 该文件包含关键词集合 W ind ⊆{0, 1} * ; 数据集DB表示为(ind i , W ind i ) i =1 n , 其中 n 表示数据集DB中文件的个数; DB中关键词集合表示为 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465527&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465527&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465527&type=middle , 包含关键词 w 的文件集合表示为DB( w )= {ind i | w ∈ W ind i }; N 表示一个文件数据集中所包含的关键词/文件对的数量(如, 一个文件数据集包含ind 1, ind 2, ind 3, 其中 W ind 1 ={ w 1 , w 2 }, W ind 2 ={ w 2 , w 3 }, W ind 3 ={ w 1 , w 2 , w 4 }, 则该文件数据集中所包含的关键词/文件对的数量为7), m =| W |表示关键词的数量。显然, N = http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465529&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465529&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465529&type=middle 一个DSSE方案∏={Setup, Search, Update}由三个客户端和服务端之间的协议组成。 Setup( λ ; ⊥) → ( σ ; EDB)是创建协议。客户端输入安全参数 λ 并创建一个状态 σ , 服务端初始化加密数据集EDB。 Search ( w , σ ; EDB) → ( σ ', DB( w ); EDB')是搜索协议。客户端输入关键词 w 和状态 σ , 服务端输入加密数据集EDB。协议运行后, 客户端得到搜索结果DB( w ), 即包含关键词 w 的所有文件, 并且更新状态为 σ ', 服务端将加密数据集更新为EDB'。 Update( σ , DOC, op; EDB) → ( σ '; EDB')是更新协议。客户端输入状态信息 σ , 在文件集DOC上进行op操作, 得到新状态 σ '。操作op∈{add, del}, add表示文件集DOC的添加, del表示删除操作。服务端输入加密数据集EDB, 经过协议, 得到更新后的EDB'。 双层加密存储结构 1 双层加密存储结构由逻辑关键词索引链和文件索引链组成。具体描述如下。 逻辑关键词索引链 2 在多数已有的前向安全DSSE方案中, 用户需要在本地存储一个逆向索引, 这一结构为每一个关键词存储了当前的状态信息用于生成搜索令牌。因此, 这些状态信息的存储开销和数据集中关键词的数量成正比。为解决这一问题, 本文设计了一个逻辑关键词索引链代替客户端的逆向索引, 该结构仅需在客户端存储一个密钥和一个全局计数器。有了这个逻辑结构, 用户可以通过计算得出每个关键词的搜索令牌。 对于每一个关键词, 都存在一条逻辑关键词索引链, 这些索引链实际上是一条哈希链, 并且共享一个全局计数器, 链中的每一个节点对应该关键词的一个搜索令牌。为了生成一个关键词的所有搜索令牌, 用户可以利用全局计数器和密钥计算出该关键词的其中一个搜索令牌, 该令牌在当前的关键词索引链中处于头节点的位置, 然后用户将计算得出的这一个搜索令牌发送给服务端, 服务端根据收到的令牌生成该关键词剩余的搜索令牌。 F (·, ·)表示伪随机函数, H (·)表示哈希函数。对于一个字符串 x ∈{0, 1}*, H j ( x )定义如下: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465487&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465487&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465487&type=middle 对于关键词 w 和当前的全局计数器ctr, 用户可以计算出关键词令牌kt w = F (key, w )和搜索令牌 H ctr (kt w ), 其中key是密钥。在服务端的逻辑关键词索引链上剩下的搜索令牌是: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465490&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465490&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465490&type=middle 其中ChainLen是在创建协议时初始化的一个常量。根据哈希链的单向可推导属性, 用户可以计算出链上任何节点的前驱节点(实际上用户可以计算任意节点), 但是服务端只能根据一个节点的值计算出该节点的后继节点。 搜索过程中, 在客户端需要进行ctr次哈希计算, 在服务端还需要计算ChainLen—ctr次哈希计算, 这部分计算会造成额外的计算开销。但是这部分额外开销在实际应用中是可以被接受的。 文件索引链 2 如果每个搜索令牌只能对应一个关键词/文件对, 则当更新的关键词/文件对数量庞大时, 逻辑关键词索引链的全局计数器会迅速耗尽。为了解决这个问题, 本文在逻辑关键词索引链的上层设计了另一个结构——文件索引链。双层加密存储结构如 图 1 图 1 所示。逻辑关键词索引链上的每个节点指向一条文件索引链, 这个文件索引链可能是空的, 一条文件索引链表示一次更新中包含某一特定关键词的文件。有了文件索引链, 就可进行ChainLen次文件集的更新, 而不需要考虑一次更新中包含的文件集合的大小。 文件索引链的技术细节描述如下。假设在一次更新中有 d 个文件(ind u 1 , ind u 2 , ⋯, ind u d )包含有关键词 w , 其中 u 1 , u 2 , ⋯, u d ∈{1, 2, ⋯, n }。在这次更新中, 对于关键词 w , 文件索引链包含 d 个节点: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465497&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465497&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465497&type=middle 其中, r 1 , r 2 , ⋯, r d -1 都是随机数。文件索引链的头节点用 H ( H j (kt w )||0)作标记, 其中 H j (kt w )是逻辑关键词索引链上的节点的值, j 是添加关键词/文件对时的全局计数器。文件索引对的每个节点存储了一次批量更新中添加的文件标识符, 随机数用于生成下一个节点的标记。特别地, 文件索引链的最后一个节点保存的是一个文件标识符和一个特殊符号⊥, 这个符号表示在本次更新中该文件是最后一个包含该关键词的文件。 本文方案FSMS 1 方案概述 2 FSMS的系统模型如 图 2 图 2 所示, 它包含三个协议:Setup(), Update()和Search (), 如 图 3 图 3 。在Setup()阶段, 数据拥有者初始化SSE整体方案中会被用到的值和结构。在Update()阶段, 数据拥有者加密关键词/文件对并上传到服务端, 用于后续的搜索。在Search ()阶段, 数据拥有者根据关键词和当前的全局计数器生成搜索令牌并将搜索令牌发送给服务端。然后, 服务端利用搜索令牌计算出逻辑关键词索引链上的所有节点, 并搜索存放在文件索引链上的文件。 主要协议 2 Find (SET, a )是一个函数, 返回字典SET中用 a 做标记的所有元素。 创建协议。Setup()协议的描述如算法1所示。在FSMS中, 逻辑关键词索引链的长度提前设置为一个常量ChainLen, 因此, 本文的创建协议用Setup(ChainLen, λ ; ⊥) → ( σ ; EDB)表示。    客户端: 1  ctr ← ChainLen; key ← {0, 1} λ 2   σ ← (key, ctr); EDB ← ∅ 3  把EDB发送给服务端 因为状态信息只包含全局计数器ctr和密钥key, 所以客户端的存储开销是一个常量并且非常小。客户端为双层加密存储结构创建一个空的加密数据集EDB并发送给服务端。 更新协议。Update()协议的描述如算法2所示。在FSMS中, 只考虑添加操作, 因此使用Add ( σ , DOC; EDB)来表示更新操作。 客户端: 1  把 σ 解析为(key, ctr) 2  ADD ← Ø; KW ← Ø; r ← 0 3   while |DOC|≠ 0 do 4     http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465530&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465530&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465530&type=middle 5    把doc解析为(ind, W ind ) 6    DOC ← DOC\{doc} 7     W ← W ind 8     while | W |≠ 0 do 9      w http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465533&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465533&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465533&type=middle 10      if Find(KW, w ) =⊥ then 11      kt w ← F (key, w ) 12      St w ← H ctr (kt w ) 13      KW ← KW∪( w , St w ) 14      entry ←( H (St w ||0), ( H (St w ||1)⊕(ind||⊥))) 15      ADD ← ADD∪{entry} 16      else 17      St w ← Find(KW, w ) 18       http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465537&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465537&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465537&type=middle 19      temp ← Find(ADD, H (St w ||0)) 20      把temp解析为             ( H (St w ||0), ( H (St w ||1)⊕Message)) 21      ADD ← ADD\{temp} 22      entry 1 ←( H (St w ||0), ( H (St w ||1)⊕(ind|| r ))) 23      entry 2 ←( H ( r ||0), H ( r ||1)⊕Message) 24      ADD ← ADD∪{entry 1 , entry 2 } 25  σ ′←(key, ctr—1) 26 把ADD发送给服务端 服务端: 1  EDB′← EDB∪ADD 当添加一个文件集DOC到加密数据集EDB时, FSMS对每一个关键词/文件对进行操作。首先, 客户端提取每一个文件doc, 然后抽取出该文件中的每一个关键词。如果关键词 w 不在临时字典KW中, 客户端需要为该关键词计算出搜索令牌St w = H ctr (kt w ), 其中kt w = F (key, w )是关键词令牌。然后, 客户端加密文件标识符ind, 并将它用 H (St w ||0)标记后加到添加字典ADD中。如果 w 在临时字典KW中, 则表示已有包含该 w 的文件被添加。此时, 将原来用 H (St w ||0)标记的文件重新用一个随机数标记, 该随机数保存在新添加的文件的节点信息中, 新添加的文件用 H (St w ||0)标记。最后, 客户端更新状态并将添加字典ADD发送给服务端。 更新协议(添加协议)在服务端的存储、计算、通信复杂度和文件集DOC中关键词/文件对的数量有关, 和文献[ 14 14 , 23 23 ]一样, 本文的复杂度达到了最优。常量ChainLen表示可以进行ChainLen次更新操作。此外, 在全局计数器归零后再进行添加操作就需要用新的密钥和计数器重构双层加密存储结构。 搜索协议。Search ()协议的描述如算法3所示。为了找到加密数据集EDB中包含关键词 w 的所有文件, 客户端通过对关键词令牌kt w = F (key, w )进行ctr次哈希计算得出搜索令牌St w 。然后, 客户端把St w 和全局计数器ctr一起发送给服务端, 服务端计算出逻辑关键词索引链上关键词 w 的其他搜索令牌: 客户端: 1  把 σ 解析为(key, ctr) 2  kt w ← F (key, w ), St w ← H ctr (kt w ) 3   σ ′ ← σ 4  把St w , ctr发送给服务端 服务端： 1   j ← ctr; SearchDOC ← Ø 2   while j ≤ ChainLen do 3     if Find (EDB, H (St w ||0)) =⊥ then 4       j ← j +1 5      St w ← H (St w ) 6     else 7      把Find (EDB, H (St w ||0))解析为        ( H (St w ||0), H (St w ||1)⊕Message) 8      把Message解析为(ind|| R ) 9       while R ≠⊥ do 10        SearchDOC ← SearchDOC∪{ind} 11        result ← Find (EDB, H ( R ||0)) 12        把result解析为          ( H ( R ||0), ( H ( R ||1)⊕(ind|| T ))) 13         R ← T 14      SearchDOC ← SearchDOC∪{ind} 15       j ← j +1 16      St w ← H (St w ) 17  DB ( w ) ← SearchDOC 18  EDB′ ← EDB 19  把DB ( w )发送给客户端 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465510&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465510&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465510&type=middle 对于逻辑关键词索引链上的每个节点, 服务端搜索头节点是( H (St w ||0), H (St w ||1)⊕(ind, R ))的非空文件索引链。从该节点所存储的信息中, 服务端可以利用随机数 R 继续找出其他文件, 直到 R =⊥。在服务端完整的检索过逻辑关键词索引链和文件索引链的所有节点之后, 就可以得到完整的文件集DB( w )。 搜索操作的计算复杂度是 O (ChainLen+|DB( w )|), 比最优的计算复杂度 O (|DB( w )|)稍大一点, 而当|DB( w )|≫ChainLen, 就可以忽略ChainLen的值并把FSMS的复杂度看作最优复杂度。通信复杂度是理论情况下的最优值 O (|DB( w )|)。 评估 1 理论评估 2 本节对已有方案和本文方案的计算复杂度、通信复杂度、客户端存储复杂度进行理论评估, 如 表 1 表 1 所示。在 表 1 表 1 中, N 表示文件集中包含的关键词/文件对的个数, n 表示文件个数, m 表示关键词个数。 n w 表示文件集中包含关键词 w 的文件个数, a w 表示被添加到文件集中包含关键词 w 的文件个数, d w 表示从文件集中删除的包含关键词 w 的文件个数。显然 n w = a w - d w 。符号 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465540&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465540&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465540&type=middle 隐藏了多重对数因子(即 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465540&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465540&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465540&type=middle ( g (·))= O ( g (·)log k ( g (·))), 省略了其中的对数因子)。 表 1 表 1 中所给的更新复杂度是针对每个关键词/文件对。 2 方案 2 计算复杂度 3 通信复杂度 2 客户端存储复杂度 搜索 更新 搜索 轮数 更新 SPS [ 18 18 ] O (min{ a w +log N , n w log 3 N }) O (log 2 N ) 8 O ( n w +log N ) 1 O (log N ) O ( N α ) TWORAM [ 13 13 ] http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465541&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465541&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465541&type=middle http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465542&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465542&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465542&type=middle http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465543&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465543&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465543&type=middle 2 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465545&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465545&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465545&type=middle O (1) Sophos [ 14 14 ] O ( a w ) O (1) O ( n w ) 1 O (1) O ( m ) KKL+ [ 23 23 ] O ( a w ) O (1) O ( n w ) 1 O (1) O ( m ) Fides [ 15 15 ] O ( a w ) O (1) O ( a w ) 2 O (1) O ( m ) Diana del [ 15 15 ] O ( a w ) O (log a w ) O ( n w + n w log a w ) 2 O (1) O ( m ) Janus [ 15 15 ] O ( n w · d w ) O (1) O ( n w ) 1 O (1) O ( m ) FSMS O (ChainLen+ a w ) O (1) O ( n w ) 1 O (1) O (1) 表 1 表 1 中的所有方案都满足前向安全属性, 服务端的存储复杂度均为理论最优复杂度的值。所谓“最优”, 在可搜索加密方案中, 计算复杂度方面: 1)最优的搜索复杂度为 O ( a w ), 因为搜索操作至少要对所有添加进文件集的包含指定关键词的文件进行搜索; 2)最优的更新复杂度为 O (1), 因为对于每个关键词/文件对都需要执行相应的更新操作。通信复杂度方面: 1)最优的搜索复杂度为 O ( n w ), 因为搜索的通信过程中需要将包含指定关键词的文件都传送给客户端; 2)更新复杂度为 O (1), 因为每个关键词/文件对信息都要发送给服务端。 从 表 1 表 1 中不难发现, 本文方案除了搜索过程中的计算复杂度稍高(比 O ( a w )大了 O (ChainLen)), 其他均为最优, 而ChainLen是常量, 因此可以将FSMS看作是具有最优搜索、更新效率的可搜索加密方案。 实验评估 2 将本文方案FSMS和几个相关方案进行对比。用Python 3实现了所有方案, 并使用Python Cryptography Toolkit(pycrypto)实现了其中的加密函数部分。伪随机函数 F 用HMAC实现。实验运行在装有Linux Ubuntu 14.04.5操作系统的服务器上, 该服务器配有2个Intel Xeon E5-2630 v3的CPU和128 GB的RAM。 数据集 3 采用著名的Enron邮件数据集来评估, 该数据集未解压时为1.32 GB。为了从该邮件数据集中抽取关键词, 本文使用了一个用Python语言实现的快速自动化关键词抽取工具RAKE。在丢弃掉一些用BASE64编码的文件后, 剩余527 080个明文文件。从这些文件中, 共抽取出390 423个关键词和22 900 317个关键词/文件对。为分析数据集的大小对实验的影响, 本文从Enron邮件数据集中派生出3个小的数据集。数据集信息如 表 2 表 2 所示。 数据集 文件个数( n ) 关键词个数( m ) 关键词/文件对的个数( N ) DB1 4 000 15 879 127 723 DB2 20 000 58 310 874 604 DB3 100 000 168 793 5 493 993 Enron 517 080 390 423 22 900 317 客户端存储评估 3 本文方案FSMS和其他方案(Sophos [ 14 14 ] , KKL+ [ 23 23 ] 和Diana del [ 15 15 ] )在客户端存储开销对比如 表 3 表 3 所示。由于KKL+方案在DB3和Enron上运行需要超过一周的时间, 因此本文放弃了这两个实验。 5 KB 方案 DB1 DB2 DB3 Enron Sophos 7 830 30 393 92 221 209 564 KKL+ 5 177 19 063 - - Diana del 233 920 2 757 6 792 FSMS 2 2 2 2 从 表 3 表 3 中可以看出, Sophos, KKL+和Diana del 的存储开销随着数据集的增大而增大, 而FSMS的客户端存储空间始终仅需要2 KB。这是因为这些方案需要在客户端存储每一个关键词的状态信息, 而本文方案FSMS仅需要存储一个密钥和一个全局计数器。因此FSMS是惟一达到常量级客户端存储开销的方案。 计算评估 3 本节将讨论本文和其他方案(Sophos [ 14 14 ] , KKL+ [ 23 23 ] 和Diana del [ 15 15 ] )在更新和搜索过程中的计算开销。实验在实现Diana del 时, 数据集DB1、DB2、DB3使用高度为16的树, Enron邮件数据集使用高度为18的树, 两棵树分别能够添加32 768和131 072个文件。 1) 更新时间 表 4 表 4 展示了4个方案在4个不同数据集上的更新时间。从 表 4 表 4 中可看出, FSMS和Diana del 方案的更新效率远优于其他两个方案, 尤其是KKL+。Sophos需要在更新过程中进行多次幂运算来生成搜索令牌和更新令牌, 因此在实际应用中非常低效。KKL+方案中, 逆向索引的状态和双重字典需要经常更新, 这使得该方案效率最差。Diana del 和FSMS只需要计算哈希函数来更新整个数据集, 因此, 这两个方案在实际中比较高效。此外, 本文还考虑了逻辑关键词索引链的长度对方案效率的影响。如 表 4 表 4 所示, 更新时间随着ChainLen的增大而增大, 这是因为逻辑关键词索引链的长度决定了进行哈希计算的次数。当ChainLen达5 000, FSMS的计算开销还是可接受的。 方案 ChainLen DB1/min DB2/min DB3/min Enron/min Sophos - 26.68 196.76 1 274.65 5 511.63 KKL+ - 227.01 6 081.66 - - Diana del - 0.33 1.35 4.55 14.15 200 0.31 1.38 5.10 16.78 500 0.69 2.68 9.19 25.68 FSMS 1 000 1.28 5.02 16.20 41.05 2 000 2.59 9.48 29.35 72.28 5 000 6.38 23.1 69.14 165.23 2) 搜索过程中的计算开销 因为KKL+的计算开销太大(当搜索到的文件数为1时的搜索时间为1.33 s), 本文丢弃了该方案的实验结果, 只选取了Sophos和Diana del 与本文方案比较( 图 4 图 4 )。从 图 4 图 4 可以看出, FSMS的性能在匹配到的文件数较大时优于其他两个方案。 图 5 图 5 描述了FSMS在4个数据集上的搜索性能, 搜索结果表明, 搜索时间和数据集的大小无关。随着数据集的增大, 匹配到的文件数会增大, FSMS更适用于大数据集。 结语 1 本文方案FSMS与Sophos, KKL+和Diana del 都是前向安全的SSE方案。虽然KKL+在理论分析中达到了最优计算复杂度, 但是该方案在实际应用中性能非常差。这一事实也促使我们设计出实际应用中高效的前向安全SSE方案。Sophos方案同样在实际应用中不够高效是因为该方案中采用了公钥加密技术。Diana del 的性能和本文相似。但是, Diana del 方案不够灵活, 该方案对于同一关键词能够存储的文件数有限制。相反地, FSMS仅仅限制了更新次数(如果每天进行一次更新, 长度为500的逻辑关键词索引链可以使用一年), 而不是一次更新中的文件数。综上所述, FSMS是在实际应用中达到高效搜索并且客户端存储开销为常量的前向安全SSE方案。 参考文献 SONG D X, WAGNER D, PERRIG A. Practical techniquesfor searches on encrypted data[C]// Proceeding 2 000 IEEE Symposium on Security and Privacy . Washington D C: IEEE, 2000: 44-55. DOI: 10.1109/SECPRI.2000.848445 http://dx.doi.org/10.1109/SECPRI.2000.848445 . 李经纬, 贾春福, 刘哲理, 等.可搜索加密技术研究综述[J].软件学报, 2015, 26(1): 109-128. DOI:10.13328/j.cnki.jos.004700. LI J W, JIA C F, LIU Z L, et al . Survey on the searchable encryption[J]. Journal of Software , 2015, 26(1):109-128. DOI: 10.13328/j.cnki.jos.004700 (Ch). 徐鹏, 金海.可搜索加密的研究进展[J].网络与信息安全学报, 2016, 2(10): 8-16. DOI: 10.11959/j.issn.2096-109x.2016.00101. XU P, JIN H. Research on the searchable encryption[J]. Chinese Journal of Network and Information Security , 2016, 2(10): 8-16.DOI: 10.11959/j.issn.2096-109x.2016.00101(Ch). 李双, 徐茂智.基于属性的可搜索加密方案[J].计算机学报, 2014, 37(5): 1017-1024. DOI:10.3724/SP.J.1016.2014.01017. LI S, XU M Z. Attribute-based public encryption withkeyword search[J]. Chinese Journal of Computers , 2014, 37(5): 1017-1024. DOI: 10.3724/SP.J.1016.2014.01017 (Ch). 秦志光, 徐骏, 聂旭云, 等.公钥可搜索加密体制综述[J].信息安全学报, 2017, 2(3): 1-12. DOI: 10.19363/j.cnki.cn10-1380/tn.2017.07.001. QIN Z G, XU J, NIE X Y, et al . A survey of public-keyencryption with keyword search[J]. Journal of Cyber Security , 2017, 2(3):1-12. DOI:10.19363/j.cnki.cn10-1380/tn.2017.07.001 (Ch). CURTMOLA R. Searchable symmetric encryption: Improved definitions and efficient constructions[C]// ACM Conference on Computer and Communications Security 2 006.New York: ACM, 2006: 79-88. DOI: 10.1145/1180405.1180417 http://dx.doi.org/10.1145/1180405.1180417 . CHASE M, KAMARA S. Structured encryption and controlled disclosure[C]// International Conference on the Theory and Application of Cryptology and Information Security . Heidelberg: Springer-Verlag, 2010: 577-594.DOI: 10.1007/978-3-642-17373-8_33 http://dx.doi.org/10.1007/978-3-642-17373-8_33 . CASH D, JARECKI S, JUTLA C, et al . Highly-scalablesearchable symmetric encryption with support for booleanqueries[C]// Annual Cryptology Conference . Heidelberg: Springer-Verlag, 2013: 353-373. DOI: 10.1007/978-3-642-40041-4_20 http://dx.doi.org/10.1007/978-3-642-40041-4_20 . CASH D, TESSARO S. The locality of searchable symmetric encryption[C]// Annual Conference on the Theory and Applications of Cryptographic Techniques . Heidelberg: Springer-Verlag, 2014: 351-368. DOI: 10.1007/978-3-642-55220-5_20 http://dx.doi.org/10.1007/978-3-642-55220-5_20 . ASHAROV G, NAOR M, SEGEV G, et al . Searchablesymmetric encryption: Optimal locality in linear space viatwo-dimensional balanced allocations[C]// Proceeding of the Forty - Eight Annual ACM Symposium on Theory of Computing . New York: ACM, 2016: 1101-1114. DOI: 10.1145/2897518.2897562 http://dx.doi.org/10.1145/2897518.2897562 . KAMARA S, PAPAMANTHOU C, ROEDER T. Dynamic searchable symmetric encryption[C]// Proceeding of the 2 012 ACM Conference on Computer and Communications Security . New York: ACM, 2012: 965-976. DOI: 10.1145/2382196.2382298 http://dx.doi.org/10.1145/2382196.2382298 . KAMARA S, PAPAMANTHOU C. Parallel and dynamicsearchable symmetric encryption[C]// International Conference on Financial Cryptography and Data Security .Heidelberg: Springer-Verlag, 2013: 258-274. DOI: 10.1007/978-3-642-39884-1_22 http://dx.doi.org/10.1007/978-3-642-39884-1_22 . GARG S, MOHASSEL P, PAPAMANTHOU C.TWORAM: Efficient oblivious RAM in two rounds withapplications to searchable encryption[C]// Annual International Cryptology Conference . Heidelberg: SpringerVerlag, 2016: 563-592. DOI: 10.1007/978-3-662-53015-3_20 http://dx.doi.org/10.1007/978-3-662-53015-3_20 . BOST R. ∑oφoς: Forward secure searchable encryption [C]// Proceedings of the 2 016 ACM SIGSAC Conference on Computer and Communications Security . New York: ACM, 2016: 1143-1154. DOI: 10.1145/2976749.2978303 http://dx.doi.org/10.1145/2976749.2978303 . BOST R, MINAUD B, OHRIMENKO O. Forward andbackward private searchable encryption from constrained cryptographic primitives[C]// Proceedings of the 2 017 ACM SIGSAC Conference on Computer and Communications Security . New York: ACM, 2017: 1465-1482. DOI: 10.1145/3133956.3133980 http://dx.doi.org/10.1145/3133956.3133980 CHAMANI J G, PAPADOPOULOS D, PAPAMANTHOU C, et al . New constructions for forward and backward private symmetric searchable encryption[C]// Proceedings of the 2 018 ACM SIGSAC Conference on Computer and Communications Security . New York: ACM, 2018: 1038-1055. DOI: 10.1145/3243734.3243833 http://dx.doi.org/10.1145/3243734.3243833 . SUN S F, YUAN X L, LIU J K, et al . Practical backward-secure searchable encryption from symmetric puncturable encryption[C]// Proceedings of the 2 018 ACM SIGSAC Conference on Computer and Communications Security . New York: ACM, 2018: 763-780. DOI: 10.1145/3243734.3243782 http://dx.doi.org/10.1145/3243734.3243782 . STEFANOV E, PAPAMANTHOU C, SHI E. Practical dynamic searchable encryption with small leakage[DB/OL]. [2019-01-20] . https : // www.ndss - symposium.org / wp - content / uploads /2017/09/07_2_1. pdf . 2014. DOI: 10.14722/ndss.2014.23298 http://dx.doi.org/10.14722/ndss.2014.23298 . GOLDREICH O, OSTROVSKY R. Software protectionand simulation on oblivious RAMs[J]. Journal of the ACM ( JACM ), 1996, 43(3): 431-473. DOI: 10.1145/233551.233553. PINKAS B, REINMAN T. Oblivious RAM revisited[C]// Annual Cryptology Conference . Heidelberg: SpringerVerlag, 2010: 502-519. DOI: 10.1007/978-3-642-14623-7_27 http://dx.doi.org/10.1007/978-3-642-14623-7_27 . SHI E, CHAN T H H, STEFANOV E, et al . Oblivious RAM with O (log 3 N )worst-case cost[C]// International Conference on the Theory and Application of Cryptology and Information Security . Heidelberg: Springer Verlag, 2011: 197-214. DOI: 10.1007/978-3-642-25385-0_11 http://dx.doi.org/10.1007/978-3-642-25385-0_11 . STEFANOV E, VAN DIJK M, SHI E, et al . PathORAM: An extremely simple oblivious RAM protocol [C]// Proceedings of the 2 013 ACM SIGSAC Conference on Computer and Communications Security . New York: ACM, 2013: 299-310. DOI: 10.1145/2508859.2516660 http://dx.doi.org/10.1145/2508859.2516660 . KIM K S, KIM M, LEE D, et al . Forward secure dynamicsearchable symmetric encryption with efficient updates[C]// Proceedings of the 2 017 ACM SIGSAC Conference on Computer and Communications Security . New York: ACM, 2017: 1449-1463. DOI: 10.1145/3133956.3133970 http://dx.doi.org/10.1145/3133956.3133970 . 10.14188/j.1671-8836.2019.05.009 TP309 whdxxblxb-65-5-479 国家自然科学基金（U1836202, 6177238361572380, 61702379）, 装备预研教育部联合基金（6141A02033341）, 深圳市科技创新计划（JCYJ20170303170108208）, 广东优世联合集团基金 2019-01-30 2019-10-24 2020-12-10 版权所有© 2019 《武汉大学学报(理学版)》编辑部 Copyright © 2019 Journal of Wuhan University(Natural Science Edition). All rights reserved. 2019 武汉大学学报(理学版) 5 65