论文部分内容阅读
众多公司与个人都将数据存储于云端的各种数据管理系统中,以获得更低的成本、更高的可扩展性、更方便的部署和无处不在的服务。然而,数据的外包也意味着随时可能泄漏。尽管云服务商声称能够保护好用户隐私,实际上存在大量个人隐私泄露事件。如,2013年雅虎30亿用户数据被盗,2014年支付宝20GB用户资料泄露等。保护数据隐私的简单办法就是对数据进行加密,但数据加密后会带来一系列问题:不仅难以查询、难以更新,而且在密文存储、计算、更新过程中仍然可能存在各种安全隐患。为了解决这些问题,本文在PBTree方案和IBTree方案的基础之上,提出了多种新型密文数据结构及其基于它们的系列方案。主要工作和贡献体现在如下三方面:
1)提出了全新的密文检索结构:虚拟二叉树。这种简洁的密文二叉树结构在没有用户查询指令时,云并不知道树节点的分布以及树枝的分布情况,整棵树仅仅存在于某个逻辑视图中。即使用户提交密文连接查询或者密文布尔查询请求,云只会了解极少数与访问路径相关的信息,树节点信息一直隐藏。使用基于哈希表的方案替换基于布隆过滤器(BloomFilter)的方案,以换取更好的动态更新性能和更高的密文检索效率。文中引入了一个新的NP难问题——数据文件划分问题(DataFilePartitionProblem,简称DFPP)——为虚拟二叉树的效率优化提供数据安全技术支撑。同时提出了基于图的分组计算近似算法对此NP难问题进行优化处理,以节省索引的存储开销和提高密文检索的效率。虚拟二叉树结构简洁,具有亚线性时间的密文查询效率和优秀的动态更新性能,易于被优化与拓展。
2)给出了零用户存储的前向隐私(ForwardPrivate)方案:查询版本管理库。它可在保证用户数据更新安全的同时,实现客户端的零用户存储空间开销和高的可扩展性。前向隐私的查询版本管理库能统一管理所有用户查询与数据更新,且更新的数据不会和历史查询记录产生相关性。所有的关键词和查询被标记为不同的版本存储于客户端,当所有的关键词都被升级成相同版本,客户端就实现了零用户存储开销。此零用户存储的前向隐私方案解决了Bost发表于CCS2016等论文中过多依赖客户端存储的问题。此系统具有亚线性时间的更新效率,能够为动态的可搜索加密(SearchableEncryption)方案提供更新方面的前向隐私保证,并能和虚拟二叉树很好地结合使用。本篇详细地证明了基于虚拟二叉树和查询版本管理库的方案满足自适应选择关键词攻击下的不可区分性(IND-CKA2)和前向隐私的安全要求。
3)提出了布尔查询效率较高的密文查询树结构:四枝树(Four-branchTree,简称FBTree)。四枝树是一种拓展的满二叉树结构,每个树节点不仅包含原有二叉树的树枝,而且还有两根额外的叉枝指向待选的节点。查询算法不仅可以在树节点之间逐步执行,而且还可以在树节点之间跳跃执行。一个密文布尔查询可以以接近最优的执行效率从树根遍历到树叶节点,且查询效率不会与文档总数相关。四枝树带来极致的查询效率和强的安全属性。能够基于此种数据结构,为同时拥有数字和字符串字段的数据表格建立高速安全可扩展的密文索引。
在此研究工作中,系统整理了较多的安全概念,尤其与可搜索对称加密相关的安全概念。修改整理了一些已有的数据结构与算法,比如精减版不可区分布隆过滤器(RIBF)等。用C++实现了全部的算法,并做了大量的实验。实验数据表明,基于虚拟二叉树、版本管理库、四枝树的一系列方案总体上满足密文检索环境中的安全、效率与可扩展性方面的各种要求。
1)提出了全新的密文检索结构:虚拟二叉树。这种简洁的密文二叉树结构在没有用户查询指令时,云并不知道树节点的分布以及树枝的分布情况,整棵树仅仅存在于某个逻辑视图中。即使用户提交密文连接查询或者密文布尔查询请求,云只会了解极少数与访问路径相关的信息,树节点信息一直隐藏。使用基于哈希表的方案替换基于布隆过滤器(BloomFilter)的方案,以换取更好的动态更新性能和更高的密文检索效率。文中引入了一个新的NP难问题——数据文件划分问题(DataFilePartitionProblem,简称DFPP)——为虚拟二叉树的效率优化提供数据安全技术支撑。同时提出了基于图的分组计算近似算法对此NP难问题进行优化处理,以节省索引的存储开销和提高密文检索的效率。虚拟二叉树结构简洁,具有亚线性时间的密文查询效率和优秀的动态更新性能,易于被优化与拓展。
2)给出了零用户存储的前向隐私(ForwardPrivate)方案:查询版本管理库。它可在保证用户数据更新安全的同时,实现客户端的零用户存储空间开销和高的可扩展性。前向隐私的查询版本管理库能统一管理所有用户查询与数据更新,且更新的数据不会和历史查询记录产生相关性。所有的关键词和查询被标记为不同的版本存储于客户端,当所有的关键词都被升级成相同版本,客户端就实现了零用户存储开销。此零用户存储的前向隐私方案解决了Bost发表于CCS2016等论文中过多依赖客户端存储的问题。此系统具有亚线性时间的更新效率,能够为动态的可搜索加密(SearchableEncryption)方案提供更新方面的前向隐私保证,并能和虚拟二叉树很好地结合使用。本篇详细地证明了基于虚拟二叉树和查询版本管理库的方案满足自适应选择关键词攻击下的不可区分性(IND-CKA2)和前向隐私的安全要求。
3)提出了布尔查询效率较高的密文查询树结构:四枝树(Four-branchTree,简称FBTree)。四枝树是一种拓展的满二叉树结构,每个树节点不仅包含原有二叉树的树枝,而且还有两根额外的叉枝指向待选的节点。查询算法不仅可以在树节点之间逐步执行,而且还可以在树节点之间跳跃执行。一个密文布尔查询可以以接近最优的执行效率从树根遍历到树叶节点,且查询效率不会与文档总数相关。四枝树带来极致的查询效率和强的安全属性。能够基于此种数据结构,为同时拥有数字和字符串字段的数据表格建立高速安全可扩展的密文索引。
在此研究工作中,系统整理了较多的安全概念,尤其与可搜索对称加密相关的安全概念。修改整理了一些已有的数据结构与算法,比如精减版不可区分布隆过滤器(RIBF)等。用C++实现了全部的算法,并做了大量的实验。实验数据表明,基于虚拟二叉树、版本管理库、四枝树的一系列方案总体上满足密文检索环境中的安全、效率与可扩展性方面的各种要求。