On the (in)efficiency of non-interactive secure multiparty
On the (in)efficiency of non-interactive secure multiparty
复制标题
关于非交互式安全多方的（低）效率
DOI：
10.1007/s10623-017-0424-7
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Satoshi Obana
中科院分区：
文献类型：
--
作者：
Maki Yoshida;Satoshi Obana
安全多方计算 (MPC) 使多个参与者能够在对手存在的情况下合作评估各种功能。在本文中，我们考虑在信息论环境中针对诚实但好奇的对手的非交互式 MPC（NIMPC），这是 Beimel 等人提出的。 在 CRYPTO 2014 上。他们的主要重点是在完全避免交互的同时实现更强的安全性，并成功地表明每个功能都承认完全健壮的 NIMPC 协议。在本文中，我们进一步开展了NIMPC的研究。我们首先根据 NIMPC 的正确性要求得出一个简单的通信复杂度下限。其次，我们提出了一种用于指标函数的高效 NIMPC 协议，它是 NIMPC 协议的重要构建块。任意函数的 NIMPC 协议也是通过使用 Beimel 等人引入的通用编译器从针对指示函数提出的 NIMPC 构建的。在 CRYPTO 2014 中。本文提出的 NIMPC 协议的通信复杂性比以前的协议要高效得多。事实上，通信复杂度的下限和上限之间的差距从输入长度的指数减小到二次。最后，我们展示了所谓的离线-在线模型效率的一些改进。具体来说，对于某些功能集，离线通信的指数量将在线通信减少到标准模型中几乎最佳的量。
Secure multi-party computation (MPC) enables multiple players to cooperatively evaluate various functions in the presence of adversaries. In this paper, we considernon-interactiveMPC (NIMPC) against honest-but-curious adversaries in the information-theoretic setting, which was introduced by Beimel et al. at CRYPTO 2014. Their main focus is to realize stronger security while completely avoiding interaction, and succeeded to show that every function admits a fully robust NIMPC protocol. In this paper, we further develop the study of NIMPC. We first present a simple lower bound on the communication complexity derived from the correctness requirement of NIMPC. Secondly, we present an efficient NIMPC protocol for indicator functions, which is an important building block of NIMPC protocols. An NIMPC protocol for arbitrary functions is also constructed from the proposed NIMPC for indicator functions by using the generic compiler introduced by Beimel et al. in CRYPTO 2014. The communication complexities of NIMPC protocols presented in this paper are much more efficient than the previous ones. In fact, the gap between the lower and upper bounds of the communication complexity is reduced from exponential in the input length toquadratic. Finally, we show some improvements on the efficiency in the so-calledoffline-onlinemodel. Specifically, for some sets of functions, the exponential amount ofofflinecommunication reduces theonlinecommunication to almost optimum amount in the standard model.