论文分享｜Forward secure searchable encryption with keyed-block chain

本文发表于《Information Sciences》，论文链接FSSE: Forward secure searchable encryption with keyed-block chains - ScienceDirect，由济南大学信息科学与工程学院2021级硕士研究生王谦进行总结。文章来源：SecurityLabUJN

1

引言

Song 等人在2000年提出了第一个实用的可搜索加密方案，该方案使用对称加密原语，也被称为对称可搜索加密（SSE）方案。SSE方案有两种，静态的和动态的。静态SSE不支持在初始化数据库或存储系统后动态添加或删除关键字文档对，因此最近的研究主要集中在动态SSE的构造上。

倒排索引的方法被广泛使用在上述方案中。与之前已有方法相比（正排索引），实现了亚线性搜索时间。然而，之前已有的创建动态方案会泄露有关更新关键字的一些信息。Raphael [1]的新颖设计提供了前向私有安全。

2

本文贡献

1、提出了块链技术以保证前向安全，进而基于块链技术和对称加密原语设计了前向安全可搜索对称加密（SSE）方案，命名为 FSSE。

 1）FSSE方案在搜索和更新方面分别比[1]快4倍和100倍；

 2）FSSE是当时所有前向私有 SSE 方案中最高效的令牌生成算法。

2、进一步对FSSE进行改进，提出了方案。

 1）方案减少FSSE方案中客户端空间开销，使其与 [1]相同；

 2）方案减少FSSE方案中服务器端中树T中的节点数及树遍历操作。    

3

块链技术

块链结构如图1所示。定义B为数据块集合，B={b0,…,bn}且|B|=n。将 C 表示为在 B 中的子集 B 上构建的链。将 nc 表示为集合 B 上的链数量。假设一个块只能属于一个链，则 1 ≤ nc ≤ n。块定义作者定义了三种类型的块：头块、尾块和内部块，分别是链C中的第一个区块、最后一个区块和其他区块，分别记为C.head、C.tail和C.internal。

对于集合B中的每个数据块b，将其定义为b=(id, value, key, ptr)，其中id和value是该块的数据标识符和数据值，ptr和key是该块的数据标识符和加密密钥下一个街区。将b.id表示为区块b的id，其他类似。向链C中插入块过程如下（链头插入）： 

1) 生成一个块 b=(id, value, C.head.key, C.head.id);  

2) 从中采样随机密钥k；

3) 加密块b中除id之外的内容；  

4）将b存储在服务器中。

4

FSSE方案

FSSE方案存储结构如图1所示，客户端存储映射W，服务器端存储树T。    

图1 FSSE存储结构。

数据库DB中有三个关键字(W1、W2和W3)及其倒排索引列表(LW1、LW2和LW3)。客户端将加密密钥、每个列表的头块的标识符和计数器存储在映射W中。服务器将这些列表中的每个文档标识符存储到树T的节点中的数据块的值部分中。

1、初始化

2、更新算法

3、查找算法    

5

FSSE改进版方案

改进点1：客户端映射W中仅存储每个关键词的计数器，不再存储密钥和链头id。从而使得存储开销由降为为|key|长度，为|id|，为关键词的数量，为文档数量。

改进点2：客户端可以要求服务器删除所有与关键词w匹配的节点，进而根据中预定义的一些规则动态地将它们合并到一个（或多个）节点中。最后，将合并后的节点连同搜索操作一起上传到服务器，实现客户端容量的动态调整。

方案如下所示：    

6

实验结果

实验展示了FSSE 和 的性能。首先，作者列出了测试数据集、安然电子邮件的特征。然后，图4显示FSSE在搜索和更新操作上都优于第一个有效的前向私有SSE方案[1]。

在图4中，作者展示改进方案在设置各种CT时的性能。图 4显示 比 FSSE 更有效，因为当设置 CT 为 1 时，FSSE 几乎可以被视为的特例。最后，作者给出了所提出的方案在 LAN/ WAN中的性能。不同规模的数据集上的 WAN 设置和结果如图6所示。

    图3 关键词-文档数分布               图4 搜索和更新性能比较    

     图5 在不同CT上的表现        图6 在大数据集上的表现

分享仅供学习参考，若有不当，请联系我们处理

END

热文推荐