The idea of using Information Theoretic Message Authentication Codes (MACs) in Multiparty Computation (MPC) goes back to Rabin and Ben-Or who used the idea in 1989 in for MPC with honest majority. Several optimizations of the technique have been proposed, but always in the honest majority setting. In recent work with Bendlin, Orlandi and Zakarias, we show that such MACs can also be used in the dishonest majority setting. Although public-key technology is required in this setting, this can all be pushed into a preprocessing phase where the actual inputs need not be known. When the inputs become available, the actual computation can be done very efficiently with only information theoretic tools. We describe several variants of the technique, including one that allows secure computation on Boolean circuits, where the work done by a player in the on-line phase approaches the complexity of computing the circuit in cleartext.
Copyright. All Rights Reserved.