Skip to content

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]

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