TL;DR
This paper introduces a novel primitive called a "message-space adapter" (MeSA) to resolve a long-standing dilemma in threshold linearly homomorphic encryption (ThLHE). By using MeSA with lattice-based encryption, they achieve the first ThLHE scheme with quasi-linear decryption complexity that doesn't impose restrictive assumptions on message space or participant sets, making it more practical for large-scale applications.
What Problem Does This Paper Address?
Threshold linearly homomorphic encryption (ThLHE) is a powerful cryptographic tool for secure multi-party computations, allowing linear functions to be evaluated on encrypted data without revealing the data itself, and without requiring a fully trusted party. However, existing ThLHE schemes face a critical trade-off between efficiency and utility. To achieve high efficiency (specifically, low decryption complexity, ideally quasi-linear in the number of parties $N$), many schemes impose restrictive assumptions. These include:
- Small-message restriction: Messages must come from a small, known set, limiting applicability in scenarios with large message spaces.
- Full-threshold restriction: All $N$ parties must participate for decryption, making it vulnerable to dropouts or denial-of-service attacks.
- Known-participants assumption: The set of $T$ participating parties must be known in advance, which is often impractical.
This "efficiency-utility dilemma" hinders the widespread adoption of ThLHE in modern applications like federated learning or blockchain, which often involve thousands of participants and dynamic environments. The paper aims to break this trade-off by developing a ThLHE scheme that is both efficient (quasi-linear decryption complexity) and highly useful (no restrictive assumptions).
Methods
The core innovation of this paper is the introduction of a message-space adapter (MeSA). MeSA is a novel primitive that acts as an intermediary, allowing an existing homomorphic encryption (HE) scheme to operate on a different, potentially larger, message space without altering the HE scheme's internal mechanisms or security.
The authors define MeSA with three key properties:
- Secret-key encryption: It's a secret-key encryption scheme over a target message space.
- Key sampling: The encryption algorithm can sample encryption keys for each message individually.
- Homomorphic properties: It's homomorphic with respect to both messages and encryption keys for a given function family $F$.
They then propose two constructions:
- MeSA-Assisted HE Construction (Construction 1): This construction shows how to build a new HE scheme with a target message space by combining an existing HE scheme with a MeSA. The HE scheme's public/secret keys are preserved, and the MeSA handles the message space transformation.
- MeSA-Assisted ThHE Construction (Construction 2): This extends the first construction to the threshold setting. By using a threshold HE (ThHE) scheme and a MeSA, they construct a ThHE scheme that inherits the threshold properties of ThHE while benefiting from the message space flexibility of MeSA.
For a concrete instantiation, they develop a lattice-based MeSA (LM) for the exponential ElGamal (Exp-ElGamal) scheme. Exp-ElGamal is known for its efficient threshold decryption but suffers from the small-message restriction. The lattice-based MeSA addresses this by:
- Allowing a flexible message space (e.g., $Z_p$ where $p$ is not necessarily prime).
- Being linearly homomorphic in both messages and keys.
- Employing a technique to reduce the growth of errors and encryption keys during homomorphic evaluation, enabling larger message spaces and more operations.
By combining this lattice-based MeSA with Exp-ElGamal (and its threshold variant), they obtain Lattice-Exp-ElGamal and Threshold Lattice-Exp-ElGamal.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- MeSA as a Decoupling Primitive: The core insight is that MeSA can decouple the message space of an HE scheme from its underlying security and efficiency properties. This allows for adapting existing efficient HE schemes to more practical message spaces.
- Lattice-Based Encryption for MeSA: Lattice-based cryptography is a natural fit for constructing MeSA due to its inherent homomorphic properties and flexible message space.
- Resolving the Efficiency-Utility Dilemma: The paper demonstrates that by carefully designing MeSA and integrating it with efficient HE schemes like Exp-ElGamal, it's possible to achieve both quasi-linear decryption complexity and broad utility without restrictive assumptions.
- New Application to MFHE: The proposed ThLHE scheme can be used to construct efficient multi-party fully homomorphic encryption (MFHE) schemes, which are crucial for advanced secure computation protocols.
Key Results
- First ThLHE with Quasi-Linear Decryption and No Restrictions: The paper presents the first ThLHE scheme (Threshold Lattice-Exp-ElGamal) that achieves quasi-linear decryption complexity ($O(N \log N)$) without imposing "small-message," "full-threshold," or "known-participants" restrictions.
- Efficient MFHE Construction: They construct the first concretely-efficient MFHE scheme with quasi-linear computation complexity and constant communication complexity, supporting arbitrary thresholds and dynamic participants.
- Performance Validation: Empirical evaluations show a quasi-linear growth trend of decryption time with respect to the number of parties $N$, validating the theoretical analysis. For $N=1000$, their scheme achieves a four-times acceleration compared to threshold Paillier.
- Comparison with Baselines: Table 1 shows that their scheme significantly outperforms existing baselines (Threshold Paillier and Shamir-based ThFHE) in terms of computation complexity for decryption, especially as $N$ grows.
Limitations and Future Work
- Parameter Instantiation Trade-offs: The paper notes that there's a trade-off in parameter selection for the lattice-based MeSA. Increasing the message space size or the number of operations can impact security and efficiency. Finding optimal parameters for specific applications is left as an open problem.
- Other MeSA Formulations: The authors mention that other formulations of MeSA that achieve the same functionality are possible and could be an interesting area for future research.
- Concrete Parameter Selection: While the paper provides guidelines for parameter instantiation, selecting concrete parameters for practical applications requires careful consideration of security, efficiency, and application demands.
Summary updated