Paper 2018/1227

Efficient Information Theoretic Multi-Party Computation from Oblivious Linear Evaluation

Louis Cianciullo and Hossein Ghodosi

Abstract

Oblivious linear evaluation (OLE) is a two party protocol that allows a receiver to compute an evaluation of a sender's private, degree $1$ polynomial, without letting the sender learn the evaluation point. OLE is a special case of oblivious polynomial evaluation (OPE) which was first introduced by Naor and Pinkas in 1999. In this article we utilise OLE for the purpose of computing multiplication in multi-party computation (MPC). MPC allows a set of $n$ mutually distrustful parties to privately compute any given function across their private inputs, even if up to $t<n$ of these participants are corrupted and controlled by an external adversary. In terms of efficiency and communication complexity, multiplication in MPC has always been a large bottleneck. The typical method employed by most current protocols has been to utilise Beaver's method, which relies on some precomputed information. In this paper we introduce an OLE-based MPC protocol which also relies on some precomputed information. Our proposed protocol has a more efficient communication complexity than Beaver's protocol by a multiplicative factor of $t$. Furthermore, to compute a share to a multiplication, a participant in our protocol need only communicate with one other participant; unlike Beaver's protocol which requires a participant to contact at least $t$ other participants.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. The 12th WISTP International Conference on Information Security Theory and Practice (WISTP'2018)
Keywords
information theoreticmulti-party computationoblivious linear evaluation
Contact author(s)
louis cianciullo @ my jcu edu au
History
2018-12-30: received
Short URL
https://ia.cr/2018/1227
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1227,
      author = {Louis Cianciullo and Hossein Ghodosi},
      title = {Efficient Information Theoretic Multi-Party Computation from Oblivious Linear Evaluation},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1227},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1227}},
      url = {https://eprint.iacr.org/2018/1227}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.