Welcome to the resource topic for 2023/382
Title:
On Homomorphic Secret Sharing from Polynomial-Modulus LWE
Authors: Thomas Attema, Pedro Capitão, Lisa Kohl
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.
ePrint: https://eprint.iacr.org/2023/382
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .