动态可搜索对称加密（Dynamic Searchable Symmetric Encryption，DSSE）是一种用于实现加密关键字检索的密码学原语。在DSSE中，存在一个客户端和一个“诚实但好奇”的服务器。服务器上存储有一个加密数据库，客户端能够更新该加密数据库的内容以及在该加密数据库上实现关键字检索，同时隐藏关键字的明文信息。DSSE因其可增强用户在使用安全云外包存储的流程中的友好性，受到广泛的研究。然而，我们发现，如果DSSE的密钥产生了泄露，那么现有DSSE方案均会失去安全性。为了解决这一问题，我们提出了密钥可更新的可搜索对称加密（Searchable Encryption with Key-Update，SEKU）。SEKU允许客户端非交互式地更新服务器上密文的密钥，使得已泄露的密钥失效。同时，我们还利用泄露函数定义了SEKU的密钥泄露后安全性。该安全性要求在密钥泄露后，采用已泄露密钥生成的密文依然具有安全性。最后，我们构造了具有密钥泄露后安全性的SEKU方案——Bamboo。Bamboo同时还具有前向安全性与后向安全性。最后的实验结果表明，Bamboo相比传统DSSE方案，具有相当或更好的性能。

该成果“The Power of Bamboo: On the Post-Compromise Security for Searchable Symmetric Encryption”已被CCF A类国际会议NDSS 2023录用。该会议主要关注网络和分布式系统安全，被称为“安全领域四大顶会之一“，2023年的论文录用率为16.2%.

• 论文链接：https://dx.doi.org/10.14722/ndss.2023.24725

背景与动机

DSSE允许一个客户端将自己的加密数据库安全外包存储到一个诚实但好奇的服务器上。通常，该加密数据库是一系列密文的集合。DSSE中，客户端通常持有一个私钥与一个私有状态，私有状态记录了加密数据库当前的状态。利用私钥和私有状态，客户端能够向加密数据库添加数据或从加密数据库中删除数据，以及对加密数据库执行关键字检索，并且在这些操作中不泄露任何关键字信息。

自从DSSE在学术界被提出以来，许多学者对其展开了研究。检索性能与安全性是DSSE中最受关注的特点。在检索性能方面，目前主流DSSE方案均实现了亚线性级检索复杂度，即检索时间开销仅与检索结果的数量线性相关。在安全性方面，目前主流的DSSE方案均以前向安全性与后向安全性作为实现目标。其中前向安全性保证了，当客户端向加密数据库中新添加一个密文，或者从加密数据库中新删除一个密文，即使被更新的密文中所包含的关键字曾经被检索过，服务器也无法将客户端的添加和删除操作与以前的任何检索请求联系起来。而后向安全性则限制检索时被删除的密文所能够泄露的信息。前向与后向安全性的提出对DSSE的安全性有很大的提升作用。

然而，已有DSSE方案的安全性，均依赖于一个假设，即客户端的密钥从不会泄露。这个假设在实用中是难以成立的。毕竟在国际上已经出现了多起知名企业密钥被泄露的事件。因此，在DSSE中也应当考虑密钥泄露的风险。

图1 知名企业的密钥泄露事件

挑战

发生密钥泄露事件后，常规的补救措施是对客户端本地的密钥，以及加密数据库中密文的加密密钥进行更新，使得已泄露的密钥失效，让密钥窃取者无法再解密尚未来得及获取的密文，从而实现止损的效果。也就是说，我们需要给DSSE配备一个密钥更新协议，使得客户端可以随时执行这个协议来进行密钥更新。

在实用中，这个密钥更新协议最直观的实现方式是，让客户端将整个加密数据库下载到本地，在本地解密之后使用新的密钥加密生成新加密数据库，再将新加密数据库上传到服务器保存。显然这样的实现方式会造成大量的带宽与客户端计算开销，是不实用的。因此出于实用性考虑，这个密钥更新协议应当是非交互式的，即客户端仅需要生成一个具有常数级大小的密钥更新凭据，再将该凭据上传到服务器上。服务器利用该凭据更新整个加密数据库的密钥。

直观来看，这样的非交互式更新操作的实现是非常简单的。仅需将密文无关的可更新加密或密钥可更新的伪随机函数与现有可搜索加密方案进行结合，即可实现这样的非交互式更新。例如可将MITRA这个DSSE方案中的伪随机函数替换为密钥可更新的伪随机函数，或将Horus这个DSSE方案中的加密方案替换为密文无关的可更新加密。然而，这样的直观实现无法解决一个重要的安全性问题：如何保证密钥泄露后、密钥更新前这段时间所生成密文的安全性。

图2 密钥泄露后、密钥更新前生成的可搜索密文

