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.