Paper 2018/1065

Homomorphic Secret Sharing for Low Degree Polynomials

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


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.

Available format(s)
Publication info
Published by the IACR in ASIACRYPT 2018
secret sharing
Contact author(s)
russell lai @ cs fau de
2018-11-09: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.