Paper 2025/094

Multi-Key Homomorphic Secret Sharing

Geoffroy Couteau, CNRS, IRIF, Université Paris Cité
Lalita Devadas, Massachusetts Institute of Technology
Aditya Hegde, Johns Hopkins University
Abhishek Jain, NTT Research, Johns Hopkins University
Sacha Servan-Schreiber, Massachusetts Institute of Technology
Abstract

Homomorphic secret sharing (HSS) is a distributed analogue of fully homomorphic encryption (FHE) where following an input-sharing phase, two or more parties can locally compute a function over their private inputs to obtain shares of the function output. Over the last decade, HSS schemes have been constructed from an array of different assumptions. However, all existing HSS schemes, except ones based on assumptions known to imply multi-key FHE, require a public-key infrastructure (PKI) or a correlated setup between parties. This limitation carries over to many applications of HSS. In this work, we construct multi-key homomorphic secret sharing (MKHSS), where given only a common reference string (CRS), two parties can secret share their inputs to each other and then perform local computations as in HSS. We present the first MKHSS schemes supporting all NC1 computations from either the decisional Diffie-Hellman (DDH), decisional composite residuosity (DCR), or class group assumptions. Our constructions imply the following applications in the CRS model: - Succinct two-round secure computation. Under the same assumptions as our MKHSS schemes, we construct succinct, two-round secure two-party computation for NC1 circuits. Previously, such a result was only known from the learning with errors assumption. - Attribute-based NIKE. Under DCR or class group assumptions, we construct non-interactive key exchange (NIKE) protocols where two parties agree on a key if and only if their secret attributes satisfy a public NC1 predicate. This significantly generalizes the existing notion of password-based NIKE. - Public-key PCFs. Under DCR or class group assumptions, we construct public-key pseudorandom correlation functions (PCFs) for any NC1 correlation. This yields the first public-key PCFs for Beaver triples (and more) from non-lattice assumptions. - Silent MPC. Under DCR or class group assumptions, we construct a p-party secure computation protocol in the silent preprocessing model where the preprocessing phase has communication O(p), ignoring polynomial factors. All prior protocols that do not rely on spooky encryption require communication.

Note: Added publication information.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2025
Keywords
hsspseudorandom correlation functionssilent secure computationmultikeynon-interactivekey exchangetwo round
Contact author(s)
couteau @ irif fr
lali @ mit edu
ahegde3 @ jhu edu
abhishek jain @ ntt-research com
3s @ mit edu
History
2025-02-24: last of 3 revisions
2025-01-21: received
See all versions
Short URL
https://ia.cr/2025/094
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/094,
      author = {Geoffroy Couteau and Lalita Devadas and Aditya Hegde and Abhishek Jain and Sacha Servan-Schreiber},
      title = {Multi-Key Homomorphic Secret Sharing},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/094},
      year = {2025},
      url = {https://eprint.iacr.org/2025/094}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.