PaperlayerView exact revision on arXiv

Source-linked AI summary

Pushing Forward Multi-Secret-Key Homomorphic Encryption for Private Average Aggregation

Miguel Morona-Mínguez, Fernando Pérez-González, Alberto Pedrouzo-Ulloa

arXiv:2609.01945v1cs.CRcs.LG

TL;DR

Federated Learning’s local data remain isolated, yet model updates can leak sensitive information, making private aggregation important in cross-silo deployments. This paper introduces multi-secret-key HE protocols that avoid collective public keys and λ-dependent smudging noise. The BFV and CKKS instantiations preserve the stated security guarantees while reducing communication overhead and improving runtimes over MHE-based alternatives.

  • Problem

    Model updates can leak private training information, while existing HE-based aggregation relies on non-collusion assumptions or large λ-dependent smudging noise that increases ciphertext and implementation costs.

  • Method

    The paper develops RLWE-based multi-secret-key HE protocols for private average aggregation, letting each client encrypt under its own secret key and cancel ciphertext noise during collaborative decryption.

  • Results

    The BFV instantiation realizes aggregation exactly and CKKS provides a bounded-error randomized approximation, while the proposed construction reduces communication overhead and improves runtimes over MHE alternatives.

  • Takeaways & Limitations

    Multi-secret-key HE offers a lightweight route to private average aggregation without a collective public key or λ-dependent smudging noise.

  • Takeaways & Limitations

    The protocol is designed for average aggregation and is evaluated in the semi-honest setting, with prior HE schemes remaining vulnerable when decryption errors are non-negligible.

Abstract

from arXiv · show

Federated Learning enables multiple clients to train a shared model while keeping their local datasets isolated. However, the exchanged model updates may still leak sensitive information, making private aggregation a central building block in practical deployments, especially in the cross-silo setting. Homomorphic Encryption naturally fits the client--aggregator communication pattern of Federated Learning, but conventional single-key deployments rely on strong non-collusion assumptions. Multiparty Homomorphic Encryption removes this limitation, although recent attacks under restricted decryption access require large-variance smudging noise during collaborative decryption, which significantly increases ciphertext size and implementation complexity. In this work, we propose lightweight multi-secret-key protocols for private average aggregation based on RLWE-based Homomorphic Encryption. Our construction departs from the usual multiparty blueprint by avoiding the generation of a collective public key. Instead, each client encrypts its update under its own secret key, while the resulting ciphertexts remain compatible with homomorphic aggregation and collaborative decryption. By explicitly tracking and cancelling the ciphertext noise during decryption, the protocol removes the need for large $λ$-dependent smudging noise. We instantiate the construction with both exact BFV-based and approximate CKKS-based variants, prove its security in the semi-honest model against an adversary corrupting the aggregator and up to $L-1$ clients, and compare its communication and runtime performance with state-of-the-art MHE-based aggregation. Our results show that the proposed approach substantially reduces ciphertext expansion and online cost, while preserving practical homomorphic aggregation performance.

1. Introduction

Federated Learning keeps training data local, but exchanged updates can still leak information, motivating private aggregation for cross-silo deployments. The paper proposes lightweight multi-secret-key HE protocols that avoid collective public keys and λ-dependent smudging overhead while supporting exact and approximate aggregation.

  • Federated Learning: Federated Learning coordinates collaborative model training through an aggregator while keeping each client’s dataset local.Clients locally train on individual datasets, send updates, and receive a newly aggregated global model in successive rounds.
  • Privacy motivation: Individual model updates can leak training-data information, especially because the aggregator receives every client update.Private aggregation prevents a single participant from accessing individual updates and reduces the trust required from the aggregator.
  • Scope and approach: The work focuses on cross-silo FL and optimizes HE-based private aggregation for settings where the aggregator should not learn intermediate or final model parameters.HE follows the client–aggregator pattern: clients encrypt updates, the aggregator evaluates the aggregation function, and clients decrypt the result.
  • Limitations of prior MHE: O(λ) bits of overhead from MHE smudging noise can easily double transmitted data for λ≥128 and complicate noise generation.The large-variance noise also increases the required modulus, communication, and computational cost.
  • Proposed protocol: The proposed protocol supports exact BFV and approximate CKKS aggregation without a collective public key, using each client’s own secret key and λ-independent smudging noise.The design is limited to homomorphic averaging, but produces more compact ciphertexts and removes the O(λ) overhead.
  • Security and evaluation: The authors formally prove privacy for a semi-honest aggregator and a majority of semi-honest clients, and compare communication, precision, and ciphertext size against MHE approaches.The evaluation covers approximate and exact variants and reports concrete implementation results.

