Post-Quantum Secure Aggregation via Code-Based Homomorphic Encryption

arXiv:2601.13031 · cs.CR, cs.IT, math.IT · Submitted 2026-01-19 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: Today's paper: "Post-Quantum Secure Aggregation via Code-Based Homomorphic Encryption".

Elias: The gist:

Nadia: First, who's behind it and why it matters.

Paper summary: Elias: So, looking at the whole 'Post-Quantum Secure Aggregation via Code-Based Homomorphic Encryption' paper, it’s about finding a way to handle secure aggregation that doesn't depend on the usual lattice assumptions we see in other post-quantum schemes. The authors have constructed a system based on key- and message-additive homomorphic encryption using the Learning Parity with Noise assumption.

Nadia: Right, they show that this construction works and is equivalent to standard LPN when you pick the right parameters. The implication for me as someone working on exploitation is that we now have a new set of mathematical tools we can build protocols on instead of just relying on lattice assumptions which are getting scrutinized for quantum resistance.

Priya: From a privacy measurement standpoint, what this means is that if we use this code-based approach, the security relies on coding theory hardness rather than number theory problems in lattices. It's an interesting shift in the foundation of post-quantum secure aggregation methods.

Elias: And they’ve also made a point about cross-silo settings. They claim that their protocol requires less communication than information-theoretically secure aggregation when there is moderate to high collusion among users, which is a pretty strong result for practical applications like federated learning.

Nadia: That's the part I find most interesting for real deployment because it addresses the practical issue of communication overhead. The authors also managed to use their committee-based decryptor and CRT optimization to keep the performance manageable even with these security guarantees in mind.

Priya: So, in simple terms, this paper gives us a concrete way to build secure aggregation that is rooted in coding theory hardness rather than lattice assumptions, while still being practical regarding communication costs for certain levels of user collusion.

Elias: Yeah, so the title 'Post-Quantum Secure Aggregation via Code-Based Homomorphic Encryption' points directly to how they achieved this by using code-based cryptography under the LPN assumption. It’s a solid contribution to finding alternative routes for secure aggregation when lattice methods might not be the right fit.

Conclusion: Nadia: So, we're wrapping up this discussion on "Post-Quantum Secure Aggregation via Code-Based Homomorphic Encryption." This paper shows they built a secure way to aggregate user data without needing lattice assumptions anymore.

Elias: Yeah, it boils down to them using key- and message-additive homomorphic encryption built on the Learning Parity with Noise assumption. It’s essentially translating a coding theory problem into a practical aggregation method.

Priya: From what I'm seeing in the data, they demonstrate that this construction works and is equivalent to standard LPN when you choose the right noise rates for their specific scheme. The measurements they use show how the security holds up under those conditions.

Nadia: And it’s interesting because they achieved something pretty practical on top of that. They showed in cross-silo settings, their protocol needs less communication than information-theoretically secure aggregation when there's moderate to high user collusion.

Elias: That part about the communication cost is significant; they managed to decouple the field size from the input range using something like the Chinese remainder theorem. That keeps things from getting bogged down in massive numbers.

Priya: But what they don't fully address is how much noise you actually need in real-world scenarios, and if that noise level scales too aggressively with the number of users. The paper shows this works for moderate collusion, but scaling up to huge groups might introduce new vulnerabilities we haven't fully tested yet.

Nadia: Exactly. So, the main thing here is that we have a concrete blueprint using code-based cryptography instead of just hoping lattice problems stay hard enough against quantum computers for aggregation tasks.

Elias: It’s a solid construction based on the LPN assumption, which gives us a path forward when we look at post-quantum security for these kinds of tasks. We've got to keep looking at those parameter choices because that's where the actual security lives.

Technical University of Munich

cs.CR, cs.IT, math.IT

Submitted: 2026-01-19

Updated: 2026-10-15

Code: https://github.com/sebastianbitzer/LPNAgg

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 76/100

The gist: The gist: A code-based alternative for secure aggregation by instantiating a general framework based on key- and messageadditive homomorphic encryption under the Learning Parity with Noise (LPN)

Key concepts

Secure Aggregation
A method allowing a server to calculate the sum of private inputs from multiple users without ever seeing the individual contributions of those users. This is vital for privacy in scenarios like federated learning where individual data must remain hidden.
Learning Parity with Noise (LPN) Assumption
A coding theory problem that forms the foundation for this encryption scheme. It relates to reconstructing a secret key from noisy linear equations, which is used here to build the security of the key- and message-additive homomorphic encryption.
Key- and Message-Additive Homomorphic Encryption (KAHE)
A specific type of encryption where both the secret keys and the encrypted messages can be added together homomorphically. This property allows a server to perform additions on encrypted data without decrypting it first, which is essential for secure aggregation.
Chinese Remainder Theorem (CRT)
A mathematical tool used to reduce the size of large numbers by breaking them down into smaller parts based on different moduli. In this protocol, it helps reconstruct the final aggregate input from smaller, per-modulus results, optimizing communication costs.

Terminology

Summary

The gist: A code-based alternative for secure aggregation by instantiating a general framework based on key- and messageadditive homomorphic encryption under the Learning Parity with Noise (LPN) assumption is presented, which is shown to be equivalent to standard LPN for suitable parameters

