Practical Covertly Secure MPC for Dishonest Majority – or: Breaking the SPDZ Limits

Ivan Damgard; Marcel Keller; Enrique Larraia; Valerio Pastro; Peter Scholl; Nigel P.  Smart

Paper 2012/642

Practical Covertly Secure MPC for Dishonest Majority – or: Breaking the SPDZ Limits

Ivan Damgard, Marcel Keller, Enrique Larraia, Valerio Pastro, Peter Scholl, and Nigel P. Smart

Abstract

SPDZ (pronounced “Speedz”) is the nickname of the MPC protocol of Damg°ard et al. from Crypto 2012. SPDZ provided various efficiency innovations on both the theoretical and practical sides compared to previous work in the preprocessing model. In this paper we both resolve a number of open problems with SPDZ; and present several theoretical and practical improvements to the protocol. In detail, we start by designing and implementing a covertly secure key generation protocol for distributed BGV secret keys. In prior work this was assumed to be provided by a given setup functionality. Protocols for distributingBGV secret keys are likely to be of wider applicability than to the SPDZ protocol alone. We then construct both a covertly and actively secure preprocessing phase, both of which compare favourably with previous work in terms of efficiency and provable security. We also build a new online phase, which solves a major problem of the SPDZ protocol: namely prior to this work preprocessed data could be used for only one function evaluation and then had to be recomputed from scratch for the next evaluation, while our online phase can support reactive functionalities. This improvement comes mainly from the fact that our construction does not require players to reveal the MAC keys to check correctness of MAC’d values. Since our focus is also on practical instantiations, our implementation offloads as much computation as possible into the preprocessing phase, thus resulting in a faster online phase. Moreover, a better analysis of the parameters of the underlying cryptoscheme and a more specific choice of the field where computation is performed allow us to obtain a better optimized implementation. Improvements are also due to the fact that our construction is in the random oracle model, and the practical implementation is multi-threaded.

Note: Full Version of Paper

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Published elsewhere. Major revision. ESORICS 2013
DOI: http://dx.doi.org/10.1007/978-3-642-40203-6_1
Contact author(s): nigel @ compsci bristol ac uk
enrique larraiadevega @ bristol ac uk
m keller @ bristol ac uk
Peter Scholl @ bristol ac uk
ivan @ cs au dk
vpastro @ cs au dk
History: 2013-08-20: last of 2 revisions; 2012-11-11: received; See all versions
Short URL: https://ia.cr/2012/642
License: CC BY

BibTeX

@misc{cryptoeprint:2012/642,
      author = {Ivan Damgard and Marcel Keller and Enrique Larraia and Valerio Pastro and Peter Scholl and Nigel P.  Smart},
      title = {Practical Covertly Secure {MPC} for Dishonest Majority – or: Breaking the {SPDZ} Limits},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/642},
      year = {2012},
      doi = {http://dx.doi.org/10.1007/978-3-642-40203-6_1},
      url = {https://eprint.iacr.org/2012/642}
}