2. Background on Aggregation Threat Models

The background distinguishes private aggregation goals across threat models and FL settings. It motivates a semi-honest focus on conventional linear aggregation because malicious clients and robust alternatives introduce unresolved compatibility and verification challenges.

  • Defining private aggregation: Private aggregation definitions depend on the threat model and the requirements of the target FL training pipeline.The paper revisits existing definitions because they originated outside FL and may not fully match FL interactions.
  • Aggregation functions: Linear aggregation computes a weighted sum of client updates, including the sum and average as special cases.The average uses λ_i=1/L for every client, while the sum uses λ_i=1.
  • Semi-honest threats: Aggregator obliviousness limits an honest-but-curious aggregator to information inferable from the aggregate, while clients should not learn the result or honest clients’ updates.The definition also allows colluding clients to learn only what follows from the aggregate and their own inputs.
  • Malicious threats: Aggregate integrity requires detecting an incorrect result from a malicious aggregator and resisting significant compromise by malicious clients when enough honest clients participate.These guarantees address deviations from the true sum or from the honest clients’ inputs.
  • Threat-model limitations: Verification mechanisms are needed for malicious aggregators and client-input validity, while even one Byzantine client can disrupt linear aggregation and prevent convergence.Robust alternatives such as median, trimmed mean, and multi-Krum may help, but their compatibility with existing secure aggregation primitives remains unclear.
  • FL-tailored scope: The paper therefore adopts a passive semi-honest model and focuses on conventional linear aggregation functions, which are widely used in practical FL.Cross-silo deployments often involve resourceful institutions and a high-risk aggregator, supporting more relaxed client threat assumptions.

3. Background on HE for FL

HE-based private aggregation encrypts client updates while allowing the aggregator to compute the aggregation homomorphically. The section contrasts single-key HE’s efficiency under relaxed trust assumptions with privacy vulnerabilities when the aggregator receives outputs.

  • Additive HE: Additive HE supports linear aggregation, including weighted sums and the common FL operation of averaging.The aggregation function is represented as w* = fΣ(w_1, …, w_L) = ∑ λ_i w_i.
  • BFV and CKKS: BFV and CKKS instantiate RLWE-based additive HE as exact and approximate schemes, respectively, with SIMD-style additions over packed values.BFV requires exact correctness, whereas CKKS permits decryption error below a tolerance ε.
  • HE-based private aggregation: HE preserves FL’s client–aggregator communication flow by encrypting local updates, homomorphically evaluating fΣ, and decrypting the aggregated update.The encrypted-update workflow keeps local data on clients while supporting server-side aggregation.
  • Single-key threat model: Single-key HE requires clients to share cryptographic keys and assumes private channels plus no aggregator–client collusion.A colluding aggregator and client can access honest clients’ ciphertexts and the common secret key.
  • Output-access vulnerabilities: When the aggregator receives output access, restricted decryption can expose internal RLWE noise and potentially leak private-key information.For CKKS, the difference between decrypted encryption and its plaintext directly reveals the underlying noise.
  • Output-access vulnerabilities: Large smudging noise is used to address these vulnerabilities, but it can lead to impractically large parameters because it must hide ciphertext error across valid circuits.The required smudging noise may grow exponentially with the security parameter λ.

4. Private Aggregation with Multiparty HE

Multiparty HE adapts FL aggregation to colluding semi-honest aggregators and clients by distributing secret-key shares and performing key generation and decryption collaboratively. Its security benefits come with vulnerability and efficiency costs associated with decryption errors and smudging noise.

  • Motivation and threat model: MHE removes the common-key trust requirement by supporting homomorphic aggregation of ciphertexts encrypted under multiple keys.This capability targets aggregator obliviousness, where clients avoid encrypting all updates under one common key.
  • Security limitations: Decryption errors create key-recovery vulnerabilities in single-key HE and MHE, including attacks against widely used HE libraries.The cited attacks are especially relevant when the probability of decryption errors is non-negligible.
  • Baseline MHE protocol: The baseline protocol provides input privacy against a colluding semi-honest aggregator and up to L−1 semi-honest clients.Its construction uses an L-party secret-sharing scheme for the collective secret key.
  • Baseline MHE protocol: The baseline MHE protocol generates individual secret keys and a collective public key, encrypts updates under the collective key, and collaboratively decrypts the aggregate.Key generation and decryption are collaborative protocol steps among the clients.
  • Collaborative decryption: MHE’s collective decryption combines client secret-key shares to recover the underlying HE decryption result.The ideal decryption functionality applies E_ahe.Dec to the combined shares and ciphertext.
  • Smudging noise: Standard MHE decryption incorporates smudging noise as a countermeasure under the restricted-decryption threat model.The protocol’s partial decryptions add client-sampled smudging errors before combining shares.
  • Smudging noise: A practical decryption oracle is difficult to implement because clients cannot determine public-key error shares and error correlations may enable key-recovery attacks.These obstacles prevent straightforward tracking of each input ciphertext’s error component.

