聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

IEEE TIFS'22:健壮且具有前后向安全性的可搜索对称加密

2022-07-25 13:29 浏览: 626535 次 我要评论(0 条) 字号:

动态可搜索对称加密(Dynamic Searchable Symmetric Encryption,DSSE)是云安全外包存储领域中的一种加密搜索技术。在DSSE的应用场景中,客户端能够对外包存储在半可信云服务器上的密文数据库执行添加、删除与关键字搜索操作,并且同时保证密文中关键字的保密性。目前,学界针对DSSE的研究工作几乎围绕着降低运行中的信息泄露与提升搜索性能开展,而忽视了实用中DSSE的一项重要特性:健壮性。DSSE的健壮性是指,当客户端发布不合理的更新请求后,DSSE仍然能够保证正常功能与所声称的安全性的一种性质。其中,不合理的更新请求包括添加重复的数据与删除不存在的数据。经过深入研究,我们发现已有的绝大部分DSSE方案都不具备健壮性,且目前尚未存在一个DSSE方案能够同时实现健壮性、前后向安全性与实用搜索性能。在本文中,我们首次定义了DSSE的健壮性,并且构造了一个全新的同时具备健壮性、前后向安全性与高性能的DSSE方案ROSE。在构造ROSE的过程中,我们还提出了一个新的密码原语——密钥可更新的伪随机函数。最后,本文通过实验说明了ROSE的高效性。

该成果“ROSE: Robust Searchable Encryption with Forward and Backward Security and Practical Performance”发表于信息安全领域的顶级期刊TIFS(IEEE Transactions On Information Forensics and Security),是实验室安全组在云数据安全领域的研究成果。

  • 原文链接:

    https://doi.org/10.1109/TIFS.2022.3155977


背景与动机

近年来,随着研究者对DSSE探索的深入,学术界涌现出了一大批提升DSSE安全性与性能的里程碑式的工作。例如:2016年USENIX Security上Zhang等人提出了针对DSSE的文件注入攻击,从此之后能够保证未来的密文不被以前的搜索请求影响的前向安全性(Forward Security)成为了一个DSSE的基本安全性质;2017年CCS上Bost等人首次形式化定义了能够限制被删除的密文在搜索请求中所泄露信息的后向安全性(Backward Security),自此之后主流的DSSE方案均同时具备前向安全性与后向安全性(统称为前后向安全性);2021年ESORICS上Chen等人构造了具有并行化检索能力与非交互式物理删除特性的DSSE方案,将DSSE的实用性能拉上了一个新台阶。

自从DSSE面世以来,研究者们从未关注过DSSE的健壮性问题,这也导致已有的绝大部分前后向安全的DSSE方案不具备健壮性。使用这些不具备健壮性的DSSE方案时,客户端若发布不合理的更新请求,要么会产生额外的信息泄露,导致方案安全性降低,要么会破坏已有的密文数据库,导致无法正常执行功能。如下表所示。在这张表中,可以看到已有DSSE方案中,只有Moneta和Fides实现了健壮性,然而它们的实际性能很低,不具备实用价值。而表中的其他方案,例如FB-DSSE等,在用户发布不合理的更新请求时,会导致密文数据库的破坏;对于ORION与HORUS方案等,用户的不合理更新请求会导致其前向安全性的破坏。因此,健壮性问题对已有DSSE方案的影响非常大,影响范围也十分广泛。


DSSE健壮性的定义

本文首先定义了DSSE的健壮性,即定义什么样的DSSE是健壮的。一言以蔽之,健壮的DSSE方案应当即使在客户端发布了重复的添加操作或删除不存在的密文时,依然保持其所声称的正确性与安全性。传统的未考虑健壮性的DSSE的正确性定义要求,搜索操作应当返回所有被添加进密文数据库,并且尚未被删除的记录。总体上来说,健壮性定义与传统的DSSE正确性定义是兼容的。然而,健壮性与传统DSSE的安全性要求无法完全兼容的,在具有健壮性的DSSE中,为了进一步实现前后向安全性,需要对前后向安全性的定义进行改造,更具体来说,对后向安全性的定义进行改造。

