Fast two-party secure computation with minimal assumptions
Fast two-party secure computation with minimal assumptions
复制标题
DOI：
10.1145/2508859.2516698
复制
发表时间：
2013-11
期刊：
影响因子：
--
通讯作者：
Abhi Shelat;Chih-Hao Shen
中科院分区：
文献类型：
--
作者：
Abhi Shelat;Chih-Hao Shen
几乎所有现有的安全两方计算协议都需要一个特定的硬度假设，如DDH，离散对数，或随机预言，即使在假设预言访问不经意传输功能的正确性和/或效率。我们提出并实现了一个基于Yao的协议，该协议对恶意攻击者是安全的，并具有以下优点：它需要最小硬度假设，即，OT;它使用10轮通信加上OT轮;它具有最佳的开销复杂度（对于使用电路级切割和选择技术的方法）;并且在每个电路可以以流水线方式处理并且所有电路可以并行处理的意义上，它是可并行的。为了实现这些属性，我们描述了新的解决方案的三个主要障碍，以实现安全防范恶意对手的切割和选择混淆电路协议。我们提出了一个有效的证明，以建立发电机的输出真实性，我们建议使用一个辅助电路，计算一个哈希值，以确保发电机的输入一致性，我们推进性能的Pinkas和Lindell的国家的最先进的方法处理选择性故障攻击。我们的协议不仅需要较弱的密码学假设，但我们的实现这个协议也证明了一个最好的先前的工作，依赖于特定的数论假设的几个因素的改进。因此，我们表明，性能不需要特定的代数假设。
Almost all existing protocols for secure two-party computation require a specific hardness assumption, such as DDH, discrete logarithm, or a random oracle, even after assuming oracle access to the oblivious transfer functionality for their correctness and/or efficiency. We propose and implement a Yao-based protocol that is secure against malicious adversaries and enjoys the following benefits: it requires the minimal hardness assumption, i.e., OTs; it uses 10 rounds of communication plus OT rounds; it has the optimal overhead complexity (for an approach that uses the circuit-level cut-and-choose technique); and it is embarrassingly parallelizable in the sense that each circuit can be processed in a pipelined manner, and all circuits can be processed in parallel. To achieve these properties, we describe novel solutions for the three main obstacles for achieving security against malicious adversaries in a cut-and-choose garbled-circuit protocol. We propose an efficient proof to establish the generator's output authenticity; we suggest the use of an auxiliary circuit that computes a hash to ensure the generator's input consistency; and we advance the performance of Pinkas and Lindell's state-of-the-art approach for handling the selective failure attack. Not only does our protocol require weaker cryptographic assumptions, but our implementation of this protocol also demonstrates a several factor improvement over the best prior work which relies on specific number-theoretic assumptions. Thus, we show that performance does not require specific algebraic assumptions.