On Homomorphic Secret Sharing from Polynomial-Modulus LWE
conference paper
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 information
retrieval we can choose ciphertext sizes of only a quarter of the
size of the scheme of Boyle et al. at essentially no extra cost.
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 information
retrieval we can choose ciphertext sizes of only a quarter of the
size of the scheme of Boyle et al. at essentially no extra cost.
TNO Identifier
986417
Source
Proceedings PKC, pp. 3-32.
Pages
3-32
Files
To receive the publication files, please send an e-mail request to TNO Repository.