Paper 2021/274

Large Message Homomorphic Secret Sharing from DCR and Applications

Lawrence Roy and Jaspal Singh

Abstract

We present the first homomorphic secret sharing (HSS) construction that simultaneously (1) has negligible correctness error, (2) supports integers from an exponentially large range, and (3) relies on an assumption not known to imply FHE --- specifically, the Decisional Composite Residuosity (DCR) assumption. This resolves an open question posed by Boyle, Gilboa, and Ishai (Crypto 2016). Homomorphic secret sharing is analogous to fully-homomorphic encryption, except the ciphertexts are shared across two non-colluding evaluators. Previous constructions of HSS either had non-negligible correctness error and polynomial-size plaintext space or were based on the stronger LWE assumption. We also present two applications of our technique: a multi-server ORAM with constant bandwidth overhead, and a rate-1 trapdoor hash function with negligible error rate.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2021
DOI
10.1007/978-3-030-84252-9_23
Keywords
homomorphic secret sharingsecure computationtrapdoor hash functionsoblivious RAM
Contact author(s)
ldr709 @ gmail com
singjasp @ oregonstate edu
History
2021-08-18: revised
2021-03-04: received
See all versions
Short URL
https://ia.cr/2021/274
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/274,
      author = {Lawrence Roy and Jaspal Singh},
      title = {Large Message Homomorphic Secret Sharing from DCR and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2021/274},
      year = {2021},
      doi = {10.1007/978-3-030-84252-9_23},
      note = {\url{https://eprint.iacr.org/2021/274}},
      url = {https://eprint.iacr.org/2021/274}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.