Paper 2019/129

Homomorphic Secret Sharing from Lattices Without FHE

Elette Boyle, Lisa Kohl, and Peter Scholl

Abstract

Homomorphic secret sharing (HSS) is an analog of somewhat- or fully homomorphic encryption (S/FHE) to the setting of secret sharing, with applications including succinct secure computation, private manipulation of remote databases, and more. While HSS can be viewed as a relaxation of S/FHE, the only constructions from lattice-based assumptions to date build atop specific forms of threshold or multi-key S/FHE. In this work, we present new techniques directly yielding efficient 2-party HSS for polynomial-size branching programs from a range of lattice-based encryption schemes, without S/FHE. More concretely, we avoid the costly key-switching and modulus-reduction steps used in S/FHE ciphertext multiplication, replacing them with a new distributed decryption procedure for performing "restricted" multiplications of an input with a partial computation value. Doing so requires new methods for handling the blowup of "noise'' in ciphertexts in a distributed setting, and leverages several properties of lattice-based encryption schemes together with new tricks in share conversion. The resulting schemes support a superpolynomial-size plaintext space and negligible correctness error, with share sizes comparable to SHE ciphertexts, but cost of homomorphic multiplication roughly one order of magnitude faster. Over certain rings, our HSS can further support some level of packed SIMD homomorphic operations. We demonstrate the practical efficiency of our schemes within two application settings, where we compare favorably with current best approaches: 2-server private database pattern-match queries, and secure 2-party computation of low-degree polynomials.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2019
Keywords
homomorphic secret sharinglattices
Contact author(s)
eboyle @ alum mit edu
lisa kohl @ kit edu
peter scholl @ cs au dk
History
2019-02-13: received
Short URL
https://ia.cr/2019/129
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/129,
      author = {Elette Boyle and Lisa Kohl and Peter Scholl},
      title = {Homomorphic Secret Sharing from Lattices Without FHE},
      howpublished = {Cryptology ePrint Archive, Paper 2019/129},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/129}},
      url = {https://eprint.iacr.org/2019/129}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.