私有信息检索中若干关键技术的研究

论文摘要

安全多方计算（Secure Multi-party Computation, SMC）是研究多方协作计算问题的,即互不信任的两个或多个用户能够进行协作计算某项计算任务,并且保证自己的私有输入是安全的。该问题由姚期智教授于1982年提出,1987年,O.Goldreich,S.Micali等提出了密码学安全的安全多方计算协议,该协议可以用来计算任意函数。但1998年,O.Goldreich（?）旨出,对于安全多方计算中的特殊问题,使用通用的协议来解决已经达不到理想的效果了,针对这些特殊问题设计相应的安全多方协议,可以高效的解决问题。正是在这一思想的推动以及学者的深入研究之下,安全多方计算细化出了很多研究方向,如：保护隐私的计算几何、私有信息检索、电子投票、电子拍卖、统计分析等,促进安全多方计算能够解决更多的实际问题。这其中私有信息检索是一个重要而又实际的问题,在军事、商业等领域有重要应用。私有信息检索（Private Information Retrieval, PIR）的问题描述是：服务器Bob拥有一个数据库,其中有n个数据d,,d2,…,dn,客户端Alice要查询这个数据库的某条数据di,而Bob却不知道i的值。这是最一开始的PIR,后来发展为对服务器的数据隐私也进行保护,即Alice除了di得不到任何其他信息,这就是对称的私有信息检索（Symmetrically-Private Information Retrieval,SPIR）。按对隐私的保护程度,我们可以将私有信息检索分为三种：①绝对安全的,即信息论安全的私有信息检索,此类的PIR提供一个很强的安全概念,在假设攻击者的计算能力是无限制的条件下保证用户的隐私性能够完全的被保护；②相对安全的,即计算安全的私有信息检索,此类PIR没有很强烈的安全概念,假设攻击者的计算能力是在多项式的时间内是有限制的,它常常基于一些密码学上的计算难题,具有一定的实用意义；③辅助安全的,即基于安全硬件的私有信息检索,借助一些安全硬件作为辅助设施,这些安全硬件都有着设备齐全的安全环境、处理器和安全存储空间,因此此类的PIR具有很高的执行效率。另外,我们还可以按参与方是否诚实将私有信息检索划分为：恶意模型的私有信息检索和半诚实模型的私有信息检索。私有信息检索是安全多方计算的重要分支,并且在现实生活中有广泛应用,例如局部可解码编码、匿名认证、不经意传输、数据库的安全查询等。本文的主要研究是针对半诚实模型下的计算安全的私有信息检索,其主要工作有：首先,详细介绍了目前已有的几种典型的基于关键字的私有信息检索方案,并据此提出问题,进行总结。其次,研究了云计算中的安全模糊关键字检索。以往的PIR方案大多不能实现关键字检索,而是通过物理地址检索,我们深入研究了支持关键字检索的PIR。因为云计算的发展速度越来越快,云服务的便捷也使其越来越受欢迎,但是云安全仍然是用户考虑的首要因素。因此本文基于云计算中的存储服务,将敏感信息经过处理之后上传至云服务器,形成加密数据库。利用位置敏感哈希函数以及中国剩余定理,实现了模糊关键字的安全检索,并且利用布隆过滤器成功实现了对合法用户的认证。理论分析表明该方案是正确的、安全的。方案在保持原有的计算复杂度以及通信复杂度的基础上,首次实现用户认证,在预存储空间上也优于现有方案。该方案能应用到很多领域,如医药、专利和商业等。再次,研究了计算几何中的保护隐私的两椭圆相交面积计算。我们将对称的私有信息检索问题简化,其实就是两个参与方各自保护自己的隐私,但同时还要得到想要的结果,我们将其进行延伸,联想到安全多方计算中的计算几何问题。安全计算几何问题也是安全多方计算的一个研究领域,Du等人在该领域做了一些工作,提到了几何计算的很多问题,并且给出了该领域的一个研究框架。我们提出了保护隐私的计算两椭圆相交面积的问题,这是一个拥有很强应用背景的问题,对于这一问题,我们利用Monte Carlo方法和OT协议给出了两个解决方案,并且对这两个协议的安全性和效率做了分析。

论文目录

• 摘要
• Abstract
• 目录
• 第一章 绪论
• 1.1 研究背景及意义
• 1.2 国内外的研究现状与进展
• 1.3 研究问题的提出
• 1.4 本文的研究思路及研究内容
• 1.4.1 本文的研究思路
• 1.4.2 本文的研究内容
• 1.5 本文的内容安排
• 1.6 本章小结
• 第二章 基本概念与协议
• 2.1 引言
• 2.2 本文研究模型及符号约定
• 2.2.1 符号介绍
• 2.2.2 私有信息检索中的问题
• 2.2.3 私有信息检索中的模型
• 2.3 基础工具及协议
• 2.3.1 BGN同态加密算法
• 2.3.2 茫然传输协议
• 2.3.3 随机化算法
• 2.3.4 双线性映射
• 2.4 本章小结
• 第三章 基于关键字检索的私有信息检索概述
• 3.1 引言
• 3.2 关键字检索方案概述
• 3.2.1 基于数据结构的关键字检索
• 3.2.2 公钥加密的关键字检索
• 3.2.3 带访问控制的关键字检索
• 3.2.4 密文数据库中的关键字检索
• 3.3 Questions及启发
• 3.4 总结
• 第四章 云计算中的安全模糊关键字检索
• 4.1 引言
• 4.2 预备知识
• 4.2.1 位置敏感哈希函数
• 4.2.2 布隆过滤器
• 4.2.3 中国剩余定理
• 4.3 云计算和云安全
• 4.4 云计算中私有信息检索
• 4.4.1 密文检索模型
• 4.4.2 具体方案
• 4.5 方案分析
• 4.5.1 正确性分析
• 4.5.2 安全性分析
• 4.5.3 通信复杂性
• 4.5.4 计算复杂性
• 4.6 结束语
• 第五章 保护隐私的两椭圆相交面积计算
• 5.1 引言
• 5.2 预备知识
• 5.2.1 蒙特卡罗算法
• 5.2.2 茫然传输
• 5.3 保护隐私的两椭圆相交面积计算
• 5.3.1 问题描述
• 5.3.2 多点包含于椭圆的计数协议
• 5.3.3 相交面积计算方案
• 5.4 方案分析
• 5.4.1 正确性分析
• 5.4.2 安全性分析
• 5.4.3 复杂度分析
• 5.5 本章小结
• 第六章 结论与展望
• 6.1 本文的主要贡献
• 6.2 进一步的研究工作
• 参考文献
• 附录A 图索引
• 附录B 表索引
• Appendix A Figure Index
• Appendix B Table Index
• 致谢
• 在读期间发表的学术论文
• 在读期间参加的科研项目