Low Communication Threshold FHE from Standard (Module-)LWE¶
Year: 2025
type: technique collection: schemes status: auto
Links: DOI · ePrint 2025/409
Summary¶
Auto-extracted summary (unreviewed)
Okada and Takagi construct a threshold FHE scheme with polynomially small decryption shares from standard LWE and module-LWE, removing the known-norm LWE assumption needed by Passelegue and Stehle (Asiacrypt 2024) through a 'noise padding' technique in which parties hold shares of a padding noise used to reshape the decryption noise so nothing about the secret key leaks. The scheme realizes arbitrary T-out-of-N threshold decryption with plain Shamir secret sharing, so keys, ciphertexts and decryption shares are O(1) in the number of parties N; this is the full version of the Asiacrypt 2025 paper.
Abstract¶
Threshold fully homomorphic encryption (ThFHE) is a multi-party extension of FHE; any subset of at least T out of N parties can decrypt the ciphertexts by combining their decryption shares. Recently, Passelègue and Stehlé (Asiacrypt 2024) presented a ThFHE scheme with polynomially short decryption shares from the “known-norm” variant of learning with errors (LWE) assumption, in which the norm of the secret key is leaked to the adversary. While known-norm LWE is reduced from standard LWE, its module extension, known-covariance module-LWE (MLWE), lacks a known reduction from standard MLWE. Hence, extending their ThFHE scheme to the MLWEbased construction remains an open question. In this paper, we address this open problem: We construct a ThFHE scheme with polynomially small decryption shares from standard LWE/MLWE. Our core technique, which we call noise padding, eliminates the need of known-norm variants of LWE. We distribute shares of a padding noise and use them to adjust the distribution of decryption noise so that no information about the secret key is leaked. Furthermore, our ThFHE efficiently realizes arbitrary T-out-of-N threshold decryption via simple Shamir secret sharing instead of {0, 1}-linear secret sharing. Hence, the sizes of the keys, ciphertexts and decryption shares in our scheme are compact: they are O(1) w.r.t. the number of parties N.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | Threshold FHE with polynomially small decryption shares from standard LWE/MLWE | llm | 0.70 |
| contribution | Noise padding technique eliminating known-norm / known-covariance LWE variants | llm | 0.70 |
| contribution | Arbitrary T-out-of-N threshold decryption via Shamir secret sharing instead of {0,1}-linear secret sharing | llm | 0.70 |
| contribution | Key, ciphertext and decryption-share sizes constant in the number of parties | llm | 0.70 |
| schemes | threshold FHE | llm | 0.70 |
| schemes | LWE/MLWE-based FHE | llm | 0.70 |
| schemes | Shamir secret sharing | llm | 0.70 |
| tasks | threshold decryption | llm | 0.70 |
| tasks | multi-party FHE | llm | 0.70 |
| threat model | N parties with T-out-of-N threshold decryption; adversary must not learn the secret key from decryption shares | llm | 0.70 |
| interaction | other | llm | 0.70 |
| llm relevance | low | llm | 0.70 |
| key result | key / ciphertext / decryption share size: O(1) with respect to number of parties N (standard LWE/MLWE, Shamir T-out-of-N) | llm | 0.70 |
| key result | decryption share size: polynomially small (without known-norm LWE assumption) | llm | 0.70 |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: Threshold HE 50 [p.1], Secret sharing 40 [p.1], MPC 8 [p.2], Hybrid HE / transciphering 3 [p.2], Functional encryption 2 [p.2]
- technique: Semi-honest model 7 [p.3], Noise flooding 6 [p.6], Bootstrapping 2 [p.34], Secure aggregation 2 [p.8]
- assumption: LWE 97 [p.1], Module-LWE 39 [p.1], Lattice-based 26 [p.8], RLWE 6 [p.1]
- topic: Homomorphic encryption 74 [p.1]
Related papers¶
- this paper follow up of Multiparty Homomorphic Encryption from Ring-Learning-with-Errors — follow-up listed for scheme "Multiparty HE (MHE) for BFV/CKKS"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s36-1_eprint-2025-409.pdf |
schemes | 40 | 765.4 KB | 98993522b806 |
Database key: low-communication-threshold-fhe-from-standard-module-lwe · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set low-communication-threshold-fhe-from-standard-module-lwe COLUMN VALUE