Constant-Overhead Secure Computation of Boolean Circuits using Preprocessing

Ivan Damgard; Sarah Zakarias

Paper 2012/512

Constant-Overhead Secure Computation of Boolean Circuits using Preprocessing

Ivan Damgard and Sarah Zakarias

Abstract

We present a protocol for securely computing a Boolean circuit $C$ in presence of a dishonest and malicious majority. The protocol is unconditionally secure, assuming access to a preprocessing functionality that is not given the inputs to compute on. For a large number of players the work done by each player is the same as the work needed to compute the circuit in the clear, up to a constant factor. Our protocol is the first to obtain these properties for Boolean circuits. On the technical side, we develop new homomorphic authentication schemes based on asymptotically good codes with an additional multiplication property. We also show a new algorithm for verifying the product of Boolean matrices in quadratic time with exponentially small error probability, where previous methods would only give a constant error.

Note: Added sketch of how preprocessing can be done based on protocol from [DPSZ12]

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Unknown where it was published
Keywords: protocols authentication secure computation
Contact author(s): ivan @ cs au dk
szakarias @ gmail com
History: 2013-03-01: last of 9 revisions; 2012-09-03: received; See all versions
Short URL: https://ia.cr/2012/512
License: CC BY

BibTeX

@misc{cryptoeprint:2012/512,
      author = {Ivan Damgard and Sarah Zakarias},
      title = {Constant-Overhead Secure Computation of Boolean Circuits using Preprocessing},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/512},
      year = {2012},
      url = {https://eprint.iacr.org/2012/512}
}