在实用中，密钥泄露事件可能无法及时被发现，即客户端可能会继续使用泄露后的密钥生成可搜索密文或发布加密检索请求。当密钥泄露时，从安全模型上来看，客户端所有已有的加密数据库可认为已被泄露。然而，如果能够保证在密钥泄露后、密钥更新前所生成可搜索密文的安全性，就相当于实现了针对外部密钥窃取者的前向安全性。这样的安全性在实用中非常重要，能够极大提升密钥泄露情况下客户端数据的安全性。

然而，显然上述非交互式更新的实现方法并未考虑到针对密钥窃取者的前向安全性。因此，如何实现针对密钥窃取者的前向安全性，是一个重要的技术挑战。

解决思路

为了解决这个问题，我们设计构造了SEKU实例化方案Bamboo。Bamboo实现了密钥泄露后安全性，即：1、密钥更新过程不向服务器泄露任何语义信息；2、在密钥泄露后、密钥更新前所生成的可搜索密文不会向密钥窃取者泄露任何信息。同时，Bamboo还具备亚线性级检索复杂度。Bamboo实现密钥泄露后安全性和亚线性级检索复杂度的核心是两点：1、双重加密和2、隐藏链式结构。

双重加密思想具体来说，就是在内层加密使用一次性随机数对数据进行加密，而外层加密则使用密钥可更新的加密体制。其中外层加密允许客户端对加密数据库执行非交互式的密文更新，而内层加密中，由于使用的是一次性随机数进行加密，即使当前客户端的密钥泄露了，服务器也无法获知新生成密文中内层加密所用的随机数，也就无法解密新生成的密文，从而保证了密钥泄露后、密钥更新前所生成密文的安全性。

而Bamboo为了实现亚线性级检索复杂度，在具有相同关键字的可搜索密文间构造了一条隐藏链式结构。该结构中，新生成的密文加密保存有前一条密文的内层加密密钥。客户端仅需保存最新生成的密文的内层密钥即可。当客户端发布检索请求时，将最新生成的密文的内层密钥上传到服务器，服务器便可根据隐藏链式结构一次性找到所有满足条件的密文，也即实现了亚线性级检索复杂度。

方案性能

最后，我们在网络环境下对Bamboo的性能进行了测试，并与传统的不具有密钥泄露后安全性的方案进行了对比。对比结果显示，Bamboo与传统方案的性能在同一级别，并且在某些指标上比传统方案要好。

在实验中，我们将所提出的方案Bamboo与三个传统方案MITRA、Aura和Fides进行了对比。这三个方案实现了与Bamboo相同级别的前向与后向安全性。在对比时，我们同时为这三个方案设计了密钥更新协议。其中MITRA的密钥更新协议是通过替换其所使用的伪随机函数为密钥可更新的伪随机函数，从而实现了非交互式的密钥更新。而Aura和Fides因其构造上的独特性，无法实现这样的替换，因此这两个方案的密钥更新协议是通过将整个加密数据库从服务器端下载下来，再由客户端对其进行重新加密而实现的。

表1 密文生成性能对比

表2 密钥更新性能对比

表1和表2分别对比了Bamboo和其他三个方案的密文更新性能与密钥更新性能。Bamboo的性能比Aura和Fides都好，但是比MITRA稍弱一些。这是因为Bamboo所生成的密文比MITRA所生成的密文多包含一个元素来保存隐藏链的信息。多出的这个元素在密文更新与密钥更新时，分别需要多一次椭圆曲线群上元素的指数运算，因此造成性能开销的增长。

图3 Bamboo的多线程密钥更新性能

图3展示了Bamboo密钥更新过程在多线程情况下的加速效果。很显然，所用线程越多，Bamboo的密钥更新耗时越短。

图4 检索性能对比

图4展示了Bamboo和其他三个方案检索性能的对比，Bamboo的性能比Fides好，比MITRA和Aura略差。

图5 检索时客户端性能对比

图5展示了Bamboo与其他三个方案在检索时客户端耗时的对比。显然Bamboo比MITAR和Fides在检索时会产生更少的客户端性能开销。但是相比Aura，Bamboo的客户端开销略高一点。

总得来说，相比起传统方案，Bamboo的性能与它们不相上下，优势之处互有来回。同时考虑到Bamboo首创性地实现了密钥泄露后安全性，该安全性并未给Bamboo带来显著的额外性能开销。因此，可以下结论说，Bamboo具有很高的实用性。

其他重要贡献

除了上述Bamboo方案的构造外，本文中还首次定义了密钥可更新的可搜索对称加密及其安全性，并对安全模型进行了详尽分析，并首次用泄露函数定义了密钥泄露后安全性。囿于篇幅，此处不再详细描述，请感兴趣的读者阅读论文了解详情。

详细内容请参见：

Tianyang Chen, Peng Xu, Stjepan Picek, Bo Luo, Willy Susilo, Hai Jin, and Kaitai Liang. “The Power of Bamboo: On the Post-Compromise Security for Searchable Symmetric Encryption.” In Proceedings of the Network and Distributed System Security Symposium (NDSS) 2023.

https://dx.doi.org/10.14722/ndss.2023.24725

来源：穿过丛林