ORAM模型下的安全两方计算若干关键问题研究

Secure computation technique (SCT) enables untrusted participants to conduct effective collaborative computation with the premise that the private information of each participant can be guaranteed. However, the present SCT cannot effectively make RAM program private yet. Consequently, a number of practical application problems fail to be solved on account of the shortage of highly efficient construction methods for secure protocols. Introducing ORAM storage mechanism makes it possible to effectively resolve the privacy issues of RAM programs. However, some open problems in the integration between ORAM storage mechanism and SCT are still starving for scientific answers at present. With this in mind, we are about to delve deeper into the following four items in the project we are applying for: i) data query and data reloading techniques under ORAM model, ii) constructions of new ORAM model, iii) the integration between ORAM mechanism and secure two-party computation with peer participants, and iv) research on the fundamental applications of secure two-party computation under ORAM model. After a preliminary investigation, two scientific questions are addressed and refined in the project: i) maintaining the confidentiality of access patterns, and ii) equivalent transformations between RAM programs. We are planning to solve other items in the project based on the solutions to these two scientific questions. Desirable research achievements are also expected to be obtained in areas such as the privacy issues of traditional ORAM construction mechanism and constructions of new ORAM storage models which are suitable for secure two-party computation.

安全计算技术能够使得互不信任的参与方在各自私有信息均得到保障的前提下，有效地进行协作计算。然而，当前的安全计算技术尚不能有效支持RAM程序的隐私化，从而导致很多实际应用问题缺乏高效的安全协议构建方法。ORAM存储机制的引入使得有效解决RAM程序的隐私化问题成为可能，但在其与安全计算技术的融合过程中仍有很多开放性问题亟待科学解答。有鉴于此，本课题拟对如下四点内容展开深入研究：ORAM模型下的数据查询及重载入技术；新ORAM模型的构建；ORAM机制与对等参与方安全两方计算问题的融合；ORAM模型下安全两方计算技术的基础应用研究。经前期调研，我们凝练出本项目的两个关键科学问题：访问模式的机密性保持和RAM程序的等效变换。我们拟通过对这两个关键问题的科学解答来带动本课题其他研究内容的顺利开展，并预期在传统ORAM构建机制的隐私化以及构造适于安全两方计算的新ORAM存储模型等方面取得较好的研究成果。

当前的安全计算技术尚不能有效支持RAM程序的隐私化，从而导致很多实际应用问题缺乏高效的安全协议构建方法。本项目在ORAM模型下的数据查询及重载入技术,新ORAM模型的构建,ORAM机制与对等参与方安全两方计算问题的融合以及ORAM模型下安全两方计算技术的基础应用等研究方面均取得了一定的研究进展，从而为实现RAM程序的高效隐私化奠定了一定的理论基础。具体而言，在ORAM模型下的数据查询及重载人方面，我们在Path-ORAM以及CLP-ORAM的机制上，围绕安全原子操作（即安全读、写）展开深入研究，在关键基础协议构建以及安全协议组合方法方面取得了令人满意的结果。并在此基础上构建出了ORAM模型下的两方协作数据查询及重载入的高效安全协议。操作复杂度的理论分析以及实际的系统模拟表明我们所构建的新安全两方计算协议较之已有工作有2-3倍的效率提升。在高效安全数据重载入方面，我们基于Yao协议及加法同态加密构建出了多交叉度的数据推送方案，理论分析表明所构建的新方案在计算及通信复杂度方面均只略高于Wang等人所构建的无交叉方案。新方案能够将数据一次推送完成，从而避免传统无交叉方案在数据推送过程中所需要的数次重载入操作，因此在整体上提高了效率。在新ORAM构建方面，我们基于Boyel等人提出的高效私有信息提取（PIR）协议，构建出了一种双服务器模型下的新型ORAM机制。理论分析表明，在所构建的新型ORAM机制下，客户端在查询数据后无需进行数据重载入操作，因而能够很好的支持双边安全模型下的两方计算。在ORAM机制与对等参与方安全两方计算问题的融合方面，我们首先利用Paillier同态加密系统以及数据打包技术，构建出了高效的ORAM初始化协议。另外，我们通过改进Huang等人所提出的回归树技术，并结合对在Yao协议执行过程中所产生附加信息的有效利用，构建出了高效批量数据茫然提取协议。我们利用这种新的协议构建方法所实现的KNN查询以及Skyline查询安全协议的运行效率较之以前的工作有2-3个数量级的优化。