5. Proposed protocol and optimizations

The proposed protocol replaces collective-public-key MHE with a multi-secret-key construction in which clients encrypt under individual secret keys while preserving homomorphic aggregation and collaborative decryption. It combines BFV and CKKS instantiations with ciphertext compression, noise cancellation, and precomputation to reduce practical overhead.

  • Each client encrypts its update under an individual secret key, while ciphertexts remain compatible with homomorphic aggregation and collaborative decryption.The construction avoids generating a collective public key and removes dependence on cpk.
  • The protocol uses setup, local training, encrypted input, homomorphic evaluation of fΣ, and collaborative decryption stages.Clients may share the decrypted aggregate with the aggregator if required.
  • Secret-key HE retains n-value packing and additive homomorphism for ciphertexts sharing the same secret key, with exact BFV and approximate CKKS instantiations.The target margin error ε is zero for exact schemes and positive for approximate schemes.
  • Ciphertext compression can reduce encrypted-input size by approximately one half because the public component is independent of the secret key and can be PRF-generated.Any party knowing (κ, T) can reconstruct the public RLWE component a, while it remains computationally indistinguishable from uniform to parties without κ.
  • Encryptors track the noise used during encryption and cancel the accumulated linear-combination noise during decryption instead of adding high-variance smudging noise.For CKKS, if every client noise satisfies ||ẽ_i|| ≤ B, the decryption error is bounded by L B/Δ.
  • Only one ciphertext component is transmitted in each direction, reducing aggregation computation by at least a factor of two and enabling precomputation of shared polynomials and partial decryptions.The construction also removes ciphertext-size dependence on λ, with concrete gains depending on target precision.

6. Performance evaluation

The evaluation compares the proposed multi-secret-key construction with an MHE-based baseline, showing that removing collective-public-key and smudging noise overhead reduces ciphertext size, communication, and runtime while preserving BFV/CKKS alternatives.

  • Protocol comparison: The proposed construction avoids a collective public key, whereas the MHE baseline encrypts under a collective public key and jointly decrypts the aggregate.Both approaches target multiparty aggregation under strong semi-honest adversaries controlling the aggregator and a majority of clients.
  • Effective noise bounds: The proposed protocol removes the high-variance smudging term and extra collective-public-key noise from the effective decryption bound.The MHE bound includes the smudging contribution, while the proposed bound is B_prop = L B.
  • Ciphertext expansion: The ciphertext-size advantage combines one polynomial component instead of two with a smaller modulus, approaching a structural factor of 2 when log2 C dominates.The ratio is largest when decryption noise dominates the moduli; at very high precision, the relative gain tends toward 2.
  • BFV versus CKKS: As L and λ grow, the proposed CKKS-favorable region expands relative to MHE because its effective noise grows linearly in L and avoids λ dependence.The MHE bound scales as O(L 2^(λ/2)), whereas the proposed bound scales as O(L).
  • BFV versus CKKS: The proposed protocol shifts the BFV/CKKS transition to lower precision values, enlarging the region where CKKS is preferable, while BFV remains preferable for exact or low-precision arithmetic.CKKS becomes preferable as precision grows, but the choice remains parameter-dependent.
  • Implementation runtimes: The proposed protocol reduces online communication and runtime overhead by transmitting one ciphertext component per direction, while its client-side setup remains below one second for L = 512.The aggregation cost is reduced by at least a factor of two; MHE runtimes are higher because of larger moduli, ring degrees, and smudging operations.

7. Conclusions and future work

The paper proposes lightweight multi-secret-key HE protocols for private average aggregation that avoid collective public keys and λ-dependent smudging noise. BFV and CKKS instantiations reduce communication overhead and improve runtimes over MHE alternatives, while future work targets broader scope and stronger evaluations.

  • The construction lets clients encrypt under individual secret keys without requiring a collective public key.
  • Noise compensation during decryption avoids λ-dependent smudging noise while preserving semi-honest security.
  • BFV and CKKS instantiations reduce communication overhead and improve runtimes over MHE-based alternatives.
  • Future work includes broader construction scope, stronger adversarial models, complete FL pipeline integration, Differential Privacy, and output privacy.

