Paper 2018/1065

Homomorphic Secret Sharing for Low Degree Polynomials

Russell W. F. Lai, Giulio Malavolta, and Dominique Schröder

Abstract

Homomorphic secret sharing (HSS) allows $n$ clients to secret-share data to $m$ servers, who can then homomorphically evaluate public functions over the shares. A natural application is outsourced computation over private data. In this work, we present the first plain-model homomorphic secret sharing scheme that supports the evaluation of polynomials with degree higher than 2. Our construction relies on any degree-$k$ (multi-key) homomorphic encryption scheme and can evaluate degree-$\left( (k+1)m -1 \right)$ polynomials, for any polynomial number of inputs $n$ and any sub-logarithmic (in the security parameter) number of servers $m$. At the heart of our work is a series of combinatorial arguments on how a polynomial can be split into several low-degree polynomials over the shares of the inputs, which we believe is of independent interest.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in ASIACRYPT 2018
Keywords
secret sharing
Contact author(s)
russell lai @ cs fau de
History
2018-11-09: received
Short URL
https://ia.cr/2018/1065
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1065,
      author = {Russell W.  F.  Lai and Giulio Malavolta and Dominique Schröder},
      title = {Homomorphic Secret Sharing for Low Degree Polynomials},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1065},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1065}},
      url = {https://eprint.iacr.org/2018/1065}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.