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.
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).
Oblivious transfer is one of the most important cryptographic primitives, both for theoretical and practical reasons and several protocols were proposed during the years. We provide the first oblivious transfer protocol which is simultaneously optimal on the following list of parameters: Security: it has universal composition. Trust in setup assumptions: only one of the parties needs to trust the setup (and some setup is needed for UC security). Trust in computational assumptions: only one of the parties needs to trust a computational assumption. Round complexity: it uses only two rounds. Communication complexity: it communicates O(1) group elements to transfer one out of two group elements. The Big-O notation hides 32, meaning that the communication is probably not optimal, but is essentially optimal in that the overhead is at least constant. Our construction is based on pairings, and we assume the presence of a key registration authority.