论文标题：IXT: Improved searchable encryption for multi-word queries based on PSI

期刊：Frontiers of Computer Science

作者：Yunbo YANG, Xiaolei DONG, Zhenfu CAO, Jiachen SHEN, Shangmin DOU

发表时间：15 Oct 2023

DOI： 10.1007/s11704-022-2236-9

微信链接：点击此处阅读微信文章

原文信息

标 题：

IXT: Improved searchable encryption for multi-word queries based on PSI

发表年份：

2023年

原文链接：

https://journal.hep.com.cn/fcs/EN/10.1007/s11704-022-2236-9

引用格式：

Yunbo YANG, Xiaolei DONG, Zhenfu CAO, Jiachen SHEN, Shangmin DOU. IXT: Improved searchable encryption for multi-word queries based on PSI. Front. Comput. Sci., 2023, 17(5): 175811

01

导读

遗忘交叉标签(Oblivious Cross-Tags, OXT)是单写单读框架中第一个用于联合查询的高效可搜索加密(searchable encryption, SE)协议。但是，它也需要在安全性和效率之间进行权衡，因为它会将部分数据库信息泄露给服务器。最近对这些SE方案的攻击表明，这些SE方案的泄漏可以用来恢复查询关键字的内容。为了解决这个问题，Lai等提出了隐藏交叉标签(Hidden Cross-Tags, HXT)，减少了从关键字对结果模式(Keyword Pair Result pattern, KPRP)到完整结果模式(Whole Result pattern, WRP)的访问模式泄漏。但是，WRP泄漏也可以用来恢复查询关键字的一些附加内容。

本文提出了一种基于标记私有集交集实现模式隐藏访问和搜索的高效可搜索加密协议——改进交叉标签(IXT)，本文还证明了所提出的标记私有集交叉(PSI)协议对半诚实对手是安全的，IXT是半诚实安全的(是泄漏函数)。最后，对IXT和HXT进行了实验比较。实验结果表明，IXT在客户端搜索阶段的存储开销和计算开销都比HXT低得多。同时，实验结果也表明IXT具有可扩展性，可以应用于各种规模的数据集。

02

系统模型

系统概述

IXT的系统模型由两个实体组成:用户和云服务器，其架构如图1所示。

图1 IXT的架构

1.客户端

客户端有许多文档，希望将这些文件外包，并将搜索操作委托给云服务器。客户机首先加密文档并生成相应的搜索令牌，然后将加密数据库发送到云服务器。如果客户端希望搜索某些关键字，则在客户端首先生成搜索令牌，然后与云服务器调用带标记的私有集交集协议。在标记的PSI协议结束时，云服务器什么也得不到，客户机接收结果。

2.云服务器

云服务器无法从加密数据库推断其他信息，根据接收来自客户机的查询请求后，云服务器将其保存为输入，并与用户一起调用标记的PSI协议。在标记的PSI协议结束时，云服务器无法获得关于客户机查询和搜索结果的任何信息。

可搜索加密:定义和安全性

在单写入器单读取器设置中有两个实体:服务器和客户机。客户端是明文数据库的数据所有者，服务器存储加密数据库。更详细地说，客户机将其搜索服务外包给不受信任的服务器，当客户机希望搜索文档时，它首先使用其私钥在本地生成搜索令牌，然后将其发送到服务器。使用搜索令牌，服务器可以为客户机检索加密的标识符或文档，而不会泄露任何附加信息。形式上，一个可搜索的加密方案由以下两种算法组成:

：该算法由客户端调用，以和客户端的数据库作为输入，其中为安全参数，输出公共参数、主密钥和加密数据库。是公开的，由客户端私下保存，被发送并存储在服务器中。

：该算法在客户端和服务器之间交互运行。客户端以公共参数、主密钥和查询搜索令牌作为输入，服务器以公共参数和加密数据库作为输入。在算法结束时，客户机输出与查询对应的文档标识符，而服务器不输出任何内容。

在本文的设置中，假设云服务器是半诚实的，即服务器诚实地执行协议，但试图从协议记录中获取更多信息。本文在标准半诚实的基于仿真的范例中证明了安全性，并形式化了所提议的IXT的理想泛函性，如图2所示。非正式地，如果服务器只获得与泄漏函数相对应的信息，而没有其他信息，则提议的协议对半诚实服务器是安全的。

图2 理想功能

本文提出的可搜索加密方案是半诚实安全的，如果(1)协议是正确的;(2)对于每一个P.P.T攻击者，都存在一个模拟器，它为协议执行生成一个服务器的记录，该记录与服务器对真实交互的看法在计算上无法区分;(3)只有泄漏函数

