(1) Our first protocol takes a generic approach using any secret-sharing based MPC protocol for binary circuits, and a correlated oblivious transfer functionality.
(2) Our specialized protocol uses secret-sharing based MPC with information-theoretic MACs. This approach is less general, but requires no additional correlated OTs to compute the garbled circuit.
In both approaches, the underlying secret-sharing based protocol is only used for one secure $F_2$ multiplication per AND gate. An interesting consequence of this is that, with current techniques, constant round MPC for binary circuits is not much more expensive than practical, non-constant round protocols.
We demonstrate the practicality of our second protocol with an implementation, and perform experiments with up to $9$ parties securely computing the AES and SHA-256 circuits. Our running times improve upon the best possible performance with previous BMR-based protocols by 60 times.
Category / Keywords: cryptographic protocols / MPC, TinyOT, BMR Original Publication (with minor differences): IACR-ASIACRYPT-2017 Date: received 1 Mar 2017, last revised 13 Apr 2020 Contact author: eduardo soria-vazquez at bristol ac uk, carmit hazay at biu ac il, peter scholl at cs au dk Available format(s): PDF | BibTeX Citation Note: Fixed minor issues. Version: 20200413:192800 (All versions of this report) Short URL: ia.cr/2017/214