1. Reducing communication costs in multi-party computation
- Author
-
Wood, Tim N. and Smart, Nigel
- Subjects
004 ,cryptography ,secret-sharing ,mpc ,garbled circuits ,preprocessing model - Abstract
Multi-party computation (MPC) is a way of computing on private data without revealing the data itself. To do this, data is "secret-shared" amongst a set of mutually-distrusting parties, which perform local computations and interactive processes to evaluate a function. MPC protocols are diverse and offer a variety of different security guarantees, and employ different methodologies to optimize for different aspects of the evaluation. The goal of this work is to show how to reduce communication costs involved in different areas of MPC. An 'access structure' defines which sets of parties a so-called adversary can corrupt such that the inputs remain private and the outputs are revealed to the right parties; one type of access structure is called Q₂, under which assumption there are many classical results on what sorts of functions can be evaluated. One of the contributions of this work is to show how special "error-detection" properties that apply in the context of Q₂ access structures can be used to define MPC protocols that improve on the efficiency of classical results. In the so-called 'preprocessing model', parties evaluate a function on random inputs, and later "derandomize" using the real (private) inputs. This model is popular in MPC as function evaluation is expensive, whereas derandomization is cheap. In this thesis, a generic method is given for outsourcing preprocessing to a set of servers, which means that low-powered clients who wish to evaluate functions on their data can do so. The final contribution is a protocol that allows parties to mix two different MPC techniques called 'garbled circuits' and 'secret-sharing' in a secure way, even when the adversary deviates arbitrarily from the protocol description. Mixing these methods is useful as they optimize for different aspects of computation.
- Published
- 2019