可以泄漏到服务器。

在下文中，定义了方案中使用的泄漏函数，以和为输入，泄漏函数输出如下项：

l是中存储的关键字总数

l是每个关键字对应的文档数

03

标记私有集交集

图5描述了标记私有集交集协议。本文遵循Pinkas B等人的《快速恶意私设交集》的工作构造，但做了一些小的修改来构造标记的私有集交集。

第一个变化是，在遗忘传输中，本文将OOS17协议(恶意安全)替换为KK13协议(半诚实安全)。这种改变使得标记私有集相交更有效，其中本文的标记私有集相交在半诚实模型中得到了证明。在有标签的PSI协议的第3步中，第二个更改是发送方加密与元素对应的所有标签，然后以M与元素相同的顺序随机排列。当且仅当在交集处时，接收方可以解密与元素对应的所有标签。

04

IXT

本文的SE协议IXT使用（1）带有密钥铲的IND-CPA安全对称密钥加密方案，（2）具有输出长度的伪随机函数PRF。IXT协议包括两种算法:和。

算法1中的设置算法获取安全参数和，返回、和，加密后的数据库由对的密文组成。客户端首先计算每个单词的值，对于数据库中的单词和每个，客户端加密每个对应的，对于相同的在不同的地方，就会产生不同的密文。

搜索算法如算法2所示，在搜索阶段，客户端首先生成其关键字的陷门，然后客户端和服务器调用一个标记的私有集合交集，其中客户端持有陷门作为输入，服务器持有所有陷门及其相应的标签。客户机在带标签的PSI协议的末尾输出所有相应的标签，而服务器什么也得不到。最后，客户端解密所有标签，并根据其搜索类型(分别为合取或析取)计算交集或并取。

05

主要贡献

本文贡献如下：

1.一个有效的标记私有集交集。本文构造了一个新的基于字符串的探测与异或(PaXoS)的标记私有集交叉点，并证明了标记PSI协议对半诚实对手是安全的，基于PaXoS的标记PSI协议是第一个没有繁重加密原语(如同态加密)的高效标记PSI协议。

2.高效的SE方案IXT，具有更强的安全保障。本文在不知道搜索和访问模式的情况下给出了详细的安全证明，这表明IXT提供了更强的安全保证。IXT是第一个搜索并且使用基于多方计算(MPC)技术的隐藏可搜索加密方案。此外，本文还通过实验比较了IXT和HXT的性能。实验结果表明，IXT在加密数据库的设置时间、加密数据库的存储大小、客户端搜索时间等方面都优于HXT。同时，云服务器可以并行执行搜索操作，以获得更好的性能。

3.支持连接和析取查询。在IXT搜索阶段结束时，服务器从标记的PSI协议中得不到任何东西，客户机可以获得一组与每个查询的关键字对应的标签。然后，客户端可以通过它的查询类型(即析取查询的联合和合取查询的交集)来计算结果。

06

性能比较实验

在本节中，首先比较了IXT和HXT之间的总体交互回合，然后做了一些实验来比较IXT和HXT的性能，包括设置和搜索阶段的存储开销和计算成本。本文在HXT中使用相同的表示法，其中表示为sterm，其他表示为xterms，用于联合查询。

IXT与HXT之间的交互比较

在HXT中，客户机与服务器有六个交互轮(6个消息流)，其中第三、第四和第五行可以并行执行。然而，在IXT中，总共只有三个交互轮，其中KK13协议花费两轮，服务器最终并行地向客户端发送和发送。这些结果分别总结在图3和图4中。

理论比较

本小节对IXT、HXT和OXT进行了理论上的比较，包括(服务器的)总体存储开销、在客户端和服务器端联合查询的每一步计算和通信。总体比较如表1所示，比较表明，包括总体计算、存储和通信开销在内，IXT的性能优于HXT。

表1 客户端和服务器之间的通信开销及其联合查询的计算开销

基准测试环境

本文所有的基准测试都使用1.3GB的安然电子邮件数据集，该数据集由444482个文件组成，使用Lucene解析器来解析和索引数据。为了测试IXT在不同大小的数据集中的可伸缩性，将数据集拆分为七个不同大小的数据库，不同文档关键字对的数量如表2所示。

表2 评估中使用的数据集的统计

在CBC模式下使用SM4实例化了128位密钥的对称加密，并使用SM3实例化了哈希函数和伪随机函数。使用OpenSSL实例化密码原语，并使用GMP执行大数操作。