Introduction and Motivation

Secure aggregation allows a server to obtain an aggregate of individual contributions without revealing the individual contributions to non-authorized parties Such mechanisms are particularly important in federated learning (FL), where model updates from participating users must be aggregated without compromising their privacy Secure aggregation methods can be categorized into two classes: information-theoretic approaches, which rely on bounded collusion assumptions, and cryptographic approaches, which relax collusion assumptions at the cost of relying on bounded computational power of adversaries However, the advent of quantum computing threatens classical cryptographic primitives, motivating the need for practical post-quantum–resilient protocols Code-based approaches demonstrate that secure aggregation constructions can alternatively be instantiated under codingtheoretic hardness assumptions, namely the Learning Parity with Noise (LPN) problem

Private Aggregation Framework

The system consists of a single server, a set of N users indexed by j ∈ [N], and a decryptor Each user j holds a k-dimensional private input mj, whose entries are quantized to Λ levels of integer precision The inputs are embedded into Fk q of cardinality q > N(Λ − 1), ensuring that Λ < qN + 1 and thereby preventing overflows during integer addition modulo q The protocol involves several steps:

  1. Key setup and sharing, where each user j generates a secret key sj using KAHE.KeyGen

  2. Input encryption, where each user j encrypts its private input mj under the secret key sj, obtaining a ciphertext yj = KAHE.Encrypt(mj, sj)

  3. User-to-server transmission, where each user sends ctj and yj to the server

  4. Individual key recovery, where the decryptor decrypts f(sj) = PKE.Decrypt(ctj, sk) and recovers the corresponding secret key as sj = f−1(f(sj))

  5. Key aggregation, where the decryptor aggregates the recovered keys as ¯s = PN j=1 sj, and transmits the aggregate to the server

  6. Aggregate input recovery, where the server aggregates the ciphertexts yj of all users j ∈ [N] using the homomorphic addition procedure of KAHE to obtain y¯ = KAHE.Add(y)j∈[N], and uses ¯s to recover m¯ = PN j=1 mj ∈ Fk q

Key-Additive Encryption from LPN

The key- and message-additive homomorphic encryption scheme KAHE is the central component of the aggregation framework It is constructed based on the LPN assumption, following a blueprint of Regev but transferring it to the Hamming metric The definition of LPN-based KAHE involves sampling a secret key s ←−R Fk q, encrypting the message m under this key as sA+e+C.enc(m), where e ←−R Bern(p) n, and aggregating ciphertexts y¯ = Pj∈[N] yj under the aggregate key ¯s = Pj∈[N] sj Theorem 1 proves that KAHE is semantically secure under the LPN assumption when instantiated with noise rate p and a specific noise rate τ

Security Analysis via Hint-LPN

The security of the construction relies on the Hint-LPN assumption, which reveals an erroneous version of the LPN error Theorem 3 establishes an efficient reduction from LPNk,τ to HintLPNp,k,p This reduction allows the proof to proceed by showing that any adversary breaking the semantic security of KAHE can be turned into a distinguisher for HintLPN Theorem 2 demonstrates that assuming an attacker colludes with z clients and receives ¯s, they can break the semantic security if they can break the LPNk,τ′ assumption

Complexity Reduction via CRT

The Chinese Remainder Theorem (CRT) is used to reduce the field size by executing the protocol repeatedly over smaller moduli The aggregate m¯ = PN j=1 mj ∈ Zq is reconstructed from per-modulus aggregates m¯ t ∈ Fk qt, where q = q1 · q2 · · · qα The modulus qt is lower bounded by the collusion parameter z, such that qt > z, and may be chosen to minimize communication costs The number of committee members Mt is selected as Mt = min(qt, M)

Performance Evaluation

The performance evaluation shows that the LPN-based KAHE with a committee-based decryptor incurs a communication cost per user of X t∈[α] kt · Mt − z + kC Rt log2(qt) bit This cost is optimized over the choices of q1,... qα and k1,...

Improvements for AI systems

  1. No-interaction secure aggregation in federated learning can be implemented by leveraging one-shot clients like those described in Willow [17] or OPA [16]. This allows model updates to be aggregated without requiring repeated interaction with a decryptor, which is crucial for communication efficiency across many training rounds.

  2. Implement secure aggregation protocols for machine learning model updates where the number of colluding clients is bounded by "z < N - 1 users" while still ensuring privacy against the server, as shown in Theorem 1. This means the aggregate value can be recovered even if up to N-2 clients collude with the server.

  3. Develop post-quantum secure aggregation for federated learning by using a code-based instantiation based on Learning Parity with Noise (LPN) instead of lattice-based assumptions, as proposed in Section IV. This provides cryptographic agility against future quantum attacks by relying on coding theory hardness assumptions.

  4. Reduce communication overhead for LPN-based aggregations by employing the Chinese Remainder Theorem (CRT)–based optimization described in Section III-C. This technique decomposes aggregation across multiple smaller moduli, which reduce the costs of LPN-based instantiations.

  5. Design a secure aggregation framework that can outperform information-theoretically secure protocols like SwiftAgg+ [3] by selecting parameters according to the concrete solver (Theorem 2) when z < N - 2. This allows for better performance trade-offs between code rate R and LPN noise rate τ.

Sources

Related papers