Constant-overhead secure computation of Boolean circuits using preprocessing. (English) Zbl 1315.94068

Sahai, Amit (ed.), Theory of cryptography. 10th theory of cryptography conference, TCC 2013, Tokyo, Japan, March 3–6, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-36593-5/pbk). Lecture Notes in Computer Science 7785, 621-641 (2013).
Summary: 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 a preprocessing functionality that is not given the inputs. For a large number of players the work for each player is the same as computing 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 only achieved constant error.
For the entire collection see [Zbl 1258.94005].


94A60 Cryptography
94A62 Authentication, digital signatures and secret sharing
94C05 Analytic circuit theory
68M14 Distributed systems
68P25 Data encryption (aspects in computer science)
Full Text: DOI