AF: SMALL: Quorums Quicken Queries - Towards Practical Secure Multiparty Computation

安全的系统需要理论上的保证。安全多方计算（MPC）问题抽象了分布式安全中的许多重要问题，从而为设计具有可证明安全保证的分布式算法提供了一个通用框架。不幸的是，目前解决MPC的算法还远远不够高效。因此，当系统构建者面对属于MPC范畴的问题时，无法使用具有众所周知的理论保证的既定算法。相反，他们经常被要求设计新的特别启发式方法。该项目的目标是通过为MPC设计资源高效的算法来解决这一空白。在MPC问题中，有n个玩家，每个玩家都有一个私人输入。我们的目标是在所有输入上安全地计算一个n元函数f，而不透露任何关于输入的信息，而不是从函数的输出中学习。我们假设f可以通过具有m个逻辑门的电路来计算。在这个项目中，PI将为MPC设计稳健的算法，因为1)它们可以容忍多达1/3的玩家被对手控制；2)即使在所有没有缺陷的玩家都是自私但理性的情况下，它们也有效。重要的是，算法将有以下资源成本：每个玩家发送O（n+m/n+ sqrt(n)）个比特，并执行O（n+m/n+ sqrt(n)）个计算。这些资源成本是对最先进的MPC算法的显著改进，MPC算法要求每个播放器发送O（nm）比特并执行O（nm）计算。MPC概括了分布式计算中的许多重要问题，包括拍卖、阈值密码学、投票和隐私保护数据挖掘等经典问题；还有当代的问题，比如云计算，以及点对点网络上的计算。因此，安全MPC问题的解决方案可能会在许多基本问题上取得进展。该项目的主要目标是将高效的MPC算法应用于可证明的安全和可扩展的匿名广播问题。

Secure systems demand theoretical guarantees.  The problem of secure multiparty computation (MPC) abstracts many important problems in distributed security, and thus offers the promise of a general framework for designing distributed algorithms with provable security guarantees.   Unfortunately, current algorithms for solving MPC are far from efficient.  Thus, system builders, when faced with a problem that falls under the rubric of MPC, are unable to make use of established algorithms with well-known theoretical guarantees. Instead, they are frequently required to design new ad hoc heuristics. The goal of this project is to address this vacuity by designing resource efficient algorithms for MPC.In the MPC problem, there are n players, each with a private input. The goal is to securely compute an n-ary function, f, over all inputs, without revealing anything more about the inputs than can be learned from the output of the function.  We assume that f can be computed by a circuit with m logic gates. In this project, the PI will design algorithms for MPC that are robust in that 1) they can tolerate up to a 1/3 fraction of the players being controlled by an adversary; and 2) they work even in the case where all non-faulty players are selfish but rational.  Importantly, the algorithms will have the following resource costs: each player sends O(n+m/n + sqrt(n)) bits, and performs O(n+m/n+ sqrt(n)) computations. These resource costs are significant improvements over state of the art MPC algorithms, which require each player to send O(nm) bits and perform O(nm) computations.MPC generalizes many important problems in distributed computing including classic problems such as: auctions, threshold cryptography, voting and privacy-preserving data mining; and contemporary problems such as: cloud computing, and computing over peer-to-peer networks. Thus, a solution to the secure MPC problem will likely enable progress in many fundamental problems.  A major goal of this project is to apply efficient MPC algorithms to the problem of provably secure and scalable anonymous broadcast.