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

University Of New Mexico, Albuquerque NM

Investigators

Abstract

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.