| The WhitePaper Reading Club Privacy Hub | Research Day [04] | 20 Nov 2025 |
|---|---|
| High-Throughput Universally Composable Threshold FHE Decryption | [Whitepaper Reading Club] |
Summary
Threshold FHE decryption protocol that replaces noise flooding with fast MPC-based rounding, enabling UC-secure decryption at massive scale with up to 20,000X higher throughput.
Why This Is Important
Prior threshold FHE schemes rely on noise flooding (requires huge LWE parameters, slow decryption, and multi-hundred-millisecond latency) This protocol removes noise instead of hiding it, making threshold FHE practical for MPC, and new usecases.
Key Innovation
Instead of adding large synthetic noise (noise flooding) to mask LWE errors, the protocol securely removes noise using MPC rounding built from preprocessed Sign and ModLTZ gates. These gates allow secure comparisons in just 3 online openings, shifting work to the offline phase, achieving UC-secure threshold decryption without parameter blowup. (Noise flooding → big parameters; MPC rounding → small parameters, fast decryption.)
Overview
(i) Works in the Arithmetic Black Box (ABB) model: compute ⟨c,s⟩ = L·μ + e inside MPC, extract noise e = z mod L, then open z−e = L·μ to reveal plaintext μ. (ii) Preprocessed gates provide masked random r and lookup tables for shifted functions F(x−r), enabling efficient mod and sign operations. (iii) Achieves 64,319 decryptions/sec with 8.48 ms latency for 4 parties (vs 3.18 dec/sec, 315 ms for previous best). (iv) Online phase uses only 656 bits of communication and consumes 346 KB of preprocessed material per decryption, while supporting both honest and dishonest-majority adversary models.
Background
(i) LWE, decrypting a message produces a value of the form z = ⟨c, s⟩ = L·μ + e, where μ is the message and e is small “noise” added for security. If z is revealed directly in a threshold setting (multiple parties jointly holding the key), the noise e unintentionally leaks patterns about the secret key s, which attackers can learn over time. (ii) Noise flooding (old approach): To hide this dangerous noise e, older systems added a massive amount of extra random noise (“noise flooding”). This does hide the leakage—but forces enormous cryptographic parameters, making ciphertexts huge and decryption extremely slow (hundreds of milliseconds), which is impractical for real-world systems like blockchains or privacy-preserving ML. (iii) Masking (new approach): Instead of drowning the original noise under giant artificial noise, this paper masks the intermediate value with a random number r, then uses secure MPC comparison tools to extract the true noise e without ever revealing it.
This completely avoids parameter inflation and makes threshold decryption fast and practical, because no large synthetic noise is required. (iv) ABB model: The Arithmetic Black Box (ABB) is a simple abstraction: it lets parties store secret numbers, add or multiply them jointly, and reveal them only through controlled “openings.” This model is implemented by existing MPC systems like SPDZ2ᵏ (works even if a majority is dishonest) and Shamir/replicated sharing (works when a majority is honest), making the protocol broadly compatible with real deployments.
Team
@Rongxin Todo after discussion
Deep Dives
| 1.LTRand: Core Secure Reduction | Needed to safely pull out the “hidden noise” inside an encrypted value without revealing anything sensitive.: (i) Masks `z with random r → produces uniformly distributed z′ = z + r (mod 2^ℓ). (ii) Splits z′ into b-bit digits; each digit compared to r via Sign gates. (iii) Aggregates digit-wise signs into a masked ordering via weighted sums. (iv) Enables constant-round secure reduction with only masked openings, no online multiplications. |
|---|---|
| 2. Sign Gates | Allows the system to compare numbers privately without converting them into bits or exposing any part of the secret value. (i) Store random r and lookup table for Sign(x−r) over all x ∈ [0,2^b). (ii) Built offline via subset-product transforms (efficient for b=8). (iii) Online phase uses masked lookups only—constant cost per digit. (iv) Provides building blocks for reconstructing global comparison results. |
| ModLTZ | Needed to decide if a private number “wraps around” a boundary in the encryption scheme — a crucial step for decrypting safely. (i) Implements modular negativity using masked carry-propagation logic. (ii) Precomputes table outputs over (d+1)-bit ranges using subset-product transforms. (iii) One masked opening; no online multiplications. (iv) Produces the single comparison bit used to recover noise e securely. |
| 4. Decryption Pipeline | Ties all the components together into a full decryption method that reveals only the final plaintext and nothing else. (i) MPC computes = ⟨c,⟩ + 2^{ℓ−1} inside ABB. (ii) LTRand + ModLTZ extract noise e without exposing any intermediate value. (iii) Parties open [z−e] = L·μ, revealing only the scaled plaintext μ. (iv) Exactly 3 sequential openings, zero online multiplications, minimal communication. |
| 5. SPDZ2ᵏ Optimization | Ensures the system stays fast even when some participants might try to cheat. (i) Pipelined MAC checks overlap verification and openings → rounds drop 9→5. (ii) Early release of masked values safe due to later MAC validation. (iii) Communication per decryption: ~656 bits. (iv) Works for any threshold setting supported by SPDZ2ᵏ. |
| 6. Offline Preprocessing | Moves all expensive work “before” decryption so the real-time step is extremely fast. (i) Each decryption requires d Sign gates + 1 ModLTZ (~2478 offline multiplications). (ii) Storage: ~346 KB per party per decryption for tables. (iii) Preprocessing throughput: ~1.35 seconds for 1000 decryptions’ worth of gates. (iv) Highly parallelizable, enabling large-batch real-time decryption. |