Paper 2019/1250

The Price of Active Security in Cryptographic Protocols

Carmit Hazay
Muthuramakrishnan Venkitasubramaniam
Mor Weiss
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 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 $F_{mult}$ , to an actively-secure protocol for general functionalities. Roughly, $F_{mult}$ is parameterized by a linear-secret sharing scheme S, where it takes S-shares of two secrets and returns S-shares of their product. We show that our compilation is concretely efficient for sufficiently large fields, resulting in an over- head of 2 when securely computing natural circuits. Our compiler has two additional benefits: (1) it can rely on any passive implementation of $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, we obtain the first honest-majority protocol with optimal corruption threshold for boolean circuits with constant communication overhead over the best passive protocol (Damgård and Nielsen, CRYPTO ‘07).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in EUROCRYPT 2020
Keywords
Secure Multi-Party ComputationConstant Communication OverheadCryptographic CompilersOblivious-TransferOblivious Linear-Evaluation
Contact author(s)
carmit hazay @ biu ac il
vmuthu @ gmail com
mormorweiss @ gmail com
History
2024-02-20: revised
2019-10-28: received
See all versions
Short URL
https://ia.cr/2019/1250
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1250,
      author = {Carmit Hazay and Muthuramakrishnan Venkitasubramaniam and Mor Weiss},
      title = {The Price of Active Security in Cryptographic Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1250},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1250}},
      url = {https://eprint.iacr.org/2019/1250}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.