Lean and Fast Secure Multi-party Computation: Minimizing Communication and Local Computation using a Helper

Johannes Schneider

2016

Abstract

A client wishes to outsource computation on confidential data to a network of servers. He does not trust a single server, but believes that multiple servers do not collude. To solve this problem we introduce a new scheme called JOS for perfect security in the semi-honest model that naturally requires at least three parties. It differs from classical secure multi-party computation (MPC) through three points: (i) a client-server setting, where all inputs and outputs are only known to the client; (ii) the use of three parties, where one party serves merely as “helper” for computation, but does not store any shares of a secret; (iii) distinct use of the distributive and associative nature of well-known linear encryption schemes to derive our protocols. We improve on the total amount of communication needed to compute both an AND and a multiplication compared to all prior schemes (even two party protocols), while matching round complexity or requiring only one more round. For big-data analysis, network bandwidth is often the most severe limitation, thus minimizing the amount of communication is essential. Therefore, we make an important step towards making MPC more practical. We also reduce the total amount of storage needed (eg. in a database setting) compared to all prior schemes using three parties. Our local computation requirements lag behind non-encrypted computation by less than an order of magnitude per party, while improving on other schemes, ie. GRR, by several orders of magnitude.

Paper Citation

in Harvard Style

Schneider J. (2016). Lean and Fast Secure Multi-party Computation: Minimizing Communication and Local Computation using a Helper . In Proceedings of the 13th International Joint Conference on e-Business and Telecommunications - Volume 4: SECRYPT, (ICETE 2016) ISBN 978-989-758-196-0, pages 223-230. DOI: 10.5220/0005954202230230

in Bibtex Style

@conference{secrypt16,
author={Johannes Schneider},
title={Lean and Fast Secure Multi-party Computation: Minimizing Communication and Local Computation using a Helper},
booktitle={Proceedings of the 13th International Joint Conference on e-Business and Telecommunications - Volume 4: SECRYPT, (ICETE 2016)},
year={2016},
pages={223-230},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005954202230230},
isbn={978-989-758-196-0},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 13th International Joint Conference on e-Business and Telecommunications - Volume 4: SECRYPT, (ICETE 2016)
TI - Lean and Fast Secure Multi-party Computation: Minimizing Communication and Local Computation using a Helper
SN - 978-989-758-196-0
AU - Schneider J.
PY - 2016
SP - 223
EP - 230
DO - 10.5220/0005954202230230