本文来自“FCS”，文章仅代表作者观点，与“科研圈”无关。

原文信息

标题：

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

发表年份：

2023 年

引用格式：

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 的安然电子邮件数据集，该数据集由 444,482 个文件组成，使用 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 协议中出现的泄漏问题。

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

审核：张琨合肥工业大学

CCF 推荐B类期刊；

SCI、Ei等收录；

中国科技期刊卓越行动计划梯队类期刊。

IF 4.2

高等教育出版社北京航空航天大学

共同主办

Frontiers of Computer Science

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

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

中国学术前沿期刊网

隐藏你的搜索记录：IXT，一种基于隐私求交的多关键词查询可搜索加密｜FCS