实用安全多方计算理论研究

This project aims at the research on some crucial theoretical problems in implementing secure multi-party computation (SMPC) practically. First, to meet the requirements arisen in practice and capture the real world attacks, we improve the secure model either by focusing on fairness or by considering leakage scenarios. For the first purpose, we explore the features of functionalities which can be completely fairly computed, and design two-output secure two-party computation protocols with complete fairness; moreover, we investigate the definition of weaker fairness in ideal/real simulation paradigm, and design protocols with proper fairness in different scenarios. For the second purpose, we study the existence and construction of leakage resilient general SMPC protocols against malicious adversaries in the standard model; in addition, we design leakage resilient SMPC protocols based on the cut-and-choose technique. Next, we improve the efficiency of the protocols either inherently or by outsourcing the computation tasks. To achieve this goal inherently, we intend to reduce the circuit replication factor in cut-and-choose-based secure two-party computation while keeping the cheating probability; besides, we try to solve the problems of the input consistency of circuit generator, the selective failure attack in OT and the two-output functions. To outsource computation tasks, we construct cloud-aided SMPC protocols in malicious adversary model based on homomorphic encryption, and design cloud-aided SMPC protocols against any collusion attack based on Yao’s garbled circuit.

本项目拟研究安全多方计算实用化面临的关键理论问题。首先，完善安全模型以反映真实协议执行的需求和环境，关注协议的公平性，考虑侧信息泄漏。在公平性方面，探寻可被完全公平计算的功能函数的特征，并设计完全公平的两输出安全两方计算协议；研究在理想/现实模拟范例中弱公平性的定义，根据不同环境设计适当公平性协议；在泄漏场景下，研究标准模型下抗恶意敌手攻击的通用多方计算协议的存在性及构造，构建泄漏场景下基于切割-选择技术的安全两方计算协议。其次，从协议本身和计算外包层面提高协议效率。协议本身层面，基于切割-选择技术，在保持错误率不变的情况下降低电路复制因子，研究高效解决混乱电路构造方输入一致性问题、OT中的选择性失败攻击问题和两输出函数问题的方法；外包计算层面，设计恶意敌手模型下基于同态加密的云辅助安全多方计算协议，以及任意合谋攻击下基于Yao混乱电路的云辅助安全多方计算协议。

项目组按照项目申请时制定的研究内容与研究计划开展研究。.首先综述了实用化安全多方计算技术，包括云辅助安全多方计算技术，梳理了研究现状，存在问题以及未来发展方向，为后续研究奠定基础。.第二，研究安全多方计算协议及其基础工具。提出cut and choose（切割-选择）双边不经意传输的密码学原语，并基于DDH假设给出一个具体的协议构造，有效降低了安全两方计算协议的交互复杂度。研究了如何在保持cut-and-choose（切割-选择）安全两方计算最优错误概率的情况下，高效解决两输出函数计算问题。此外，还在OT协议、ORAM协议、云辅助安全计算以及抗泄露函数加密方面取得一些研究成果。.第三，在云计算及区块链技术背景之下，应用安全多方计算技术解决数据安全与隐私保护。提出了一种前向安全的可搜索加密方案，具备更好的I/O效率。提出一个隐私保护的安全外包模式匹配协议。研究位置隐私保护协议，提出一类隐私保护的无线定位算法，并提出一个具有位置隐私保护的位置认证协议。构造具有高安全等级的密码水印方案，给出了新的安全性定义和新的构造方法，得到具有更高安全性的方案。借助区块链技术，构造具有撤销功能的无中心匿名认证方案。.第四，研究后量子安全多方计算技术。构造了一个基于格的高效零知识证明系统，解决了现有基于格的零知识证明系统无法兼顾标准可靠性与低可靠性误差的问题，利用得到的基本零知识证明系统模型，构造了对多个格中基本问题（比如，LWE, SIS）及密码学关系（比如，明文-密文，消息-签名）进行证明的高效零知识证明系统，并将其用于构造应用协议。