A. Bounds for the ciphertext modulus 𝑞

The appendix derives decryption-correctness bounds for BFV ciphertexts and uses final effective noise bounds to compare the modulus requirements of BFV and CKKS constructions.

  • Protocol comparison: The appendix compares BFV and CKKS modulus requirements through protocol-independent correctness conditions once the final effective noise bound is fixed.
  • BFV correctness bounds: Fresh public-key BFV ciphertexts have effective noise bounded by (2n + 1)B, yielding the correctness condition (2n + 1)B < q.
  • BFV correctness bounds: Fresh secret-key BFV ciphertexts have effective noise bounded by B, with correctness requiring B < q before the remaining rounding condition is applied.
  • Protocol comparison: The proposed protocol substitutes its effective noise bound B_prop for the MHE bound B_MHE in the generalized BFV comparison.
  • Protocol comparison: The resulting comparison identifies when q_BFV exceeds q_CKKS.

B. Ciphertext expansion regimes

Ciphertext-expansion behavior is governed mainly by the precision term, with gains from removing MHE’s smudging and collective-public-key noise terms. The proposed construction retains a one-polynomial transmission advantage even in its worst asymptotic regime.

  • Regime analysis: The regime approximations are determined by the relative sizes of log2 B_MHE, log2 B_prop, and log2 C because the expression depends logarithmically on them.
  • Low-to-moderate precision: At low-to-moderate precision, the gain is driven by removing the smudging factor 2^(λ/2) and collective-public-key term (2nL + 1).
  • Moderate precision: At moderate precision, the precision term C contributes to both numerator and denominator, so it can no longer be neglected.
  • Intermediate precision: For roughly 40–64-bit precision and λ = 128, the second term remains significant for common cross-silo L values and standard HE ring dimensions.
  • Worst-case regime: In the worst asymptotic regime for relative ciphertext expansion, the construction still transmits one polynomial component instead of two.
  • The appendix supplements the analysis with parameter-region plots, modulus-gap heat maps, and clarification of approximate HE’s role in private aggregation.

C.1. Parameter regions for each protocol

The figures plot the CKKS-favorable boundary for the MHE-based and proposed protocols under representative cross-silo parameters. CKKS becomes increasingly favorable as target precision grows once the quadratic term matters, while λ and L affect the protocols differently.

  • Figure setup: Figures 5 and 6 plot Eq. (10) for the MHE-based and proposed constructions, respectively.The settings use n = 8192 and B = 19.2; Figure 5 varies λ and L, while Figure 6 varies L at λ = 128.
  • Boundary behavior: When t − 1 dominates, the CKKS-favorable boundary is approximately log2(t − 1) > log2 ε^-1.
  • Boundary behavior: When the quadratic term dominates, the boundary is approximately 2 log2 t − log2 B_MP.
  • Protocol effects: Once the quadratic term becomes relevant, CKKS becomes increasingly favorable as target precision grows.
  • Protocol effects: Increasing λ affects only the MHE-based protocol through its smudging term, whereas increasing L affects both protocols more strongly for MHE.

C.2. Modulus 𝗀𝖺𝗉between BFV and CKKS

The section defines the modulus gap between BFV and CKKS and uses heat maps to characterize how it affects correctness requirements. The gap shifts level curves vertically but does not move the regime transition horizontally.

  • The modulus gap is defined as gap = log2 q_BFV − log2 q_CKKS and is evaluated across a grid of plaintext modulus and precision parameters.The minimum modulus required by each scheme is computed using Eqs. (3) and (4).
  • Figure 7 compares BFV-based and CKKS-based instantiations using heat-map color bands that represent gap in bits.
  • The transition between the main regimes occurs when the linear and quadratic terms in t have comparable size.This balance is expressed by t 2^gap ≈ t^2.
  • The transition is located around log2 t ≈ 1 + log2 B_MPC^ct, independently of gap.
  • Increasing gap shifts the curves downward by approximately gap bits on the log2 epsilon^-1 axis.
  • The BFV comparison uses decryption by multiplication with t/q; when t does not divide q, rounding introduces an extra quadratic term.Using a scaling factor Delta instead would make the relevant BFV expression resemble the approximately linear regime.

F. Scalability with the number of clients

