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

Pushing Forward Multi-Secret-Key Homomorphic Encryption for Private Average Aggregation Miguel Morona-Míngueza , Fernando Pérez-Gonzáleza and Alberto Pedrouzo-Ulloaa,∗

arXiv:2609.01945v1 [cs.CR] 1 Sep 2026

a atlanTTic, Universidade de Vigo, Escola de Enxeñaría de Telecomunicación, Vigo, 36310, Galicia, Spain

ARTICLE INFO

ABSTRACT

Keywords: Federated Learning (FL) Private Aggregation Homomorphic Encryption (HE) Ring Learning with Errors (RLWE) Multi-Key Encryption

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 semihonest model against an adversary corrupting the aggregator and up to 𝐿 − 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 (FL), first introduced in [42], is a Machine Learning (ML) framework in which multiple clients collaboratively address a learning task under the coordination of a central server, typically referred to as the aggregator. A distinctive property of FL is that the training data are distributed across different clients, such that each dataset remains stored locally and never leaves the corresponding client’s premises. While FL was initially proposed in [42] as a decentralized collaborative solution to avoid the prohibitive communication cost of collecting training data from many clients, it also provides a natural mechanism to reinforce data control and privacy protection by keeping local datasets isolated within each client’s premises [31]. Federated Learning process: Starting from an initial ⃗ ∗ , an FL protocommon ML model parameterized by 𝑤 col typically proceeds through successive communication rounds. In each round, 𝐿 participating clients, indexed by 𝑖 ∈ {1, … , 𝐿}, perform the following steps: (1) clients locally update the common model by partially training it using only their individual datasets, thereby producing lo⃗ 𝑖 , and (2) the central server aggregates all cal updates 𝑤 received local updates to compute a new global model. This aggregation step is usually performed by evaluating an ∗ Corresponding author

mmorona@gts.uvigo.es (M. Morona-Mínguez); fperez@gts.uvigo.es (F. Pérez-González); apedrouzo@gts.uvigo.es (A.

Pedrouzo-Ulloa) ORCID (s): 0009-0000-3759-1420 (M. Morona-Mínguez); 0000-0002-0568-1373 (F. Pérez-González); 0000-0002-7283-6275 (A. Pedrouzo-Ulloa)

Page 1 of 29

⃗ ∗ = 𝑓Σ (𝑤 ⃗ 1, … , 𝑤 ⃗ 𝐿 ). The aggregation function of the form 𝑤 resulting global model is then distributed to the clients for the next communication round. The process is repeated until a predefined convergence criterion is satisfied. Privacy issues: Unfortunately, even though clients’ raw data are not explicitly shared during training, privacy risks in FL still persist. Several works have shown that the exchanged local model updates may leak information about the data used during training, making them vulnerable to different types of inference attacks, particularly when adversaries have white-box access to both individual and aggregated updates [47, 34]. This issue is especially relevant for the aggregator, which, unlike other participants, has access to all individual updates sent by the clients. In view of this situation, additional protection mechanisms are required to mitigate residual privacy leakage, highlighting the importance of incorporating additional PrivacyEnhancing Technologies (PETs) [53] into the FL pipeline. In particular, private aggregation solutions [9] prevent any single participant from accessing individual local updates, thereby reducing the level of trust required from honest participants, especially with respect to the aggregator. As surveyed in [41], a wide range of PETs can be employed for this purpose. However, no single candidate suffices in all cases, since different PETs exhibit distinct trade-offs in terms of communication, computation, and robustness. Moreover, FL deployments differ in their requirements and are commonly categorized into two highlevel settings: the cross-device setting, in which the model is trained using data from many intermittently available and resource-constrained devices, and the cross-silo setting, in

which the model is trained using data from a smaller number of always-available and computationally powerful servers. Scope of our work: In this paper, we focus on the cross-silo setting, in which a set of stateful clients collaboratively train and improve a shared model using their collective data, while the aggregator coordinates the process but is not necessarily allowed to learn either intermediate or final model parameters. First, we analyze in detail the privacy and functional requirements that private aggregation mechanisms must satisfy in the cross-silo FL context; a review of existing definitions in the literature is provided in Section 2. Second, we concentrate on a specific PET, namely Homomorphic Encryption (HE) [45, 3] and, after studying its security properties, focus on optimizing its use for private aggregation in cross-silo FL scenarios.