由于实验室设备的限制，本文在具有16GB RAM的Intel Core i5处理器上运行IXT和HXT来实现服务器和客户端实例。所有的计算都在一个线程中进行，并使用C++编写。Bloom filter是HXT的重要组成部分，在HXT求值时用哈希函数、Bloom filter=(其中为TSet的大小)来设置假阳性率。在HXT和IXT求值中，我们都设置了安全参数。在本文所有的实验中，忽略服务器和客户端传输数据的时间消耗。

EDB存储开销

本文使用如表2所示的单个线程和数据库来研究IXT与HXT在客户端的存储开销，图5和图6显示了HXT和IXT之间设置阶段的总体EDB存储大小和消耗。实验结果表明，随着数据集大小的增加，IXT中的EDB存储容量和时间消耗比HXT中的增长更平缓。主要原因是HXT需要存储Bloom过滤器的密文，并在设置阶段为每个关键字构建TSet，而IXT只使用计算成本低廉的伪随机函数和对称密钥加密来加密数据，并且只将关键字的密文和对应的标识符存储到每个关键字。

EDB搜索时间消耗比较

本文使用单个线程来研究IXT与HXT协议在客户端和服务器端的计算开销，只报告连接查询的搜索时间消耗。在不同的数据集上选择变量项，如表2所示。的选择范围从1到1000个文档，然后，选择一个固定的词(在DB4到DB7中出现相同的不同键)，并在EDB4到EDB7上执行两种类型的联合查询。术语“的选择性”是指匹配关键字的文档数量。在所有实验中，的选择性选择为10，并作为基线。

图7、图8、图9和图10是双关键字查询，这些实验测试了匹配关键字的文档数量对客户端和服务器端时间消耗的影响。另外，虽然搜索关键字的顺序并不影响最终的结果，但是整体的时间消耗与顺序有关。同时，图11和图12是多关键字查询，这些实验测试了关键字数量对客户端和服务器端时间消耗的影响。

第一个连接查询使用作为sterm和作为xterm，可以发现，随着变量项选择性的增加，HXT的时间成本的增加要比IXT明显得多，变量Term的选择性对IXT查询的时间成本影响最小。另一个连接查询使用作为sterm和作为xterm，IXT和HXT的行为与作为sterm和作为xterm的行为略有不同，IXT的时间成本比HXT高一些，变量项的选择性对IXT和HXT的影响都很小。

图11和图12分别显示了IXT和HXT在客户端和服务器端查询多个关键字时的性能比较，使用单个线程和两个不同大小的数据集(分别为和)来评估IXT和HXT的性能。在这次求值中，在之前的求值中选择一个固定的关键词，然后在连接查询中引入更多的关键词作为xterms。

从图9、图10、图12可以看出，IXT中服务器端的搜索时间消耗高于HXT。主要原因是IXT将更多的计算交给服务器，以提高客户端的效率。但是，由于实验室和设备的限制，本文只使用单个线程来执行服务器实例。服务器实例可以并行执行以获得更好的性能，就像HXT中的实验一样。HXT分析了随着并行度因子的增加，每个服务器端的任务的计算成本可以大大降低，以显著提高性能。

07

与其他相关研究对比

大多数SE协议都需要在安全性、性能和功能之间进行权衡，最近的SE方案关注的是有效扩展到大型数据集的性能，许多高效的SE协议使用倒排索引来允许在亚线性时间内执行关键字搜索。这些SE方案在安全性上做了权衡，以获得更高的性能，然而，这将向云服务器泄露一些信息。

本文提出的基于标记PSI协议的高效SE方案IXT，具有访问和搜索模式隐藏功能，可以在保留性能的同时，避免现有用于联合查询的最先进的高效SE协议中出现的泄漏问题。

解读：戴西件 南昌大学第二附属医院

审核：张 琨 合肥工业大学

Frontiers of Computer Science

Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社和北京航空航天大学共同主办、SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，双月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为周志华教授，共同主编为熊璋教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”；入选“中国科技期刊卓越行动计划项目”。

《前沿》系列英文学术期刊

由教育部主管、高等教育出版社主办的《前沿》（Frontiers）系列英文学术期刊，于2006年正式创刊，以网络版和印刷版向全球发行。系列期刊包括基础科学、生命科学、工程技术和人文社会科学四个主题，是我国覆盖学科最广泛的英文学术期刊群，其中12种被SCI收录，其他也被A&HCI、Ei、MEDLINE或相应学科国际权威检索系统收录，具有一定的国际学术影响力。系列期刊采用在线优先出版方式，保证文章以最快速度发表。

中国学术前沿期刊网

http://journal.hep.com.cn