[Resource Topic] 2016/809: Binary AMD Circuits from Secure Multiparty Computation

Welcome to the resource topic for 2016/809

Title:
Binary AMD Circuits from Secure Multiparty Computation

Authors: Daniel Genkin, Yuval Ishai, Mor Weiss

Abstract:

An AMD circuit over a finite field \mathbb F is a randomized arithmetic circuit that offers the best possible protection'' against additive attacks. That is, the effect of every additive attack that may blindly add a (possibly different) element of $\mathbb F$ to every internal wire of the circuit can be simulated by an ideal attack that applies only to the inputs and outputs. Genkin et al. (STOC 2014, Crypto 2015) introduced AMD circuits as a means for protecting MPC protocols against active attacks, and showed that every arithmetic circuit C over F can be transformed into an equivalent AMD circuit of size $O(|C|)$ with $O(1/|\mathbb F|)$ simulation error. However, for the case of the binary field $\mathbb F=\mathbb F_2$, their constructions relied on a tamper-proof output decoder and could only realize a weaker notion of security. We obtain the first constructions of fully secure binary AMD circuits. Given a boolean circuit $C$ and a statistical security parameter $s$, we construct an equivalent binary AMD circuit $C'$ of size $|C|*polylog(|C|,s)$ (ignoring lower order additive terms) with $2^{-s}$ simulation error. That is, the effect of toggling an arbitrary subset of wires can be simulated by toggling only input and output wires. Our construction combines in a general way two types of simple’’ honest-majority MPC protocols: protocols that only offer security against passive adversaries, and protocols that only offer correctness against active adversaries. As a corollary, we get a conceptually new technique for constructing active-secure two-party protocols in the OT-hybrid model, and reduce the open question of obtaining such protocols with constant computational overhead to a similar question in these simpler MPC models.

ePrint: https://eprint.iacr.org/2016/809

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .