Round Optimal Concurrent MPC via Strong Simulation
Round Optimal Concurrent MPC via Strong Simulation
复制标题
DOI：
10.1007/978-3-319-70500-2_25
复制
发表时间：
2017-11
期刊：
影响因子：
--
通讯作者：
S. Badrinarayanan;Vipul Goyal;Abhishek Jain;Dakshita Khurana;A. Sahai
中科院分区：
文献类型：
--
作者：
S. Badrinarayanan;Vipul Goyal;Abhishek Jain;Dakshita Khurana;A. Sahai
本文利用超多项式模拟(SPS)研究了平面模型下并发安全多方计算(MPC)的轮复杂性。在纯模型中，已知的显式攻击表明多项式模拟的并发安全MPC是不可能实现的；SPS安全是平面模型中研究最广泛的并发安全MPC模型。我们得到了以下结果：假设次指数安全的DDH和LWE，对抗拜占庭攻击的具有SPS安全性的三轮并发MPC。假设次指数安全的不可区分混淆和DDH，对抗拜占庭攻击的具有SPS安全的两轮并发MPC。在我们的工作之前，据我们所知，具有SPS安全的并发MPC需要大约20轮，尽管我们不知道有任何工作甚至给出了足以用于多方设置的恒定轮复杂性的近似值。我们还改进了之前的两方设置的最好轮的复杂性，其中需要5轮(Garg，Kiyoshima和Pandey，Eurocrypt 2017)。为了获得我们的结果，我们编译了已经实现了对“半恶意”对手的安全性的协议，以保护协议免受完全恶意的对手的攻击，另外假设次指数DDH。我们的协议开发了新的技术来使用两轮零知识和超多项式强模拟，这是由PASS(Eurocrypt 2003)定义的，最近由Khurana和Sahai(FOCS 2017)实现。对于运行时间大于模拟器运行时间的对手，这些仍然是零知识。
In this paper, we study the round complexity of concurrently secure multi-party computation (MPC) with super-polynomial simulation (SPS) in the plain model. In the plain model, there are known explicit attacks that show that concurrently secure MPC with polynomial simulation is impossible to achieve; SPS security is the most widely studied model for concurrently secure MPC in the plain model. We obtain the following results:Three-round concurrent MPC with SPS security against Byzantine adversaries, assuming sub-exponentially secure DDH and LWE.Two-round concurrent MPC with SPS security against Byzantine adversaries for input-less randomized functionalities, assuming sub-exponentially secure indistinguishability obfuscation and DDH. In particular, this class includes sampling functionalities that allow parties to jointly sample a secure common reference string for cryptographic applications.Prior to our work, to the best of our knowledge, concurrent MPC with SPS security required roughly 20 rounds, although we are not aware of any work that even gave an approximation of the constant round complexity sufficient for the multi-party setting. We also improve over the previous best round complexity for the two-party setting, where 5 rounds were needed (Garg, Kiyoshima, and Pandey, Eurocrypt 2017).To obtain our results, we compile protocols that already achieve security against “semi-malicious” adversaries, to protocols secure against fully malicious adversaries, additionally assuming sub-exponential DDH. Our protocols develop new techniques to use two-round zero-knowledge with super-polynomialstrongsimulation, defined by Pass (Eurocrypt 2003) and very recently realized by Khurana and Sahai (FOCS 2017). These remain zero-knowledge against adversaries running in time larger than the running time of the simulator.