A Geometric Approach to Homomorphic Secret Sharing
Ishai Y, Lai RWF, Malavolta G (2021)
Publication Type: Conference contribution
Publication year: 2021
Journal
Publisher: Springer Science and Business Media Deutschland GmbH
Book Volume: 12711 LNCS
Pages Range: 92-119
Conference Proceedings Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Event location: Online
ISBN: 9783030752477
DOI: 10.1007/978-3-030-75248-4_4
Abstract
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.
Authors with CRIS profile
Involved external institutions
Max-Planck-Institut für Sicherheit und Privatsphäre / Max Planck Institute for Security and Privacy
Germany (DE)
Technion - Israel Institute of Technology
Israel (IL)
Germany (DE)
Technion - Israel Institute of Technology
Israel (IL)
How to cite
APA:
Ishai, Y., Lai, R.W.F., & Malavolta, G. (2021). A Geometric Approach to Homomorphic Secret Sharing. In Juan A. Garay (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 92-119). Online: Springer Science and Business Media Deutschland GmbH.
MLA:
Ishai, Yuval, Russell W. F. Lai, and Giulio Malavolta. "A Geometric Approach to Homomorphic Secret Sharing." Proceedings of the 24th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2021, Online Ed. Juan A. Garay, Springer Science and Business Media Deutschland GmbH, 2021. 92-119.
BibTeX: Download