The protocol’s local encryption and partial decryption costs are independent of the client count per ciphertext block, while aggregation and share combination scale linearly with L. Setup has stronger dependence, yet remains below one second at L = 512 in the evaluated settings.

  • Client-side encryption and partial decryption costs are independent of L per ciphertext block, whereas aggregation and share combination grow linearly with L.
  • Table 10 reports average single-threaded client-side setup runtimes as a function of L across four proposed and two MHE parameter sets.
  • The proposed protocol’s effective decryption-noise bound is B_prop = L B, causing q to grow linearly with L while its bit length grows logarithmically.The larger modulus mainly affects computation when it requires an additional modulus limb or a large implementation change.
  • Setup computation and communication scale linearly with L, while total pairwise communication scales quadratically.Each client samples L − 1 elements, exchanges one contribution with every other client, and combines received shares.
  • Below one second: proposed-protocol client-side setup remains under one second for every evaluated parameter set at L = 512.The MHE-based setup is faster in these experiments.

G. Proof of Theorem 1

Theorem 1 is proved through a real/ideal simulation argument for fixed linear aggregation against static semi-honest adversaries. Client-local noise cancellation enables simulation with fresh noise without large λ-dependent smudging noise.

  • The proof establishes simulation-based input privacy for the aggregation functionality fΣ in the semi-honest model.It uses the standard real/ideal paradigm tailored to static semi-honest adversaries and fixed linear aggregation.
  • The security definition permits corruption of the aggregator and any subset of up to L − 1 clients, with the adversary’s real view computationally indistinguishable from an ideal simulated view.
  • The simulator uses corrupted parties’ inputs, secret keys, randomness, and the aggregate output to construct the adversarial view.
  • The security notion guarantees that the adversary learns no additional information about honest clients’ inputs beyond its own inputs and the aggregation result.
  • The hybrid proof relies on RLWE indistinguishability, with collections of M replacements bounded by 2M epsilon_RLWE(λ).The argument applies triangle-inequality and hybrid replacements to encryption and decryption distributions.
  • Honest clients’ encryption noises are stored in local oracles, allowing decryption to cancel ciphertext-dependent noise and replace it with fresh error-distribution samples.This removes the need for large λ-dependent smudging noise in the simulation.

G.3. Hybrid simulator experiments

The hybrid simulator replaces honest ciphertexts and partial decryptions through a sequence of RLWE-based hybrids. The final simulated execution preserves the exact BFV or approximate CKKS output convention while keeping at least one honest contribution fresh from the adversary’s view.

  • HYB0 is the real protocol execution with honest clients’ real inputs, and the proof introduces four hybrid experiments leading to the ideal simulated execution.
  • HYB1 replaces honest clients’ ciphertexts with encryptions of zero, except for one distinguished honest client whose ciphertexts encrypt a simulator-selected value.Updates are encoded blockwise across N_ctx ciphertexts per client.
  • HYB2 replaces the distinguished client’s ciphertexts and modifies honest partial decryptions, while preserving the target reconstructed value through programmed shares.
  • The simulator samples fresh error terms independently for honest clients, yielding exact BFV decoding or CKKS output w* + Delta^-1 sum_i ẽ_i.Because at least one honest client exists, the aggregated approximation error includes a fresh contribution independent of the adversary’s view.
  • HYB3 replaces honest zero-encryptions with uniformly random ciphertexts and coincides with the ideal execution under the exact or approximate output convention.
  • Joint ciphertext–partial-decryption replacements are justified by three RLWE transitions and preserve the prescribed reconstructed value under the zero-sharing relation.The proof applies these transitions across honest clients and ciphertext blocks.

G.5. Conclusion of the proof of Theorem 1

The proof establishes simulation-based input privacy for the aggregation functionality in the semi-honest model, with correctness defined for exact or approximate outputs. Its security bound depends on RLWE advantage without additional noise-parameter dependence, because client-local randomness replaces large smudging noise.

  • Theorem 1 conclusion: The hybrid argument proves simulation-based input privacy for aggregation in the semi-honest model.Correctness is interpreted according to the exact or approximate output convention.
  • Explicit bounds: The explicit security bound depends on the number of honest clients and the RLWE distinguishing advantage.The proof writes the honest-client count as L_H := |C_H| before making the bound explicit.
  • Hybrid transitions: The hybrid sequence replaces ciphertexts, partial decryptions, and fresh-randomness ciphertexts across its transitions.The H_YB1 → H_YB2 transition replaces N_ctx ciphertexts and (L_H−1)N_ctx partial decryptions, while H_YB2 → H_YB3 replaces L_HN_ctx ciphertexts.
  • Security discussion: The overall distinguishing advantage reduces to RLWE advantage up to a factor independent of additional noise parameters.Client-local oracles inject fresh decryption noise independently of ciphertexts, so the proof avoids λ-dependent large smudging noise.
Loading 2609.01945v1…