1、华南师范大学学报(自然科学版)Journal of South China Normal University(Natural Science Edition)2022，54(6):109118doi:106054/jjscnun2022092收稿日期:20211219华南师范大学学报(自然科学版)网址:http:journalnscnueducn基金项目:国家自然科学基金项目(61672243)*通信作者:马昌社，Email:Chsma 163com支持多用户的高效前向安全可搜索加密方案马昌社*，李晓聪，陈海龙(华南师范大学计算机学院，广州 510631)摘要:大多数已有的前向安全可搜索加密
2、方案主要针对单用户环境，本地存储的关键词状态使得这些方案无法有效拓展到多用户环境;同时支持多用户检索的前向安全方案较少，且需要增设可信的代理服务器，带来了额外的开销，实用性不足。针对目前缺乏实用的多用户前向安全可搜索加密方案的问题，基于一个双链索引结构，设计了满足前向安全和支持多用户检索且无需增设代理服务器的可搜索加密方案(EMFS)。该方案中，双层索引结构由主链索引和侧链索引组成，其中主链索引由陷门单向函数和全局状态生成，不依赖于各个关键词的单独状态，从而避免了关键词状态在多用户间的同步问题;侧链索引采用流密码的方式生成，提高了搜索效率。并将 EMFS 方案与 3个现有的单用户前向安全方案(
3、Sophos、FAST、BESTIE)进行对比实验，实验结果表明 EMFS 方案有良好的拓展性和实用性:(1)EMFS 方案以合理的搜索性能代价实现了支持多用户检索的拓展;(2)EMFS 方案尤其适合匹配文件数较大的数据集;(3)EMFS 方案具有客户端存储开销小的优势。关键词:云存储;可搜索加密;前向安全;多用户中图分类号:TP309文献标志码:A文章编号:10005463(2022)06010910Efficient Forward Secure Searchable Symmetric Encryption for MultiuserMA Changshe*，LI Xiaocong，CH
4、EN Hailong(School of Computer Science，South China Normal University，Guangzhou 510631，China)Abstract:Most of the existing forward secure searchable encryption schemes are mainly for singleuser settings andcannot be easily extended to multiuser settings since the keyword state is maintained locally;th
5、ere are few forwardsecure schemes that support multiuser retrieval，and they require additional trusted proxy servers，which bringsadditional overhead and insufficient practicality Aiming at the current lack of practical multiuser forward securesearchable encryption scheme，a searchable encryption sche
6、me(EMFS)based on a twochain index structure isdesigned，which meets forward security and supports multiuser retrieval without the need for a proxy server Thedoublelayer index consists of the main chain index and a slave chain index The main chain index is generated bythe oneway trapdoor function and
7、the global state and does not depend on the separate state of each keyword，thusavoiding the synchronization problem of the keyword state among multiple users;the slave chain index is generatedby stream cipher，which improves the search efficiency Compared with three existing singleuser forward securi
8、tyschemes(Sophos，FAST，BESTIE)，the results show that the EMFS scheme has good scalability and practicabili-ty:(1)The EMFS scheme achieves the expansion of multiuser retrieval at a reasonable cost of search perfor-mance;(2)The EMFS scheme is especially suitable for matching datasets with a large numbe
9、r of files;(3)TheEMFS scheme has the advantage of small client storage overheadKeywords:cloud storage;searchable symmetric encryption;forward security;multiuser随着大数据时代的到来，数据量的高速增长使不少个人用户和企业选择将数据外包存储到云服务器上。云服务器一般被视为诚实且好奇的:诚实地执行程序，却存在窥探用户数据的可能。因此，一般将数据加密后再存储。但是，经过加密算法处理后的数据不支持快速检索，为了满足数据加密后的高效搜索需求，学术界
10、开始研究可搜索对称加密(Searchable Symmetric Encryption，SSE)技术。2000 年，SONG 等1 提出了实用对称可搜索加密的概念，并给出了第1 个 SSE 方案。此后，学者们提出了一系列在搜索性能、功能、安全性之间权衡的静态 SSE 方案26。如:为了提高搜索性能，GOH2 构建了基于正排索引的 SSE 方案，CUTMOLA 等3 给出了基于倒排索引的 SSE 方案;为了拓展更多功能特性，CASH 等4 提出了支持大数据集上联合查询的可搜索加密方案(OXT)，SUN 等5 将 OXT 方案拓展到了多用户场景，孙僖泽等6 提出了一个密态数据库查询框架，将可搜索加
11、密技术应用到了现有的主流数据库中。然而，已有的静态 SSE 方案无法满足现实中对文件进行动态更新的需求。2012 年，KAMAA 等7 提出了首个动态 SSE 方案(DynamicSSE，DSSE)，该方案实现了次线性级别的搜索效率，但因引入数据更新机制而导致易泄露更多信息;ZHANG 等8 针对 DSSE 方案的攻击指出，只需要注入不多于 100 个文件，就可恢复全部的关键字信息。为了减缓动态 SSE 方案中的文件注入攻击，STE-FANOV 等9 给出了 DSSE 方案中的前向安全定义，指出前向安全为 DSSE 方案的必备要求，并设计了一个基于茫然随机访问内存10(Obilivious a
12、ndomAccess Memory，OAM)的前向安全 DSSE 方案。支持前向安全的方案避免了旧的搜索令牌与新加入的密文文件产生关联，从而减缓隐私泄露。从技术角度概括，除了基于开销巨大的 OAM 的方案外，实现前向安全的方式主要可以分为以下 3 种:(1)通过单向函数构建索引。如 BOST11 首次基于公钥密码学原语设计了高效 DSSE 方案;HE 等12 通过原像不可逆的哈希函数构建索引，减少了客户端本地存储，但引入了更新次数的限制。(2)通过多次更换密钥重构索引。如 ETEMAD 等13 提出了基于重构索引的方案，该方案虽然不要求服务器有计算功能，但要求客户端为查询结果重新构造索引，因此
13、在搜索时的通信开销和客户端的计算开销巨大。(3)通过对称加密函数构建索引。如 SONG等14 针对文献 11 中公钥密码学原语带来的性能瓶颈，构造了基于对称密码学原语的前向安全方案，为目前理论搜索性能最优的前向安全 DSSE 方案。然而，在现有的前向安全 DSSE 方案中，大部分方案仅支持单用户环境，这是由于为了生成最新的搜索令牌，这些方案在客户端本地维护了一个存储了所有关键字状态信息的状态表，而关键字状态存储在本地使得方案难以支持多用户检索15。目前仅有的 2 种支持多用户检索的前向安全方案1617 增设了一个可信中间件来记录关键字状态，数据拥有者在动态更新后，将状态表保存在可信中间件中，其
14、他用户发起查询时，首先将搜索请求发送到可信中间件，再由可信中间件根据当时的状态表计算出最新的搜索令牌发送给服务器。尽管支持多用户检索的前向安全方案1617 为设计多用户前向安全DSSE 方案提供了思路，但在资源受限的情况下，增设可信服务器的方法并不实用。针对上述问题，本文提出了一个基于双链索引结构的支持多用户的高效前向安全可搜索加密方案(Efficient Multiuser Forward Secure SSE，EMFS)。该方案无需增设可信中间件，基于陷门单向函数构建主链索引，基于流密码寻址式结构构建从链索引，利用陷门函数在无密钥时的单向计算性，以及主索引链的长度不依赖于各关键词状态，实现
15、了前向安全和多用户;利用从链高效遍历的特性以及对主链检索长度的缓存优化，达到了搜索的高效性。最后，将 EMFS 方案与 Sophos11、FAST14、BESTIE18 方案进行对比实验。1预备知识11伪随机函数令 F:0，1 0，1n 0，1n是一个多项式时间可计算函数，如果对于任何敌手A，都有|Pr AF(K，)(1)=1 Pr Af()(1)=1|negl()成立，则称 F 是一个伪随机函数，其中第 1 个概率依赖于 K 0，1n的均匀随机性，第 2 个概率依赖于从 n 比特字符串映射到 n 比特字符串的函数集合中抽样出 f 的随机性。12陷门置换陷门置换(Trapdoor Permut
16、ation，TDP)是定义域与值域相同的陷门单向函数。对于给定的运行在置换域 D 的一个陷门置换，使用公钥 pk 可以快速地进行正向计算，使用私钥 sk 可以反向计算置换1。陷门置换是一个算法三元组(KeyGen，1)，其中:(1)(pk，sk)KeyGen()是一个随机生成算011华 南 师 范 大 学 学 报(自 然 科 学 版)第 54 卷法。其输入是安全参数，输出是公钥 pk 和私钥 sk。(2)y(pk，x)是一个确定性算法。其输入是公钥 pk 和原像 xD，输出是置换下的像 yD。(3)x(sk，y)是一个确定性算法。其输入是私钥 sk 和像 yD，输出是原像 xD。陷门置换还应满足以下安全性质:在没有私钥的情形下，反向计算置换1十分困难。任何一个PPT 敌手A在没有私钥的情况下成功求解反向置换的概率AdvA()negl()。13多用户 SSE 参与者一般来讲，多用户 SSE 系统的参与者由三方组成:(1)数据拥有者:数据拥有者将数据加密后存放到云服务器，并为密文数据生成检索索引，为被授权用户生成授权信息。此外，在支持动态更新的SSE 方案中，数据拥有者负责给新添加的文件选
