Paper 2021/260

A Geometric Approach to Homomorphic Secret Sharing

Yuval Ishai, Russell W. F. Lai, and Giulio Malavolta


An (n,m,t)-homomorphic secret sharing (HSS) scheme allows n clients to share their inputs across m servers, such that the inputs are hidden from any t colluding servers, and moreover the servers can evaluate functions over the inputs locally by mapping their input shares to compact output shares. Such compactness makes HSS a useful building block for communication-efficient secure multi-party computation (MPC). In this work, we propose a simple compiler for HSS evaluating multivariate polynomials based on two building blocks: (1) homomorphic encryption for linear functions or low-degree polynomials, and (2) information-theoretic HSS for low-degree polynomials. Our compiler leverages the power of the first building block towards improving the parameters of the second. We use our compiler to generalize and improve on the HSS scheme of Lai, Malavolta, and Schröder [ASIACRYPT'18], which is only efficient when the number of servers is at most logarithmic in the security parameter. In contrast, we obtain efficient schemes for polynomials of higher degrees and an arbitrary number of servers. This application of our general compiler extends techniques that were developed in the context of information-theoretic private information retrieval (Woodruff and Yekhanin [CCC'05]), which use partial derivatives and Hermite interpolation to support the computation of polynomials of higher degrees. In addition to the above, we propose a new application of HSS to MPC with preprocessing. By pushing the computation of some HSS servers to a preprocessing phase, we obtain communication-efficient MPC protocols for low-degree polynomials that use fewer parties than previous protocols based on the same assumptions. The online communication of these protocols is linear in the input size, independently of the description size of the polynomial.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in PKC 2021
secret sharing
Contact author(s)
yuval ishai @ gmail com
russell lai @ cs fau de
giulio malavolta @ hotmail it
2021-03-03: received
Short URL
Creative Commons Attribution


      author = {Yuval Ishai and Russell W.  F.  Lai and Giulio Malavolta},
      title = {A Geometric Approach to Homomorphic Secret Sharing},
      howpublished = {Cryptology ePrint Archive, Paper 2021/260},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.