An Efficient Threshold Access-Structure for RLWE-Based Multiparty Homomorphic Encryption

Abstract

We propose and implement a multiparty homomorphic encryption (MHE) scheme with a $t$-out-of-$N$-threshold access-structure that is efficient and does not require a trusted dealer in the common random-string model. We construct this scheme from the ring-learning-with-error (RLWE) assumptions, and as an extension of the MHE scheme of Mouchet et al. (PETS 21). By means of a specially adapted share re-sharing procedure, this extension can be used to relax the $N$-out-of-$N$-threshold access structure of the original scheme into a $t$-out-of-$N$-threshold one. This procedure introduces only a single round of communication during the setup phase, after which any set of at least $t$ parties can compute a $t$-out-of-$t$ additive sharing of the secret key with no interaction; this new sharing can be used directly in the scheme of Mouchet et al. We show that, by performing Shamir re-sharing over the MHE ciphertext-space ring with a carefully chosen exceptional set, this reconstruction procedure can be made secure and has negligible overhead. Moreover, it only requires the parties to store a constant-size state after its setup phase. Hence, in addition to fault tolerance, lowering the corruption threshold also yields considerable efficiency benefits, by enabling the distribution of batched secret-key operations among the online parties. We implemented and open-sourced our scheme in the Lattigo library.

Available format(s)
Category
Cryptographic protocols
Publication info
DOI
10.1007/s00145-023-09452-8
Keywords
Multiparty homomorphic EncryptionThreshold access-structure
Contact author(s)
christian mouchet @ epfl ch
History
2023-03-22: revised
See all versions
Short URL
https://ia.cr/2022/780

CC BY

BibTeX

@misc{cryptoeprint:2022/780,
author = {Christian Mouchet and Elliott Bertrand and Jean-Pierre Hubaux},
title = {An Efficient Threshold Access-Structure for RLWE-Based Multiparty Homomorphic Encryption},
howpublished = {Cryptology ePrint Archive, Paper 2022/780},
year = {2022},
doi = {10.1007/s00145-023-09452-8},
note = {\url{https://eprint.iacr.org/2022/780}},
url = {https://eprint.iacr.org/2022/780}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.