前向安全性的定义要求,新生成的密文数据最多仅能泄露该数据所对应的操作类型(添加或删除)以及对应的文件标识符,这一定义是符合健壮性要求的。然而对后向安全性来说,情况变得复杂起来了。以第三类后向安全性(Type-III Backward Security)为例,第三类后向安全性要求搜索请求仅泄露两种信息:1、所有曾经被添加进密文数据库且未被删除的满足搜索条件的文件标识符及其被添加进密文数据库的时间戳;2、对与所有曾经被添加但是又被删除的密文,返回既包含其被添加进密文数据库的时间戳,也包含其对应删除请求发生时的时间戳的元组。在传统的DSSE中,因为无需考虑客户端会添加重复的密文以及删除不存在的密文,上述两种信息泄露的定义是简单且直观的。然而在健壮性条件下,这样的直观性不复存在。例如,对于第一种信息来说,若客户端将某一密文重复添加多次,或在删除过某密文后又重新向密文数据库添加了一次该密文,第一种信息就无法描述这两类情况。因此,第一种信息泄露的表述应当修改为“所有依然存在于密文数据库的满足搜索条件的文件标识符以及被添加进密文数据库的时间戳集合”。而第二种信息要考虑的情况则更为复杂,例如若某客户端先多次重复添加了某密文,未来又发布了多个针对该密文的删除请求,服务器就会获知密文数据库中存在多个删除请求对应多个添加请求,而显然已有表述无法准确描述此时服务器所获得的泄露内容。因此,第二种信息泄露的表述应当修改为“对与所有曾经被添加但是又被删除的密文,返回既包含其被添加进密文数据库的时间戳集合,也包含其对应删除请求发生时的时间戳集合的元组”。按照上述思路,本文扩展了第三类后向安全性的定义,并进一步定义了能够用于满足具有健壮性的DSSE性质的通用第三类后向安全性。


ROSE:健壮且具有前后向安全性的DSSE实例化方案

在定义了前后向安全DSSE的健壮性之后,本文还提出了一个具有健壮性的前后向安全的DSSE实例化方案ROSE。ROSE是第一个证明了健壮性、前后向安全性与第三类后向安全性的DSSE方案。ROSE采用了链式结构来组织具有同一个关键字的密文。链式结构的好处有两点:1、能够实现亚线性级的搜索复杂度;2、链式结构为密文天然赋予了时间上的偏序关系。然而,链式结构存在一个问题,即难以在保证后向安全性的情况下实现密文的删除功能。为了解决这个问题,我们进一步定义并构造了一个全新的密码工具——密钥可更新的伪随机函数。密钥可能新的伪随机函数是能够利用更新凭据来更新已有伪随机数生成密钥的全新密码学原语,其在功能语义上与已有的密钥同态伪随机函数存在本质差别。借助密钥可更新的伪随机函数,我们在ROSE中实现了对同一密文,每次搜索后其对应的删除凭据都不同的特性,同时在发布搜索请求时也同时上传一个对应的搜索密文来存储密钥可更新的伪随机函数的密钥更新凭据,保证了在不泄露密文中文件标识符的前提下,未来的删除请求可以删除以前发布的对应密文,从而确保了ROSE的后向安全性。

在ROSE的构造中,密文在时间上的偏序关系是实现健壮性的重要依据。第三类后向安全性要求,服务器在对密文执行安全搜索与删除时,不能获知被删除的密文中所包含的文件标识符,因此服务器仅能利用密文中所包含的伪随机化的删除凭据来进行删除操作。而在健壮性中,客户端可能会先后针对同一个密文发布多个添加或删除请求。此时服务器是否返回这个密文,取决于客户端所发布的最后一个关于此密文的请求是添加还是删除。若密文间不存在时间上的偏序关系,或这样的偏序关系无法在搜索过程中暴露给服务器,服务器就无法正确执行删除操作,也就无从实现健壮性了。

下图用一个例子简要展示ROSE的运行流程:


实验结果

DSSE的研究属于应用密码学范畴,其最终目标是实现实用化部署。因此,一个DSSE方案的性能表现是衡量其好坏的重要指标。我们将ROSE与已有的几个具有健壮性或能够很容易改造为具有健壮性的方案进行了对比,实验结果显示ROSE具有很好的性能表现。下图分别展示了ROSE与已有方案的搜索时间与搜索带宽开销上随搜索结果数量的变化,可以看到ROSE的开销仅略高于IMDSSEI+II。

下图展示了ROSE方案与已有方案的客户端时间开销随搜索结果数量的变化。在这个实验中没有列出HORUS方案,因为HORUS方案的绝大部分搜索时间开销都是在客户端上产生的,与其比较意义不大。从实验结果可以看出,ROSE的客户端开销是最低的。

因为ROSE的构造特点,其在执行删除时会因为密钥可更新的伪随机函数而调用密钥可更新的伪随机函数。而密钥可更新的伪随机函数需要在椭圆曲线群上执行代数运算,这增加了删除时候的时间开销,虽然在一次搜索后这些删除密文就会被删除,但是在处理这些删除密文时,服务器还是会消耗不少的时间。为了解决这个问题,我们在删除阶段引入了多线程技术,来并行化地执行删除凭据的判定,从而在不降低安全性的基础上大大提升了删除的效率。下图展示了在密文数据库存在不同数量搜索请求(S'=50, 100, 150, 200)的情况下,搜索阶段的时间开销随删除密文占总密文比例的变化。


详细内容请参见:

Peng Xu, Willy Susilo, Wei Wang, Tianyang Chen, Qianhong Wu, Kaitai Liang, Hai Jin. "ROSE: Robust Searchable Encryption With Forward and Backward Security." IEEE Transactions on Information Forensics and Security (TIFS), 17 (2022), pp. 1115-1130, doi: 10.1109/TIFS.2022.3155977.



网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复