1.1. FL Privacy via Homomorphic Encryption HE-based private aggregation naturally aligns with FL’s client–aggregator communication pattern. First, clients encrypt their local updates. Then, the aggregator homomor⃗ 1, … , 𝑤 ⃗ 𝐿 ). phically evaluates the aggregation function 𝑓Σ (𝑤 Finally, the clients decrypt the aggregated update. Multiple keys and HE-based aggregation: Several works, such as [61, 24], consider a simple deployment scenario in which all clients share the same secret and public keys. This implicitly imposes a strong non-collusion assumption between the aggregator and any party with access to the secret key (see Section 3). To relax this assumption, HE schemes can be extended to support ciphertexts encrypted under multiple keys [3]. While several approaches already allow the homomorphic aggregation of ciphertexts encrypted under different keys [39, 52], the most versatile class of solutions corresponds to threshold variants of single-key HE. A representative example is Multiparty Homomorphic Encryption (MHE), as proposed in [45], where a set of secret keys and a collective public key are generated during an offline setup phase prior to the execution of the FL protocol [43]. These multi-key constructions require decryption to be performed collaboratively by all participating clients (see Section 4).

1.2. Contributions and improvements over [43] In our preliminary work [43], we surveyed the MHE state of the art and analyzed its privacy vulnerabilities in the FL setting. We showed how MHE can be securely employed for private aggregation. In particular, removing the non-collusion assumption among participants when using MHE, whether based on CKKS or BFV, requires adding a smudging noise with variance proportional to 2𝜆 during decryption. Its central result was a detailed theoretical and experimental comparison of two MHE instantiations based on approximate CKKS and exact BFV single-key HE schemes, showing that CKKS-based MHE can match or even exceed the performance of BFV-based alternatives. This contrasts with previous observations in works such as [16], particularly when a large smudging noise is required.

Page 2 of 29

For a statistical security parameter 𝜆, the use of a smudging noise with variance 2𝜆 times larger introduces an overhead of (𝜆) bits in the size of the encrypted updates exchanged during each aggregation round. For practical and cryptographically secure choices, such as 𝜆 ≥ 128, this overhead can easily double the transmitted data size. Beyond its direct impact on efficiency, this also introduces additional implementation challenges, since noise generation must handle values exceeding the typical machine word size. Main contributions: The efficiency degradation caused by the large smudging noise motivates the search for alternative HE-based solutions that preserve security while avoiding this additional cost. In this work, we propose more efficient and lightweight private aggregation protocols based on two families of HE schemes supporting multiple secret keys, corresponding to approximate and exact HE. Following [52], our approach relies on a lightweight setup phase using additive secret sharing. More importantly, it departs from the blueprint of [45, 43] by eliminating the need to generate a collective public key. The main ideas and contributions of this work can be summarized as follows: • We introduce a new protocol tailored to average aggregation that extends single-key HE schemes, either approximate CKKS-based or exact BFV-based, to support multiple secret keys. This design removes the (𝜆) overhead by allowing the use of a smudging noise whose variance is independent of 𝜆. As in [52], the protocol is limited to homomorphic averaging, yet provides important advantages over the state of the art. First, it does not require a public key. Second, each client encrypts updates using its own secret key, which allows more compact ciphertexts and slightly improves performance. Third, the smudging noise has the same variance as the cryptosystem error distribution and is independent of 𝜆. This property enables a significant reduction in ciphertext size compared to previous approaches [43, 52]. • We formally prove the security and privacy of the proposed multi-secret-key protocol for private average aggregation using a simulation-based argument, assuming a semi-honest aggregator and a majority of semi-honest clients. • We provide concrete estimates of the overhead introduced by the proposed HE-based protocol and compare them with state-of-the-art MHE approaches, which incur an asymptotic overhead of (𝜆) bits. We extend the performance evaluation of [43] by presenting more detailed experimental results comparing approximate and exact MHE aggregation. In addition, we compare both approaches with our proposed secret-key HE-based aggregation in terms of bit precision and ciphertext size. We also analyze the parameter regimes in which the approximate or exact variants are preferable and report concrete implementation runtimes across practical parameter ranges.

Although our solutions are primarily designed for the cross-silo setting, they naturally extend to cross-device scenarios by re-running a lightweight setup phase per aggregation round. This allows the protocol to accommodate intermittent client participation. The additional setup phase incurs minimal overhead, provided that clients have sufficient computational and memory resources to perform additive share generation, encryption, and partial decryption.

1.3. Notation and structure Polynomials are denoted by lowercase letters, omitting the polynomial variable when there is no ambiguity, for example, writing 𝑎 instead of 𝑎(𝑥). We also represent polynomials as column vectors of coefficients 𝑎. ⃗ Scalar vectors are denoted with arrows (e.g., 𝑣), ⃗ while vectors whose entries are polynomials are denoted in boldface (e.g., 𝐯). Let 𝑅𝑞 = ℤ𝑞 [𝑥]∕(1 + 𝑥𝑛 ), where 𝑞 ∈ ℕ and 𝑛 is a power of two, denote the polynomial ring modulo 1 + 𝑥𝑛 with coefficients in ℤ𝑞 , represented in the interval (−𝑞∕2, 𝑞∕2]. Let 𝜒 denote the error distribution over 𝑅𝑞 , whose coefficients are independently sampled from a discrete Gaussian distribution with standard deviation 𝜎 and truncated support [−𝐵, 𝐵]. For a finite set , the notation 𝑥 ←  denotes uniform sampling from , while 𝑥 ← 𝜒 denotes sampling from the distribution 𝜒. Finally, both ||𝑎|| ⃗ and ||𝑎|| denote the infinity norm of 𝑎. ⃗ The rest of the document is organized as follows: Section 2 surveys existing security definitions for private aggregation. Section 3 reviews approximate and exact singlekey HE schemes and their application to private aggregation under simpler threat models, including a discussion of privacy vulnerabilities arising from restricted decryption access. Section 4 introduces Multiparty HE as an extension of HE supporting multiple secret keys in the FL setting and analyzes current countermeasures against the attacks described in [16, 17], together with analytical comparisons between Multiparty BFV and Multiparty CKKS. Section 5 presents our proposed solution, which does not rely on a large-variance smudging error. Section 6 evaluates and compares the performance of approximate and exact MHE with our proposed approach. Finally, Section 7 concludes the paper and outlines future research directions.

2. Background on Aggregation Threat Models This section surveys the definitions typically considered in the literature for private aggregation and examines how they align with the actual requirements of FL. Since this primitive was not originally introduced in the FL context, we first recall, in Section 2.1, the commonly used threatmodel definitions, and then revisit them in Section 2.2 to identify which assumptions should be refined for the FL setting considered in this work. As introduced in Section 1, the private computation of ⃗ 1, … , 𝑤 ⃗ 𝐿 ) has become a the aggregation functionality 𝑓Σ (𝑤 key tool for mitigating privacy leakage from the exchange of ML model updates in FL protocols [31, 47]. While numerous private aggregation algorithms have been proposed in the literature [41], covering various properties and formal security Page 3 of 29

definitions [56, 41], the appropriate definition of a private aggregation primitive depends on the specific threat model and the particular requirements of the target FL training pipeline. In light of this, we aim to clarify next not only which functions 𝑓Σ are typically considered, but also what is commonly understood by computing them privately. This discussion also motivates the threat models and security limitations analyzed in Section 3 for a first, straightforward HE-based implementation of private aggregation in FL. More advanced threat models, involving stronger semihonest adversaries and requiring the use of multiple secret keys, are considered in Sections 4 and 5.

2.1. Threat Models for Private Aggregation In the FL literature, the aggregation of the local updates sent by the clients to the aggregator is commonly based ⃗ 1, … , 𝑤 ⃗ 𝐿) = on linear functions [31]. We denote by 𝑓Σ (𝑤 ∑𝐿 ⃗ 𝑖 a general linear aggregation function, where the 𝑖=1 𝜆𝑖 𝑤 𝜆𝑖 , 1 = 1, … , 𝐿, are arbitrary public coefficients. This formulation includes, as common special cases, the sum, obtained for 𝜆𝑖 = 1 for all 𝑖, and the average, obtained for 𝜆𝑖 = 1∕𝐿 for all 𝑖. Most private aggregation proposals aim to securely compute a linear function of this form [41]. The term secure aggregation first appeared outside FL, in the context of Wireless Sensor Networks (WSNs), for the private aggregation of data generated by multiple nodes [29, 41, 56]. It was later applied to smart grids and smart meters [50, 13, 33], leading to a growing body of related solutions, including privacy-preserving aggregation [56], privacy-friendly aggregation [33], and private stream aggregation [15]. The first work discussing secure aggregation in the FL setting appeared in [9]. For more on the history of secure aggregation and its applications beyond FL, we refer the reader to [41]. As that work highlights, current secure aggregation protocols for FL still follow the blueprint established by early WSN solutions [41], which continues to shape the requirements considered today. In particular, [41] outlines two main security definitions that an ideal secure aggregation protocol should satisfy under a strict threat model involving dishonest adversaries. While our focus here is on the semi-honest model,1 we include for completeness the corresponding definition for malicious behaviors. These notions serve as a baseline for the FL-specific discussion in Section 2.2. We begin with their requirement for semi-honest adversaries: Definition 1 (Aggregator Obliviousness [56]. Adapted with major changes from [41] and [56]). This definition captures the following security notions: • An honest-but-curious aggregator cannot learn more than what can be inferred from the sum of the clients’ inputs (“aggregator capability”). • Clients alone (even when colluding among them) cannot learn anything about the aggregation result or the 1 A participant is semi-honest if they follow the protocol but try to infer additional information from the messages received.

updates of honest clients (as they lack the “aggregator capability”). • If clients collude with the aggregator by sharing their private inputs, the adversary learns nothing beyond what can be inferred from the aggregated value and the inputs of the colluding clients. This definition is formalized in [56] via a security game (Aggregator Obliviousness or AO security game), which can be extended to cover more general statistics. We refer the reader to [56] for further details. Beyond the semi-honest case, [41] introduces the following notion for entities that may deviate from the protocol: Definition 2 (Aggregate Integrity [41]. Adapted with minor changes from [41]). This security notion ensures that: • A malicious aggregator cannot forge an incorrect aggregation result without being detected by the clients. A forgery is defined as an aggregation outcome that differs from the true sum of the clients’ inputs. • A group of malicious clients cannot compromise the aggregation result as long as a sufficient number of honest clients (above a certain threshold) participate. A compromise is defined as a significant deviation of the aggregation outcome from the sum of the honest clients’ inputs. Implementing secure aggregation primitives satisfying Definition 2 typically requires mechanisms for clients to verify the aggregator’s behavior [28] and ensure that dishonest clients’ inputs meet validity conditions [37]. While such verification helps limit malicious-client drift, linear aggregation functions are not well-suited to Byzantine clients, since even one Byzantine participant can manipulate the result and prevent convergence of the trained FL model [8]. A common alternative is to replace the average with a more robust aggregation function, such as the median, trimmed mean, or multi-Krum [8], among others [25]. However, it remains unclear whether these robust functions are compatible with existing secure aggregation primitives [41], which are primarily designed for linear aggregation and, as discussed, remain vulnerable to Byzantine clients. Due to these limitations, we consider a passive threat model where clients behave semi-honestly. Moreover, since average functions are widely adopted in practical FL deployments, this work focuses on the private implementation of conventional linear aggregation functions.

2.2. FL-tailored Private Aggregation Definitions We now revisit Definitions 1 and 2 from the perspective of FL. Although these definitions provide clear guidelines regarding the properties a secure aggregation functionality should satisfy, they are strongly influenced by the context of wireless sensor networks, where a third party computes the aggregation of data from multiple nodes with no further interaction between the nodes and the aggregator. While this Page 4 of 29

setting does not exactly align with the specific requirements of FL, relevant surveys such as [31] already assume secure aggregation as a foundational component in FL, typically requiring that the server learn no more than an aggregated function of the clients’ inputs. We therefore examine whether all the properties of this building block are truly suitable for FL, by revisiting the general definition provided in [31]: Definition 3 (FL definition taken literally from [31]). “Federated learning is a machine learning setting where multiple entities (clients) collaborate in solving a machine learning problem, under the coordination of a central server or service provider. Each client’s raw data is stored locally and not exchanged or transferred; instead, focused updates intended for immediate aggregation are used to achieve the learning objective.” We note that Definition 3 does not explicitly require the aggregator to learn the intermediate aggregation result during training. Rather, its role is to coordinate the aggregation process. This distinction is important for determining which properties a private aggregation functionality should satisfy in FL. First, allowing the aggregator to inspect aggregated updates at each round increases the privacy leakage already associated with the exchange of model updates [31, 47]. From a privacy perspective, this exposure should therefore be minimized. Second, in FL, the aggregator coordinates the aggregation rounds and forwards the result to the clients, who are the actual recipients of the intermediate aggregation outputs. In contrast, Definition 1 assumes a setting where clients do not receive the aggregation result. Early secure aggregation protocols thus appear to follow a one-way communication model from clients to the aggregator, always revealing the aggregated output to the server. As a result of this modeling choice, several potentially valid approaches are often excluded, even though their guarantees may be appropriate in practical FL applications. A clear example is the cross-silo FL setting [61], where clients typically have more computational resources and influence over training than in cross-device settings. Such deployments often involve institutions, such as hospitals or financial organizations, collaborating over distributed private datasets [22, 26, 30]. In this setting, clients are often considered less adversarial, while the aggregator remains a highrisk entity due to its access to intermediate updates during training. Accordingly, recent works, including [22, 59], frequently adopt more relaxed threat models for clients. In hospital collaborations, for instance, institutions may be reasonably trusted because they are known to each other and can establish agreements before training; legal safeguards and shared interests further support semi-honest behavior. In addition to private aggregation, complementary countermeasures such as Differential Privacy (DP), or metrics to evaluate privacy risks in the aggregated result (output privacy) [4], can be applied beforehand by the clients to decide whether to participate in training [53]. We treat this issue as independent from privately computing the aggregation itself (input privacy) [4]. Therefore, we focus on the private

⃗ ∗ = 𝑓Σ (𝑤 ⃗ 1, … , 𝑤 ⃗ 𝐿 ), regardless of how computation of 𝑤 much information the aggregated result may reveal about the training data (output privacy) [41, 59]. In particular, in our preliminary work [43, Definition 2], we considered the following general multiparty aggregation problem [45], where multiple clients, each owning a locally stored and isolated dataset, collaborate using their private local updates: Definition 4 (Adapted from Def. 1 in [46]). Let  = {𝐶1 , 𝐶2 , … , 𝐶𝐿 } be a set of 𝐿 clients, where each client ⃗ 𝑖 and receives an output 𝑤 ⃗ ∗ . Let 𝐶𝑖 holds an input 𝑤 ∗ ⃗ 1, 𝑤 ⃗ 2, … , 𝑤 ⃗ 𝐿) = 𝑤 ⃗ be the average aggregation 𝑓Σ (𝑤 function (𝑓Σ is referred to as the ideal functionality) over the input parties. Let  be a static semi-honest adversary that can corrupt up to 𝐿 − 1 clients in , and let  be the subset of clients corrupted by . Then, the secure multiparty ⃗ ∗, aggregation problem consists in providing  with 𝑤 ⃗ 𝑖 }𝐶𝑖 ∉ than ensuring that  learns nothing more about {𝑤 ⃗ 𝑖 }𝐶𝑖 ∈ and the what can be inferred from the inputs {𝑤 ⃗ ∗ it controls. This condition ensures input privacy. output 𝑤 The formulation in Definition 4 deliberately abstracts away from the aggregator, even though the aggregator is part of the FL protocol and may participate in the computation for computational or communication efficiency. This omission in [43] emphasized that, in the cross-silo setting [61], clients are the sole owners of the data whose privacy must be protected and the recipients of the intermediate aggregation results during FL training. In this setting, the aggregator acts neither as an input party nor, in general, as a receiver of the intermediate outputs. However, in certain aggregation executions, such as at the end of training, the aggregator may also receive the aggregated result. For this reason, we refine the formulation here to reflect that possibility: Definition 5 (Adapted from Def. 4 to our FL setting). Let 𝐴𝑔𝑔 be the aggregator, which may act as a receiver party when applicable, and let  = {𝐶1 , 𝐶2 , … , 𝐶𝐿 } be a set of 𝐿 clients, where each client 𝐶𝑖 holds an input 𝑤⃗𝑖 and acts as ⃗ 1, 𝑤 ⃗ 2, … , 𝑤 ⃗ 𝐿) = 𝑤 ⃗∗ an input and receiver party. Let 𝑓Σ (𝑤 be the average aggregation function, referred to as the ideal functionality, over the input parties. Let  be a static semihonest adversary that may corrupt up to 𝐿 − 1 clients in , and potentially 𝐴𝑔𝑔 as well. Let  denote the subset of clients corrupted by . Then, the secure multiparty aggre⃗ ∗ to the clients gation problem in FL consists of providing 𝑤 in , and to 𝐴𝑔𝑔 if required in that execution, while ensuring ⃗ 𝑖 }𝐶𝑖 ∉ than what can that  learns nothing more about {𝑤 ⃗ 𝑖 }𝐶𝑖 ∈ and the be inferred from the corrupted inputs {𝑤 ⃗ ∗ it observes. In this problem, 𝐴𝑔𝑔 coordinates and output 𝑤 ⃗ ∗ . This condition assists the clients in the computation of 𝑤 ensures input privacy. A solution to the secure multiparty aggregation problem in FL consists of a protocol 𝜋𝑓Σ that realizes the ideal functionality 𝑓Σ while preserving input privacy [36]. This definition makes clear that, while the aggregator may be involved in the execution of 𝜋𝑓Σ throughout the training Page 5 of 29

process, it does not necessarily need access to the clients’ inputs. In some cases, output access can be allowed, e.g., access to the final trained model. Consequently, Definition 5 does not categorically prevent the aggregator from learning the output. Rather, it separates that aspect explicitly from input privacy. As we will show in the following sections, this distinction can significantly impact the implementation of 𝜋𝑓Σ when relying on modern HE schemes. Note also that some HE-based instantiations compute an approximation of 𝑓Σ . For such instantiations, we keep 𝑓Σ as the exact mathematical aggregation functionality and distinguish input privacy from approximate correctness: the protocol output may be a bounded, randomized approximation of 𝑓Σ , while the privacy guarantee is still defined with respect to the exact functionality 𝑓Σ .

3. Background on HE for FL The role of the aggregator discussed in Definitions 4 and 5 resembles that of a third party in outsourced computation, to whom clients delegate computational tasks. Moreover, as discussed above for Definition 1, previous research [61] has pointed out how certain FL settings, such as cross-silo, impose more stringent privacy requirements on the aggregator. A natural way to mitigate privacy leakage in such outsourcing scenarios is HE, which has already been considered for average aggregation in several works [56, 7, 61, 40]. Notably, HE-based aggregation is particularly well suited to these settings, as it satisfies these privacy constraints while imposing fewer constraints on the underlying FL system architecture than alternative approaches. Lattice-based HE: Although HE has previously been considered in the context of FL, the adoption of modern lattice-based HE schemes, such as BFV, BGV, and CKKS [1, 10], remains relatively recent [54, 55]. Beyond their efficiency in implementing linear functions over encrypted long vectors via SIMD (Single Instruction Multiple Data), latticebased HE schemes offer additional advantages. First, they are widely believed to be resilient against quantum adversaries; indeed, most proposals selected in the NIST PostQuantum Cryptography Standardization Process are latticebased [48]. Second, they provide sufficient expressiveness to homomorphically evaluate more complex functions than earlier schemes such as Paillier [51] or ElGamal [21, 27]. As a result, while most prior work on private aggregation focuses on average computations [41], recent studies have begun leveraging lattice-based HE to support more complex, Byzantine-resilient aggregation functions [20]. However, lattice-based HE schemes introduce challenges under multiple keys. We discuss them for publickey schemes in Section 4, and then introduce our proposed symmetric-key protocol in Section 5. Before that, as argued in Section 2.2, relaxed threat models can be addressed using single-key HE. In particular, when private channels exist between the aggregator and the clients and no collusions are assumed, single-key HE remains the simplest, most efficient. It is in this setting that our distinction in Definition 5, on

Table 1 Summary of 𝖡𝖥𝖵 & 𝖢𝖪𝖪𝖲 HE Schemes. Parameters remarks 𝖡𝖥𝖵: 𝑅𝑞 is the ciphertext ring. Δ = ⌊ 𝑞𝑡 ⌋. 𝑅𝑡 is the plaintext ring, with 𝑞 > 𝑡. 𝖢𝖪𝖪𝖲: 𝑅𝑞 is the ciphertext ring. Given an arbitrary target margin error 𝜖 and 𝐵, we can set the scale Δ. Cryptographic Primitives BFV

Select 𝑝𝑝 ← (𝑡, 𝑛, 𝑞, 𝜎, 𝐵, Δ)

CKKS

Select 𝑝𝑝 ← (𝜖, 𝑛, 𝑞, 𝜎, 𝐵, Δ)

𝖤𝖺𝗁𝖾 .𝖲𝖾𝗍𝗎𝗉() = 𝑝𝑝 𝖤𝖺𝗁𝖾 .𝖲𝖾𝖼𝖪𝖾𝗒𝖦𝖾𝗇(1𝜆 ) = 𝗌𝗄

Given the security parameter 𝜆, sample 𝑠 ← 𝑅3 . Output 𝗌𝗄 = 𝑠

𝖤𝖺𝗁𝖾 .𝖯𝗎𝖻𝖪𝖾𝗒𝖦𝖾𝗇(𝗌𝗄) = 𝗉𝗄

Sample 𝑝1 ← 𝑅𝑞 , and 𝑒𝗉𝗄 ← 𝜒. 𝗉𝗄 = (𝑝0 , 𝑝1 ) = (−𝑠 ⋅ 𝑝1 + 𝑒𝗉𝗄 , 𝑝1 )

𝖤𝖺𝗁𝖾 .𝖤𝗇𝖼(𝗉𝗄, 𝑚) = 𝖼𝗍

Sample 𝑢 ← 𝑅3 and 𝑒0 , 𝑒1 ← 𝜒. 𝖼𝗍 = (𝑐0 , 𝑐1 ) = (Δ𝑚 + 𝑢 ⋅ 𝑝0 + 𝑒0 , 𝑢 ⋅ 𝑝1 + 𝑒1 )

𝖤𝖺𝗁𝖾 .𝖠𝖽𝖽(𝖼𝗍, 𝖼𝗍′ ) = 𝖼𝗍𝖺𝖽𝖽

Given 𝖼𝗍 = (𝑐0 , 𝑐1 ) and 𝖼𝗍′ = (𝑐0′ , 𝑐1′ ), 𝖼𝗍𝖺𝖽𝖽 = (𝑐0 + 𝑐0′ , 𝑐1 + 𝑐1′ ) BFV

𝑚 = [⌊ 𝑞𝑡 [𝑐0 + 𝑐1 ⋅ 𝑠]𝑞 ⌉]

CKKS

𝑚≈

𝖤𝖺𝗁𝖾 .𝖣𝖾𝖼(𝗌𝗄, 𝖼𝗍) = 𝑚

𝑡

[𝑐0 +𝑐1 ⋅𝑠]𝑞 Δ

Decryption remarks 𝖡𝖥𝖵: Decryption correctness holds if (2𝑛 + 1)𝐵 < 2𝑡𝑞 − 2𝑡

(see Lemma 1), being 𝑛 > 𝛿𝑅 an upper bound for the expansion factor 𝛿𝑅 of the ring 𝑅 [14].

𝖢𝖪𝖪𝖲: After decryption, we obtain 𝑚̃ = 𝑚 + 𝑒𝖼𝗍 ≈ 𝑚, where 𝑒𝖼𝗍 is the internal error of the ciphertext, with ||𝑒𝖼𝗍 || < (2𝑛+1)⋅𝐵 . Δ

whether the aggregator learns the output, becomes crucial for protocol efficiency. We first recall HE building blocks in Section 3.1. We then describe their use for private aggregation under a relaxed threat model with private channels in Section 3.2. Finally, Section 3.3 analyzes the security and efficiency implications of aggregator access to the output.

3.1. HE building blocks ⃗∗ = Since we focus on linear aggregation functions 𝑤 ∑𝐿 ⃗ 1, … , 𝑤 ⃗ 𝐿 ) = 𝑖=1 𝜆𝑖 𝑤 ⃗ 𝑖 , with averaging being the most 𝑓Σ (𝑤 common in FL, we restrict ourselves to additive HE schemes. Definition 6 (Additive Homomorphic Encryption). Let 𝖤 = {𝖲𝖾𝗍𝗎𝗉, 𝖲𝖾𝖼𝖪𝖾𝗒𝖦𝖾𝗇, 𝖯𝗎𝖻𝖪𝖾𝗒𝖦𝖾𝗇, 𝖤𝗇𝖼, 𝖣𝖾𝖼} be an asymmetric encryption scheme, whose security is parameterized by 𝜆. An additive homomorphic encryption scheme extends 𝖤 with the 𝖠𝖽𝖽 procedure, having 𝖤𝖺𝗁𝖾 = {𝖤.𝖲𝖾𝗍𝗎𝗉, 𝖤.𝖲𝖾𝖼𝖪𝖾𝗒𝖦𝖾𝗇, 𝖤.𝖯𝗎𝖻𝖪𝖾𝗒𝖦𝖾𝗇, 𝖤.𝖤𝗇𝖼, 𝖤.𝖣𝖾𝖼, 𝖠𝖽𝖽}, where • Let 𝑐𝑣⃗ and 𝑐𝑤⃗ be two ciphertexts encrypting, respec⃗ The procedure 𝖠𝖽𝖽 satisfies: tively, 𝑣⃗ and 𝑤. ⃗ 𝖤𝖺𝗁𝖾 .𝖣𝖾𝖼(𝖤𝖺𝗁𝖾 .𝖠𝖽𝖽(𝑐𝑣⃗, 𝑐𝑤⃗ )) = 𝑣⃗ + 𝑤.

(1)

We choose two state-of-the-art RLWE (Ring Learning with Errors)-based cryptosystems to instantiate the 𝖤𝖺𝗁𝖾 scheme of Definition 6. Specifically, they correspond to BFV [11, 23] and CKKS [18], representing exact and approximate HE schemes, respectively. We refer the reader to Table 1 for details on their primitives and parameters. Both schemes allow us to perform SIMD-style additions by packing a total of 𝑛 values.2 However, they still present 2 For the more general case of SIMD-style additions and multiplications, we can pack in each separate ciphertext a total of, respectively, 𝑛 integer values and 𝑛∕2 approximate complex values for BFV and CKKS.

Page 6 of 29

significant differences regarding correctness [2]. While for BFV we can choose adequate parameters which satisfy Eq. (1) for all the homomorphic additions needed to compute 𝑓Σ (⋅), capturing the behavior of approximate HE requires relaxing the exact correctness of 𝖤. This can be done by ⃗ instead. considering 𝖤𝖺𝗁𝖾 .𝖣𝖾𝖼(𝖤𝖺𝗁𝖾 .𝖠𝖽𝖽(𝑐𝑣⃗, 𝑐𝑤⃗ )) ≈ 𝑣⃗ + 𝑤 ⃗ 𝑖 ) denote an encryption of Now, let 𝑐𝑤⃗ 𝑖 = 𝖤𝖺𝗁𝖾 .𝖤𝗇𝖼(𝗉𝗄, 𝑤 ⃗ 𝑖 . Given an error tolerance 𝜖 > 0, we say that the CKKS 𝑤 scheme is approximately correct, if the following holds: ‖ ⃗ 1, … , 𝑤 ⃗ 𝐿 ) − 𝖤𝖺𝗁𝖾 .𝖣𝖾𝖼(𝑓Σ (𝑐𝑤⃗ 1 , … , 𝑐𝑤⃗ 𝐿 ))‖ ‖ < 𝜖. ‖𝑓Σ (𝑤 ‖ ‖ Further details on the lattice-based HE: To ensure a fair comparison between BFV and CKKS, we made minor modifications to the original CKKS scheme described in [18]. These changes primarily involve sampling the randomness in both BFV and CKKS from the same distributions. Additionally, CKKS and BFV use different slot packing methods [58, 18], leading to some variations in operations before and after encryption and decryption. However, since our focus in this work is on homomorphic additions, for which SIMD-style operations hold without packing, we remove this step in both schemes. Consequently, some of the procedures described in Table 1 coincide for both schemes.

3.2. Single-Key HE under a Relaxed Threat Model The incorporation of HE for securely computing the aggregation function in FL follows two main principles: (1) unprotected local data is isolated in silos and remains on the clients’ premises, and (2) all local model updates leaving a silo are encrypted using HE. Figure 1 sketches the process followed to train a model. The protocol proceeds as follows: 1. Setup step: All involved clients generate the common protocol cryptographic keys. An initial common ML model is agreed upon by clients and the aggregator.

the decryptions could leak information regarding the private key. We elaborate next on 𝖨𝖭𝖣-𝖢𝖯𝖠𝖣 , which is the security definition that best captures this output-access setting.

3.3. More advanced Threat Models: 𝖨𝖭𝖣-𝖢𝖯𝖠𝖣

Figure 1: Protocol for private aggregation in FL using singlekey HE. Private channels exist between aggregator and clients.

2. Local training step: Each client trains locally with its data to obtain a local model update. 3. Input step: Each client encrypts its local model update with the public key 𝗉𝗄 and sends it to the aggregator over a private channel. 4. Evaluation step: The aggregator homomorphically computes the functionality 𝑓Σ . 5. Output step: Finally, all involved parties receive the aggregated model update and locally decrypt it using their shared secret key. 6. Output (extra) step: If the aggregator receives the output, the clients send the decryption to the aggregator. Steps 2 to 5 are repeated several times until convergence. We remind the reader that in this setting, collusions between the aggregator and any client break security, since the aggregator has access to the ciphertexts of the honest clients while a dishonest client holds the common secret key.3 Consequently, assuming private channels between each client and the aggregator and no such collusions, both HE schemes described in Section 3.1 are a convenient fit for private aggregation. Under these assumptions, and when the aggregator does not learn the output, the protocol above preserves input privacy and solves the multiparty aggregation problem of Definition 5. First, as the HE scheme satisfies 𝖨𝖭𝖣-𝖢𝖯𝖠 (indistinguishability under chosen-plaintext attack; see Appendix D), the aggregator is unable to infer any information regarding the local updates except their length. Second, since the clients only receive the encrypted aggregation, several colluding semi-honest clients (up to 𝐿 − 1 out of a total of 𝐿) cannot learn more about the honest clients’ inputs than what can be deduced from their shared inputs. However, RLWE-based schemes also present important limitations if applied straightforwardly. In particular, if the Output (extra) step is executed and the aggregator learns the output, the protocol may exhibit unexpected vulnerabilities. If the HE scheme is not adequately instantiated, 3 We refer the reader to Section 4 for a detailed description of multiparty

HE schemes that address collusions between aggregator and clients.

Page 7 of 29

The notion 𝖨𝖭𝖣-𝖢𝖯𝖠𝖣 extends 𝖨𝖭𝖣-𝖢𝖯𝖠 by allowing the adversary access to a restricted decryption oracle that can only be used for genuine ciphertexts, or ciphertexts obtained from genuine ciphertexts through valid homomorphic operations.4 Specialized to our aggregation function 𝑓Σ , the idea ⃗ 1, … , 𝑤 ⃗ 𝐿 and 𝑓Σ can also is that an adversary knowing 𝑤 ⃗ 1, … , 𝑤 ⃗ 𝐿 ). Then, if this adversary has access obtain 𝑓Σ (𝑤 ⃗ 1 ), … , 𝖤𝗇𝖼(𝑤 ⃗ 𝐿 ) and homomorphically evaluates to 𝖤𝗇𝖼(𝑤 ⃗ 1 ), … , 𝖤𝗇𝖼(𝑤 ⃗ 𝐿 )), the aggregation function 𝑓Σ as 𝑓Σ (𝖤𝗇𝖼(𝑤 she should not gain more information from the decryp( ( )) ⃗ 1 ), … , 𝖤𝗇𝖼(𝑤 ⃗ 𝐿 ) than what she can tion 𝖣𝖾𝖼 𝑓Σ 𝖤𝗇𝖼(𝑤 ⃗ 1, … , 𝑤 ⃗ 𝐿 ). Unfortunately, in [35], already obtain from 𝑓Σ (𝑤 the authors showed that some HE schemes, which are 𝖨𝖭𝖣𝖢𝖯𝖠 secure, leak information through the difference between 𝖣𝖾𝖼(𝖤𝗏𝖺𝗅(𝑓 , 𝖤𝗇𝖼(𝑚))) and 𝑓 (𝑚) and hence are not 𝖨𝖭𝖣-𝖢𝖯𝖠𝖣 secure. An example is the case of approximate HE schemes like CKKS [18], for which even the difference ⃗ 𝑖 )) − 𝑤 ⃗ 𝑖 directly leaks the internal noise of the 𝖣𝖾𝖼(𝖤𝗇𝖼(𝑤 underlying RLWE sample, allowing the adversary to break the RLWE indistinguishability assumption. Until very recently, the cryptographic community believed that only approximate HE presented this vulnerability and that exact HE schemes like BFV [11, 23], BGV [12] or CGGI [19] were invulnerable to such attacks, thus being naturally safe under 𝖨𝖭𝖣-𝖢𝖯𝖠𝖣 . However, recent works [16, 17] have shown that this vulnerability can also be present in practice for exact schemes, whenever they have a nonnegligible probability of incorrect decryption. Both works exemplify how this vulnerability can be exploited to implement effective key-recovery attacks against several mainstream HE libraries. These attacks are especially relevant when dealing with threshold HE schemes [16, 17, 6]. Fortunately, the authors also propose several countermeasures to achieve 𝖨𝖭𝖣-𝖢𝖯𝖠𝖣 security. In particular, the problem can be mitigated by adding an independent smudging noise, whose variance grows exponentially in 𝜆, during decryption. Notably, [16] demonstrates how this countermeasure significantly impacts the cryptosystem’s parameters, subsequently reducing its efficiency. According to the authors, this effect is even more pronounced for CKKS, where using a largevariance smudging noise is likely to severely reduce the precision of the decrypted result. Impact of the smudging noise: Given a ciphertext 𝖼𝗍, the key-recovery attacks mentioned above aim to extract its noise component 𝑒𝖼𝗍 . If this extraction is feasible, the secret key can be recovered using linear algebra techniques. For approximate HE schemes, this process is relatively straightforward once decryption is accessible. However, for exact HE schemes, these attacks attempt to induce decryption 4 Formal security games are detailed in the Appendix D.

failures as a way to estimate the corresponding 𝑒𝖼𝗍 component. Therefore, even in extreme cases where the postprocessed decryption becomes unusable, adding sufficiently large smudging noise after decryption is necessary to hide any information leakage about the original error 𝑒𝖼𝗍 . Regarding this countermeasure, recent work by [2] discusses how the application-agnostic nature of 𝖨𝖭𝖣-𝖢𝖯𝖠𝖣 often leads to impractically large parameters when adding large smudging noise. This occurs because 𝑒𝗌𝗆𝗀 must statistically hide 𝑒𝖼𝗍 for all possible homomorphic circuits that satisfy correctness for the initially chosen cryptosystem parameters with the 𝖤𝖺𝗁𝖾 .𝖲𝖾𝗍𝗎𝗉() procedure. The authors propose a relaxation of this definition, termed application-aware 𝖨𝖭𝖣𝖢𝖯𝖠𝖣 , which is better suited for the FL setting. In our work, we follow their guidelines and assume that both the clients and the aggregator behave semi-honestly, meaning that they are expected to follow exactly the prescribed instructions for the aggregator to compute 𝑐𝑤⃗ ∗ = 𝑓Σ (𝑐𝑤⃗ 1 , … , 𝑐𝑤⃗ 𝐿 ) and for the clients to encrypt their local updates as 𝑐𝑤⃗ 1 , … , 𝑐𝑤⃗ 𝐿 .

4. Private Aggregation with Multiparty HE As described in Section 3, a key advantage of HE-based aggregation is that it preserves the natural communication flow of FL while enabling privacy against an untrusted aggregator. However, achieving Aggregator Obliviousness (Definition 1) requires clients to avoid encrypting updates under a common key. [41] shows that secure linear aggregation calls for multi-user HE variants [56, 3], which allow ciphertexts encrypted under distinct keys to be homomorphically aggregated. In the context of our multiparty aggregation problem in FL (Definition 5), these variants enable the construction of private aggregation protocols that remain secure against strong semi-honest adversaries controlling a majority of participants. This guarantee holds even when FL training runs over a public channel where all exchanged messages are observable by the remaining parties. Multiparty HE: We briefly review in Subsection 4.1 the MHE (Multiparty HE) construction introduced in [45]. This construction is based on a threshold variant of single-key HE, where the secret key associated with a collective public key is split into multiple additive shares distributed among clients. These shares are generated during an offline setup phase before the FL protocol starts. MHE enables encryption of local updates under this collective public key, while the corresponding secret key remains unknown to any individual party and decryption requires client collaboration. Since this construction can be instantiated from different underlying HE schemes, such as BFV and CKKS, we later discuss the resulting parameter constraints and ciphertext expansion in Section 6, with additional details provided in Appendix C. Despite this setup phase, MHE schemes scale well with the number of clients and allow the straightforward reuse of techniques from single-key HE. Unfortunately, recent works [16, 17, 6] show that both single-key HE and MHE become particularly vulnerable when there is a non-negligible probability of decryption errors. These works illustrate how Page 8 of 29

this vulnerability can be exploited to carry out effective keyrecovery attacks against several widely used HE libraries. Security models for HE with multiple keys: Previous works [45] have shown that MHE schemes can be proven secure under the 𝖨𝖭𝖣-𝖢𝖯𝖠 (Indistinguishability under Chosen-Plaintext Attack) security model, based on the hardness of the RLWE problem. Under this passive security model, the adversary only has access to encryptions via an encryption oracle. While this model may be sufficient from the aggregator’s perspective when only RLWE ciphertexts and the public key are visible, it no longer captures the more general case considered in Definition 5 when the FL protocol is executed over a public channel. As discussed in Section 3, 𝖨𝖭𝖣-𝖢𝖯𝖠𝖣 extends 𝖨𝖭𝖣-𝖢𝖯𝖠 by introducing a decryption oracle, which better captures scenarios in which the aggregator receives the output. With multiple keys, this distinction becomes more relevant, as participants may gain access not only to full decryptions without knowing the secret key, but also to partial decryptions from individual clients. Notably, the same countermeasure used in the single-key 𝖨𝖭𝖣-𝖢𝖯𝖠𝖣 setting applies to MHE, namely adding an appropriate amount of smudging noise to the partial decryptions [16, 17]. We discuss the role and concrete impact of this smudging noise in Subsection 4.2. General overview: The FL training process with singlekey HE, described in Section 3, must be adapted when using MHE. In particular, the key generation and decryption steps (steps 1 and 5) differ, as they are performed collaboratively by the participants.5 We now present an adapted FL protocol ⃗ 1, … , 𝑤 ⃗ 𝐿) that securely implements the aggregation 𝑓Σ (𝑤 using an 𝐿-party secret sharing scheme (see Definition 7 in Subsection 4.1). This protocol ensures input privacy against a colluding semi-honest aggregator and up to 𝐿 − 1 semihonest clients. In this setting, local updates are encrypted using MHE before leaving each silo, following the general approach proposed in [45]. Steps 2–5 are repeated until convergence. Figure 2 illustrates the full training process: 1. Setup step: All clients generate individual secret keys and a collective public key. An initial common ML model is agreed upon by the clients and the aggregator. 2. Local training step: Each client locally trains a model update using its private data. 3. Input step: Each client encrypts its local model update using the collective public key before sending it out. 4. Evaluation step: The aggregator homomorphically evaluates 𝑓Σ over the encrypted updates. 5. Output step: All clients collaboratively decrypt the aggregated model update. The result can then be explicitly shared with the aggregator, if needed.

4.1. MHE-based protocol for private aggregation This subsection details the baseline MHE-based protocol for securely evaluating 𝑓Σ (⋅) within an FL protocol executed over a public channel. We build on the MHE scheme 5 The public key is generated during setup and is associated with a global secret key that remains unknown to any single party, while this global secret key is “reconstructed” during collaborative decryption (Output step).

Table 2 Multiparty Private Aggregation Protocol. Public input: ideal aggregation functionality 𝑓Σ ⃗ 𝑖 for each 𝐶𝑖 ∈  Private input: 𝑤 Output for all clients in  and for the Aggregator : the ⃗ ∗ = 𝑓 Σ (𝑤 ⃗ 1, … , 𝑤 ⃗ 𝐿 ) for BFV, and an exact aggregate 𝑤 approximation for CKKS Setup

All clients 𝐶𝑖 instantiate the MHE scheme 𝖤𝗆𝗁𝖾 𝗌𝗄𝑖 = 𝖤𝗆𝗁𝖾 .𝜋𝑖,𝖲𝖾𝖼𝖪𝖾𝗒𝖦𝖾𝗇 (𝜆, 𝜅)* 𝖼𝗉𝗄 = 𝖤𝗆𝗁𝖾 .𝜋𝖯𝗎𝖻𝖪𝖾𝗒𝖦𝖾𝗇 (𝜅, 𝗌𝗄1 , … , 𝗌𝗄𝐿 )

Input

⃗ 𝑖 and provides it to Each 𝐶𝑖 encrypts its input 𝑤 the Aggregator + ⃗ 𝑖) 𝑐𝑤⃗ 𝑖 = 𝖤𝗆𝗁𝖾 .𝖤𝗇𝖼(𝖼𝗉𝗄, 𝑤

Figure 2: Protocol for private aggregation in FL using MHE.

proposed in [45], which provides a threshold construction on top of the two single-key HE schemes introduced in Section 3. The resulting protocol provides a solution to the multiparty aggregation problem in FL of Definition 5, with the aggregator also acting as a receiver party. The scheme in [45] is proven secure in the Common Reference String (CRS) model,6 and assumes that parties communicate over authenticated channels. Our tailored protocol for private aggregation is summarized in Table 2 and relies on the following augmented multiparty encryption scheme: Definition 7 (Multiparty Additive HE). Let 𝖤𝖺𝗁𝖾 = (𝖤.𝖲𝖾𝗍𝗎𝗉, 𝖤.𝖲𝖾𝖼𝖪𝖾𝗒𝖦𝖾𝗇, 𝖤.𝖯𝗎𝖻𝖪𝖾𝗒𝖦𝖾𝗇, 𝖤.𝖤𝗇𝖼, 𝖤.𝖣𝖾𝖼, 𝖤.𝖠𝖽𝖽) be the asymmetric and additive homomorphic encryption scheme from Definition 6, whose security is parameterized by 𝜆 (see Table 1 for two concrete examples with 𝖡𝖥𝖵 and 𝖢𝖪𝖪𝖲), and let 𝖲 = (𝖲.𝖲𝗁𝖺𝗋𝖾, 𝖲.𝖢𝗈𝗆𝖻𝗂𝗇𝖾) be an 𝐿-party secret sharing scheme. The associated multiparty homomorphic encryption scheme (𝖤𝗆𝗁𝖾 ) is obtained by applying the secretsharing scheme 𝖲 to 𝖤𝖺𝗁𝖾 ’s secret key 𝗌𝗄 (ideal secret key) and is defined as the tuple 𝖤𝗆𝗁𝖾 = (𝖤𝖺𝗁𝖾 .𝖤𝗇𝖼, 𝖤𝖺𝗁𝖾 .𝖣𝖾𝖼, 𝖤𝖺𝗁𝖾 .𝖠𝖽𝖽, 𝖤𝖲𝖺𝗁𝖾 ), where 𝖤𝖲𝖺𝗁𝖾 = (𝜋𝖲𝖾𝖼𝖪𝖾𝗒𝖦𝖾𝗇 , 𝜋𝖯𝗎𝖻𝖪𝖾𝗒𝖦𝖾𝗇 , 𝜋𝖣𝖾𝖼 ) is a set of multiparty protocols executed among the clients in the set , and having the following private ideal functionalities for each client 𝐶𝑖 :

The Aggregator computes the encrypted output Evaluation for the ideal functionality 𝑓Σ relying on 𝖤𝗆𝗁𝖾 .𝖠𝖽𝖽 𝑐𝑤⃗ ∗ = 𝑓Σ (𝑐𝑤⃗ 1 , … , 𝑐𝑤⃗ 𝐿 ) Output * +

The parties in  execute the decryption protocol ⃗ ∗ = 𝖤𝗆𝗁𝖾 .𝜋𝖣𝖾𝖼 (𝗌𝗄1 , … , 𝗌𝗄𝐿 , 𝑐𝑤⃗ ∗ ) 𝑤

𝜅 parameterizes the homomorphic capacity of 𝖤𝗆𝗁𝖾 . The Aggregator is in charge of performing the aggregation.

4.1.1. Concrete instantiations for Multiparty HE The private ideal functionalities introduced in Definition 7 can be implemented by clients via the following concrete protocols. In the decryption functionality 𝑓𝜋𝖣𝖾𝖼 , smudging noise is explicitly incorporated, as it constitutes a standard countermeasure required to achieve security in MHE schemes under the previously discussed threat model [16]: • 𝑓𝑖,𝜋𝖲𝖾𝖼𝖪𝖾𝗒𝖦𝖾𝗇 (𝜆): Each client 𝐶𝑖 independently runs the procedure 𝖤𝖺𝗁𝖾 .𝖲𝖾𝖼𝖪𝖾𝗒𝖦𝖾𝗇(1𝜆 ) = 𝗌𝗄𝑖 . • 𝑓𝜋𝖯𝗎𝖻𝖪𝖾𝗒𝖦𝖾𝗇 (𝗌𝗄1 , 𝗌𝗄2 , … , 𝗌𝗄𝐿 ): Given a common random polynomial 𝑝1 , each client 𝐶𝑖 ∈  samples 𝑒𝗉𝗄,𝑖 ← 𝜒 and discloses to the other clients 𝑝0,𝑖 = −𝑝1 ⋅𝗌𝗄𝗂 +𝑒𝗉𝗄,𝑖 . The collective public key is computed as: ∑ ∑ ∑ 𝑒𝗉𝗄,𝑖 , 𝑝1 ). 𝗌𝗄𝑖 + 𝑝0,𝑖 , 𝑝1 ) = (−𝑝1 ⋅ 𝖼𝗉𝗄 = ( ⏟⏟⏟

⏟⏟⏟

𝗌𝗄

𝑒𝗉𝗄

• Ideal secret-key generation: 𝑓𝑖,𝜋𝖲𝖾𝖼𝖪𝖾𝗒𝖦𝖾𝗇 (𝜆) = 𝖲.𝖲𝗁𝖺𝗋𝖾𝑖 (𝖤𝖺𝗁𝖾 .𝖲𝖾𝖼𝖪𝖾𝗒𝖦𝖾𝗇(𝜆)) = 𝗌𝗄𝑖 . • Collective public-key generation: 𝑓𝜋𝖯𝗎𝖻𝖪𝖾𝗒𝖦𝖾𝗇 (𝗌𝗄1 , 𝗌𝗄2 , … , 𝗌𝗄𝐿 ) = 𝖤𝖺𝗁𝖾 .𝖯𝗎𝖻𝖪𝖾𝗒𝖦𝖾𝗇(𝖲.𝖢𝗈𝗆𝖻𝗂𝗇𝖾(𝗌𝗄1 , 𝗌𝗄2 , … , 𝗌𝗄𝐿 )). • Collective decryption: 𝑓𝜋𝖣𝖾𝖼 (𝗌𝗄1 , 𝗌𝗄2 , … , 𝗌𝗄𝐿 , 𝖼𝗍) = 𝖤𝖺𝗁𝖾 .𝖣𝖾𝖼(𝖲.𝖢𝗈𝗆𝖻𝗂𝗇𝖾(𝗌𝗄1 , 𝗌𝗄2 , … , 𝗌𝗄𝐿 ), 𝖼𝗍). Definition 7 particularizes [46, Def. 2] to the case where the encryption scheme 𝖤𝖺𝗁𝖾 is additively homomorphic. 6 This model assumes that all parties share a common random string.

𝑖

𝑖

𝐶𝑖 ∈

• 𝑓𝜋𝖣𝖾𝖼 (𝗌𝗄1 , 𝗌𝗄2 , … , 𝗌𝗄𝐿 , 𝖼𝗍): The collaborative decryption protocol can be divided into two phases. – Given a ciphertext 𝖼𝗍 = (𝑐0 , 𝑐1 ) encrypted under the ideal secret key 𝗌𝗄, each client 𝐶𝑖 samples 𝑒𝗌𝗆𝗀,𝑖 ← 𝜒 and discloses its partial decryption ℎ𝑖 = 𝗌𝗄𝑖 ⋅ 𝑐1 + 𝑒𝗌𝗆𝗀,𝑖 . – Given all the decryption shares ℎ𝑖 from the clients, the protocol outputs: [ ] ∑ 𝑑 = 𝑐0 + ℎ𝑖 𝐶𝑖 ∈

𝑞

∑ = Δ𝑚 + 𝑢 ⋅ 𝑝0 + 𝑒0 + 𝗌𝗄𝑖 ⋅ 𝑐1 ⏟⏞⏞⏞⏞⏞⏞⏞⏞⏟⏞⏞⏞⏞⏞⏞⏞⏞⏟ 𝐶𝑖 ∈ 𝑐0

Page 9 of 29

+

∑

𝑒𝗌𝗆𝗀,𝑖

𝐶𝑖 ∈

⏟⏞⏞⏟⏞⏞⏟ 𝑒𝗌𝗆𝗀

= Δ𝑚 + 𝑒𝗉𝗄 ⋅ 𝑢 + 𝑒0 + 𝗌𝗄 ⋅ 𝑒1 +𝑒𝗌𝗆𝗀 . ⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟ 𝑒𝖼𝗍

The final step for decryption depends on whether BFV or CKKS is used as the underlying single-key HE scheme: • For BFV, the obtained decryption is 𝑚 = [⌊ 𝑞𝑡 𝑑⌉] . 𝑡

• For CKKS, the obtained decryption is 𝑚̃ = 𝑒𝖼𝗍 +𝑒𝗌𝗆𝗀

𝑑 Δ

=

𝑚+ ≈ 𝑚 for large enough Δ. Therefore, Δ 𝖬𝖯 , where 𝐵 𝖬𝖯 is defined in if ‖𝑒𝖼𝗍 + 𝑒𝗌𝗆𝗀 ‖ ≤ 𝐵𝖼𝗍 𝖼𝗍 𝖬𝖯 ∕Δ. Section 6.1, then ‖𝑚̃ − 𝑚‖ ≤ 𝐵𝖼𝗍 We can obtain lower bounds for 𝑞, similar to the singlekey counterparts (see Table 1), by taking into account the larger noise terms present in the threshold versions (see Section 6 for further details).

4.2. Impact of the smudging noise in MHE The smudging technique was introduced in [5] to address security vulnerabilities inherent to threshold HE schemes. In that work, the authors consider a slightly stronger class of semi-malicious adversaries who follow the protocol but may deviate from the prescribed randomness distributions. These deviations can be adversarially adapted based on the inputs provided by the honest parties. They show that sufficiently large smudging noise is required to securely execute several protocol phases, such as setup and decryption. Under our semi-honest threat model, smudging noise is required only during collaborative decryption. Given a ciphertext 𝖼𝗍, once all partial decryptions ℎ𝑖 = 𝗌𝗄𝑖 ⋅𝑐1 +𝑒𝗌𝗆𝗀,𝑖 are collected, the adversary gains direct access to 𝑑 = Δ⋅𝑚+ 𝑒𝖼𝗍 + 𝑒𝗌𝗆𝗀 . Thus, 𝑒𝗌𝗆𝗀 must be chosen so that the sum 𝑒𝖼𝗍 + 𝑒𝗌𝗆𝗀 is statistically indistinguishable from fresh noise 𝑒̃𝗌𝗆𝗀 (see the Smudging Lemma in [5]). We follow the practical guidelines provided in [16], which recommend Gaussian 2 . Applying an 2 smudging noise with variance 𝜎𝗌𝗆𝗀 = 2𝜆 𝜎𝖼𝗍 𝜆

upper bound 𝐵 = (𝜎),7 this results in 𝐵𝗌𝗆𝗀 = 2 2 𝐵𝖼𝗍 (for example, 𝜆 = 128 is suggested in [45]). Can we do better? An ideal alternative to large smudging noise: Assume each client has access to an oracle 𝑖 (⋅) which, given the ciphertext to be decrypted 𝖼𝗍 as input, ∑ outputs 𝗌𝗁𝖺𝗋𝖾𝑖 such that 𝐿 𝑖=1 𝗌𝗁𝖺𝗋𝖾𝑖 = 𝑒𝖼𝗍 ; that is, 𝑖 (𝖼𝗍) = 𝗌𝗁𝖺𝗋𝖾𝑖 , where 𝗌𝗁𝖺𝗋𝖾𝑖 is ideally uniformly random in 𝑅𝑞 . By calling this oracle, clients could remove the ciphertext error from the collaborative decryption result and replace it with fresh independent noise. For example, this can be done by computing ℎ𝑖 = 𝗌𝗄𝑖 ⋅ 𝑐1 − 𝗌𝗁𝖺𝗋𝖾𝑖 + 𝑒𝗌𝗆𝗀,𝑖 . Once all partial decryptions are gathered, the adversary obtains 𝑑 = Δ ⋅ 𝑚 + 𝑒𝗌𝗆𝗀 . Although this expression is similar to the previous one, 7 𝐵 = 6𝜎 is commonly used by HE libraries.

Page 10 of 29

note that now 𝑒𝗌𝗆𝗀 does not need to grow exponentially with 𝜆 because it no longer has to hide 𝑒𝖼𝗍 to make 𝑒𝖼𝗍 + 𝑒𝗌𝗆𝗀 statistically indistinguishable from fresh noise 𝑒̃𝗌𝗆𝗀 . Despite the apparent strength of this idea, implementing such an oracle in practice is not straightforward in a publickey encryption scheme. First, the simplest approach would require each client to track the error component introduced in its input ciphertext. However, since clients do not know the underlying error of the public key, they cannot determine the share that aggregates into the final error of the output ciphertext. Second, even if clients could know this error, it would be correlated with the collective-public-key error, potentially making the scheme vulnerable to key-recovery attacks similar to those described in [16, 17] and Section 3. We explore this idea in more detail in Section 5 and show that it is feasible when using symmetric-key encryption schemes. The main drawback is that clients must store and track the errors of their input ciphertexts. While this may not be practical for homomorphic evaluation of general functions, it is reasonable in our FL scenario with homomorphic average aggregation, where clients only need to store the errors used during a single communication round.

5. Proposed protocol and optimizations The MHE-based approach analyzed in the previous section provides a practical baseline for private aggregation in FL, but it also presents several limitations. In particular, ciphertexts must remain compatible with 𝖼𝗉𝗄, collaborative decryption requires large smudging noise, and the noise embedded in 𝖼𝗉𝗄 grows with the number of clients 𝐿. To overcome these issues, we introduce a construction based on multi-secret-key HE. Instead of encrypting client updates under 𝖼𝗉𝗄, each client encrypts using its own secret key, while ciphertexts remain compatible with homomorphic aggregation and collaborative decryption. This removes the dependency on 𝖼𝗉𝗄 and enables several practical optimizations, including reduced ciphertext size. This section is organized as follows: Subsection 5.1 introduces the secret-key HE building blocks used in our construction. Subsection 5.2 presents the proposed multi-secretkey aggregation protocol, including concrete instantiations based on BFV and CKKS together with implementationoriented optimizations. Finally, Subsection 5.3 states the main security result and provides a proof overview. General overview of our protocol: The proposed protocol follows the same high-level FL workflow as the MHEbased baseline, but replaces the 𝖼𝗉𝗄 encryption with a correlated symmetric-key construction across clients. The overall workflow is summarized below and illustrated in Figure 3. 1. Setup step: All clients generate individual secret keys and run a lightweight protocol establishing auxiliary shares for the protocol execution. An initial ML model is agreed upon by the clients and the aggregator. 2. Local training step: Each client locally trains a model update using its private data.

Zero-sharing Aggregate Aggregated Secret Key

Figure 3: Protocol for private aggregation in FL using the proposed multi-secret-key HE-based construction.

3. Input step: Each client encrypts its local model update using its individual secret key and sends the resulting ciphertext to the aggregator. 4. Evaluation step: The aggregator homomorphically evaluates 𝑓Σ over the encrypted updates. 5. Output step: All clients collaboratively decrypt the aggregated model update, which can then be shared with the aggregator if required.

5.1. Secret-Key HE building blocks We revisit Definition 6 for additive HE schemes by adapting it to the secret-key setting and removing the publickey generation procedure 𝖯𝗎𝖻𝖪𝖾𝗒𝖦𝖾𝗇. The scheme retains the same packing capacity (𝑛 values) and additive homomorphism whenever ciphertexts share the same secret key. Definition 8 (Additive Symmetric-Key Homomorphic Encryption). Let 𝖤 = {𝖲𝖾𝗍𝗎𝗉, 𝖲𝖾𝖼𝖪𝖾𝗒𝖦𝖾𝗇, 𝖤𝗇𝖼, 𝖣𝖾𝖼} be a symmetric encryption scheme, whose security is parameterized by 𝜆. An additive symmetric-key homomorphic encryption scheme extends 𝖤 with the 𝖠𝖽𝖽 procedure, having 𝖤𝖺𝗌𝗁𝖾 = {𝖤.𝖲𝖾𝗍𝗎𝗉, 𝖤.𝖲𝖾𝖼𝖪𝖾𝗒𝖦𝖾𝗇, 𝖤.𝖤𝗇𝖼, 𝖤.𝖣𝖾𝖼, 𝖠𝖽𝖽}. The correctness condition for 𝖠𝖽𝖽 is stated in terms of 𝜖 as follows: • Let 𝜖 ≥ 0 be the target margin error: 0 for exact HE schemes and positive for approximate HE schemes. • Let 𝑐𝑣⃗ and 𝑐𝑤⃗ be two ciphertexts encrypting under ⃗ The the same secret key 𝗌𝗄, respectively, 𝑣⃗ and 𝑤. procedure 𝖠𝖽𝖽 satisfies: ‖𝑣⃗ + 𝑤 ⃗ − 𝖤𝖺𝗌𝗁𝖾 .𝖣𝖾𝖼(𝖤𝖺𝗌𝗁𝖾 .𝖠𝖽𝖽(𝑐𝑣⃗, 𝑐𝑤⃗ ))‖ ‖ ‖ ≤ 𝜖. (2) As in Section 3 for the public-key HE setting, we instantiate 𝖤𝖺𝗌𝗁𝖾 using both approximate and exact variants, namely secret-key versions of CKKS and BFV, respectively. Their security relies on the RLWE problem, and Table 3 details their primitives and cryptographic parameters. Among the properties of these secret-key constructions, we next highlight two aspects that are particularly relevant for our private average aggregation protocol (see Section 5.2). Compressed ciphertext size: While in public-key HE schemes (see Table 1) the two components of a ciphertext Page 11 of 29

𝖼𝗍 = (𝑐0 , 𝑐1 ) depend on 𝗉𝗄, in the symmetric-key setting the public component (denoted 𝑎 in Table 3, from which 𝑐0 is derived) is a uniformly random polynomial in 𝑅𝑞 and therefore independent of 𝗌𝗄. As discussed in [52], this allows clients in an FL protocol to compress their encrypted inputs by approximately one half. Under the CRS model, this public component can be generated deterministically using a pseudorandom function 𝖯𝖱𝖥 (see Definition 9 below). Definition 9 (Pseudorandom Function (PRF)). Let , , and  be finite sets. A function 𝐹 ∶  ×  →  is efficiently computable if there exists a probabilistic polynomial-time (PPT) algorithm that, on input (𝜅, 𝑇 ) ∈  × , outputs 𝐹𝜅 (𝑇 ). We say that 𝐹 is a PRF (see [32]) if, for every PPT distinguisher , ] [ ]| | [ 𝐹𝜅 (⋅) 𝜆 (1 ) = 1 − Pr 𝑅(⋅) (1𝜆 ) = 1 | ≤ 𝗇𝖾𝗀𝗅(𝜆), |Pr  | | with 𝜅 ←  and 𝑅 ∶  →  a uniformly random function. We derive the public RLWE component as 𝑎 ← 𝖯𝖱𝖥𝜅 (𝑇 ). Any party that knows (𝜅, 𝑇 ) can deterministically reconstruct 𝑎, enabling ciphertext compression. Since 𝑎 is public in RLWE, its predictability given (𝜅, 𝑇 ) does not affect security provided that 𝜅 is sampled uniformly at random. For parties that do not know 𝜅 (e.g., the aggregator), the distribution of 𝖯𝖱𝖥𝜅 (𝑇 ) remains computationally indistinguishable from uniform over 𝑅𝑞 . Ciphertext noise is known by the encryptor: Even under ciphertext compression, and as a consequence of the RLWE assumption, the secret-key versions of both approximate and exact HE schemes satisfy 𝖨𝖭𝖣-𝖢𝖯𝖠 security. To achieve 𝖨𝖭𝖣-𝖢𝖯𝖠𝖣 security, one may again rely on adding large smudging noise after decryption. However, in these schemes, encryptors not only hold 𝗌𝗄 but also know the internal ciphertext noise 𝑒𝖼𝗍 , thereby effectively realizing the oracle 1 (𝖼𝗍) introduced in Section 4.2 for the special case 𝐿 = 1 (i.e., 1 (𝖼𝗍) = 𝑒𝖼𝗍 = 𝗌𝗁𝖺𝗋𝖾0 ). This contrasts with the public-key setting, where a party knowing 𝗉𝗄 can encrypt but does not (know 𝑒𝖼𝗍 . Focusing on the homomorphic eval) ⃗ 1 ), … , 𝖤𝗇𝖼(𝗌𝗄, 𝑤 ⃗ 𝐿 ) , and assuming uation of 𝑓Σ 𝖤𝗇𝖼(𝗌𝗄, 𝑤 a party holding 𝗌𝗄 acts as both encryptor and decryptor, this property allows the encryptor to record the noise used during encryption and track the linear combination applied to the ciphertexts. Consequently, the accumulated noise in the encrypted result can be explicitly computed and canceled during decryption, without relying on high-variance smudging noise. While this assumption is generally unrealistic in generic HE settings, it aligns well with FL deployments, where the number and lifetime of ciphertexts are naturally bounded between aggregation rounds. As discussed in Section 5.2, this observation is instrumental for our protocol.

5.2. Multi-Secret-Key HE Private Aggregation The 𝖤𝖺𝗌𝗁𝖾 .𝖠𝖽𝖽 primitive in Definition 8 assumes that input ciphertexts are encrypted under the same unknown secret key. In our protocol, however, ciphertexts under different secret keys must be combined while preserving privacy

Table 3 Summary of 𝖡𝖥𝖵 & 𝖢𝖪𝖪𝖲 Additive Secret-key HE schemes. Parameters remarks 𝖡𝖥𝖵: 𝑅𝑞 is the ciphertext ring. Δ = ⌊ 𝑞𝑡 ⌋. 𝑅𝑡 is the plaintext ring, with 𝑞 > 𝑡. 𝖢𝖪𝖪𝖲: 𝑅𝑞 is the ciphertext ring. Given an arbitrary target error margin 𝜖 and 𝐵, we can set the scale Δ. Cryptographic Primitives BFV

Select 𝑝𝑝 ← (𝑡, 𝑛, 𝑞, 𝜎, 𝐵, Δ)

CKKS

Select 𝑝𝑝 ← (𝜖, 𝑛, 𝑞, 𝜎, 𝐵, Δ)

𝖤𝖺𝗌𝗁𝖾 .𝖲𝖾𝗍𝗎𝗉() = 𝑝𝑝

𝖤𝖺𝗌𝗁𝖾 .𝖲𝖾𝖼𝖪𝖾𝗒𝖦𝖾𝗇(1𝜆 ) = 𝗌𝗄

Given the security parameter 𝜆, sample 𝑠 ← 𝑅3 . Output 𝗌𝗄 = 𝑠

𝖤𝖺𝗌𝗁𝖾 .𝖤𝗇𝖼(𝗌𝗄, 𝑚) = 𝖼𝗍

Sample 𝑎 ← 𝑅𝑞 and 𝑒 ← 𝜒. 𝖼𝗍 = (𝑐0 , 𝑐1 ) = (−𝑎 ⋅ 𝗌𝗄 + 𝑒 + Δ𝑚, 𝑎)

𝖤𝖺𝗌𝗁𝖾 .𝖠𝖽𝖽(𝖼𝗍, 𝖼𝗍′ ) = 𝖼𝗍𝖺𝖽𝖽

Given 𝖼𝗍 = (𝑐0 , 𝑐1 ) and 𝖼𝗍′ = (𝑐0′ , 𝑐1′ ), 𝖼𝗍𝖺𝖽𝖽 = (𝑐0 + 𝑐0′ , 𝑐1 + 𝑐1′ ) BFV

𝑚 = [⌊ 𝑞𝑡 [𝑐0 + 𝑐1 ⋅ 𝗌𝗄]𝑞 ⌉]

CKKS

[𝑐0 +𝑐1 ⋅𝗌𝗄]𝑞 𝑚≈ Δ

𝖤𝖺𝗌𝗁𝖾 .𝖣𝖾𝖼(𝗌𝗄, 𝖼𝗍) = 𝑚

𝑡

Decryption remarks 𝖡𝖥𝖵: Decryption correctness now holds if 𝐵 < 2𝑡𝑞 − 2𝑡 .

𝖢𝖪𝖪𝖲: After decryption, we obtain 𝑚̃ = 𝑚+𝑒𝖼𝗍 ≈ 𝑚, where 𝑒𝖼𝗍 is the internal error of the ciphertext, with ||𝑒𝖼𝗍 || < 𝐵Δ .

and correctness during decryption. We address this challenge using two additional building blocks: (i) a practical implementation of the oracle 𝑖 (𝖼𝗍) discussed in Section 4, which is feasible with secret-key HE schemes; and (ii) an extension of the 𝖤𝖺𝗌𝗁𝖾 .𝖠𝖽𝖽 procedure (see Table 3) that, together with an 𝐿-party linear secret sharing scheme (Definitions 10 and 11), supports the homomorphic evaluation of linear aggregations 𝑓Σ (𝖤𝗇𝖼(𝗌𝗄1 , 𝑤1 ), … , 𝖤𝗇𝖼(𝗌𝗄𝐿 , 𝑤𝐿 )) over ciphertexts encrypted under distinct secret keys [52]. We first discuss the required property of secret-key HE schemes to extend 𝖤𝖺𝗌𝗁𝖾 .𝖠𝖽𝖽 under multiple secret keys. Next, we detail the general construction of our proposed multi-secret-key HE-based solution to the multiparty aggregation problem in FL (see Definition 5). Key homomorphisms with secret-key encryptions: We make explicit the uniformly random polynomial term 𝑎 in the encryption procedure of Table 3. A fresh encryption of 𝑚 under secret key 𝗌𝗄 is written as 𝖼𝗍 = 𝖤𝗇𝖼(𝑎, 𝗌𝗄, 𝑚) = (−𝑎 ⋅ 𝗌𝗄 + 𝑒 + Δ𝑚, 𝑎). This formulation reconnects with the collective public-key generation functionality 𝑓𝜋𝖯𝗎𝖻𝖪𝖾𝗒𝖦𝖾𝗇 (𝗌𝗄1 , … , 𝗌𝗄𝐿 ) in the 𝖤𝗆𝗁𝖾 scheme. Under the CRS model, clients rely on a preshared polynomial 𝑝1 ∈ 𝑅𝑞 to generate RLWE samples 𝖼𝗍𝑖 = (𝑝0,𝑖 , 𝑝1 ) with the same second component. In particular, by renaming 𝑝1 as 𝑎, these RLWE samples can be viewed as fresh secretkey encryptions of zero 𝖤𝗇𝖼(𝑎, 𝗌𝗄𝑖 , 0) for each client 𝐶𝑖 ∈ . To formalize aggregation across ciphertexts encrypted under distinct secret keys but sharing the same 𝑎, we introduce the following extended addition procedure: Definition 10 (Extended Addition Procedure). Let 𝖼𝗍 = (𝑏1 , 𝑎) and 𝖼𝗍′ = (𝑏2 , 𝑎) be two ciphertexts produced by 𝖤𝗇𝖼(𝑎, 𝗌𝗄𝑖 , 𝑚𝑖 ). The procedure 𝖤𝗑𝗍𝖠𝖽𝖽 is defined as follows:

Page 12 of 29

• If both ciphertexts are encrypted under the same secret key, then 𝖤𝗑𝗍𝖠𝖽𝖽(𝖼𝗍, 𝖼𝗍′ ) = 𝖠𝖽𝖽(𝖼𝗍, 𝖼𝗍′ ). • If the ciphertexts share the same polynomial component 𝑎 but are encrypted under distinct secret keys, then 𝖤𝗑𝗍𝖠𝖽𝖽(𝖼𝗍, 𝖼𝗍′ ) = 𝖼𝗍𝖺𝖽𝖽 = (𝑏1 + 𝑏2 , 𝑎), where 𝑏𝑖 = −𝑎 ⋅ 𝗌𝗄𝑖 + 𝑒𝑖 + Δ𝑚𝑖 (see Table 3). By linearity, the result is (−𝑎(𝗌𝗄1 + 𝗌𝗄2 ) + (𝑒1 + 𝑒2 ) + Δ(𝑚1 + 𝑚2 ), 𝑎), i.e., 𝖼𝗍𝖺𝖽𝖽 = 𝖤𝗇𝖼(𝑎, 𝗌𝗄1 + 𝗌𝗄2 , 𝑚1 + 𝑚2 ). More generally, ( aggregating 𝐿 ciphertexts with )the same 𝑎 yields 𝖤𝗇𝖼 𝑎, 𝑓Σ (𝗌𝗄1 , … , 𝗌𝗄𝐿 ), 𝑓Σ (𝑚1 , … , 𝑚𝐿 ) for any linear aggregation function 𝑓Σ defined by public coefficients 𝜆𝑖 . Thus, secret-key encryptions with a shared random component satisfy a key homomorphism: ciphertext aggregation induces aggregation of both messages and secret keys. One could then attempt to reuse the collective decryption procedure of 𝖤𝗆𝗁𝖾 . However, this would introduce a security flaw: the partial decryptions would reuse the input ciphertexts’ random component 𝑎, potentially enabling attacks that leak information about the underlying secret keys. The complete protocol is presented below, where this issue is addressed by preventing the unsafe reuse of shared polynomial components, in line with the approach introduced in [52]. Multiparty secret-key private aggregation: While the baseline MHE-based construction 𝖤𝗆𝗁𝖾 from Section 4.1 applies a generic 𝐿-party secret sharing scheme to an unknown ideal secret key, our approach uses a linear secret-sharing layer whose reconstruction coefficients 𝜆𝑖 are aligned with the aggregation function 𝑓Σ . In particular, we consider the following 𝐿-party secret sharing scheme: Definition 11 (Zero-Sharing Linear Secret Sharing Scheme). Let 𝖲 = (𝖲.𝖲𝗁𝖺𝗋𝖾, 𝖲.𝖢𝗈𝗆𝖻𝗂𝗇𝖾) be a linear secret sharing scheme (LSSS) over the ring 𝑅𝑞 . The algorithm 𝖲.𝖲𝗁𝖺𝗋𝖾

outputs 𝐿 shares 𝑟1 , … , 𝑟𝐿 ∈ 𝑅𝑞 , where 𝑟1 , … , 𝑟𝐿−1 are sampled uniformly at random and 𝑟𝐿 is computed such ∑ that 𝐿 𝑖=1 𝜆𝑖 𝑟𝑖 = 0, with 𝜆1 , … , 𝜆𝐿 ∈ ℤ𝑞 being public reconstruction coefficients. The reconstruction algorithm ∑ satisfies 𝖲.𝖢𝗈𝗆𝖻𝗂𝗇𝖾(𝑟1 , … , 𝑟𝐿 ) = 𝐿 𝑖=1 𝜆𝑖 𝑟𝑖 = 0. In particular, the reconstruction coefficients correspond to the linear aggregation function 𝑓Σ (𝑟1 , … , 𝑟𝐿 ) used in the FL protocol. We write 𝖲.𝖲𝗁𝖺𝗋𝖾𝑖 to denote the 𝑖-th share output by 𝖲.𝖲𝗁𝖺𝗋𝖾.

Table 4 Multiparty Secret-Key Private Aggregation Protocol. Public input: ideal aggregation functionality 𝑓Σ ⃗ 𝑖 for each 𝐶𝑖 ∈  Private input: 𝑤 Output for all clients in , and for the Aggregator if required: ⃗ ∗ = 𝑓 Σ (𝑤 ⃗ 1, … , 𝑤 ⃗ 𝐿 ) for BFV, and an the exact aggregate 𝑤 approximation for CKKS

We assume a secure realization of 𝖲 against static semi-honest adversaries; the concrete realization in Appendix E uses pairwise private authenticated channels between clients. Our protocol is summarized in Table 4 and relies on the following multi-secret-key HE construction:

Setup

All clients 𝐶𝑖 instantiate the Multiparty secret-key scheme 𝖤𝗆𝗌𝗁𝖾 (𝑟𝑖 , 𝗌𝗄𝑖 ) = 𝖤𝗆𝗌𝗁𝖾 .𝜋𝑖,𝖲𝖾𝖼𝖪𝖾𝗒𝖦𝖾𝗇 (𝜆, 𝜅)*

Input

⃗ 𝑖 and provides it to Each 𝐶𝑖 encrypts† its input 𝑤 the Aggregator + 𝑎 ← 𝑅𝑞 shared across all 𝐶𝑖 ⃗ 𝑖) 𝑐𝑤⃗ 𝑖 = 𝖤𝗆𝗌𝗁𝖾 .𝖤𝗇𝖼(𝑎, 𝗌𝗄𝑖 + 𝑟𝑖 , 𝑤

Definition 12 (Multiparty Additive Symmetric-Key HE). Let 𝖤𝖺𝗌𝗁𝖾 = (𝖤.𝖲𝖾𝗍𝗎𝗉, 𝖤.𝖲𝖾𝖼𝖪𝖾𝗒𝖦𝖾𝗇, 𝖤.𝖤𝗇𝖼, 𝖤.𝖣𝖾𝖼, 𝖤.𝖠𝖽𝖽) be the symmetric additive homomorphic encryption scheme from Definition 8, whose security is parameterized by 𝜆 (see Table 3 for concrete 𝖡𝖥𝖵 and 𝖢𝖪𝖪𝖲 instantiations), and let 𝖲 = (𝖲.𝖲𝗁𝖺𝗋𝖾, 𝖲.𝖢𝗈𝗆𝖻𝗂𝗇𝖾) be the Zero-Sharing LSSS from Definition 11. The associated multiparty symmetric homomorphic encryption scheme (𝖤𝗆𝗌𝗁𝖾 ) is defined as follows:

The Aggregator computes† the encrypted output for the ideal functionality 𝑓Σ relying on Evaluation 𝖤𝗆𝗌𝗁𝖾 .𝖤𝗑𝗍𝖠𝖽𝖽 𝑐𝑤⃗ ∗ = 𝑓Σ (𝑐𝑤⃗ 1 , 𝑐𝑤⃗ 2 , … , 𝑐𝑤⃗ 𝐿 )

(i) During setup, each client 𝐶𝑖 samples (𝑟𝑖 , 𝗌𝗄𝑖 ) where 𝑟𝑖 ← 𝖲.𝖲𝗁𝖺𝗋𝖾𝑖 and 𝗌𝗄𝑖 ← 𝖤𝖺𝗌𝗁𝖾 .𝖲𝖾𝖼𝖪𝖾𝗒𝖦𝖾𝗇(𝜆). The effective encryption key of 𝐶𝑖 is 𝗌𝗄𝑖 + 𝑟𝑖 . By Def. 11, the shares satisfy 𝖲.𝖢𝗈𝗆𝖻𝗂𝗇𝖾(𝑟1 , … , 𝑟𝐿 ) = 𝑓Σ (𝑟1 , … , 𝑟𝐿 ) = 0. Hence, by linearity, 𝖲.𝖢𝗈𝗆𝖻𝗂𝗇𝖾(𝗌𝗄1 +𝑟1 , … , 𝗌𝗄𝐿 +𝑟𝐿 ) = 𝑓Σ (𝗌𝗄1 , … , 𝗌𝗄𝐿 ), which corresponds to the aggregated (ideal) secret key. (ii) The homomorphic addition procedure 𝖠𝖽𝖽 is replaced by 𝖤𝗑𝗍𝖠𝖽𝖽 from Definition 10. (iii) The scheme is finally defined as 𝖤𝗆𝗌𝗁𝖾 = (𝖤𝖺𝗌𝗁𝖾 .𝖤𝗇𝖼, 𝖤𝖺𝗌𝗁𝖾 .𝖣𝖾𝖼, 𝖤𝗑𝗍𝖠𝖽𝖽, 𝖤𝖲𝖺𝗌𝗁𝖾 ), where 𝖤𝖲𝖺𝗌𝗁𝖾 = (𝜋𝖲𝖾𝖼𝖪𝖾𝗒𝖦𝖾𝗇 , 𝜋𝖤𝗇𝖼 , 𝜋𝖣𝖾𝖼 ) denotes a set of multiparty protocols run by the clients 𝐶𝑖 ∈  with the following private ideal functionalities: • Ideal secret-key generation: 𝑓𝑖,𝜋𝖲𝖾𝖼𝖪𝖾𝗒𝖦𝖾𝗇 (𝜆) ( ) = 𝖲.𝖲𝗁𝖺𝗋𝖾𝑖 , 𝖤𝖺𝗌𝗁𝖾 .𝖲𝖾𝖼𝖪𝖾𝗒𝖦𝖾𝗇(𝜆) = (𝑟𝑖 , 𝗌𝗄𝑖 ). • Correlated encryption: 𝑓𝑖,𝜋𝖤𝗇𝖼 ((𝑟𝑖 , 𝗌𝗄𝑖 ), 𝑚𝑖 ) = 𝖤𝖺𝗌𝗁𝖾 .𝖤𝗇𝖼(𝑎, 𝗌𝗄𝑖 + 𝑟𝑖 , 𝑚𝑖 ), where 𝑎 ∈ 𝑅𝑞 is sampled internally once per aggregation round (or once per ciphertext block when multiple blocks are needed to encode each client update) and used consistently across all clients 𝐶𝑖 ∈ . • Collective decryption: 𝑓𝜋𝖣𝖾𝖼 ((𝗌𝗄1 , 𝑟1 ), (𝗌𝗄2 , 𝑟2 ), … , (𝗌𝗄𝐿 , 𝑟𝐿 ), 𝖼𝗍) = 𝖤𝖺𝗌𝗁𝖾 .𝖣𝖾𝖼(𝖲.𝖢𝗈𝗆𝖻𝗂𝗇𝖾(𝗌𝗄1 + 𝑟1 , 𝗌𝗄2 + 𝑟2 , … , 𝗌𝗄𝐿 + 𝑟𝐿 ), 𝖼𝗍). Remark on ciphertext encoding: For simplicity of exposition, we describe the protocol in Table 4 as if each ⃗ 𝑖 were encrypted into a single ciphertext. client update 𝑤 ⃗ 𝑖 is partitioned into 𝑁𝖼𝗍𝗑 blocks and enWhen needed, 𝑤 𝑁𝖼𝗍𝗑 crypted blockwise by each client as {𝖼𝗍𝑖,𝑗 = (𝑏𝑖,𝑗 , 𝑎𝑗 )}𝑗=1 . Page 13 of 29

Output

The parties in  execute† the decryption protocol ⃗ ∗ = 𝖤𝗆𝗌𝗁𝖾 .𝜋𝖣𝖾𝖼 ((𝗌𝗄1 , 𝑟1 ), … , (𝗌𝗄𝐿 , 𝑟𝐿 ), 𝑐𝑤⃗ ∗ ) 𝑤

*

𝜅 parameterizes the additive homomorphic capacity of 𝖤𝖺𝗌𝗁𝖾 . Remember that, for readability, 𝑐𝑤⃗ 𝑖 and 𝑐𝑤⃗ ∗ denote the ⃗ 𝑖 is single-ciphertext case. In the general case, each input 𝑤 encoded into 𝑁𝖼𝗍𝗑 ciphertexts, each with a different 𝑎𝑗 , and all operations are performed blockwise. + The Aggregator is in charge of performing the aggregation.

†

Aggregation with 𝖤𝗑𝗍𝖠𝖽𝖽 and collective decryption are applied blockwise. Throughout this section, this blockwise interpretation is assumed where appropriate. Observe that when the same secret key is reused across rounds, the public components 𝑎𝑗 must be pairwise distinct across all ciphertexts encrypted under that key, including future aggregation rounds under the same setup. See Section 5.2.1 for CKKS- and BFV-based instantiations, and Section 5.3 and Appendix G for details on the protocol’s security guarantees.

5.2.1. Concrete Multiparty HE instantiation: In Section 4.2, we introduced an oracle 𝑖 (⋅) allowing client 𝐶𝑖 to obtain a share of the aggregated ciphertext noise. We now formalize this abstraction as a client-local programmable functionality. In our construction, the oracle can be indexed by the relevant ciphertext component (e.g., the 𝑎 component of 𝖼𝗍 in Table 3), instead of the full ciphertext. Definition 13 (Client-Local Programmable Oracle 𝑖 (⋅)). For each client 𝑖, we define an abstract stateful functionality 𝑖 ∶ 𝑅𝑞 → 𝑅𝑞 ∪ {⊥} with the following interfaces: • 𝖲𝖾𝗍𝗎𝗉: The functionality is initialized as an empty table. Formally, for all 𝑎 ∈ 𝑅𝑞 , we set 𝑖 (𝑎) = ⊥. It is local to client 𝑖 and not accessible to other parties. • 𝖶𝗋𝗂𝗍𝖾(𝑎, 𝑒): Upon input (𝑎, 𝑒) with 𝑎, 𝑒 ∈ 𝑅𝑞 , the client updates the internal state by setting 𝑖 (𝑎) ∶= 𝑒. Optionally, this assignment may be restricted to previously undefined entries, i.e., only if 𝑖 (𝑎) = ⊥.

• 𝖱𝖾𝖺𝖽(𝑎): Upon input 𝑎 ∈ 𝑅𝑞 , the functionality returns 𝑖 (𝑎), i.e., it outputs 𝑒 if 𝑖 (𝑎) = 𝑒, and ⊥ otherwise. Thus, 𝑖 behaves as a deterministic client-local lookup table whose entries are defined during the protocol execution. The oracle 𝑖 admits a natural realization within our scheme 𝖤𝗆𝗌𝗁𝖾 . By construction, each client 𝐶𝑖 already knows its local encryption noise 𝑒𝑖 , and hence its weighted contribution 𝜆𝑖 ⋅ 𝑒𝑖 to the aggregated ciphertext noise 𝑒, where 𝑒 = 𝑓Σ (𝑒1 , … , 𝑒𝐿 ). Consequently, 𝑖 can be implemented by locally programming the value associated with the relevant ciphertext component (e.g., 𝑎). We now describe how this mechanism is used in the protocols implementing the ideal functionalities from Definition 12: • 𝑓𝑖,𝜋𝖲𝖾𝖼𝖪𝖾𝗒𝖦𝖾𝗇 (𝜆): Each client 𝐶𝑖 independently runs 𝖤𝖺𝗌𝗁𝖾 .𝖲𝖾𝖼𝖪𝖾𝗒𝖦𝖾𝗇(1𝜆 ) = 𝗌𝗄𝑖 and samples 𝑟𝑖 ← 𝖲.𝖲𝗁𝖺𝗋𝖾𝑖 through an interaction with the other clients implementing 𝖲 (see Definition 11). Finally, 𝐶𝑖 ∈  invokes the 𝖲𝖾𝗍𝗎𝗉 interface of its local oracle 𝑖 (⋅). See Appendix E for an example implementation of 𝖲. • 𝑓𝑖,𝜋𝖤𝗇𝖼 ((𝑟𝑖 , 𝗌𝗄𝑖 ), 𝑚𝑖 ): All clients jointly sample a common random polynomial 𝑎 ← 𝑅𝑞 . Each client 𝐶𝑖 ∈  samples 𝑒𝑖 ← 𝜒 and sends 𝑏𝑖 = −𝑎 ⋅ (𝗌𝗄𝑖 + 𝑟𝑖 ) + 𝑒𝑖 + Δ𝑚𝑖 to the aggregator. Finally, each client invokes 𝖶𝗋𝗂𝗍𝖾(𝑎, 𝑒𝑖 ) to update its local oracle 𝑖 (⋅). • 𝑓𝜋𝖣𝖾𝖼 ((𝗌𝗄1 , 𝑟1 ), (𝗌𝗄2 , 𝑟2 ), … , (𝗌𝗄𝐿 , 𝑟𝐿 ), 𝖼𝗍): The collaborative decryption protocol proceeds in two phases. – Given a ciphertext 𝖼𝗍 = (𝑏, 𝑎) encrypted under the ideal secret key 𝗌𝗄 = 𝑓Σ (𝗌𝗄1 + 𝑟1 , … , 𝗌𝗄𝐿 + 𝑟𝐿 ), each client retrieves 𝑒𝑖 = 𝖱𝖾𝖺𝖽(𝑎), samples 𝑒̃𝑖 ← 𝜒, and computes its partial decryption share as ℎ𝑖 = 𝜆𝑖 𝑎 ⋅ 𝗌𝗄𝑖 − 𝜆𝑖 𝑒𝑖 + 𝑒̃𝑖 . – The decryption shares ℎ𝑖 are sent to a designated output party,8 which computes: ] [ ∑ 𝑑 = 𝑏+ ℎ𝑖 𝐶𝑖 ∈

𝑞

= 𝑓Σ (𝑏1 , … , 𝑏𝐿 ) +

∑( ) 𝜆𝑖 𝑎 ⋅ 𝗌𝗄𝑖 − 𝜆𝑖 𝑒𝑖 + 𝑒̃𝑖 𝐶𝑖 ∈

= − 𝑎 ⋅ 𝗌𝗄 + 𝑒 + Δ ⋅ 𝑚 + (𝑎 ⋅ 𝗌𝗄 − 𝑒 + 𝑒) ̃ = Δ⋅

𝑚 + 𝑒̃ . ⏟⏟⏟ ⏟⏟⏟ 𝑓Σ (𝑚1 ,…,𝑚𝐿 )

∑𝐿

𝑖=1 𝑒̃𝑖

The final step for decryption depends on whether BFV or CKKS is used as the underlying secret-key HE scheme: • For BFV, the obtained decryption is 𝑚 = [⌊ 𝑞𝑡 𝑑⌉] . 𝑡

• For CKKS, the obtained decryption is 𝑚̃ = Δ𝑑 = 𝑚 + 𝑒̃ ≈ 𝑚 for large enough Δ. Therefore, if ‖𝑒̃𝑖 ‖ ≤ 𝐵 for Δ every client, then ‖𝑚̃ − 𝑚‖ ≤ 𝐿𝐵∕Δ (see Section 6).

8 Any client may act as the designated output party; the aggregator may do so only when it is also a receiver in that execution.

Page 14 of 29

Further practical considerations: Our protocol presents several advantages over the baseline MHE-based protocol from Section 4. Since the second ciphertext component is shared across clients and remains unchanged under 𝖤𝗑𝗍𝖠𝖽𝖽, only one ciphertext component must be transmitted in each direction: clients send a component of their encrypted inputs and the aggregator returns a component of the aggregated ciphertext. As a result, the computational cost of aggregation is reduced by at least a factor of two. These estimates do not account for the overhead of public-key encryption compared to secret-key encryption, such as extra polynomial operations and larger ciphertext noise. Moreover, the setup phase does not require 𝖼𝗉𝗄, but only a lightweight execution of the secret-sharing scheme 𝖲 once during setup (see Appendix E). Our construction also removes the dependence of ciphertext size on 𝜆. This can further reduce the size of exchanged encrypted data, with concrete gains depending on the target precision, as quantified in Section 6. This contrasts with other secret-key approaches such as [52], where additional redundancy is required to compensate for the unknown noise in the aggregated ciphertext during decryption. The oracle 𝑖 (⋅) from Definition 13 avoids this overhead by allowing exact removal of the ciphertext noise, assuming that clients can trace the encryption errors associated with their inputs during a single aggregation round. Finally, the protocol enables precomputation. The shared polynomial 𝑎 can be generated during setup, and partial decryptions can be precomputed since, unlike in MHE-based schemes, they do not depend on the aggregated result. Using a 𝖯𝖱𝖥 to derive the 𝑎 values per round (see Section 5.1) further reduces interaction, requiring only agreement on a random seed 𝜅 and an update rule for 𝑇 . Lower bounds for the modulus 𝑞 and a quantitative comparison with the MHEbased protocol are provided in Section 6.

5.3. Simulation-based security of our protocol We now state the main security result for our aggregation protocol. Recall that Definition 5 formalizes the secure multiparty aggregation problem in federated learning, where a set of clients  = {𝐶1 , … , 𝐶𝐿 } holds private model ⃗ 𝑖 and jointly computes 𝑤 ⃗ ∗ = 𝑓Σ (𝑤 ⃗ 1, … , 𝑤 ⃗ 𝐿 ), updates 𝑤 or a randomized approximation of this aggregate, with the assistance of an aggregator. The ideal aggregation function ∑ ⃗ 𝑖 with 𝑓Σ corresponds to a linear combination 𝐿 𝑖=1 𝜆𝑖 𝑤 public coefficients 𝜆𝑖 ∈ ℤ𝑞 . We assume gcd(𝑞, 𝜆𝑖 ) = 1 for all 𝑖, ensuring that the coefficients admit multiplicative inverses in ℤ𝑞 and avoiding non-invertible reconstruction coefficients in the homomorphic aggregation procedure. Our goal is to ensure input privacy: an adversary should learn nothing about the inputs of honest clients beyond what can be inferred from corrupted inputs and the final aggregated output. We consider a static semi-honest adversary that may corrupt the aggregator and up to 𝐿 − 1 clients. If exactly one client remains honest, the adversary inevitably learns that client’s contribution from the aggregate; this leakage is inherent to the functionality and falls outside the scope of secure computation. In practical FL deployments,

protecting the aggregated model against inference attacks typically requires complementary mechanisms. Differential Privacy can be incorporated into the aggregation by injecting noise locally at the client side before encryption [60, 55]. In particular, approximate HE schemes such as CKKS introduce numerical noise in the decrypted result, which may provide output perturbation and potentially be leveraged to obtain formal differential privacy guarantees [49]. Our proof follows the approach of the threshold fully homomorphic encryption construction for secure multiparty computation from [5], specialized to our aggregation functionality and simplified to the semi-honest setting. The argument relies on the homomorphic properties of RLWEbased encryption and its key-homomorphic structure, together with the smudging technique introduced in that work to prevent information leakage from partial decryptions. A key difference in our construction is the introduction of the client-local oracle 𝑖 (⋅) from Definition 13. This functionality allows each client to locally recover the noise component associated with its ciphertext contribution during collaborative decryption. Consequently, the protocol can deterministically cancel the ciphertext noise without relying on large smudging distributions, simplifying the noise analysis while preserving the indistinguishability guarantees required by the simulation-based proof. We remark that, throughout the ⃗ ∗ = 𝑓Σ (𝑤 ⃗ 1, … , 𝑤 ⃗ 𝐿 ) denotes the exact security argument, 𝑤 aggregate, which is the value made available to the simulator in the ideal execution. The BFV and CKKS instantiations ⃗ ∗ under differ only in output correctness: BFV returns 𝑤 its correctness condition, whereas CKKS returns a bounded ⃗ ∗. randomized approximation of 𝑤 Theorem 1 (Security of the aggregation protocol). Assume the RLWE assumption holds for the parameters of the underlying single-key HE schemes. Then the protocol from Definition 12, instantiated with either the exact or approximate HE schemes described in Section 5.2.1, provides simulationbased input privacy for the aggregation functionality 𝑓Σ from Definition 5 in the presence of a static semi-honest adversary that may corrupt the aggregator and a subset of at most 𝐿 − 1 clients. The BFV-based instantiation realizes 𝑓Σ exactly under its correctness condition, whereas the CKKSbased instantiation provides a randomized approximation of 𝑓Σ with bounded error. Proof overview: The proof follows a standard simulationbased argument. We construct a simulator that interacts with the adversary in the ideal world using only the inputs of corrupted parties and the output of the ideal aggregation functionality, and produces messages computationally indistinguishable from those of a real execution. By semantic security of the underlying RLWE encryption, ciphertexts of honest clients can be replaced by encryptions of zero without being detected by the adversary. During collaborative decryption, the simulator programs the partial decryption share of one honest client so that the reconstructed plaintext matches the output of the ideal functionality for BFV, while for CKKS it yields a bounded Page 15 of 29

randomized approximation of that ideal output. In this step, the client-local oracle 𝑖 (⋅) plays a key role: since each client records the encryption noise, the protocol can explicitly cancel the aggregated ciphertext noise during decryption. This avoids the need for large smudging noise distributions while preserving indistinguishability of the decryption shares. A full proof, including the sequence of hybrid arguments and the parameter constraints, is given in Appendix G.

6. Performance evaluation In the previous sections, we presented two approaches for extending single-key HE to the multiparty aggregation problem in FL of Def. 5, under strong semi-honest adversaries that may control the aggregator and a majority of clients. The first is the MHE-based baseline of Section 4, where clients encrypt under a collective public key and jointly decrypt the aggregate. The second is the proposed construction of Section 5, which avoids the collective public key by letting each client encrypt under its own secret key. This section compares the two approaches and evaluates the practical improvement obtained by the proposed construction. Subsections 6.1 and 6.2 recall the correctness conditions and instantiate the effective noise bounds used to select the ciphertext modulus 𝑞. These bounds are then used in Subsection 6.3 to quantify the reduction in ciphertext expansion. Finally, Subsections 6.4 and 6.5 compare BFV/CKKS instantiations and report implementation runtimes. Throughout Sections 6.2–6.5, we consider the unweighted sum, i.e., 𝜆𝑖 = 1 for all 𝑖, with averaging performed after decryption. This is the most favorable setting for the MHEbased protocol, since evaluating 𝑓Σ requires only ciphertext additions. For nontrivial coefficients 𝜆𝑖 , each ciphertext component would require a scalar multiplication; as MHE ciphertexts contain twice as many polynomial components as ours, this would further increase their relative cost.

6.1. Correctness bounds and modulus choice We first recall how the decryption correctness conditions from Tables 1 and 3 determine the minimum admissible ciphertext modulus 𝑞 for the aggregation protocols of Sections 4 and 5. In particular, we use the multiparty derivations given in Proposition 1 of Appendix A. 𝖬𝖯 denote an upper bound on the infinity norm of Let 𝐵𝖼𝗍 the effective noise tolerated at the end of the aggregation protocol. This notation is generic: depending on the protocol, it is instantiated either with the MHE-based bound or with the smaller bound of the proposed protocol (see Subsection 6.2). With this convention, the BFV-based and CKKSbased correctness conditions can be written as follows. For BFV-based constructions, the correctness condition 𝑞 − 2𝑡 , where 𝑡 is the plaintext has the form 𝐵𝖡𝖥𝖵 < 𝖡𝖥𝖵 2𝑡 modulus. Equivalently, it is sufficient to choose 𝑞𝖡𝖥𝖵 > 2𝑡𝐵𝖡𝖥𝖵 + 𝑡2 .

(3)

For CKKS-based constructions, assume that the aggregated plaintext 𝑚 = 𝑓Σ (𝑚1 , … , 𝑚𝐿 ) satisfies ‖𝑚‖ < 𝐵𝑚 ,

where 𝑚𝑖 denotes the input plaintext of client 𝑖. The correct𝑞 , where Δ𝖢𝖪𝖪𝖲 ness condition is Δ𝖢𝖪𝖪𝖲 𝐵𝑚 + 𝐵𝖢𝖪𝖪𝖲 < 𝖢𝖪𝖪𝖲 2 is the CKKS scaling factor. Writing the approximation error as 𝜖 = 𝐵𝖢𝖪𝖪𝖲 ∕Δ𝖢𝖪𝖪𝖲 (see Section 3.1), it suffices to choose ( ) 𝑞𝖢𝖪𝖪𝖲 > 2𝐵𝖢𝖪𝖪𝖲 𝜖 −1 𝐵𝑚 + 1 . (4) When inputs are normalized so that 𝐵𝑚 ≤ 1, the parameter 𝜖 −1 can be directly interpreted as the target precision of the approximate aggregation. For a fixed precision target, both BFV and CKKS therefore require a modulus essentially linear in the corresponding decryption noise bound. More precisely, in the parameter regimes where the precision term dominates the additive constants, we can write 𝑞 ≃ 𝐶 ⋅ 𝐵𝖼𝗍 ,

(5) 2𝜖 −1 for CKKS, after

with 𝐶 ≃ 2𝑡 for BFV and 𝐶 ≃ absorbing 𝐵𝑚 into the CKKS precision parameter. We keep the exact expressions (3) and (4) for the BFV/CKKS comparison in Subsection 6.4. The simplified form (5) is used in Subsection 6.3 and Appendix B to compare the asymptotic ciphertext expansion of the proposed protocol and the MHE-based baseline.

6.2. Effective noise bounds for HE-based protocols 𝖬𝖯 for the two protocols. In both We now instantiate 𝐵𝖼𝗍 cases, ‖𝑒𝖼𝗍 ‖ < 𝐵𝖼𝗍 denotes an upper bound on the infinity norm of the ciphertext noise before final decryption. MHE-based protocol: For a fresh single-key ciphertext, Lemma 1 in Appendix A gives the bound ‖𝑒𝖼𝗍 ‖ < (2𝑛+ 1)𝐵, where ‖𝑒‖ ≤ 𝐵 for any 𝑒 ← 𝜒 (see Table 1). In the MHE setting of Section 4, three additional effects must be accounted for. First, the collective public key is generated from 𝐿 secret-key shares, leading to a fresh-ciphertext noise bound of 𝐵(2𝑛𝐿 + 1). Second, the homomorphic evaluation of 𝑓Σ adds 𝐿 ciphertexts, multiplying this term by 𝐿. Third, each client adds a smudging noise with ‖𝑒𝗌𝗆𝗀,𝑖 ‖ ≤ 𝐵𝗌𝗆𝗀 during collective decryption. Therefore, the effective decryption noise in the MHEbased protocol is upper-bounded by ( ) 𝖬𝖯 𝐵𝖼𝗍 = 𝐵𝗆𝗁𝖾 = 𝐵𝖼𝗍 + 𝐿𝐵𝗌𝗆𝗀 = 1 + 𝐿2𝜆∕2 𝐵𝖼𝗍 , (6)

where 𝐵𝖼𝗍 = 𝐿𝐵(2𝑛𝐿 + 1) and, as described in Section 4, 𝐵𝗌𝗆𝗀 = 2𝜆∕2 𝐵𝖼𝗍 . Since 𝑞 = (𝐵𝗆𝗁𝖾 ) for both BFV and CKKS, the high-variance smudging term increases the required modulus and, consequently, the communication and computational cost. Proposed protocol: For the protocol from Section 5, Lemma 2 gives a fresh single-secret-key ciphertext noise bound 𝐵𝖼𝗍 = 𝐵. Homomorphic evaluation of 𝑓Σ adds 𝐿 ciphertexts, so the noise grows by a factor 𝐿. During collaborative decryption, each client cancels the noise introduced in its own input ciphertext and replaces it with fresh noise from the same distribution. Thus, no smudging noise depending on the statistical security parameter 𝜆 is required. The corresponding effective decryption noise is therefore bounded by 𝖬𝖯 𝐵𝖼𝗍 = 𝐵𝗉𝗋𝗈𝗉 = 𝐿𝐵.

Page 16 of 29

(7)

Table 5 Approximate ciphertext expansion of the MHE-based construction with respect to the proposed construction. Precision regime

log2 𝐶

Approx. 𝑅(𝐶)

Low

5

≈ 13–16

Low/moderate

10

≈ 10–12

Moderate

20

≈8

Intermediate

32–64

≈ 4.3–6.3

Very high

128

≈ 3.3

Representative parameters 𝑛 = 212 , 𝐿 ∈ [5, 100], 𝐵 = 19.2, 𝜆 = 128 𝑛 = 212 , 𝐿 ∈ [5, 100], 𝐵 = 19.2, 𝜆 = 128 𝑛 = 213 , 𝐿 ∈ [5, 100], 𝐵 = 19.2, 𝜆 = 128 𝑛 = 213 , 𝐿 ∈ [5, 100], 𝐵 = 19.2, 𝜆 = 128 𝑛 = 214 , 𝐿 ∈ [5, 100], 𝐵 = 19.2, 𝜆 = 128

This is the main quantitative advantage of the proposed protocol: it removes the high-variance smudging term and the extra noise introduced by the collective public key.

6.3. Ciphertext expansion comparison We compare the ciphertext expansion induced by the MHE-based and proposed protocols. For a fixed HE family, either BFV or CKKS, let 𝑞𝗆𝗁𝖾 and 𝑞𝗉𝗋𝗈𝗉 denote the ciphertext moduli required by the two constructions, respectively. Ciphertext sizes are measured in bits, and both protocols are assumed to encrypt model updates of the same length. From (6) (and (7), the)effective decryption-noise bounds are 𝐵𝗆𝗁𝖾 = 1 + 𝐿2𝜆∕2 𝐿𝐵(2𝑛𝐿 + 1) and 𝐵𝗉𝗋𝗈𝗉 = 𝐿𝐵. Using the approximation in (5), log2 𝑞 ≃ log2 𝐵𝖼𝗍 + log2 𝐶, where 𝐶 depends on the selected HE family and precision target. For a model update of length 𝑀, both protocols require ⌈𝑀∕𝑛⌉ encrypted blocks when using the same ring degree 𝑛. The resulting ciphertext-size ratio between the MHE-based and proposed protocols can be approximated as

𝑅(𝐶) = 2

log2 𝐵𝗆𝗁𝖾 + log2 𝐶 . log2 𝐵𝗉𝗋𝗈𝗉 + log2 𝐶

(8)

Here, the factor 2 captures the reduction from two polynomial components to one, while the remaining factor captures the reduction in modulus size. Since 𝐵𝗆𝗁𝖾 > 𝐵𝗉𝗋𝗈𝗉 , the ratio is largest when decryption noise dominates the moduli and approaches the structural factor 2 as log2 𝐶 dominates. Table 5 summarizes the behavior of (8) in representative precision regimes, using parameters satisfying at least 128 bits of security following [10]. The reported values are obtained directly from this expression and rounded over 𝐿 ∈ [5, 100]. Across these regimes, the dominant trend is driven by log2 𝐶, while the dependence on 𝐿 is mild; Appendix B provides a detailed derivation, simplifications, and regimewise approximations. At low-to-moderate precision, the gain mainly comes from removing the smudging factor 2𝜆∕2 and the collective-public-key noise term (2𝑛𝐿+1). At intermediate precision, log2 𝐶 affects the proposed protocol, but 𝑞𝗆𝗁𝖾 remains dominated by its larger decryption noise. In the very high precision limit, log2 𝐶 dominates both constructions and the relative gain tends to the structural factor 2.

6.4. BFV versus CKKS for private aggregation The previous subsections compared the MHE-based and proposed protocols independently of the underlying HE family. We now compare BFV- and CKKS-based instantiations of both approaches. In [16], the authors argue that threshold variants of CKKS become less practical under the 𝖨𝖭𝖣-𝖢𝖯𝖠𝖣 model because the high-variance smudging noise required for security may compromise the precision of the decrypted result. However, in [43] we showed that this conclusion does not hold for all parameter regimes: CKKS-based private aggregation can be comparable to, and sometimes more compact than, BFV-based aggregation for practical precision targets. We extend that comparison here by considering our proposed protocol, where the variance of the noise used at decryption does not depend on 𝜆. The comparison relies on the correctness expressions from Subsection 6.1, which determine the ciphertext modulus required by each instantiation. Consider a fixed aggrega𝖬𝖯 be tion protocol, either MHE-based or proposed, and let 𝐵𝖼𝗍 the corresponding final effective noise bound, instantiated as 𝖬𝖯 = 𝐵 𝖬𝖯 𝐵𝖼𝗍 𝗆𝗁𝖾 for the MHE-based protocol and 𝐵𝖼𝗍 = 𝐵𝗉𝗋𝗈𝗉 for the proposed protocol. Combining Eqs. (3) and (4), CKKS requires a smaller ciphertext modulus than BFV whenever 𝖬𝖯 > 𝐵𝖼𝗍

2Δ𝖢𝖪𝖪𝖲 𝐵𝑚 − 𝑡2 . 2(𝑡 − 1)

(9)

Equivalently, if the aggregated plaintext is normalized so that 𝐵𝑚 < 1 and the CKKS scale is expressed through 𝜖 = 𝐵𝖢𝖪𝖪𝖲 ∕Δ𝖢𝖪𝖪𝖲 , the condition becomes 𝑡2 + 𝑡 − 1 > 𝜖 −1 . 𝖬𝖯 2𝐵𝖼𝗍

(10)

We refer to Proposition 1 in Appendix A for the derivation. Equation (10) provides a direct criterion for identifying the CKKS-favorable region. For small and medium values of 𝑡, the linear term 𝑡 − 1 is the main contribution, and BFV and CKKS behave similarly when compared at the same bit precision. For larger values of 𝑡, the quadratic 𝖬𝖯 ) becomes relevant, and CKKS may require a term 𝑡2 ∕(2𝐵𝖼𝗍 smaller modulus than BFV for the same target precision. The position of this transition depends on the final effective noise bound. Since 𝐵𝗉𝗋𝗈𝗉 ≪ 𝐵𝗆𝗁𝖾 , the transition occurs earlier in the proposed protocol than in the MHE-based construction. Figure 4 illustrates this effect by showing the CKKSfavorable regions of both protocols. We set 𝑛 = 8192 and 𝐵 = 19.2, and vary 𝐿 and 𝜆. The axes represent the bit precisions log2 𝑡 for BFV and log2 𝜖 −1 for CKKS. A point (log2 𝑡, log2 𝜖 −1 ) is shaded when CKKS requires a smaller ciphertext modulus than BFV. Let 𝖱𝗆𝗁𝖾 denote the CKKS-favorable region for the MHE-based protocol, and 𝖱𝗉𝗋𝗈𝗉 the corresponding region for the proposed protocol. Since the proposed protocol has a smaller final effective noise bound, 𝖱𝗆𝗁𝖾 ⊂ 𝖱𝗉𝗋𝗈𝗉 . As 𝐿 and 𝜆 grow, the gap between both regions increases. This follows from the asymptotic behavior 𝐵𝗆𝗁𝖾 = (𝐿3 2𝜆∕2 ) and 𝐵𝗉𝗋𝗈𝗉 = (𝐿). Therefore, the MHE-based protocol is Page 17 of 29

(a) 𝐿 = 8, 𝜆 = 32.

(b) 𝐿 = 𝜆 = 128.

Figure 4: CKKS-favorable regions for the MHE-based protocol and for the proposed protocol.

affected by both the number of clients and the high-variance smudging term, whereas the proposed protocol only exhibits linear dependence on 𝐿 and avoids dependence on 𝜆. As already discussed in Subsection 6.3, the proposed protocol reduces the ciphertext size for both BFV and CKKS. The comparison in this subsection provides an additional conclusion: it also shifts the BFV/CKKS transition point to lower precision values, enlarging the practical parameter region in which CKKS is preferable to BFV. Additional parameter-region plots, heat maps quantifying the modulus gap between BFV and CKKS, and a discussion of approximate aggregation are provided in Appendix C.

6.5. Implementation runtimes We implemented the two main protocols in Go using Lattigo [44]. The MHE-based protocols [45] use Lattigo’s multiparty package, whereas our proposed protocol builds on the low-level ring package and on the implementation of [52].9 We extended the latter to support BFV-based and CKKSbased variants, and removed the rounding and rescaling steps required in [43]; this is necessary to achieve the smaller ciphertext expansion predicted by the analysis above. All experiments were run single-threaded on a system with 2× Intel Xeon Gold 6342 CPUs at 2.80 GHz and 1 TB of RAM. Implementation code is available at https://github. com/miguelmorona/MSKHE-priavgagg. We evaluate four aggregation families: the BFV-based and CKKS-based variants of both the MHE construction and our proposed construction. Precision is measured as log2 𝑡 for BFV and as log2 𝜖 −1 for CKKS. Each parameter set of the proposed protocol was evaluated over 50 independent runs, whereas each MHE parameter set was evaluated over 25 independent runs. The reported runtimes are the corresponding averages. We report the offline setup separately, since it is executed only once. The total runtime includes the encryption and collaborative-decryption costs of one client, together with the homomorphic aggregation cost. Unless otherwise stated, we set 𝐿 = 32 as a representative number of clients for the cross-silo setting considered here. All online runtimes correspond to synthetic model updates with 16,384,000 randomly generated parameters per client. More generally, for a model update with 𝑀 parameters, runtimes scale approximately linearly with the number of ciphertexts, ⌈𝑀∕𝑛⌉. Thus, if 𝖱𝗎𝗇𝗍𝗂𝗆𝖾(𝑛) denotes the runtime for one ciphertext 9 Code [52] is available at https://github.com/apedrouzoulloa/mkagg.

Table 6 Example parameter sets for the proposed private aggregation protocol (𝜎 = 3.2 and 128 bits of security).

Table 8 Example parameter sets for the MHE-based and for the proposed protocols (𝜎 = 3.2, 𝜆 = 128, and 128 bits of security).

Param.

Set 1 𝖡𝖥𝖵

Set 2 𝖢𝖪𝖪𝖲

Set 3 𝖡𝖥𝖵

Set 4 𝖢𝖪𝖪𝖲

Param.

Set 1 Prop.

Set 2 Prop.

Set 3 MHE

Set 4 MHE

{𝑛, 𝐿} {𝑡, 𝜖 −1 , Δ} [bits] {#Limbs, 𝑞} [bits]

{2048, 32} {21, −, 21} {2, 42}

{2048, 32} {−, 30, 40} {2, 42}

{4096, 32} {46, −, 46} {2, 92}

{4096, 32} {−, 80, 90} {2, 92}

{𝑛, 𝐿} {𝑡, 𝜖 −1 , Δ} [bits] {#Limbs, 𝑞} [bits]

{2048, 32} {21, −, 21} {2, 42}

{2048, 32} {−, 30, 40} {2, 42}

{8192, 32} {20, −, 100} {2, 120}

{8192, 32} {−, 20, 118} {2, 120}

Table 7 Implementation runtimes for the proposed private aggregation protocol. The total runtime excludes the offline setup.

Table 9 Implementation runtimes for the proposed and MHE-based protocols. The total runtime excludes the offline setup.

Protocol step

Par. set 1

Par. set 2

Par. set 3

Par. set 4

Protocol step

Par. set 1

Par. set 2

Par. set 3

Par. set 4

Setup (𝖢𝗅𝗂𝖾𝗇𝗍) Encryption (𝖢𝗅𝗂𝖾𝗇𝗍) Aggregation (𝖠𝗀𝗀) Coll. dec. (𝖢𝗅𝗂𝖾𝗇𝗍)

14.12 ms 2.56 s 1.42 s 2.13 s

14.84 ms 2.53 s 1.43 s 2.34 s

36.04 ms 2.53 s 1.37 s 2.06 s

41.03 ms 2.47 s 1.38 s 13.15 s

Setup (𝖢𝗅𝗂𝖾𝗇𝗍) Encryption (𝖢𝗅𝗂𝖾𝗇𝗍) Aggregation (𝖠𝗀𝗀) Coll. dec. (𝖢𝗅𝗂𝖾𝗇𝗍)

14.12 ms 2.56 s 1.42 s 2.13 s

14.84 ms 2.53 s 1.43 s 2.34 s

2.20 ms 6.45 s 2.44 s 28.76 s

1.75 ms 12.61 s 3.13 s 37.29 s

Total runtime

6.12 s

6.35 s

5.97 s

16.97 s

Total runtime

6.12 s

6.35 s

37.65 s

53.03 s

with ⌈ ⌉ring degree 𝑛, the runtime for size 𝑀 is approximately 𝑀 𝖱𝗎𝗇𝗍𝗂𝗆𝖾(𝑛). For a fixed ring degree, this scaling factor 𝑛 is architecture-independent and depends only on the number of aggregated parameters. This scaling applies to both the proposed and MHE-based protocols. The number of clients 𝐿 affects the protocol phases differently. For fixed cryptographic and model parameters, aggregation and the combination of partial decryption shares scale approximately linearly with 𝐿, whereas client-local encryption and the computation of each partial decryption share do not directly depend on 𝐿. Additional dependence arises indirectly through parameter selection and explicitly in the setup phase. Further details are provided in Appendix F. Runtime of the proposed protocol: We first report runtimes for the proposed protocol under different precision targets. Table 6 lists four parameter sets, with the corresponding runtimes in Table 7. The BFV-based variant is slightly faster than the CKKS-based one for comparable modulus sizes. This difference is mainly due to implementation-level details in decryption. Although CKKS avoids the rounding and reduction modulo 𝑡 required by BFV, our CKKS implementation must reconstruct each decrypted value modulo 𝑞, represented over several limbs, before converting it into a floating-point value. When 𝑞 fits within a machine word, this reconstruction can be performed efficiently using native integer arithmetic. However, the overhead becomes significantly more pronounced when 𝑞 exceeds the machine-word size, as in parameter set 4, since the reconstruction then requires multiprecision integer arithmetic. In contrast, the optimized BFV rounding available in Lattigo’s ring package first reduces the number of limbs through a resize operation before recovering the plaintext, so that reconstruction only needs to operate over the modulus required to represent the plaintext. The magnitude of this effect should therefore be interpreted as implementation- and parameter-dependent.

Page 18 of 29

Comparison with the MHE-based protocol: We next compare the proposed protocol with the MHE-based construction following the blueprint of [45]. Table 8 lists two parameter sets for each approach, and Table 9 reports their corresponding runtimes. The higher runtimes of the MHEbased protocols are consistent with the larger modulus and ring degree required to accommodate the high-variance smudging countermeasure. This overhead is already visible during aggregation, whose cost also depends on the number of polynomial components in each ciphertext, and becomes more pronounced during collaborative decryption because of the cost of sampling and adding the large-variance smudging noise. The overhead is particularly significant for the CKKS-based MHE variant: preserving the target precision in the presence of such noise requires encoding the original floating-point plaintexts with a scale Δ whose bit length exceeds that of a single limb, thereby introducing additional encoding overhead. This additional cost does not arise in the BFV-based MHE variant implemented in Lattigo, where plaintext encoding can be performed efficiently using modular arithmetic. In contrast, our proposed construction benefits from a smaller modulus, singlecomponent ciphertexts, and smudging noise whose variance is independent of 𝜆. For the proposed protocol, we do not include optimizations based on precomputing encryption and partial-decryption material. Such optimizations would reduce its absolute online runtimes but would not affect the comparison in terms of ciphertext size or required modulus. Regarding setup, although the MHE-based construction is faster, the additional cost of the proposed protocol remains small in practice. Table 10 shows that its client-side setup remains below one second for all evaluated parameter sets even for 𝐿 = 512. Thus, even if repeated in every aggregation round, it would not become a dominant component of the per-round runtime for the evaluated model size. Further details on its scaling with 𝐿 are provided in Appendix F. Discussion of the performance results: Overall, the proposed protocol reduces the communication overhead

of MHE-based aggregation by removing the smudging term from the decryption noise bound and by transmitting a single polynomial component per encrypted update. The BFV/CKKS comparison remains parameter-dependent: BFV is preferable for exact or low-precision arithmetic, whereas CKKS becomes preferable as precision grows.

7. Conclusions and future work This work revisited RLWE-based Homomorphic Encryption for private average aggregation in Federated Learning, paying particular attention to the cross-silo setting and the security implications of granting access to aggregated decryptions. We analyzed single-key and multiparty HE approaches, highlighting the limitations imposed by restricted decryption access and the need, in conventional MHE constructions, for large-variance smudging noise. To overcome this limitation, we proposed a lightweight multi-secret-key HE protocol tailored to average aggregation. Unlike MHE, our construction does not require a collective public key and lets each client encrypt under its own secret key. By compensating the ciphertext noise during decryption, the protocol avoids 𝜆-dependent smudging noise while preserving security in the semi-honest model. We instantiated the approach with BFV and CKKS, showing that the proposed construction reduces communication overhead and improves runtimes over MHE-based alternatives. Future work includes extending our construction scope, studying stronger adversarial models, and assessing integration into complete FL training pipelines, including its combination with Differential Privacy and output privacy.

References [1] Albrecht, M.R., Chase, M., Chen, H., Ding, J., Goldwasser, S., Gorbunov, S., Halevi, S., Hoffstein, J., Laine, K., Lauter, K.E., Lokam, S., Micciancio, D., Moody, D., Morrison, T., Sahai, A., Vaikuntanathan, V., 2019. Homomorphic encryption standard. IACR Cryptol. ePrint Arch. , 939. [2] Alexandru, A., Badawi, A.A., Micciancio, D., Polyakov, Y., 2024. Application-aware approximate homomorphic encryption: Configuring FHE for practical use. IACR Cryptol. ePrint Arch. , 203. [3] Aloufi, A., Hu, P., Song, Y., Lauter, K.E., 2022. Computing blindfolded on data homomorphically encrypted under multiple keys: A survey. ACM Comput. Surv. 54, 195:1–195:37. [4] Archer, D.W., de Balle Pigem, B., Bogdanov, D., Craddock, M., Gascón, A., Jansen, R., Jug, M., Laine, K., McLellan, R., Ohrimenko, O., Raykova, M., Trask, A., Wardley, S., 2023. UN handbook on privacy-preserving computation techniques. CoRR abs/2301.06167. [5] Asharov, G., Jain, A., López-Alt, A., Tromer, E., Vaikuntanathan, V., Wichs, D., 2012. Multiparty computation with low communication, computation and interaction via threshold fhe, in: EUROCRYPT, Springer. pp. 483–501. [6] Bendoukha, A., Sirdey, R., Boudguiga, A., Kaaniche, N., 2025. Unveiling the (in)security of threshold fhe-based federated learning: The practical impact of recent CPAD attacks, in: CSF, IEEE. pp. 425–440. [7] Benhamouda, F., Joye, M., Libert, B., 2016. A new framework for privacy-preserving aggregation of time-series data. ACM Trans. Inf. Syst. Secur. 18, 10:1–10:21. [8] Blanchard, P., El Mhamdi, E.M., Guerraoui, R., Stainer, J., 2017. Machine learning with adversaries: Byzantine tolerant gradient descent. NIPS 30.

Page 19 of 29

[9] Bonawitz, K.A., Ivanov, V., Kreuter, B., Marcedone, A., McMahan, H.B., Patel, S., Ramage, D., Segal, A., Seth, K., 2017. Practical secure aggregation for privacy-preserving machine learning, in: CCS, ACM. pp. 1175–1191. [10] Bossuat, J., Cammarota, R., Chillotti, I., Curtis, B.R., Dai, W., Gong, H., Hales, E., Kim, D., Kumara, B., Lee, C., Lu, X., Maple, C., Pedrouzo-Ulloa, A., Player, R., Polyakov, Y., Lopez, L.A.R., Song, Y., Yhee, D., 2024. Security guidelines for implementing homomorphic encryption. IACR Commun. Cryptol. 1, 26. [11] Brakerski, Z., 2012. Fully homomorphic encryption without modulus switching from classical gapsvp, in: CRYPTO, Springer. pp. 868–886. [12] Brakerski, Z., Gentry, C., Vaikuntanathan, V., 2014. (leveled) fully homomorphic encryption without bootstrapping. ACM Trans. Comput. Theory 6, 13:1–13:36. [13] Castelluccia, C., Mykletun, E., Tsudik, G., 2005. Efficient aggregation of encrypted data in wireless sensor networks, in: MOBIQUITOUS, IEEE. pp. 109–117. [14] de Castro, L., Juvekar, C., Vaikuntanathan, V., 2021. Fast vector oblivious linear evaluation from ring learning with errors, in: WAHC@CCS, pp. 29–41. [15] Chan, T.H.H., Shi, E., Song, D., 2012. Privacy-preserving stream aggregation with fault tolerance, in: Financial Cryptography and Data Security, Springer. pp. 200–214. URL: https://doi.org/10.1007/ 978-3-642-32946-3_15, doi:10.1007/978-3-642-32946-3_15. [16] Checri, M., Sirdey, R., Boudguiga, A., Bultel, J., Choffrut, A., 2024. On the practical CPAD security of "exact" and threshold FHE schemes and libraries. IACR Cryptol. ePrint Arch. , 116. [17] Cheon, J.H., Choe, H., Passelègue, A., Stehlé, D., Suvanto, E., 2024. Attacks against the INDCPA-D security of exact FHE schemes. IACR Cryptol. ePrint Arch. , 127. [18] Cheon, J.H., Kim, A., Kim, M., Song, Y.S., 2017. Homomorphic encryption for arithmetic of approximate numbers, in: ASIACRYPT, Springer. pp. 409–437. [19] Chillotti, I., Gama, N., Georgieva, M., Izabachène, M., 2016. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds, in: ASIACRYPT, pp. 3–33. [20] Choffrut, A., Guerraoui, R., Pinot, R., Sirdey, R., Stephan, J., Zuber, M., 2024. Towards practical homomorphic aggregation in byzantineresilient distributed learning, in: MIDDLEWARE, ACM. pp. 431– 444. [21] Cramer, R., Gennaro, R., Schoenmakers, B., 1997. A secure and optimally efficient multi-authority election scheme, in: Advances in Cryptology - EUROCRYPT’97, Springer. pp. 103–118. [22] Cremonesi, F., Vesin, M., Cansiz, S., Bouillard, Y., Balelli, I., Innocenti, L., Silva, S., Ayed, S.S., Taiello, R., Kameni, L., Vidal, R., Orlhac, F., Nioche, C., Lapel, N., Houis, B., Modzelewski, R., Humbert, O., Önen, M., Lorenzi, M., 2023. Fed-biomed: Open, transparent and trusted federated learning for real-world healthcare applications. CoRR abs/2304.12012. [23] Fan, J., Vercauteren, F., 2012. Somewhat practical fully homomorphic encryption. IACR Cryptol. ePrint Arch. , 144. [24] Fang, H., Qian, Q., 2021. Privacy preserving machine learning with homomorphic encryption and federated learning. Future Internet 13, 94. [25] Farhadkhani, S., Guerraoui, R., Gupta, N., Pinot, R., Stephan, J., 2022. Byzantine machine learning made easy by resilient averaging of momentums, in: ICML, PMLR. pp. 6246–6283. [26] Froelicher, D., Troncoso-Pastoriza, J.R., Raisaro, J.L., Cuendet, M.A., Sousa, J.S., Cho, H., Berger, B., Fellay, J., Hubaux, J.P., 2021. Truly privacy-preserving federated analytics for precision medicine with multiparty homomorphic encryption. Nature Communications 12, 5910. [27] Gamal, T.E., 1985. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31, 469–472. [28] Guo, X., Liu, Z., Li, J., Gao, J., Hou, B., Dong, C., Baker, T., 2021. Verifl: Communication-efficient and fast verifiable aggregation for federated learning. IEEE Transactions on Information Forensics and Security 16, 1–1. doi:10.1109/TIFS.2021.3078673.

[29] Hu, L., Evans, D., 2003. Secure aggregation for wireless network, in: SAINTW, IEEE Computer Society. pp. 384–394. [30] Islam, T.U., Ghasemi, R., Mohammed, N., 2022. Privacy-preserving federated learning model for healthcare data, in: CCWC, IEEE. pp. 0281–0287. [31] Kairouz, P., McMahan, H.B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A.N., Bonawitz, K.A., Charles, Z., Cormode, G., Cummings, R., D’Oliveira, R.G.L., Eichner, H., Rouayheb, S.E., Evans, D., Gardner, J., Garrett, Z., Gascón, A., Ghazi, B., Gibbons, P.B., Gruteser, M., Harchaoui, Z., He, C., He, L., Huo, Z., Hutchinson, B., Hsu, J., Jaggi, M., Javidi, T., Joshi, G., Khodak, M., Konečný, J., Korolova, A., Koushanfar, F., Koyejo, S., Lepoint, T., Liu, Y., Mittal, P., Mohri, M., Nock, R., Özgür, A., Pagh, R., Qi, H., Ramage, D., Raskar, R., Raykova, M., Song, D., Song, W., Stich, S.U., Sun, Z., Suresh, A.T., Tramèr, F., Vepakomma, P., Wang, J., Xiong, L., Xu, Z., Yang, Q., Yu, F.X., Yu, H., Zhao, S., 2021. Advances and open problems in federated learning. Found. Trends Mach. Learn. 14, 1–210. [32] Katz, J., Lindell, Y., 2014. Introduction to Modern Cryptography. 2nd ed., Chapman and Hall/CRC. [33] Kursawe, K., Danezis, G., Kohlweiss, M., 2011. Privacy-friendly aggregation for the smart-grid, in: PETS, Springer. pp. 175–191. [34] Leino, K., Fredrikson, M., 2020. Stolen memories: Leveraging model memorization for calibrated white-box membership inference, in: USENIX, USENIX Association. pp. 1605–1622. [35] Li, B., Micciancio, D., 2021. On the security of homomorphic encryption on approximate numbers, in: EUROCRYPT, Springer. pp. 648–677. [36] Lindell, Y., 2017. How to Simulate It - A Tutorial on the Simulation Proof Technique, in: Tutorials on the Foundations of Cryptography. Springer, pp. 277–346. [37] Lycklama, H., Burkhalter, L., Viand, A., Küchler, N., Hithnawi, A., 2023. Rofl: Robustness of secure federated learning, in: SP, IEEE. pp. 453–476. [38] Lyubashevsky, V., Peikert, C., Regev, O., 2013. On ideal lattices and learning with errors over rings. J. ACM 60, 43:1–43:35. [39] Ma, J., Naas, S., Sigg, S., Lyu, X., 2022. Privacy-preserving federated learning based on multi-key homomorphic encryption. Int. J. Intell. Syst. 37, 5880–5901. [40] Madi, A., Stan, O., Mayoue, A., Grivet-Sébert, A., Gouy-Pailler, C., Sirdey, R., 2021. A secure federated learning framework using homomorphic encryption and verifiable computing, in: RDAAPS, pp. 1–8. [41] Mansouri, M., Önen, M., Jaballah, W.B., Conti, M., 2023. Sok: Secure aggregation based on cryptographic schemes for federated learning. Proc. Priv. Enhancing Technol. 2023, 140–157. [42] McMahan, B., Moore, E., Ramage, D., Hampson, S., y Arcas, B.A., 2017. Communication-efficient learning of deep networks from decentralized data, in: AISTATS, PMLR. pp. 1273–1282. [43] Morona-Mínguez, M., Pedrouzo-Ulloa, A., Pérez-González, F., 2024. A Critical Look into Threshold Homomorphic Encryption for Private Average Aggregation, in: Proceedings of the 2024 Federated Learning and Trusted Aggregation (FLTA24), Valencia, Spain. [44] Mouchet, C., Bossuat, J.P., Troncoso-Pastoriza, J.R., Hubaux, J.P., 2020. Lattigo: A multiparty homomorphic encryption library in go, in: Proceedings of the 8th Workshop on Encrypted Computing and Applied Homomorphic Cryptography, pp. 64–70. [45] Mouchet, C., Troncoso-Pastoriza, J.R., Bossuat, J., Hubaux, J., 2021. Multiparty homomorphic encryption from ring-learning-with-errors. Proc. Priv. Enhancing Technol. 2021, 291–311. [46] Mouchet, C., Troncoso-Pastoriza, J.R., Hubaux, J., 2019. Computing across trust boundaries using distributed homomorphic cryptography. IACR Cryptol. ePrint Arch. , 961. [47] Nasr, M., Shokri, R., Houmansadr, A., 2019. Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning, in: SP, IEEE. pp. 739–753. [48] National Institute of Standards and Technology, 2023. Nist postquantum cryptography standardization. URL: https://csrc.nist.

gov/Projects/post-quantum-cryptography/selected-algorithms. acce-

dido: 2025-06-07. [49] Ogilvie, T., 2024. Differential privacy for free? harnessing the noise in approximate homomorphic encryption, in: CT-RSA, Springer. pp. 292–315. [50] Önen, M., Molva, R., 2007. Secure data aggregation with multiple encryption, in: Langendoen, K., Voigt, T. (Eds.), Wireless Sensor Networks. Springer. volume 4373 of Lecture Notes in Computer Science, pp. 117–132. [51] Paillier, P., 1999. Public-key cryptosystems based on composite degree residuosity classes, in: Advances in Cryptology—EUROCRYPT ’99, Springer. pp. 223–238. [52] Pedrouzo-Ulloa, A., Boudguiga, A., Chakraborty, O., Sirdey, R., Stan, O., Zuber, M., 2023a. Practical multi-key homomorphic encryption for more flexible and efficient secure federated average aggregation, in: CSR, IEEE. pp. 612–617. [53] Pedrouzo-Ulloa, A., Ramon, J., Pérez-González, F., Lilova, S., Duflot, P., Chihani, Z., Gentili, N., Ulivi, P., Hoque, M.A., Mukammel, T., Pritzker, Z., Lemesle, A., Loureiro-Acuña, J., Luaña, X.M., JiménezBalsa, G., 2023b. Introducing the TRUMPET project: Trustworthy multi-site privacy enhancing technologies, in: CSR, IEEE. pp. 604– 611. [54] Sav, S., Pyrgelis, A., Troncoso-Pastoriza, J.R., Froelicher, D., Bossuat, J., Sousa, J.S., Hubaux, J., 2021. POSEIDON: privacypreserving federated neural network learning, in: NDSS, The Internet Society. [55] Sébert, A.G., Checri, M., Stan, O., Sirdey, R., Gouy-Pailler, C., 2023. Combining homomorphic encryption and differential privacy in federated learning, in: PST, IEEE. pp. 1–7. [56] Shi, E., Chan, T.H., Rieffel, E.G., Chow, R., Song, D., 2011. Privacypreserving aggregation of time-series data, in: NDSS, The Internet Society. [57] Smart, N.P., 2016. Cryptography made simple. Springer. [58] Smart, N.P., Vercauteren, F., 2014. Fully homomorphic SIMD operations. Des. Codes Cryptogr. 71, 57–81. [59] United Nations, 2023. Un guide on privacy-enhancing technologies for official statistics. https://unstats.un.org/bigdata/task-teams/ privacy/guide/. Accessed: 2025-06-07. [60] Wei, K., Li, J., Ding, M., Ma, C., Yang, H.H., Farokhi, F., Jin, S., Quek, T.Q., Poor, H.V., 2020. Federated learning with differential privacy: Algorithms and performance analysis. IEEE transactions on information forensics and security 15, 3454–3469. [61] Zhang, C., Li, S., Xia, J., Wang, W., Yan, F., Liu, Y., 2020. Batchcrypt: Efficient homomorphic encryption for cross-silo federated learning, in: USENIX, USENIX Association. pp. 493–506.

A. Bounds for the ciphertext modulus 𝑞 This appendix collects technical bounds for determining the ciphertext modulus 𝑞 used in Section 6. We first derive bounds ensuring correct decryption for fresh public-key and secret-key BFV ciphertexts, then use these bounds to compare the ciphertext modulus required by the BFV and CKKS-based multi-client protocol constructions. Lemma 1 (Lemma 1 in [43]). We follow the notation for 𝖡𝖥𝖵 indicated in Table 1, and assume that 𝑒 ← 𝜒 satisfies ‖𝑒‖ ≤ 𝐵. For a fresh ciphertext 𝖼𝗍 = (𝑐0 , 𝑐1 ), we have [𝑐0 + 𝑐1 𝑠]𝑞 = Δ𝑚 + 𝑒𝖼𝗍 with ‖𝑒𝖼𝗍 ‖ ≤ (2𝑛 + 1)𝐵. This implies that whenever (2𝑛 + 1)𝐵 < 2𝑡𝑞 − 2𝑡 , decryption works correctly. Proof. We start by computing [𝑐0 + 𝑐1 ⋅ 𝑠]𝑞 = Δ𝑚 + 𝑢 ⋅ 𝑒 + 𝑒0 + 𝑒1 ⋅ 𝑠, from which we can directly upper-bound ⏟⏞⏞⏞⏞⏞⏞⏞⏞⏟⏞⏞⏞⏞⏞⏞⏞⏞⏟ 𝑒𝖼𝗍

Page 20 of 29

the error polynomial 𝑒𝖼𝗍 as: (11)

‖𝑒𝖼𝗍 ‖ = ‖𝑢 ⋅ 𝑒 + 𝑒0 + 𝑒1 ⋅ 𝑠‖

(12)

≤ ‖𝑢 ⋅ 𝑒‖ + ‖𝑒0 ‖ + ‖𝑒1 ⋅ 𝑠‖ ≤ 𝛿𝑅 𝐵 + 𝐵 + 𝛿𝑅 𝐵

(13)

≤ 𝑛𝐵 + 𝐵 + 𝑛𝐵

(14)

= (2𝑛 + 1)𝐵.

(15)

Now, the decryption process requires to multiply by 𝑞𝑡 and apply a final coefficient-wise rounding: ⌊ ⌉ ⌊ ⌉ 𝑡 𝑡 ([𝑐 + 𝑐 ⋅ 𝑠] ) = (Δ𝑚 + 𝑒 ) , 0 1 𝑞 𝖼𝗍 𝑞 𝑞 which must output 𝑚 for correct decryption. If we define Δ = 𝑞𝑡 − 𝑟 with 0 ≤ 𝑟 < 1, the condition for correct decryption can be expressed equivalently as: ‖𝑡 ‖ 1 ‖ 𝑞 (−𝑟𝑚 + 𝑒𝖼𝗍 )‖ < 2 . ‖ ‖ By upper-bounding the expression in the left, we obtain: ‖𝑡 ‖ 𝑡 𝑡 ‖ 𝑞 (−𝑟𝑚 + 𝑒𝖼𝗍 )‖ ≤ 𝑞 (‖−𝑟𝑚‖+‖𝑒𝖼𝗍 ‖) < 𝑞 ‖ ‖

(

) 1 𝑡 + ‖𝑒 ‖ < . 𝖼𝗍 2 2 (16)

Therefore, combining the expressions (15) and (16), we see that decryption correctness holds if (2𝑛 + 1)𝐵 < 2𝑡𝑞 − 2𝑡 . Lemma 2 (Secret-key analogue of the BFV correctness bound). We follow the notation for secret-key 𝖡𝖥𝖵 indicated in Table 3, and assume that 𝑒 ← 𝜒 satisfies ‖𝑒‖ ≤ 𝐵. For a fresh ciphertext 𝖼𝗍 = (𝑐0 , 𝑐1 ) = 𝖤𝖺𝗌𝗁𝖾 .𝖤𝗇𝖼(𝗌𝗄, 𝑚) under 𝗌𝗄 = 𝑠, with 𝑚 ∈ 𝑅𝑡 represented coefficient-wise in (−𝑡∕2, 𝑡∕2], we have [𝑐0 + 𝑐1 𝑠]𝑞 = Δ𝑚 + 𝑒𝖼𝗍 with ‖𝑒𝖼𝗍 ‖ ≤ 𝐵. This implies that whenever 𝐵 < 2𝑡𝑞 − 2𝑡 , decryption works correctly. Proof. We start by computing the decryption phase for a fresh secret-key ciphertext. By the definition of 𝖤𝖺𝗌𝗁𝖾 .𝖤𝗇𝖼 in Table 3, we have (𝑐0 , 𝑐1 ) = (−𝑎 ⋅ 𝑠 + 𝑒 + Δ𝑚, 𝑎) for some 𝑎 ← 𝑅𝑞 and 𝑒 ← 𝜒. Therefore [𝑐0 + 𝑐1 ⋅ 𝑠]𝑞 = [−𝑎 ⋅ 𝑠 + 𝑒 + Δ𝑚 + 𝑎 ⋅ 𝑠]𝑞 = Δ𝑚 + 𝑒 = Δ𝑚 + 𝑒𝖼𝗍 , and the ciphertext error satisfies ‖𝑒𝖼𝗍 ‖ = ‖𝑒‖ ≤ 𝐵.

(17)

The remaining correctness argument is identical to the one in Lemma 1. Namely, after multiplying by 𝑞𝑡 and applying coefficient-wise rounding, decryption is correct when‖ ‖ ever ‖ 𝑞𝑡 (−𝑟𝑚 + 𝑒𝖼𝗍 )‖ < 21 , where Δ = 𝑞𝑡 − 𝑟 with 0 ≤ 𝑟 < 1. ‖ ‖ Using ‖𝑚‖ ≤ 2𝑡 and the bound in Eq. (17), this condition ( ) is satisfied if 𝑞𝑡 2𝑡 + 𝐵 < 12 . Equivalently, decryption correctness holds whenever 𝐵 < 2𝑡𝑞 − 2𝑡 . Proposition 1 (Generalized version of Proposition 1 in [43]). Consider the descriptions of the primitives for either the MHE-based protocol (from Tables 1 and 2) or the proposed protocol (from Tables 3 and 4), instantiated with their 𝖡𝖥𝖵 Page 21 of 29

𝖬𝖯 denote the final effective noise and 𝖢𝖪𝖪𝖲 variants. Let 𝐵𝖼𝗍 bound entering the decryption correctness condition of the considered multi-client protocol. Then, the ciphertext modulus 𝑞 for 𝖡𝖥𝖵 constructions is larger than the one for 𝖢𝖪𝖪𝖲 constructions if the following condition is satisfied: 𝖬𝖯 𝐵𝖼𝗍 >

2Δ𝖢𝖪𝖪𝖲 𝐵𝑚 − 𝑡2 . 2(𝑡 − 1)

This condition applies to both protocols with the substitution 𝖬𝖯 = 𝐵 𝖬𝖯 𝐵𝖼𝗍 𝗆𝗁𝖾 for the MHE-based protocol and 𝐵𝖼𝗍 = 𝐵𝗉𝗋𝗈𝗉 for the proposed protocol. Section 6.4 uses this expression as Eq. (9) to compare the cipher expansion of both schemes. Proof. The derivation relies only on the BFV and CKKS correctness conditions, hence is protocol-independent once 𝖬𝖯 is fixed. From the corthe final effective noise bound 𝐵𝖼𝗍 rectness bounds in Subsection 6.1, both schemes must satisfy: 𝖬𝖯 < 𝑞 − 𝑡 . • 𝑞𝖡𝖥𝖵 ∶ 𝐵𝖼𝗍 2𝑡 2 𝖬𝖯 < 𝑞 . • 𝑞𝖢𝖪𝖪𝖲 ∶ Δ𝖢𝖪𝖪𝖲 𝐵𝑚 + 𝐵𝖼𝗍 2

Comparing both expressions, we have that 𝑞𝖡𝖥𝖵 > 𝑞𝖢𝖪𝖪𝖲 if: 𝖬𝖯 𝖬𝖯 . + 𝑡2 > 2Δ𝖢𝖪𝖪𝖲 𝐵𝑚 + 2𝐵𝖼𝗍 2𝑡𝐵𝖼𝗍

Rearranging terms gives 𝖬𝖯 > 2Δ𝖢𝖪𝖪𝖲 𝐵𝑚 − 𝑡2 , 2(𝑡 − 1)𝐵𝖼𝗍

or equivalently, 𝖬𝖯 > 𝐵𝖼𝗍

2Δ𝖢𝖪𝖪𝖲 𝐵𝑚 − 𝑡2 . 2(𝑡 − 1)

B. Ciphertext expansion regimes This appendix derives the approximations summarized in Table 5. Starting from (8), 𝑅(𝐶) = 2

log2 𝐵𝗆𝗁𝖾 + log2 𝐶 , log2 𝐵𝗉𝗋𝗈𝗉 + log2 𝐶

we distinguish three regimes based on the precision term 𝐶. Since Eq. (8) depends only logarithmically on 𝐵𝗆𝗁𝖾 , 𝐵𝗉𝗋𝗈𝗉 , and 𝐶, the regime approximations are determined by the relative sizes of log2 𝐵𝗆𝗁𝖾 , log2 𝐵𝗉𝗋𝗈𝗉 , and log2 𝐶. Low-to-moderate precision regime: Assume first that log2 𝐶 ≪ log2 𝐵𝗉𝗋𝗈𝗉 < log2 𝐵𝗆𝗁𝖾 . Then ( ) log2 (1 + 𝐿2𝜆∕2 )(2𝑛𝐿 + 1) log2 𝐵𝗆𝗁𝖾 = 2+2 . 𝑅(𝐶) ≃ 2 log2 𝐵𝗉𝗋𝗈𝗉 log2 (𝐿𝐵) (18) In the range where 𝐿2𝜆∕2 ≫ 1 and 2𝑛𝐿 ≫ 1, this becomes 𝑅(𝐶) ≃ 2 + 2

𝜆∕2 + log2 (2𝑛𝐿2 ) . log2 (𝐿𝐵)

(19)

105

105

log2(

log2(

1)

155

1)

155

55 5

2

32

64

96

log2(t)

(a) 𝐿 = 10, 𝜆 = 32.

(21)

105

105

Intermediate precision regime: Assume now that we have log2 𝐵𝗉𝗋𝗈𝗉 < log2 𝐶 < log2 𝐵𝗆𝗁𝖾 . Here, the denominator of (8) is affected by the precision term, whereas the numerator still contains the large MHE noise bound. If log2 𝐶 dominates log2 𝐵𝗉𝗋𝗈𝗉 , i.e., log2 𝐵𝗉𝗋𝗈𝗉 ≪ log2 𝐶, then

𝑅(𝐶) ≃ 2 + 2

64

96

log2(t)

128

2

32

64

96

log2(t)

(c) 𝐿 = 8, 𝜆 = 128.

128

55 5

2

32

64

96

log2(t)

128

(d) 𝐿 = 128, 𝜆 = 128.

Figure 5: CKKS-favorable regions for the MHE-based protocol.

log2 𝐵𝗆𝗁𝖾 𝜆 + 2 log2 (2𝑛𝐿3 𝐵) ≈ 2+ . (22) log2 𝐶 log2 𝐶

For precision targets in the range of roughly 40–64 bits and 𝜆 = 128, this second term remains significant for common cross-silo values of 𝐿 and standard HE ring dimensions. Very high precision regime: If log2 𝐶 ≫ log2 𝐵𝗆𝗁𝖾 , the precision term dominates both numerator and denominator in (8), so 𝑅(𝐶) → 2.

(23)

This is the worst asymptotic regime for the proposed construction in terms of relative ciphertext expansion. Even in this case, the protocol preserves the structural advantage of transmitting one polynomial component instead of two.

C. Additional BFV/CKKS comparison details This appendix complements the BFV/CKKS comparison of Subsection 6.4. We include separate parameter-region plots for the MHE-based and proposed protocols, heat maps quantifying the modulus 𝗀𝖺𝗉 in bits, and a brief clarification on the role of approximate HE in private aggregation.

C.1. Parameter regions for each protocol Figures 5 and 6 plot Eq. (10) for the MHE-based construction and for the proposed construction, respectively. In Figure 5, we set 𝑛 = 8192 and 𝐵 = 19.2. The first row fixes 𝐿 = 10, with 𝜆 ∈ {32, 128}, and the second fixes 𝜆 = 128, with 𝐿 ∈ {8, 128}. In Figure 6, we set 𝑛 = 8192, 𝐵 = 19.2, and 𝜆 = 128, with 𝐿 ∈ {8, 128}. These parameters are representative of cross-silo settings and compatible with at least 128 bits of security for the represented precision ranges. The behavior in the figures follows directly from Eq. (10): Page 22 of 29

55 5

32

1)

155

log2(

𝜆∕2 + log2 (2𝑛𝐿2 ) 𝑅(𝐶) ≃ 2 + . log2 (𝐿𝐵)

2

(b) 𝐿 = 10, 𝜆 = 128.

155

log2(

Using again 𝐿2𝜆∕2 ≫ 1 and 2𝑛𝐿 ≫ 1, we obtain

55 5

128

1)

The gain is therefore driven by removing the smudging factor 2𝜆∕2 and the collective-public-key term (2𝑛𝐿 + 1). Up to different constants, the same reasoning and conclusions also apply in the moderate-precision regime, where 𝐶 ≈ 𝐵𝗉𝗋𝗈𝗉 < 𝐵𝗆𝗁𝖾 . In this case, the term log2 𝐶 in Eq. (8) can no longer be neglected. In the numerator, it contributes approximately log2 𝐵𝗉𝗋𝗈𝗉 , while in the denominator it gives log2 𝐵𝗉𝗋𝗈𝗉 + log2 𝐶 ≈ 2 log2 𝐵𝗉𝗋𝗈𝗉 . This yields ( ) log2 (1 + 𝐿2𝜆∕2 )(2𝑛𝐿 + 1) . (20) 𝑅(𝐶) ≃ 2 + log2 (𝐿𝐵)

(a) 𝐿 = 8.

(b) 𝐿 = 128.

Figure 6: CKKS-favorable regions for the proposed protocol.

• When the term 𝑡 − 1 dominates, the boundary is approximately log2 (𝑡 − 1) > log2 𝜖 −1 . • When the quadratic term dominates, the boundary is 𝖬𝖯 − 1 > log 𝜖 −1 . approximately 2 log2 𝑡 − log2 𝐵𝖼𝗍 2 Thus, once the quadratic term becomes relevant, CKKS becomes increasingly favorable as the target precision grows. Increasing 𝜆 affects only the MHE-based protocol through the smudging term. Increasing 𝐿 affects both protocols, but its impact is stronger for MHE because 𝐵𝗆𝗁𝖾 contains the additional factor (1 + 𝐿2𝜆∕2 ) ⋅ (2𝑛𝐿 + 1).

C.2. Modulus 𝗀𝖺𝗉 between BFV and CKKS We next quantify the modulus gap between the BFVbased and CKKS-based instantiations, for which we define 𝗀𝖺𝗉 = log2 𝑞𝖡𝖥𝖵 −log2 𝑞𝖢𝖪𝖪𝖲 . For a fixed public parametrization and for each point (log2 𝑡, log2 𝜖 −1 ), we compute the minimum modulus required by both schemes using Eqs. (3) and (4). Repeating this computation over the parameter grid gives the heat maps of 𝗀𝖺𝗉 shown in Figure 7. The black dashed curve marks the separation between the BFV-favorable and CKKS-favorable regions. To interpret the behavior of the heat maps, we incorporate an explicit 2 modulus 𝗀𝖺𝗉 into Eqs. (9) and (10). This gives 𝑡 𝖬𝖯 + 𝑡 − 2𝐵𝖼𝗍

fundamental notion for public-key encryption under passive attacks is indistinguishability under chosen-plaintext attack (𝖨𝖭𝖣-𝖢𝖯𝖠), which is equivalent to semantic security [57]. Informally, it requires that an adversary cannot distinguish the encryptions of two chosen plaintexts with probability significantly better than random guessing. IND-CPA security game (a) Proposed protocol with 𝐿 = 128.

(b) MHE-based protocol with 𝐿 = 𝜆 = 128.

Challenger

Adversary 𝜆

(𝗉𝗄, 𝗌𝗄) ←$ .𝖪𝖾𝗒𝖦𝖾𝗇(1 )

Figure 7: Heat map comparison between the BFV-based and CKKS-based instantiations of the proposed and MHE-based protocols. The color bands represent the value of 𝗀𝖺𝗉 in bits.

𝗉𝗄

←←←←←←←←←←←←←←←←←←←←→ ← 𝑚0 , 𝑚1 ∈  𝑚0 ,𝑚1

←←←←←←←←←←←←←←←←←← 𝑏 ←$ {0, 1}

2𝗀𝖺𝗉 ≈ 𝜖 −1 2𝗀𝖺𝗉 , and therefore 𝜖 −1 (𝑡, 𝗀𝖺𝗉) ≈

𝑡2 𝖬𝖯 2𝗀𝖺𝗉 2𝐵𝖼𝗍

𝑐𝑏 = .𝖤𝗇𝖼𝗉𝗄 (𝑚𝑏 )

+

𝑡 2𝗀𝖺𝗉

− 1.

The transition between the two main regimes occurs when the linear and quadratic terms in 𝑡 have comparable 2 𝑡 size, that is, 2𝗀𝖺𝗉 ≈ 𝖬𝖯𝑡 𝗀𝖺𝗉 . At this transition point, the factor 2𝐵𝖼𝗍 2

𝖬𝖯 . Hence, in logarithmic 2𝗀𝖺𝗉 cancels out, yielding 𝑡 ≈ 2𝐵𝖼𝗍 𝖬𝖯 , scale, the transition is located around log2 𝑡 ≈ 1 + log2 𝐵𝖼𝗍 independently of 𝗀𝖺𝗉. Thus, the modulus gap does not shift the transition horizontally, but mainly produces a vertical displacement of the level curves. In the regime where the constant term in Eq. (24) is negligible, we have ( ) 𝑡2 −1 log2 𝜖 ≈ log2 𝑡 + − 𝗀𝖺𝗉. 𝖬𝖯 2𝐵𝖼𝗍

Equivalently, increasing 𝗀𝖺𝗉 shifts the curves downward by approximately 𝗀𝖺𝗉 bits in the log2 𝜖 −1 axis.

C.3. Some remarks on approximate aggregation We close with a clarification on the BFV/CKKS comparison. Our analysis considers BFV decryption with multiplication by 𝑡∕𝑞, following [23]. When 𝑡 does not divide 𝑞, the rounding error causes the extra quadratic term in Eq. (10). If BFV decryption were instead modified to divide by a scaling factor Δ, then Eq. (10) would resemble the first approximately linear interval of Figures 5, 6, 4, and 7. This does not remove the practical appeal of CKKS for private aggregation. Its approximate nature accounts for controlled error in the decrypted result, which can be useful when combined with output-privacy mechanisms applied to the released aggregate [41, 43]. BFV could emulate this by adding encoded noise homomorphically, but this would consume part of the plaintext-modulus budget. In CKKS, the target precision 𝜖 −1 already captures this trade-off.

D. Indistinguishability Security Definitions The security of encryption schemes is commonly formalized through indistinguishability-based definitions. A Page 23 of 29

𝑐𝑏

(24)

←←←←←←←←←←←←←←←←←←←←→ ← 𝑏′ ∈ {0, 1} Wins if 𝑏 = 𝑏′

Definition 14 (IND-CPA Security). Let Π be an encryption scheme. We say that Π is 𝖨𝖭𝖣-𝖢𝖯𝖠 secure if for every probabilistic polynomial-time adversary , | | () = |Pr[ wins] − 12 | 𝖠𝖽𝗏𝖨𝖭𝖣-𝖢𝖯𝖠 Π | | is negligible in the security parameter 𝜆. 𝖨𝖭𝖣-𝖢𝖯𝖠𝖣 security: For HE schemes, the 𝖨𝖭𝖣-𝖢𝖯𝖠 notion can be extended to capture the evaluation functionality. This leads to the 𝖨𝖭𝖣-𝖢𝖯𝖠𝖣 security model, in which the adversary may additionally access an evaluation oracle 𝖤𝗏𝖺𝗅 and a restricted decryption oracle 𝖣𝖾𝖼 . For general HE schemes, the evaluation oracle allows the adversary to evaluate arbitrary circuits over ciphertexts. In our setting, however, the supported homomorphic operation is addition, and therefore 𝖤𝗏𝖺𝗅 corresponds to sequences of homomorphic additions (i.e., repeated applications of 𝖠𝖽𝖽). 𝖨𝖭𝖣-𝖢𝖯𝖠𝖣 security game Challenger

Adversary

(𝗉𝗄, 𝗌𝗄, 𝖾𝗄) ←$ .𝖪𝖾𝗒𝖦𝖾𝗇(1𝜆 ) 𝑏 ←$ {0, 1} 𝗉𝗄

←←←←←←←←←←←←←←←←←←←←→ ← 𝑆=[] Encryption Oracle Evaluation Oracle Decryption Oracle 𝑏′ ∈ {0, 1} Wins if 𝑏′ = 𝑏

Encryption Oracle 𝖤𝗇𝖼 (𝑚0 , 𝑚1 , 𝗉𝗄, 𝑏, 𝑖) Adversary

Oracle

𝑚0 , 𝑚1 ∈  𝑚0 , 𝑚1 𝖼𝗍 ← 𝖤𝗇𝖼(𝗉𝗄, 𝑚𝑏 ) 𝑆[𝑖] = (𝑚0 , 𝑚1 , 𝖼𝗍) 𝑖=𝑖+1 𝖼𝗍, 𝑖

𝖣 | | () = |Pr[ wins] − 12 | 𝖠𝖽𝗏𝖨𝖭𝖣-𝖢𝖯𝖠 Π | |

is negligible in 𝜆.

E. Auxiliary Zero-Sharing Protocols We describe two simple protocols used to generate additive shares of zero among 𝐿 clients 𝐶𝑖 ∈ . The first protocol [52] produces uniformly random additive shares that sum to zero. The second protocol derives shares compatible with the zero-sharing LSSS defined in Definition 11. The concrete protocols below assume pairwise private authenticated channels between clients; alternative secure realizations of 𝖲 may also be used.

Evaluation Oracle 𝖤𝗏𝖺𝗅 (𝐶, 𝑖1 , … , 𝑖𝑘 , 𝖾𝗄, 𝑆) Adversary

Definition 15 (𝖨𝖭𝖣-𝖢𝖯𝖠𝖣 Security). Let Π = (𝖲𝖾𝗍𝗎𝗉, 𝖪𝖾𝗒𝖦𝖾𝗇, 𝖤𝗇𝖼, 𝖣𝖾𝖼, 𝖤𝗏𝖺𝗅) be a homomorphic encryption scheme. We say that Π is 𝖨𝖭𝖣-𝖢𝖯𝖠𝖣 secure if for every probabilistic polynomial-time adversary  with oracle access to 𝖤𝗇𝖼 , 𝖤𝗏𝖺𝗅 , and 𝖣𝖾𝖼 ,

Oracle

{𝑖1 , … , 𝑖𝑘 } ⊆  𝐶∈ 𝐶, 𝑖1 , … , 𝑖𝑘 𝖼𝗍 ← 𝖤𝗏𝖺𝗅(𝐶, 𝖾𝗄,

Protocol 1: Additive Zero Sharing. Given 𝐿 clients

𝑆[𝑖1 ].𝖼𝗍, … , 𝑆[𝑖𝑘 ].𝖼𝗍) 𝐶𝑖 ∈ , the parties generate additive shares 𝑟1 , … , 𝑟𝐿 ∈ 𝑅𝑞 𝑚′0 = 𝐶(𝑆[𝑖1 ].𝑚0 , … , 𝑆[𝑖𝑘 ].𝑚0 ) 𝑚′1 = 𝐶(𝑆[𝑖1 ].𝑚1 , … , 𝑆[𝑖𝑘 ].𝑚1 ) 𝑆[𝑖] = (𝑚′0 , 𝑚′1 , 𝖼𝗍) 𝑖=𝑖+1 𝑚′0 , 𝑚′1 , 𝖼𝗍, 𝑖

Decryption Oracle 𝖣𝖾𝖼 (𝑖, 𝗌𝗄, 𝑆) Adversary

Oracle

𝑖∈ 𝑖 if (𝑆[𝑖].𝑚0 = 𝑆[𝑖].𝑚1 ) then 𝑚 ← 𝖣𝖾𝖼(𝗌𝗄, 𝑆[𝑖].𝖼𝗍) 𝗈𝗎𝗍 = 𝑚 else out = ⊥ 𝗈𝗎𝗍

In this security game, the adversary attempts to guess the secret bit 𝑏 ∈ {0, 1} chosen uniformly at random by the challenger. The adversary may query the encryption oracle 𝖤𝗇𝖼 arbitrarily many times. Each query stores the pair (𝑚0 , 𝑚1 ) and the ciphertext 𝖼𝗍 = 𝖤𝗇𝖼(𝗉𝗄, 𝑚𝑏 ) in the list 𝑆. The adversary may also evaluate circuits using the evaluation oracle 𝖤𝗏𝖺𝗅 . The resulting ciphertext and the corresponding evaluated messages are added to the list 𝑆. Finally, the adversary may query the restricted decryption oracle 𝖣𝖾𝖼 . This oracle returns the decryption of 𝑆[𝑖].𝖼𝗍 only if the associated messages satisfy 𝑆[𝑖].𝑚0 = 𝑆[𝑖].𝑚1 ; otherwise it returns ⊥. Page 24 of 29

such that

∑𝐿

𝑖=1 𝑟𝑖 = 0. This is done as follows: $

1. Each client 𝐶𝑖 samples (𝐿 − 1) elements 𝑟(𝑖,𝑗) ←←←← 𝑅𝑞 for all 𝑗 ∈ {1, … , 𝐿} with 𝑗 ≠ 𝑖. ∑ 2. Each client 𝐶𝑖 sets 𝑟(𝑖,𝑖) = − 𝑗≠𝑖 𝑟(𝑖,𝑗) , so that ∑𝐿 (𝑖,𝑗) = 0. 𝑗=1 𝑟 3. Client 𝐶𝑖 sends 𝑟(𝑖,𝑗) to client 𝐶𝑗 over their private authenticated channel for all 𝑗 ≠ 𝑖. ∑ (𝑗,𝑖) . 4. Each client 𝐶𝑖 computes its share 𝑟𝑖 = 𝐿 𝑗=1 𝑟 ∑ It follows that the resulting shares satisfy 𝐿 𝑖=1 𝑟𝑖 = 0. Protocol 2: Zero Sharing with Reconstruction Coefficients. Let 𝜆1 , … , 𝜆𝐿 ∈ ℤ𝑞 be the public reconstruction coefficients from Definition 11. The protocol is as follows: 1. Run Protocol 1 to obtain additive shares 𝑟1 , … , 𝑟𝐿 ∑ such that 𝐿 𝑖=1 𝑟𝑖 = 0. 2. Each client 𝐶𝑖 locally computes 𝑟̃𝑖 = 𝜆−1 𝑖 ⋅ 𝑟𝑖 . ∑ ∑𝐿 The resulting shares 𝑟̃1 , … , 𝑟̃𝐿 satisfy 𝐿 𝑖=1 𝜆𝑖 𝑟̃𝑖 = 𝑖=1 𝑟𝑖 = 0, thus forming a valid zero-sharing by Definition 11.

F. Scalability with the number of clients For fixed cryptographic parameters and model size, the direct dependence on the number of clients 𝐿 only appears in operations that combine client contributions. Each client independently encrypts its input and computes its partial decryption share, so the local cost of both operations is independent of 𝐿 per ciphertext block. In contrast, aggregating the encrypted contributions and combining the partial decryption shares require processing 𝐿 client contributions, leading to a cost that grows linearly with 𝐿.

Table 10 Client-side setup runtime as a function of the number 𝐿 of participating clients for the proposed and MHE-based protocols. The first four columns of the proposed protocol use the four parameter sets of Table 6, whereas the last two MHEbased columns use the two MHE parameter sets of Table 8. Reported values are average single-threaded runtimes under the experimental setting of Section 6.5. 𝐿

Set 1*

Set 2

32 14.12 ms 14.84 ms 64 39.52 ms 48.60 ms 128 79.90 ms 77.73 ms 256 156.69 ms 145.25 ms 512 277.68 ms 293.02 ms

Set 3 Prop. Set 4 Prop. Set 3 MHE Set 4 MHE 36.04 ms 100.51 ms 184.21 ms 375.37 ms 733.94 ms

41.03 ms 139.60 ms 193.44 ms 354.61 ms 742.92 ms

2.20 ms 5.10 ms 8.10 ms 12.29 ms 20.43 ms

1.75 ms 3.98 ms 5.13 ms 9.27 ms 15.40 ms

* The parameter sets corresponding to the columns are, from left to right,

Set 1 BFV, Set 2 CKKS, Set 3 BFV (Prop.), and Set 4 CKKS (Prop.) from Table 6, and Set 3 BFV (MHE) and Set 4 CKKS (MHE) from Table 8.

There is also an indirect dependence through parameter selection. For the proposed protocol, the effective decryption-noise bound is 𝐵𝗉𝗋𝗈𝗉 = 𝐿𝐵, as given in Eq. (7). Together with the BFV and CKKS correctness conditions in Eqs. (3) and (4), this implies that, for a fixed precision target, the required ciphertext modulus 𝑞 grows linearly with 𝐿, while its bit length grows only logarithmically. In practice, this affects computation mainly when a larger 𝑞 requires an additional modulus limb or a larger ring degree. This dependence is substantially milder than in the MHE-based construction, whose effective noise bound in Eq. (6) grows as (𝐿3 2𝜆∕2 ). The setup phase has the strongest explicit dependence on 𝐿. In the zero-sharing protocol of Appendix E, each client samples 𝐿 − 1 elements of 𝑅𝑞 , exchanges one contribution with every other client, and combines the received shares. The resulting local computation and communication scale linearly with 𝐿, while the total pairwise communication scales quadratically. Table 10 shows the practical impact of this scaling. Even for 𝐿 = 512, the setup of the proposed protocol remains below one second for all evaluated parameter sets. Although the MHE-based setup is faster in these experiments, setup is performed only once in the offline phase. Moreover, its cost remains small relative to the online computation for the evaluated model size, as shown in Table 9. Thus, even if setup were repeated in every aggregation round instead of being performed only once offline, it would not become the dominant runtime cost.

G. Proof of Theorem 1 Proof strategy: We prove Theorem 1 by showing that our protocol from Table 4 provides simulation-based input privacy for the aggregation functionality 𝑓Σ (see Definition 16 below). This is done by running a simulation-based argument in the standard real/ideal paradigm, following [5] but tailored to our simpler semi-honest setting. Our proof is substantially simpler than the general framework of [5] for three reasons: (i) we only consider static semi-honest adversaries, (ii) the functionality is the fixed linear aggregation Page 25 of 29

function 𝑓Σ , and (iii) the use of symmetric-key encryption together with the client-local oracle 𝑖 (⋅) allows the real protocol to inject a fresh decryption noise locally per client, so that no 𝜆-dependent large-variance smudging noise is needed in the simulation. Definition 16 (Simulation-based input privacy for 𝑓Σ ). Let 𝜋𝑓Σ be a protocol for private aggregation between the clients  and the Aggregator (see Table 4 and Definition 12). We say that 𝜋𝑓Σ securely realizes the aggregation functionality 𝑓Σ in the semi-honest model if, for every static semihonest adversary  that may corrupt the Aggregator and an arbitrary subset of up to 𝐿 − 1 clients, there exists a probabilistic polynomial-time simulator  such that, for ⃗ 𝑖 }𝐿 every input tuple {𝑤 , the joint view of the adversary 𝑖=1 in the real execution of 𝜋𝑓Σ , i.e., the collection of all inputs, randomness, internal states, and messages held by corrupted parties, is computationally indistinguishable from its view in an ideal execution where: • honest clients provide their inputs only to the ideal functionality 𝑓Σ ; • corrupted parties provide their inputs through the adversary; ⃗∗ = • the functionality computes the exact aggregate 𝑤 ⃗ ⃗ 𝑓Σ (𝑤1 , … , 𝑤𝐿 ), then output parties receive this value under the exact-output convention, or a randomized approximation of it under the CKKS output convention described below; and • the simulator  interacts with  using only the inputs ⃗ ∗ , and proof the corrupted parties and the output 𝑤 duces a view for a distinguisher  computationally indistinguishable from the real one. This notion captures input privacy in the sense of Definition 5: the adversary learns no additional information about the inputs of honest clients beyond what follows from its own inputs and the aggregation result. Output convention: For the exact BFV instantiation, the ⃗ ∗ whenever the correspondprotocol output coincides with 𝑤 ing correctness condition holds. For the approximate CKKS ∑ ⃗ ∗ +Δ−1 𝐿 ̃𝑖 instantiation, the protocol output is instead 𝑤 𝑖=1 𝒆 (see Eq. (25)). This distinction affects only correctness and the form of the protocol output. In both cases, input privacy ⃗ ∗ , which is defined with respect to the exact aggregate 𝑤 remains the value made available to the simulator in the ideal execution. Blockwise encoding of client updates: Following the blockwise convention introduced in Section 5.2, we make explicit how the proof handles ⌈vector updates ⌉ spanning #𝖬𝗈𝖽𝖾𝗅𝖯𝖺𝗋𝖺𝗆𝗌 denote the several ciphertexts. Let 𝑁𝖼𝗍𝗑 ∶= 𝑛(𝜆) number of secret-key ciphertexts required to encode one client update, where #𝖬𝗈𝖽𝖾𝗅𝖯𝖺𝗋𝖺𝗆𝗌 is the total number of model parameters and 𝑛(𝜆) is the number of plaintext slots supported by the underlying RLWE scheme. Accordingly,

⃗ 𝑖 does not fit into a single ciwhenever a client update 𝑤 phertext, it is represented blockwise by 𝑁𝖼𝗍𝗑 ciphertexts. In that case, all encryptions, aggregations, and partial decryptions appearing below are understood componentwise over these 𝑁𝖼𝗍𝗑 ciphertext blocks. For the 𝑗-th ciphertext block, the public component is sampled independently as 𝑎𝑗 ← 𝑅𝑞 , and, whenever the same secret key is reused, these public components are required to be pairwise distinct; more generally, ciphertexts generated under a common secret key always use fresh, non-repeated public components.

G.1. Indistinguishability of encryptions We begin by formalizing the distinguishing advantage [32, 5], the central quantity in the hybrid arguments. For experiment distributions 𝐻, 𝐻 ′ over a common sample space, i.e., producing outputs of the same form, and any PPT distinguisher  taking samples from that space as input, define: 𝖠𝖽𝗏 (𝐻, 𝐻 ′ ) ∶= ||Pr[(𝐻) = 1] − Pr[(𝐻 ′ ) = 1]|| . Here, (𝐻) = 1 denotes the event that  outputs 1 when given a sample drawn from 𝐻; distinguishability is measured by the gap between the corresponding output probabilities. This notion satisfies the triangle inequality: for any three distributions 𝐻0 , 𝐻1 , 𝐻2 , it holds that 𝖠𝖽𝗏 (𝐻0 , 𝐻2 ) ≤ 𝖠𝖽𝗏 (𝐻0 , 𝐻1 ) + 𝖠𝖽𝗏 (𝐻1 , 𝐻2 ). This property, together with Proposition 2, will be used repeatedly in our proof of Theorem 1 to justify the replacements of honest ciphertexts and partial decryptions across the sequence of hybrids of the simulator construction: Proposition 2 (Indistinguishability of hybrid encryption distributions). Following Table 3, let 𝑅𝑞 be the ciphertext ring, let 𝜒 be the error distribution, and let 𝖤𝗇𝖼(𝑎, 𝗌𝗄, 𝑚) = (−𝑎 ⋅ 𝗌𝗄 + 𝑒 + Δ𝑚, 𝑎) denote a fresh encryption of 𝑚 ∈ 𝑅𝑞 , where 𝗌𝗄 ∈ 𝑅𝑞 is a valid secret key, 𝑎 ← 𝑅𝑞 is uniform, and 𝑒 ← 𝜒. Let 𝜖𝖱𝖫𝖶𝖤 (𝜆) denote the single-sample RLWE distinguishing advantage. Then the following results on 𝖠𝖽𝗏 (⋅, ⋅) hold: 1. For every 𝑚 ∈ 𝑅𝑞 and every PPT distinguisher , | | | Pr[(𝖤𝗇𝖼(𝑎, 𝗌𝗄, 𝑚)) = 1]−Pr[(𝑢, 𝑎) = 1] | ≤ 𝜖𝖱𝖫𝖶𝖤 (𝜆), | | where 𝑎, 𝑢 ← 𝑅𝑞 are uniformly random. 2. For every fixed 𝑚, 𝑚′ ∈ 𝑅𝑞 , every pair of valid secret keys 𝗌𝗄, 𝗌𝗄′ ∈ 𝑅𝑞 , and every PPT distinguisher , [ ]| | | Pr[(𝖤𝗇𝖼(𝑎, 𝗌𝗄, 𝑚)) = 1] − Pr (𝖤𝗇𝖼(𝑎, 𝗌𝗄′ , 𝑚′ )) = 1 | | | ≤ 2 𝜖𝖱𝖫𝖶𝖤 (𝜆). 3. Let {𝖼𝗍𝑖 }𝑀 be a collection of 𝑀 valid encryptions of 𝑖=1 𝑚𝑖 ∈ 𝑅𝑞 under the same or different valid secret keys 𝗌𝗄𝑖 ∈ 𝑅𝑞 , where 𝖼𝗍𝑖 = (𝑏𝑖 , 𝑎𝑖 ) with 𝑏𝑖 = −𝑎𝑖 ⋅ 𝗌𝗄𝑖 + 𝑒𝑖 + Δ𝑚𝑖 , and, for all 𝑖 ≠ 𝑗, 𝑎𝑖 ≠ 𝑎𝑗 if 𝗌𝗄𝑖 = 𝗌𝗄𝑗 . Then, for every PPT distinguisher , | [ ( ) ] [ ( ) ]| | Pr  {(𝑏𝑖 , 𝑎𝑖 )}𝑀 = 1 − Pr  {(𝑢𝑖 , 𝑎𝑖 )}𝑀 = 1 | | | 𝑖=1 𝑖=1 | | ≤ 𝑀 𝜖𝖱𝖫𝖶𝖤 (𝜆), Page 26 of 29

where each 𝑢𝑖 ← 𝑅𝑞 is uniformly random. Note also that, by applying result #2, any two such collections with the same public components {𝑎𝑖 }𝑀 but possibly 𝑖=1 different plaintexts, noises, and/or secret keys are computationally indistinguishable with distinguishing gap at most 2𝑀𝜖𝖱𝖫𝖶𝖤 (𝜆). Proof. For Item 1, for any fixed 𝑚, the map 𝑥 ↦ 𝑥 + Δ𝑚 is a bijection over 𝑅𝑞 . Hence, the distribution (−𝑎⋅𝗌𝗄+𝑒+Δ𝑚, 𝑎) is obtained from the RLWE distribution (−𝑎 ⋅ 𝗌𝗄 + 𝑒, 𝑎) by adding the public offset Δ𝑚 to the first component. Likewise, if 𝑢 ← 𝑅𝑞 is uniform, then 𝑢 + Δ𝑚 is also uniform in 𝑅𝑞 . Therefore, distinguishing 𝖤𝗇𝖼(𝑎, 𝗌𝗄, 𝑚) from (𝑢, 𝑎) is equivalent to distinguishing one RLWE sample from one uniform sample [38], which is bounded by 𝜖𝖱𝖫𝖶𝖤 (𝜆). Item 2 follows from Item 1 and the triangle inequality, using the uniform distribution as an intermediate hybrid. For Item 3, use a standard hybrid argument replacing the 𝑀 samples one by one with uniform samples. Each replacement incurs loss at most 𝜖𝖱𝖫𝖶𝖤 (𝜆), and summing over positions gives 𝑀𝜖𝖱𝖫𝖶𝖤 (𝜆). Applying the argument twice yields the bound 2𝑀𝜖𝖱𝖫𝖶𝖤 (𝜆) between two such collections.

G.2. An overview of the simulator construction Let  be a static semi-honest adversary corrupting a subset of clients 𝐴 ⊆  and possibly also the Aggregator. Let 𝐻 =  ⧵ 𝐴 denote the subset of honest clients, with |𝐻 | ≥ 1. During several steps of the simulation, we fix one distinguished honest client 𝐶ℎ ∈ 𝐻 , whose simulated messages will be handled separately whenever ∑ ⃗ 1, … , 𝑤 ⃗ 𝐿 ) = 𝑖 𝜆𝑖 𝑤 ⃗𝑖 = 𝑤 ⃗ ∗. required. Recall also that 𝑓Σ (𝑤 ∑ ∗ ∗ ∗ ⃗ −𝑤 ⃗ ∗𝐴 . ⃗ 𝐴 ∶= 𝑖∶𝐶 ∈ 𝜆𝑖 𝑤 ⃗ 𝑖 and 𝑤 ⃗ 𝐻 ∶= 𝑤 We define 𝑤 𝑖 𝐴 ⃗ ∗𝐻 can be computed by the simulator solely Observe that 𝑤 ⃗ ∗ and the corrupted parties’ from the prescribed output 𝑤 inputs. We next describe the main building blocks used to construct a simulator  for the ideal execution. Access of the simulator: Since corrupted parties are semi-honest, their internal state is part of the adversarial view. Thus, the simulator has access to: (i) the inputs of corrupted parties; (ii) their secret keys; and (iii) their randomness, including encryption and decryption noises. Client-local oracle: Each honest client 𝐶𝑖 ∈ 𝐻 maintains a local oracle 𝑖 (⋅) storing the encryption noise used in the ciphertexts generated by 𝐶𝑖 (see Definition 13). During decryption, this oracle is used to cancel the ciphertextdependent noise and replace it with fresh noise sampled from the error distribution 𝜒. This feature is what allows our protocol, and therefore the simulator, to work with a fresh decryption noise independent of the ciphertext, without requiring a large 𝜆-dependent smudging noise. Main simulation steps: • Setup: (i) For corrupted parties, the simulator uses their prescribed randomness and generates the corresponding keys honestly, preserving their real internal state. (ii) For honest parties, whose internal state is not

visible to the adversary, the simulator generates fresh keys and randomness consistent with the protocol. • Input phase: (i) For each honest client 𝐶𝑖 ∈ 𝐻 ⧵ {𝐶ℎ }, the simulator first replaces the encryptions of ⃗ 𝑖 by encryptions of the same-length zero-vector 𝟎⃗ 𝑤 under the corresponding secret key, while maintaining the associated local state needed by the oracle 𝑖 (⋅). For the distinguished honest client 𝐶ℎ , the simulator instead first replaces its encryptions by encryptions ⃗ ∗𝐻 , which are subsequently replaced by enof 𝜆−1 𝑤 ℎ ⃗ Later, all these encryptions are further cryptions of 𝟎. replaced by uniformly random samples in 𝑅2𝑞 . (ii) Corrupted parties behave honestly on their actual inputs. ⃗ ∗ = 𝑓Σ (𝑤 ⃗ 1, … , 𝑤 ⃗ 𝐿) • Aggregation and decryption: Let 𝑤 be the exact output returned by the ideal functionality. Then, during decryption: – the simulator computes the partial decryptions of corrupted parties honestly using their known keys and randomness; – for all but one honest client, the simulator replaces their partial decryptions by several fresh uniform polynomials from 𝑅𝑞 ; – for one distinguished honest client 𝐶ℎ ∈ 𝐻 , the simulator programs its partial decryptions so that the final reconstructed vector equals the addition ⃗ ∗, of (i) the prescribed functionality output 𝑤 scaled by Δ, and (ii) an adequate aggregated decryption noise 𝑒⃗̃ which is independent of the honest inputs.

G.3. Hybrid simulator experiments We now define a series of hybrid games [32] used to prove the indistinguishability against  of the real and 𝑐

ideal executions; i.e., 𝖨𝖣𝖤𝖠𝖫𝑓Σ ,, ≡ 𝖱𝖤𝖠𝖫𝜋,, , where 𝑐

≡ denotes computational indistinguishability. The output of each game is just that of the environment/distinguisher . In particular, we define the following four hybrid experiments. ⊳ 𝖧𝖸𝖡0 : This is the experiment 𝖱𝖤𝖠𝖫𝜋,, ; i.e., the real execution of the protocol of Table 4 with real honest inputs. ⊳ 𝖧𝖸𝖡1 : Same as 𝖧𝖸𝖡0 , except that for every honest client 𝐶𝑖 ∈ 𝐻 , its ciphertexts10 𝑁

𝑁

𝖼𝗍𝗑 𝖼𝗍𝗑 𝐜𝐭 𝑤⃗ 𝑖 ∶= {𝑐𝑖,𝑗 }𝑗=1 = {𝖤𝗆𝗌𝗁𝖾 .𝖤𝗇𝖼(𝑎𝑗 , 𝗌𝗄𝑖 +𝑟𝑖 , 𝖻𝗅𝗈𝖼𝗄𝑤⃗ 𝑖 ,𝑗 )}𝑗=1

are modified as follows: • For each 𝐶𝑖 ∈ 𝐻 ⧵ {𝐶ℎ }, the ciphertexts 𝐜𝐭 𝑤⃗ 𝑖 are ⃗ 𝑁𝖼𝗍𝗑 . replaced by {𝖤𝗆𝗌𝗁𝖾 .𝖤𝗇𝖼(𝑎𝑗 , 𝗌𝗄𝑖 + 𝑟𝑖 , 𝟎)} 𝑗=1

𝑁𝖼𝗍𝗑 10 Updates 𝑤 ⃗ 𝑖 are encoded blockwise as {𝖻𝗅𝗈𝖼𝗄𝑤⃗ 𝑖 ,𝑗 }𝑗=1 and encrypted

across 𝑁𝖼𝗍𝗑 ciphertexts per client; see the blockwise encoding remark above.

Page 27 of 29

• For the distinguished honest client 𝐶ℎ , the ciphertexts 𝐜𝐭 𝑤⃗ ℎ are instead replaced by encryptions of 𝑣⃗ℎ ∶= ⃗ ∗𝐻 , namely 𝜆−1 𝑤 ℎ 𝑁

𝑁

𝖼𝗍𝗑 𝖼𝗍𝗑 𝐜𝐭 𝑣⃗ℎ ∶= {𝑐ℎ,𝑗 }𝑗=1 = {𝖤𝗆𝗌𝗁𝖾 .𝖤𝗇𝖼(𝑎𝑗 , 𝗌𝗄ℎ +𝑟ℎ , 𝖻𝗅𝗈𝖼𝗄𝑣⃗ℎ ,𝑗 )}𝑗=1 .

⊳ 𝖧𝖸𝖡2 : Same as 𝖧𝖸𝖡1 , except that the ciphertexts 𝐜𝐭 𝑣⃗ℎ of the distinguished honest client 𝐶ℎ are first replaced by ⃗ 𝑁𝖼𝗍𝗑 . The partial deencryptions {𝖤𝗆𝗌𝗁𝖾 .𝖤𝗇𝖼(𝑎𝑗 , 𝗌𝗄ℎ + 𝑟ℎ , 𝟎)} 𝑗=1 cryptions of honest parties are then modified as follows: • for every honest client except one distinguished party 𝐶ℎ ∈ 𝐻 , its partial decryptions are replaced by an independent and uniformly random vector of polyno𝑁 mials 𝒖 ← 𝑅𝑞 𝖼𝗍𝗑 ; • the remaining honest client’s partial decryptions are programmed so the final reconstructed value equals ∑ ∑ ⃗∗ + 𝒆̃ 𝑖 , (25) 𝒆̃ 𝑖 + Δ⋅𝑤 𝐶𝑖 ∈𝐴

𝐶𝑖 ∈𝐻

where each polynomial component of 𝒆̃ 𝑖 for all 𝐶𝑖 ∈ 𝐻 is sampled independently from 𝜒. For corrupted clients, the terms 𝒆̃ 𝑖 are those determined by their prescribed randomness, whereas the honest-client terms are unknown to the adversary. Hence, BFV decod⃗ ∗ under its correctness condition, while ing yields 𝑤 ∑ ⃗ ∗ + Δ−1 𝐿 ̃ 𝑖 . Moreover, CKKS rescaling yields 𝑤 𝑖=1 𝒆 since |𝐻 | ≥ 1, the aggregated approximation error contains at least one contribution that is fresh and independent from the adversary’s point of view. ⊳ 𝖧𝖸𝖡3 : Same as 𝖧𝖸𝖡2 , except that the honest encryptions of 𝟎⃗ are replaced by uniformly random polynomial samples in 𝑅2𝑞 . By construction, 𝖧𝖸𝖡3 coincides with 𝖨𝖣𝖤𝖠𝖫𝑓Σ ,, ; i.e., the ideal execution generated by the simulator  under the corresponding exact or approximate output convention defined above.

G.4. Indistinguishability arguments Let 𝑁𝖾𝗇𝖼𝟢 denote the number of honest ciphertexts replaced in the transition 𝖧𝖸𝖡0 → 𝖧𝖸𝖡1 , let 𝑁𝖾𝗇𝖼𝟣 denote the number of distinguished honest ciphertexts replaced in 𝖧𝖸𝖡1 → 𝖧𝖸𝖡2 , let 𝑁𝗉𝖽 denote the number of honest partial decryptions replaced in 𝖧𝖸𝖡1 → 𝖧𝖸𝖡2 , and let 𝑁𝗋𝖺𝗇𝖽 denote the number of honest ciphertexts replaced in 𝖧𝖸𝖡2 → 𝖧𝖸𝖡3 . By repeated application of Proposition 2, each of the above terms admits a bound linear in the number of replaced samples and in 𝜖𝖱𝖫𝖶𝖤 (𝜆), which is negligible in 𝜆 under the RLWE assumption [38]. We now bound each term. 𝑐

Claim 1. 𝖧𝖸𝖡0 ≡ 𝖧𝖸𝖡1 . Proof. The only difference between the two hybrids is that ⃗ 𝑖 are replaced by encryptions the honest encryptions of 𝑤 ⃗ of 𝟎 for 𝐶𝑖 ∈ 𝐻 ⧵ {𝐶ℎ }, and by encryptions of 𝑣⃗ℎ for 𝐶ℎ , under the same secret keys 𝗌𝗄𝑖 + 𝑟𝑖 and with the same

public polynomials 𝑎𝑗 . By Item 2 of Proposition 2, each such replacement changes the adversarial view by at most 2 𝜖𝖱𝖫𝖶𝖤 (𝜆). Therefore, by a standard hybrid argument [32] over the 𝑁𝖾𝗇𝖼𝟢 = 𝑁𝖼𝗍𝗑 |𝐻 | replaced honest ciphertexts, 𝖠𝖽𝗏 (𝖧𝖸𝖡0 , 𝖧𝖸𝖡1 ) ≤ 2𝑁𝖾𝗇𝖼𝟢 ⋅ 𝜖𝖱𝖫𝖶𝖤 (𝜆) = 𝗇𝖾𝗀𝗅(𝜆). 𝑐

Claim 2. 𝖧𝖸𝖡1 ≡ 𝖧𝖸𝖡2 . Proof. In 𝖧𝖸𝖡1 , the ciphertexts of all honest clients except ⃗ while those of the distinguished honest 𝐶ℎ already encrypt 𝟎, client encrypt 𝑣⃗ℎ . In 𝖧𝖸𝖡2 , the latter are also replaced by encryptions of 𝟎⃗ under the same secret key 𝗌𝗄ℎ + 𝑟ℎ and with the same public polynomials 𝑎𝑗 . By construction of the client-local oracle, the decryption shares contributed by honest parties contain fresh noise independent of the aggregated ciphertext. However, since each ciphertext and its corresponding partial decryption share secret-key and error terms, replacing the corresponding partial decryption by a uniform polynomial must be justified with respect to their joint distribution. For this purpose, for every 𝐶𝑖 ∈ 𝐻 ⧵ {𝐶ℎ } and 𝑗 ∈ {1, … , 𝑁𝖼𝗍𝗑 }, write the 𝑗-th zero-encryption as 𝖼𝗍𝑖,𝑗 = (𝑏𝑖,𝑗 , 𝑎𝑗 ), where 𝑏𝑖,𝑗 = −𝑎𝑗 (𝗌𝗄𝑖 + 𝑟𝑖 ) + 𝑒𝑖,𝑗 , and let ℎ𝑖,𝑗 = 𝜆𝑖 𝑎𝑗 𝗌𝗄𝑖 − 𝜆𝑖 𝑒𝑖,𝑗 + 𝑒̃𝑖,𝑗 denote its corresponding real partial decryption. Define 𝑦𝑖,𝑗 ∶= −𝑎𝑗 𝗌𝗄𝑖 + 𝑒𝑖,𝑗 and consider the public bijection 𝑇𝑖 (𝑏𝑖,𝑗 , ℎ𝑖,𝑗 ) = (𝑧𝑖,𝑗 , ℎ𝑖,𝑗 ), with 𝑧𝑖,𝑗 ∶= 𝜆𝑖 𝑏𝑖,𝑗 +ℎ𝑖,𝑗 = −𝜆𝑖 𝑎𝑗 𝑟𝑖 + 𝑒̃𝑖,𝑗 and inverse 𝑏𝑖,𝑗 = 𝜆−1 𝑖 (𝑧𝑖,𝑗 −ℎ𝑖,𝑗 ). Let 𝑢𝑖,𝑗 , 𝑣𝑖,𝑗 ← 𝑅𝑞 be independent and uniform. Then, three consecutive RLWE replacements, respectively for the prescribed distributions of 𝗌𝗄𝑖 , 𝑟𝑖 , and the effective key 𝗌𝗄𝑖 + 𝑟𝑖 , give

∑ block. Since 𝑑𝑗 = 𝑘 𝑧𝑘,𝑗 , this is enforced by setting 𝑧ℎ,𝑗 = ∑ 𝑑𝑗 − 𝑘≠ℎ 𝑧𝑘,𝑗 and then programming ℎℎ,𝑗 = 𝑧ℎ,𝑗 − 𝜆ℎ 𝑏ℎ,𝑗 . Since the coordinate transformations are bijective, this programming requires no additional hybrid and preserves the prescribed reconstructed value in Eq. (25). The programmed partial decryptions of the distinguished honest client are therefore distributed consistently with the target simulated execution. As in 𝖧𝖸𝖡2 , the simulator samples the fresh polynomial vectors 𝒆̃ 𝑖 independently from 𝜒 for all 𝐶𝑖 ∈ 𝐻 ; consequently, the programmed final share reveals no additional information beyond the allowed output. By Item 2 of Proposition 2, replacing the 𝑁𝖾𝗇𝖼𝟣 = 𝑁𝖼𝗍𝗑 ciphertexts of 𝐶ℎ changes the adversarial view by at most 2𝑁𝖾𝗇𝖼𝟣 ⋅ 𝜖𝖱𝖫𝖶𝖤 (𝜆). Moreover, by repeated application of Item 1 of Proposition 2, and Item 3 for the corresponding collection-wise hybrid, each replacement of a nondistinguished honest partial decryption requires the three RLWE transitions above and therefore changes the joint adversarial view by at most 3𝜖𝖱𝖫𝖶𝖤 (𝜆). Therefore, accounting for 𝑁𝗉𝖽 = 𝑁𝖼𝗍𝗑 (|𝐻 |−1) replaced honest partial decryptions yields ) ( 𝖠𝖽𝗏 (𝖧𝖸𝖡1 , 𝖧𝖸𝖡2 ) ≤ 2𝑁𝖾𝗇𝖼𝟣 + 3𝑁𝗉𝖽 ⋅𝜖𝖱𝖫𝖶𝖤 (𝜆) = 𝗇𝖾𝗀𝗅(𝜆). 𝑐

Claim 3. 𝖧𝖸𝖡2 ≡ 𝖧𝖸𝖡3 . Proof. The only difference is that the honest encryptions of 𝟎⃗ are replaced by uniformly random ciphertexts in 𝑅2𝑞 . By Item 1 of Proposition 2, each replacement of an honest encryption of 𝟎⃗ by a uniform ciphertext changes the adversarial view by at most 𝜖𝖱𝖫𝖶𝖤 (𝜆). Therefore, by a standard hybrid argument over the 𝑁𝗋𝖺𝗇𝖽 = 𝑁𝖼𝗍𝗑 |𝐻 | replaced ciphertexts, 𝖠𝖽𝗏 (𝖧𝖸𝖡2 , 𝖧𝖸𝖡3 ) ≤ 𝑁𝗋𝖺𝗇𝖽 𝜖𝖱𝖫𝖶𝖤 (𝜆) = 𝗇𝖾𝗀𝗅(𝜆).

𝑐

(𝑧𝑖,𝑗 , −𝜆𝑖 𝑦𝑖,𝑗 + 𝑒̃𝑖,𝑗 ) ≈ (𝑧𝑖,𝑗 , 𝑢𝑖,𝑗 ) 𝑐

≈ (𝑣𝑖,𝑗 , 𝑢𝑖,𝑗 ) 𝑐

≈ (𝜆𝑖 𝑏𝑖,𝑗 + 𝑢𝑖,𝑗 , 𝑢𝑖,𝑗 ). In the first transition, when 𝑦𝑖,𝑗 is replaced by a uniform polynomial independent of 𝑎𝑗 , the polynomial component −𝜆𝑖 𝑦𝑖,𝑗 + 𝑒̃𝑖,𝑗 remains uniform even conditioned on (𝑎𝑗 , 𝑟𝑖 , 𝑒̃𝑖,𝑗 ), and is therefore independent of 𝑧𝑖,𝑗 ; the second transition replaces the secret-dependent component 𝑧𝑖,𝑗 of the RLWE sample associated with 𝑟𝑖 by a uniform polynomial; and the third restores exactly the original ciphertext distribution using RLWE under 𝗌𝗄𝑖 + 𝑟𝑖 . Applying 𝑇𝑖−1 𝑐

therefore yields (𝑏𝑖,𝑗 , ℎ𝑖,𝑗 ) ≈ (𝑏𝑖,𝑗 , 𝑢𝑖,𝑗 ). Importantly, the above transformations are applied to the joint honest view rather than marginally. By the zero-sharing reconstruction equation, 𝑟ℎ is determined by the remaining zero-shares {𝑟𝑖 }𝑖≠ℎ ; conditioned on the corrupted parties’ setup view, their zero-shares are fixed, and any remaining dependence on the non-distinguished honest zero-shares is preserved in the transformed coordinates. For each block 𝑗, let 𝑑𝑗 denote the prescribed reconstructed value in that Page 28 of 29

G.5. Conclusion of the proof of Theorem 1 Combining the above bounds via the triangle inequality [32], we obtain: 𝖠𝖽𝗏 (𝖧𝖸𝖡0 , 𝖧𝖸𝖡3 ) ≤ 𝖠𝖽𝗏 (𝖧𝖸𝖡0 , 𝖧𝖸𝖡1 ) + 𝖠𝖽𝗏 (𝖧𝖸𝖡1 , 𝖧𝖸𝖡2 ) + 𝖠𝖽𝗏 (𝖧𝖸𝖡2 , 𝖧𝖸𝖡3 ) ( ≤ 2𝑁𝖾𝗇𝖼𝟢 + 2𝑁𝖾𝗇𝖼𝟣 ) + 3𝑁𝗉𝖽 + 𝑁𝗋𝖺𝗇𝖽 ⋅ 𝜖𝖱𝖫𝖶𝖤 (𝜆) ≤ 𝗇𝖾𝗀𝗅(𝜆). Since 𝖧𝖸𝖡0 corresponds to the real execution and 𝖧𝖸𝖡3 to the ideal execution produced by the simulator , the protocol 𝜋𝑓Σ provides simulation-based input privacy for the aggregation functionality 𝑓Σ in the semi-honest model, with correctness interpreted according to the corresponding exact or approximate output convention. Explicit bounds: We now make the dependence on the number of honest clients and the RLWE distinguishing advantage explicit. If we write 𝐿𝐻 ∶= |𝐻 | for the number of honest clients, we obtain:

• 𝖧𝖸𝖡0 → 𝖧𝖸𝖡1 : 𝑁𝖾𝗇𝖼𝟢 = 𝐿𝐻 𝑁𝖼𝗍𝗑 ciphertexts replaced; • 𝖧𝖸𝖡1 → 𝖧𝖸𝖡2 : 𝑁𝖾𝗇𝖼𝟣 = 𝑁𝖼𝗍𝗑 ciphertexts and 𝑁𝗉𝖽 = (𝐿𝐻 − 1)𝑁𝖼𝗍𝗑 partial decryptions replaced; • 𝖧𝖸𝖡2 → 𝖧𝖸𝖡3 : 𝑁𝗋𝖺𝗇𝖽 = 𝐿𝐻 𝑁𝖼𝗍𝗑 ciphertexts replaced. Substituting into the bound above yields: 𝖠𝖽𝗏 (𝖧𝖸𝖡0 , 𝖧𝖸𝖡3 ) ≤ (6𝐿𝐻 − 1) 𝑁𝖼𝗍𝗑 𝜖𝖱𝖫𝖶𝖤 (𝜆). Using ⌈ the trivial⌉ bound 𝐿𝐻 ≤ 𝐿 and recalling that #𝖬𝗈𝖽𝖾𝗅𝖯𝖺𝗋𝖺𝗆𝗌 , we obtain: 𝑛(𝜆)

𝑁𝖼𝗍𝗑 =

⌈

⌉ #𝖬𝗈𝖽𝖾𝗅𝖯𝖺𝗋𝖺𝗆𝗌 𝖠𝖽𝗏 (𝖧𝖸𝖡0 , 𝖧𝖸𝖡3 ) ≤ 6𝐿 𝜖𝖱𝖫𝖶𝖤 (𝜆). 𝑛(𝜆) Security discussion: Importantly, the distinguishing advantage of the overall simulation reduces directly to the RLWE distinguishing advantage 𝜖𝖱𝖫𝖶𝖤 (𝜆), up to a multiplicative factor independent of any additional noise parameters. In contrast to the protocol of [5], our construction does not rely on 𝜆-dependent large smudging noise to decorrelate the simulated decryption shares. Instead, the client-local oracle ensures that fresh decryption noise is injected independently of the ciphertexts, allowing all hybrid transitions to be justified solely under the RLWE assumption [38]. As a result, the overall security follows directly from the hardness of RLWE, without introducing additional approximation losses stemming from smudging parameters. In particular, the CKKS approximation affects only correctness and the form of the output, while the simulation-based privacy bound remains negligible under RLWE.

Page 29 of 29

Related documents

• Homomorphic encryption for privacy-preserving data aggregation in data spaces.#263139
• GoldenRetriever: Non-Interactive Homomorphic Encrypted Retrieval for Privacy-Preserving RAG#422201
• Efficient Verifiable Protocol for Privacy-Preserving Aggregation in Federated Learning#177285
• Filters in abstract aggregation with infinite sequences of signals#427317
• Homomorphic Aggregation of Continuous-Variable GKP States#620456