Ad Hoc PSM Protocols: Secure Computation Without Coordination
Ad Hoc PSM Protocols: Secure Computation Without Coordination
复制标题
DOI：
10.1007/978-3-319-56617-7_20
复制
发表时间：
2017-04
期刊：
影响因子：
--
通讯作者：
A. Beimel;Yuval Ishai;E. Kushilevitz
中科院分区：
文献类型：
--
作者：
A. Beimel;Yuval Ishai;E. Kushilevitz
我们研究了Beimel等人（ITCS 2016）最近提出的ad hoc安全计算的概念，在Feige等人（STOC 2004）的私人同时消息（PSM）模型的背景下。在ad hoc安全计算中，我们有可能参与协议的各方，但在实际执行时，只有k个各方实际参与，他们的身份事先未知。这种情况是特别具有挑战性的PSM设置，其中协议是非交互式的（一个单一的消息从每个参与方到一个特殊的输出方）和各方依赖于预先分布的，相关的随机性（在特设设置将不得不考虑所有可能的参与者集）。这些建设意味着，特别是，有效的信息理论的ad hoc PSM协议存在NC和不同类别的日志空间计算，和有效的计算安全的ad hoc PSM协议的多项式时间可计算函数可以基于单向函数。作为应用，我们得到了一个信息论实现的forder-revealing协议，其安全性对两个消息成立，我们还考虑了实际参与方的数目可能大于协议设计的最小值的情况。在这种情况下，不可避免的是，输出方学习与thetparticipants的kout的每个子集相对应的输出。因此，需要一个“最佳可能安全性”的概念，要求这将是输出方学习的唯一信息。我们提出了这个概念和以前研究的概念oft-robust PSM（也称为“非交互式MPC”）之间的连接。我们表明，即使是简单的功能（如AND或阈值），在这种设置中的结构可以转化为非平凡的程序混淆的情况下（如点函数混淆和模糊点函数混淆，分别）。我们认为这些结果是一个负面的迹象，协议与“尽可能最好的安全性”是不可能实现有效的信息理论设置或需要强有力的假设，在计算环境。
We study the notion ofad hoc secure computation, recently introduced by Beimel et al. (ITCS 2016), in the context of thePrivate Simultaneous Messages(PSM) model of Feige et al. (STOC 2004). In ad hoc secure computation we havenparties that may potentially participate in a protocol but, at the actual time of execution, onlykof them, whose identity isnotknown in advance, actually participate. This situation is particularly challenging in the PSM setting, where protocols are non-interactive (a single message from each participating party to a special output party) and where the parties rely on pre-distributed, correlated randomness (that in the ad-hoc setting will have to take into account all possible sets of participants).We present several different constructions of ad hoc PSM protocols from standard PSM protocols. These constructions imply, in particular, that efficient information-theoretic ad hoc PSM protocols exist for NCand different classes of log-space computation, and efficient computationally-secure ad hoc PSM protocols for polynomial-time computable functions can be based on a one-way function. As an application, we obtain an information-theoretic implementation oforder-revealing encryptionwhose security holds for two messages.We also consider the case where the actual number of participating partiestmay be larger than the minimalkfor which the protocol is designed to work. In this case, it is unavoidable that the output party learns the output corresponding to each subset ofkout of thetparticipants. Therefore, a “best possible security” notion, requiring that this will be theonlyinformation that the output party learns, is needed. We present connections between this notion and the previously studied notion oft-robust PSM(also known as “non-interactive MPC”). We show that constructions in this setting for even simple functions (like AND or threshold) can be translated into non-trivial instances of program obfuscation (such aspoint function obfuscationandfuzzy point function obfuscation, respectively). We view these results as a negative indication that protocols with “best possible security” are impossible to realize efficiently in the information-theoretic setting or require strong assumptions in the computational setting.