查看原文
其他

论文分享|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

1.论文分享|基于Ring-OLE构造的隐私求交(PSI)协议(CCS 2022)

2.论文分享|LAFED:一种用于支持区块链的联邦学习系统的轻量级认证机制

3.会议通知丨第 25 届国际信息与通信安全学术会议(ICICS 2023)

4.论文分享|一种基于本地化差分隐私的网格聚类方法


个人观点,仅供参考
继续滑动看下一个
隐私计算研习社
向上滑动看下一个

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存