At Crypto 2003 Ishai et al. gave a protocol which given a small number of (possibly extremely inefficient) oblivious transfers implements an essentially unbounded number of oblivious transfers for an additional overhead, per oblivious transfer, of computing and sending only two hash values. This highly efficient protocol is however only passive secure. To get active security, except with probability 2 −m, the protocol had to suffer an additional overhead of a factor 1 + m. We introduce a new approach to adding robustness. For practical security parameters this approach allows to add robustness while suffering only a small constant overhead over the passive secure protocol. As an example we can generate one million oblivious transfers with security 2 −42 with an amortized cost of just 9 hash values per oblivious transfer. 1
Abstract We construct the first actively-secure Multi-Party Computation (MPC) protocols with an arbitrary number of parties in the dishonest majority setting, for an arbitrary field
F F with constant communication overhead over the “passive-GMW” protocol (Goldreich, Micali and Wigderson, STOC ‘87). Our protocols rely on passive implementations of Oblivious Transfer (OT) in the Boolean setting and Oblivious Linear function Evaluation (OLE) in the arithmetic setting. Previously, such protocols were only known over sufficiently large fields (Genkin et al. STOC ‘14) or a constant number of parties (Ishai et al. CRYPTO ‘08). Conceptually, our protocols are obtained via a new compiler from a passively-secure protocol for a distributed multiplication functionality
FMULT F MULT , to an actively-secure protocol for general functionalities. Roughly,
FMULT F MULT is parameterized by a linear-secret sharing scheme
S S , where it takes
S S -shares of two secrets and returns
S S -shares of their product. We show that our compilation is concretely efficient for sufficiently large fields, resulting in an overhead of 2 when securely computing natural circuits. Our compiler has two additional benefits: (1) It can rely on any passive implementation of
FMULT F MULT , which, besides the standard implementation based on OT (for Boolean) and OLE (for arithmetic), allows us to rely on implementations based on threshold cryptosystems (Cramer et al. Eurocrypt ‘01), and (2) it can rely on weaker-than-passive (i.e., imperfect/leaky) implementations, which in some parameter regimes yield actively-secure protocols with overhead less than 2. Instantiating this compiler with an “honest-majority” implementation of
FMULT F MULT , we obtain the first honest-majority protocol (with up to one-third corruptions) for Boolean circuits with constant communication overhead over the best passive protocol (Damgård and Nielsen, CRYPTO ‘07).
In this work, we present two new actively secure, constant-round multi-party computation (MPC) protocols with security against all-but-one corruptions. Our protocols both start with an actively secure MPC protocol, which may have linear round complexity in the depth of the circuit, and compile it into a constant-round protocol based on garbled circuits, with very low overhead. Our first protocol takes a generic approach using any secret-sharing-based MPC protocol for binary circuits, and a correlated oblivious transfer functionality. Our second protocol builds on secret-sharing-based MPC with information-theoretic MACs. This approach is less flexible, being based on a specific form of MPC, but requires no additional oblivious transfers to compute the garbled circuit. In both approaches, the underlying secret-sharing-based protocol is only used for one actively secure
F2 multiplication per AND gate . An interesting consequence of this is that, with current techniques, constant-round MPC for binary circuits is not much more expensive than practical, non-constant-round protocols. We demonstrate the practicality of our second protocol with an implementation and perform experiments with up to 9 parties securely computing the AES and SHA-256 circuits. Our running times improve upon the best possible performance with previous protocols in this setting by 60 times.