Paper 2023/382

On Homomorphic Secret Sharing from Polynomial-Modulus LWE

Abstract

Homomorphic secret sharing (HSS) is a form of secret sharing that supports the local evaluation of functions on the shares, with applications to multi-server private information retrieval, secure computation, and more. Insisting on additive reconstruction, all known instantiations of HSS from "Learning with Error (LWE)"-type assumptions either have to rely on LWE with superpolynomial modulus, come with non-negligible error probability, and/or have to perform expensive ciphertext multiplications, resulting in bad concrete efficiency. In this work, we present a new 2-party local share conversion procedure, which allows to locally convert noise encoded shares to non-noise plaintext shares such that the parties can detect whenever a (potential) error occurs and in that case resort to an alternative conversion procedure. Building on this technique, we present the first HSS for branching programs from (Ring-)LWE with polynomial input share size which can make use of the efficient multiplication procedure of Boyle et al.~(Eurocrypt 2019) and has no correctness error. Our construction comes at the cost of a -- on expectation -- slightly increased output share size (which is insignificant compared to the input share size) and a more involved reconstruction procedure. More concretely, we show that in the setting of 2-server private counting queries we can choose ciphertext sizes of only a quarter of the size of the scheme of Boyle et al. at essentially no extra cost.