arXiv CSopen access

Giskard : Byzantine Robust and Confidential Aggregation for Large-Scale Decentralized Learning

arXiv:2606.19129v1 [cs.CR] 17 Jun 2026

Giskard: Byzantine Robust and Confidential Aggregation for Large-Scale Decentralized Learning Ousmane Touat

César Sabater

[email protected] INSA Lyon, LIRIS, CNRS Villeurbanne, France

[email protected] INSA Lyon, LIRIS, CNRS Villeurbanne, France

Mohamed Maouche

Sonia Ben Mokhtar

[email protected] INRIA, INSA Lyon Villeurbanne, France

[email protected] INSA Lyon, LIRIS, CNRS Villeurbanne, France

Abstract

Keywords

Dealing simultaneously with confidentiality and Byzantine behaviors in decentralized learning is a challenging problem. Indeed, in decentralized learning, clients train a machine learning model while keeping their data locally and share their model parameters or gradients with a set of neighbors. While enforcing confidentiality calls for hiding the exchanged model parameters/gradients (e.g., by using cryptographic techniques), dealing with Byzantine contributions often requires inspecting the latter. Hence, most research works address these objectives separately. A recent line of work proposes to employ secure multi-party computation (MPC) to implement robust aggregators against model poisoning, thereby enforcing both confidentiality and Byzantine resilience. However, these solutions scale badly: they either require all-to-all communication between participants or delegate the entire computation to a small subset, whose computational and communication load grows proportionally with the size of the network. In this paper, we present Giskard, a protocol for confidential and Byzantine-robust decentralized aggregation. Giskard organizes 𝑛 parties into a tree of committees of size 𝑂 (log 𝑛) and evaluates a coordinate-wise approximate median via a committee-adapted distributed binary search over the value domain, using BGW-style MPC within each committee. We assess Giskard both theoretically by proving its security and confidentiality properties and experimentally through extensive experiments involving up to one million participants. Compared to its closest competitors, Giskard reduces per-party communication complexity asymptotically while exhibiting comparable model utility under up to 𝑛/4 Byzantine parties.

Decentralized learning, Byzantine robustness, Secure multiparty computation, Privacy-preserving aggregation, Distributed machine learning

CCS Concepts • Computing methodologies → Machine learning; Distributed algorithms; • Security and privacy → Cryptography; Privacypreserving protocols. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. Conference’17, Washington, DC, USA © 2026 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-x-xxxx-xxxx-x/YYYY/MM https://doi.org/10.1145/nnnnnnn.nnnnnnn

ACM Reference Format: Ousmane Touat, César Sabater, Mohamed Maouche, and Sonia Ben Mokhtar. 2026. Giskard: Byzantine Robust and Confidential Aggregation for LargeScale Decentralized Learning. In . ACM, New York, NY, USA, 17 pages. https://doi.org/10.1145/nnnnnnn.nnnnnnn

1

Introduction

Federated learning (FL) was initially promoted as a privacy-preserving alternative to centralized training, since raw data remains on users’ devices [39]. However, subsequent work has shown that FL is vulnerable to a wide range of attacks, many of which exploit the privileged role of the aggregation server [41]. This centralization also creates a governance bottleneck: the entity operating the server retains effective control over the learning process, including the choice of the training objective, model architecture, aggregation rule. As a result, FL may decentralize data storage, but it does not decentralize decision-making. From this perspective, decentralized learning, where participants interact directly in a peer-to-peer manner [23, 35] appears to be an appealing alternative as it eliminates the need for a trusted central all-mighty orchestrator while preserving the convergence properties of centralized training [1]. Nevertheless, decentralized learning systems face several challenges that hinder their wider adoption. First, these systems are inherently vulnerable to Byzantine participants, i.e., malicious or faulty nodes that submit arbitrary, manipulated, or erroneous model updates with the intent to corrupt the global model [19]. Unlike in FL, where the server can act as a gatekeeper (albeit a trusted and potentially compromised one), the absence of a central authority in decentralized settings makes model poisoning attacks harder to detect and mitigate. An orthogonal yet equally critical challenge concerns the confidentiality of participants’ contributions. Even in the absence of a central server, nodes must exchange model updates (gradients or parameter vectors) that can leak sensitive information about their training data. Examples of such attacks include membership inference attacks [40, 43, 60], where an adversary determines whether a particular record was used during training and more critically, gradient inversion attacks [25], whereby an adversary reconstructs

Conference’17, July 2017, Washington, DC, USA

raw training samples with high fidelity directly from the exchanged gradients. These two challenges have been extensively studied in isolation, each giving rise to its own line of defenses. On the one hand, robust aggregation functions have been devised to deal with Byzantine contributions. These aggregation functions are designed to limit the influence of malicious updates by filtering outliers or computing statistics robust to a fraction of corrupted inputs, such as coordinatewise Median, Trimmed Mean, or Krum [3, 27]. These methods offer provable robustness guarantees up to a bounded fraction of Byzantine participants. On the other hand, protecting participants against inference attacks has been approached through two main strategies: differential privacy [53], which introduces calibrated noise to bound what an adversary can infer, or cryptographic techniques such as Secure Aggregation [38] or homomorphic encryption [59], which ensure that individual updates are never exposed in the clear. However, it is well known that these two challenges are fundamentally in tension: Byzantine-resilient aggregation functions require inspecting and comparing individual contributions, while confidentiality mechanisms are designed to hide them. This conflict limits the applicability of naive combinations. Approaches that combine robust aggregators with DP mechanisms face impossibility results that bound the simultaneous achievability of privacy, robustness, and utility [4]. Alternatively, implementing robust aggregation inside cryptographic protocols (using MPC or homomorphic computation) is a natural direction, but incurs a heavy computational and communication cost: aggregation rules such as Trimmed Mean or coordinate-wise Median inherently require sorting and comparison operations, which are notoriously expensive to implement in encrypted form. Prior work has explored MPC-based robust aggregation in federated settings [17, 26, 37, 46], where a central coordinator can structure the computation. Extending these guarantees to fully decentralized systems is considerably harder. Existing decentralized proposals [20, 21] involve either all nodes or a randomly elected committee within a shared MPC instance to perform robust aggregation. These designs yield all-to-all or all-to-committee communication topologies, where the per-node communication load grows at least linearly with the number of participants. This constitutes a fundamental scalability bottleneck that renders them impractical for large-scale deployments. Our work: In this paper, we aim at bridging this gap by proposing Giskard, a practical, robust and confidential decentralized learning system. To reach this objective we build on scalable MPC systems designed for the malicious setting [42, 58], which distribute secure computation across small, overlapping committees to achieve sub-linear per-party communication. A key technical insight of our work is a new formulation of coordinate-wise median as a binary-search problem: instead of evaluating the median through generic sorting or comparison circuits, we reduce robust aggregation to a sequence of secure counting operations. This insight allows us to specialize the committee-based architecture into a lightweight hierarchical aggregation protocol that is both communication-efficient and cryptographically strong while being robust to Byzantine contributions. As a result, Giskard is a scalable, load-balanced, UC-secure decentralized learning system

Ousmane Touat, César Sabater, Mohamed Maouche, and Sonia Ben Mokhtar

that tolerates up to 𝑛/4 byzantine nodes via a hierarchical aggregation tree, matching the robustness threshold of coordinate-wise median. Our contributions are summarized as follows: • We propose Giskard, a novel robust and confidential decentralized learning protocol that scales up to millions of parties. • We theoretically prove that Giskard is UC-secure. • We analyze Giskard’s communication cost and show that the worst per-party communication is polylogarithmic in 𝑛 while its closest competitors have worst per-party communication complexity in the order of 𝑂 (𝑛 log2 𝑛). • We experimentally evaluate Giskard on MNIST and CIFAR10 and at network sizes up to 𝑛 = 106 . Giskard reduces worst-case per-party communication by three orders of magnitude over the closest competitor, while its robust aggregation function matches the utility of formally robust aggregators. The code is publicly available1 . This paper is structured as follows. We first present the collaborative learning setting, threat model, design goals, and technical preliminaries in Section 2. We then present the full Giskard protocol, its security and robustness analyses, and its communication cost in Section 3. We empirically validate our theoretical analysis in Section 4. Finally, we discuss related work in Section 5 before concluding in Section 6.

2

Background and Model

This section introduces the setting in which Giskard operates and the components on which it is built. We first formalize the collaborative learning problem (§2.1), describe our system and threat models (§2.2–§2.3), and the design goals that Giskard must satisfy (§2.4). We then recall the three technical components our construction relies on, that are robust aggregation (§2.5), secure multi-party computation (§2.6) and committee formation (§2.7).

2.1

Collaborative Learning

Collaborative learning is a category of distributed learning where the objective is to learn a statistical/learning model from independent computing units, each holding its own local data. In particular, here we consider a set of parties P = {1, . . . , 𝑛}, each holding a local data set D𝑖 , whose common objective is to learn a shared model 𝜃 ★ that minimizes the following loss function: 𝑛

L (𝜃 ★) =

1 ∑︁ 𝑙𝑖 (𝜃 ★, D𝑖 ), |D| 𝑖=1

(1)

Ð where 𝑙𝑖 (,i)s the local loss function of party 𝑖 and D = 𝑖 ∈ P D𝑖 as defined in [11]. There are different ways to implement this framework, for example in federated learning [39], where there is a server whose role is to aggregate the models trained locally by the parties in the system, via an averaging function. In any case, one might wonder what would happen if, in such a system, parties began to deviate from the given protocol or send corrupted models. 1 https://anonymous.4open.science/r/Giskard-ByzRobustConfidentialDL-B3E9

Giskard: Byzantine Robust and Confidential Aggregation for Large-Scale Decentralized Learning

2.2

System and Network Model

We model our distributed learning system as a set of 𝑛 parties, P = {𝑃1, . . . , 𝑃𝑛 }. The parties jointly execute a prescribed protocol Π to collaboratively learn a global model. We partition P into two disjoint sets: the honest parties H , which strictly follow Π, and the adversarial parties A (also called Byzantine parties), with H ∪ A = P and H ∩ A = ∅. We assume a synchronous communication network in which parties interact in rounds, and a public-key infrastructure (PKI) that authenticates point-to-point channels; TLS provides channel confidentiality.

(3) Correctness and Verifiability. Any deviation from the prescribed protocol must either be detected and rejected or have a provably bounded influence on the final output. This ensures that neither faulty nor malicious participants can silently bias the outcome of the aggregation. (4) Scalability. The per-party communication overhead must grow sublinearly in the total number of participants, ensuring that the protocol remains practical at cross-device scale (concretely, for deployments involving 𝑛 ≥ 104 ).

2.5 2.3

Threat Model

We consider a static, computationally bounded adversary A who corrupts a set of parties of size 𝑓 = |A| prior to protocol execution. The adversarial objective is to undermine the confidentiality and correctness of the decentralized training process. The threat model is independent of the underlying ML algorithm: Giskard inherits its robustness guarantees directly from formalized distributed learning robustness guarantees (see [3, 29, 44]), which apply to any distributed gradient-based optimizer regardless of model architecture or task. The confidentiality guarantees apply to any context: they protect any deployment in which local model updates must remain hidden from external parties. Attacker capabilities. Giskard operates under a hybrid threat model in which corrupted parties may deviate along two axes: • Protocol deviation. Corrupted parties behave arbitrarily: they may deviate from Π by sending malformed shares, colluding to reconstruct shared secrets, or attempting to abort the protocol. • Model poisoning. Even when following Π faithfully, corrupted parties may submit adversarially crafted model updates for aggregation.

Conference’17, July 2017, Washington, DC, USA

Model Poisoning Attacks & Defense

2.5.1 Threat to Collaborative Learning Model. While averaging is the most common aggregation policy in collaborative learning, it is also the most vulnerable to cases where parties fail to send the prescribed model update. Such failures include parties that fail to respond, have their updates corrupted by faults, or adversarially submit crafted updates that distort the aggregate. We refer to this class of attacks as model poisoning attacks [8, 54]. 2.5.2 Defense against Model Poisoning Attacks. The literature gives a wide range of defenses against model poisoning. A first class restricts client updates to a bounded domain, preventing deviations far from the mean [28]. A second class deterministically detects and excludes corrupted updates from aggregation [16]. A third class replaces averaging with robust statistical functions that tolerate a fraction of corrupted inputs. We focus on this third class, which is supported by the theoretical framework described below.

This model captures both coordinated attacks and non-malicious failures such as parties submitting corrupted or missing values due to technical faults.

Definition 1. (𝑓 , 𝜅)-Byzantine robustness [3] Let 𝑓 = 𝜌𝑛 with 𝜌 ≤ 12 and 𝜅 ≥ 0, the aggregation rule 𝐹 is (𝑓 , 𝜅)-Byzantine robust if for any (𝑥 1, . . . , 𝑥𝑛 ) ∈ R𝑁 and any subset 𝑆 ⊆ [𝑛] of size n-f the output of F is bounded as follow : 𝜅 ∑︁ ∥𝐹 (𝑥 1, . . . , 𝑥𝑛 ) − 𝑥𝑆 ∥ ≤ ∥𝑥𝑖 − 𝑥𝑆 ∥ 2 (2) |𝑆 | 𝑖 ∈𝑆 Í where 𝑥𝑆 = |𝑆1 | 𝑖 ∈𝑆 𝑥𝑖 .

Corruption bound. We require 𝑓 < 𝑛/4, a corruption fraction realistic for practical large-scale decentralized deployment. Two independent constraints pin this bound: a per-committee threshold 𝜏 < 𝑚/4 on our committee-level protocol, and the breakdownpoint analysis of our robust aggregator. Both constraints translate to 𝑓 < 𝑛/4 globally as we derive them in Section 3.

Such an aggregator’s output cannot deviate from the average of honest parties regardless of adversarial input, including against omniscient adversaries who can craft vectors from full knowledge of the honest contributions. Assuming standard regularity conditions on the loss function and honest-gradient bounded heterogeneity, a (𝑓 , 𝜅)-Byzantine robust aggregation rule yields the following convergence guarantee:

2.4

Design Goals

Our primary objective is to ensure secure and reliable decentralized learning even when a subset of parties acts maliciously. Specifically, Giskard is designed to enforce the following four goals: (1) Byzantine Robustness. The global model must remain close to the aggregate of honest participants’ updates, even under arbitrary or coordinated model and data poisoning attacks. (2) Confidentiality. Individual updates must remain hidden throughout the protocol execution. In particular, no party or coalition of corrupted parties should be able to reconstruct, distinguish, or infer any participant’s contribution beyond what is revealed by the aggregate output.

Theorem 1 (Allouah et al. [3]). Assuming that L is L-smooth, a distributed gradient descent using a (𝑓 , 𝜅)-Byzantine robust aggregation rule give the following : 4(L (𝜃 0★) − L∗ ) 𝑇 with 𝜁 the variance of honest gradients, T the current iteration of D-GD, and L∗ the optimal loss value. ∥∇L (𝜃 ★)∥ 2 ≤ 4𝜅𝜁 +

Examples of (𝑓 , 𝜅)-Byzantine robust aggregators include coordinatewise estimators (trimmed mean and median [57]) and geometrybased aggregators (Krum and Multi-Krum [57], Geometric Median [45]).

Conference’17, July 2017, Washington, DC, USA

2.6

Secure MPC Primitives

Our construction relies on secure multi-party computation (MPC) [55]: a set of parties 𝑃 = {1, . . . , 𝑛}, each holding a private input 𝑥𝑖 ∈ I, jointly compute a public function 𝑓 : I𝑛 → O𝑛 such that party 𝑖 learns only its own output 𝑓𝑖 ((𝑥 𝑗 )𝑛𝑗=1 ) ∈ O. We instantiate this with secret-sharing-based MPC in the honest-majority setting, building on Shamir’s scheme and the BGW verifiable variant. We recall both schemes below. 2.6.1 Secret Sharing. Let F𝑞 be a field of size at least 𝑞 > 𝑛. A (𝑡, 𝑛)-secret sharing scheme allows a party, known as a dealer, to distribute a secret 𝑠 ∈ F𝑞 , among 𝑛 parties such that any 𝑡 parties can reconstruct the secret, while any subset of 𝑡 − 1 parties learns nothing. Most such schemes derive from Shamir’s construction [48]: the dealer samples a polynomial 𝑓 (𝑥) ∈ F𝑞 [𝑥] of degree 𝑡 − 1 with 𝑓 (0) = 𝑠, and distributes the evaluation 𝑠𝑖 = 𝑓 (𝑖) to party 𝑃𝑖 . Reconstruction proceeds by Lagrange interpolation over any authorized subset S with |S| ≥ 𝑡. A key property we exploit is linearity: given shares of 𝑎 and 𝑏, a share of 𝑎 + 𝑏 is obtained by locally summing the two shares, with no further interaction between MPC parties. 2.6.2 BGW VSS scheme. Verifiable Secret Sharing (VSS) extends Shamir sharing to malicious dealers and parties: honest parties can reject inconsistent shares or reconstruct the secret despite malformed ones. We use the BGW scheme [7, 12] and rely on three of its protocols, sketched below. VSS-Share. The dealer samples a random bivariate polynomial 𝐵(𝑥, 𝑦) ∈ F𝑝 [𝑥, 𝑦] of degree 𝑡 − 1 with 𝐵(0, 0) = 𝑠 and sends 𝐵(𝑥, 𝑖), 𝐵(𝑖, 𝑦) to each party 𝑃𝑖 . A pairwise consistency check then guarantees that every honest party either holds a valid share of 𝑠 on a polynomial of degree 𝑡 − 1 , or the dealer is disqualified. Multiply. Given shares of 𝑎 and 𝑏 on polynomials of degree 𝑡 − 1, parties first multiply locally, obtaining a share of 𝑎 · 𝑏 on a degree-2(𝑡 − 1) polynomial. They then verifiably subshare the products and evaluate a fixed linear combination, yielding a fresh degree-(𝑡 − 1) share of 𝑎 · 𝑏. Reconst. Each party broadcasts its share to the reconstructing set. Reed–Solomon decoding over 𝑛 ≥ 3𝑡 + 1 points recovers 𝑠, tolerating up to 𝑡 corrupted or missing shares. Theorem 2 (Asharov and Lindell [7]). The BGW protocol is unconditionally secure against a static malicious adversary corrupting up to 𝑡 < 𝑛/3 parties, with a straight-line black-box simulator. 2.6.3 Universal Composability. We prove security in the Universal Composability (UC) framework of Canetti [15]. A cryptographic task is specified by an ideal functionality F : an interactive trusted machine that receives inputs from the parties, performs the prescribed computation, returns outputs, and exposes to the adversary only the leakage the specification permits. A protocol Π UC-realizes F if, for every for every probabilistic polynomial-time (PPT) adversary A attacking a real execution of Π, there exists a PPT simulator S such that no PPT environment Z can distinguish the real execution from the ideal execution of F with S. The environment Z chooses the parties’ inputs, observes their outputs, and interacts with the adversary throughout the

Ousmane Touat, César Sabater, Mohamed Maouche, and Sonia Ben Mokhtar

execution. The guarantees encoded in F : input confidentiality, output correctness, and any explicitly modelled leakage or abort behaviour, therefore transfer to Π. By the universal composition theorem, they are preserved when Π is invoked as a sub-protocol inside an arbitrary larger system. Each sub-protocol (VSS-Share, Multiply, Reshare, . . . ) is shown to UC-realize its own functionality, and Giskard is analysed in the (FVSS-Share , FMultiply , FReshare , . . . )-hybrid model, from which UCsecurity of the composed protocol follows.

2.7

Seed Agreement and Committee Formation

To make our method scalable, we need to be able to form committees of a small number of parties that guarantee, with an extremely high probability, that they contain a sufficient proportion of honest parties. This requires the robust generation of a random seed, followed by the use of a public function so that each party can sample the committee membership. This is a standard construction that has been extensively studied and which we therefore reuse [42, 58], based on the composition of scalable Byzantine Agreement [14, 31, 32], which gives the following. Lemma 1 (Common Reference String Generation). For all 𝜖 > 0, there exists a protocol such that for 𝑛 parties in a synchronous network with authenticated channels, against a static adversary corrupting at most (1/4 − 𝜖)𝑛 parties: • With probability 1 − 𝑛 −𝑐 for any constant 𝑐, all honest parties agree on a common string seed of length Θ(log 𝑛) with at least a 2/3 + 𝜖 fraction of uniformly random bits. • The per-party communication cost is polylog(𝑛) bits. • The round complexity is polylog(𝑛). The proof is adapted from composing [32] with [14, Lemma 9]. The protocol is run only once during system setup. Its output seed deterministically defines the tree topology via the public random functions. This topology is then reused across all subsequent operations, so no further BA invocations are needed per-operation.

3 The Giskard Protocol 3.1 Overview and Intuition Giskard is a decentralized protocol that replaces the central parameter server in Federated Robust D-SGD. In the classical setting with 𝑛 parties, each party 𝑗 holds a local dataset D 𝑗 . At each round, parties send locally computed gradients to a parameter server, which applies a robust aggregator (e.g., coordinate-wise median) and broadcasts the updated model 𝜃 (𝑡 +1) . Giskard performs this robust aggregation in a fully decentralized manner: no party reveals its individual gradient vector in the clear, and the aggregation workload is distributed across multiple committees rather than concentrated at a single server. The result is a protocol that jointly achieves confidentiality, Byzantine robustness and load balancing. Specifically, Giskard computes the coordinate-wise median via binary search over the value domain: at each iteration, every party compares its local vector to a current pivot and secret-shares the resulting bit vector; the system then aggregates these bits to determine the next pivot. The core primitive is therefore a secure, scalable counter invoked ⌈log2 (2𝑢/𝑞)⌉ times, where 𝑢 is the domain size, and 𝑞 the precision.

Giskard: Byzantine Robust and Confidential Aggregation for Large-Scale Decentralized Learning

In standard MPC structures (all-to-all or all-to-committee), the secure aggregation step imposes a heavy computational burden on the parties responsible for it. To address this load imbalance, Giskard generates multiple committees arranged in a 𝑘-ary tree of depth 𝐿, where each level is assigned a distinct role as depicted in Figure 1: • Leaves (depicted as Level 0 in Figure 1) – all 𝑛 parties. Each compares its local vector to the current pivot coordinatewise and secret-shares the resulting bit vector to its assigned base committee. • Base committees (depicted as Level 1 in Figure 1) – each receives shares from 𝑛/𝑘 𝐿 leaves, validates share domain and well-formedness, sums them, and forwards re-shared sums to its parent. • Intermediate committees (depicted as Levels 2 to 𝐿−1 in Figure 1) – receive shares from 𝑘 child committees, convert and re-aggregate, forward upward. • Root committee (depicted as Level 𝐿 in Figure 1) – performs final checks and aggregation, reconstructs the count in the clear, selects the next pivot, and disseminates it down the tree. After aggregating the count, the latter is revealed and from that the next pivot is chosen before being sent down the tree so that every parties get the updated pivot for the next iteration. The protocol terminates after 𝑁 iter = ⌈log2 (2𝑢/𝑞)⌉ iterations, at which point the median is disseminated via the same tree.

3.2

Sub-Protocols

We now detail the three sub-protocols invoked by Giskard (Algorithm 1): BuildTree (line 1), InputShare (line 5), and Reshare (line 9). 3.2.1 BuildTree for Topology generation. The first step is a onetime protocol that randomly generates the communication topology. All honest parties agree on their arrangement within a 𝑘-ary tree of depth 𝐿: the leaves represent individual parties, and each internal node is a well-constructed committee, a group of 𝑚 parties with fewer than 𝑚/4 corrupted members. A single party may belong to multiple committees. Once the topology is fixed, each party learns the base committee it is assigned to, the internal committees it belongs to, and the membership of those committees. By Theorem 1, a seed-agreement protocol yields an unpredictable string; from this seed, two public pseudorandom functions determine committee membership and leaf assignment. Committee membership. For each tree level ℓ ∈ {1, . . . , 𝐿}, we derive a permutation 𝜋ℓ of [𝑛] by Fisher–Yates shuffling seeded with 𝐻 (seed ∥ ℓ), where 𝐻 is a public hash function modeled as a random oracle. The committees at level ℓ are the 𝑘 𝐿−ℓ disjoint 𝑚blocks in the prefix of 𝜋ℓ . By construction, every party sits in at most one committee per level, so in the worst case a party participates in 𝐿 committees, one per level. Within any level, each committee is marginally a uniformly random 𝑚-subset of [𝑛], so per-committee corruption follows Hyp(𝑛, 𝑓 , 𝑚); the global failure probability is bounded by a union bound over all committees. Leaf assignment. Each party 𝑖 ∈ [𝑛] is assigned to leaf position 𝜋𝐿 (𝑖). The base committee of party 𝑖 is the level-(𝐿 − 1) committee whose 𝑘 children include leaf 𝜋𝐿 (𝑖), i.e., committee ⌈𝜋𝐿 (𝑖)/𝑘⌉ in

Conference’17, July 2017, Washington, DC, USA

Algorithm 1 Giskard: secure Byzantine-robust coordinate-wise median Input: Tree T (𝑘-ary, depth 𝐿); committee size 𝑚 = 𝑂 (log 𝑛); threshold 𝜏 = ⌊(1/4 − 𝜖)𝑚⌋; precision 𝑞; value-domain bound 𝑢 Input: Each leaf 𝑗 ∈ [𝑛] holds private x 𝑗 ∈ R𝐷 Output: Coordinate-wise median 𝑀ˆ ∈ R𝐷 — Setup (once) — 1: Run BuildTree; instantiate T — Median computation (each FL round) — 2: Left ← −𝑢 · 1; Right ← 𝑢 · 1 3: p1 ← (Left + Right)/2 4: for 𝑡 = 1, . . . , 𝑁 iter do — Phase 1: input sharing — 5: Each leaf 𝑗 runs InputShare(x 𝑗 , p𝑡 ) → C𝑗 ⊲ Prot. 1 6: Each 𝑃𝑖 ∈ C𝑗 : verify and aggregate → 𝝈 𝑖 — Phase 2: tree resharing — 7: for ℓ = 1 to 𝐿 − 1 do 8: for each Cch → Cpa in parallel do 9: Run Reshare(Cch, Cpa ) ⊲ Prot. 2 10: end for 11: Cross-child aggregation at each Cpa : Í ′ 𝝈 𝑟 ← ch 𝝈 𝑟,ch for each 𝑃𝑟′ ∈ Cpa 12: end for — Phase 3: reconstruction — 13: count ← VSS-Reconst({𝝈 𝑟 }𝑟 ∈ C𝐿 ) — Phase 4: broadcast and update — 14: C𝐿 updates (Left, Right) coordinate-wise from count and p𝑡 15: C𝐿 broadcasts p𝑡 +1 ← (Left + Right)/2 down the tree 16: end for ˆ ← (Left + Right)/2; broadcast down the tree 17: 𝑀 ˆ 18: return 𝑀

the level-(𝐿 − 1) ordering. Since 𝜋𝐿 is a permutation, every party occupies exactly one leaf and every leaf is occupied by exactly one party. We call this protocol BuildTree. It includes the seed-agreement subprotocol and the local committee-membership and leaf-assignment computations. The benefit of this topology is most pronounced when committee size is small relative to 𝑛. We show that such a tree exists under global corruption bounded by (1/4 − 𝜖)𝑛: Theorem 3. Against a static adversary corrupting at most (1/4−𝜖)𝑛 parties, BuildTree produces a 𝑘-ary tree of depth 𝐿 in which every committee has size 𝑚 = 𝑂 (𝜖 −2 ln 𝑛) and fewer than 𝑚/4 corrupted members, with probability 1 − 𝑛 −𝑐 for any constant 𝑐. Proof sketch. Let seed be the output of the seed-agreement protocol (Lemma 1) Since corruption is static and fixed before seed is sampled, each committee is a uniformly random 𝑚-subset of [𝑛], and its corruption count follows Hyp(𝑛, 𝑓 , 𝑚). A Hoeffding reduction [24] to Bin(𝑚, 𝑓 /𝑛) followed by a Chernoff bound with 𝑓 /𝑛 = 1/4 − 𝜖 gives Pr[𝑋 ≥ 𝑚/4] ≤ exp(−2𝜖 2𝑚/(3 + 4𝜖)). Unionbounding over the 𝑂 (𝑛) committees and solving for the desired 𝑛 −𝑐 failure probability yields 𝑚 = 𝑂 (𝜖 −2 ln 𝑛). Full proof in Appendix C.3. □

Conference’17, July 2017, Washington, DC, USA

Ousmane Touat, César Sabater, Mohamed Maouche, and Sonia Ben Mokhtar

Phases 3–4 reveal global count, broadcast 𝑝𝑡 +1

COM Σ

Level 𝐿

Σ

Σ

···

···

.. .

.. .

.. .

.. . broadcast 𝑝𝑡 +1

Phase 2 Í verify, aggregate b 𝑗 , re-share upward

···

C1′ Σ

Σ

···

C𝑎′

Σ

Σ

Σ

Σ

C𝑏′ Σ

···

 

𝑃2

· · · 𝑃𝑛/𝑏

x1

x2

· · · x𝑛/𝑏

···

C𝑎  



𝑃1

 Σ: shared partial count

Σ

···

···

C1 Phase 1 clients hold x 𝑗 , compare 𝑥 𝑗,𝑑 < 𝑝𝑡,𝑑 , share [b 𝑗 ]

Σ

Level 2

···



𝑃𝑖

𝑃𝑖+1 · · ·𝑃𝑖+𝑛/𝑏

x𝑖

x𝑖+1 · · ·x𝑖+𝑛/𝑏

C𝑏 

···

Level 1  [b 𝑗 ]: shared bit vector

 

𝑃𝑛−𝑛/𝑏· · · 𝑃𝑛−1

𝑃𝑛

x𝑛−𝑛/𝑏· · · x𝑛−1

x𝑛

Level 0

Figure 1: Giskard secure median computation. The 𝑛 parties 𝑃1, . . . , 𝑃𝑛 are partitioned across 𝑏 = 𝑛/𝑘 𝐿 base committees C1, . . . , C𝑏 , each of size 𝑚. Each base committee receives 𝑛/𝑏 bit-vector shares from its assigned parties and aggregates them into a partial count. Partial counts are re-shared upward through 𝐿 levels of 𝑘-ary aggregation to the root committee COM, which broadcasts the next threshold 𝑝𝑡 +1 downward (dashed).

Committee Size (m)

The bound above is loose. Figure 2 reports a tighter numerical evaluation at target Pr[failure] = 10−5 , showing that the required committee size shrinks as the gap between the global corruption fraction and the 1/4 per-committee requirement widens, and that for 𝑓 /𝑛 ∈ [0, 1/5] it remains stable as the network size grows. 106

n = 1,000 n = 10,000 n = 100,000

105

n = 1,000,000 f = n/4

104 103 102 0

5 10 15 20 Global Corruption Percentage (\%)

25

Figure 2: Minimum committee size for varying global corruption fractions across different network sizes, at Pr[failure] = 10−5 .

3.2.2 InputShare with domain proof. After locally comparing its vector coordinates to the current pivot, leaf 𝑗 secret-shares the resulting bit vector 𝑏 𝑗,𝑑 = 1[𝑥 𝑗,𝑑 < 𝑝𝑡,𝑑 ] via VSS-Shareto its assigned base committee. A malicious leaf could share an arbitrary field element instead of a bit, biasing the aggregated count by an unbounded amount. To prevent this, the committee verifies that each shared value 𝑏 satisfies 𝑏 ∈ {0, 1} via the standard degree-2 domain proof: it runs Multiply([𝑏], [1 − 𝑏]) and reconstructs the

result using VSS-Reconst. If the reconstruction yields 0, the share is accepted; otherwise the committee collectively replaces it with a canonical zero sharing. This bounds the Byzantine contribution per iteration to 𝐶𝐵 ∈ [0, 𝑓 ], matching the breakdown-point analysis of Theorem 5. Committee parties then locally sum the validated shares, then by linearity of Shamir sharing, this produces a share of the partial count from the incoming leaves, which becomes the input to the tree-aggregation phase. 3.2.3 Verifiable share redistribution via Reshare. Reshare converts a (𝜏, 𝑚)-Shamir sharing held by a child committee Cch into a fresh (𝜏, 𝑚)-sharing held by its parent Cpa (all committees have size 𝑚 and threshold 𝜏 < 𝑚/4). Two adversarial behaviors must be taken into account: a corrupted child may send sub-shares that are inconsistent with any degree-𝜏 polynomial, breaking reconstruction. Even consistent sub-shares must provably interpolate to the partial sum held by the child committee, not an adversarially chosen value. Both are handled by VSS-SubShare [7, Prot. 6.8], using the 𝜏 < 𝑚/4 optimization of their Appendix A. Each 𝑃𝑖 ∈ Cch holds a share 𝜎𝑖 = 𝑓 (𝛼𝑖 ) of the child’s partial sum, where 𝑓 is the degree-𝜏 sharing polynomial and 𝛼𝑖 is 𝑃𝑖 ’s evaluation point. 𝑃𝑖 samples a fresh degree𝜏 polynomial 𝑔𝑖 with 𝑔𝑖 (0) = 𝜎𝑖 and sends 𝑔𝑖 (𝜔𝑟 ) to each parent 𝑃𝑟′ ∈ Cpa at that party’s evaluation point 𝜔𝑟 . The functionality guarantees 𝑔𝑖 (0) = 𝑓 (𝛼𝑖 ) via Reed-Solomon decoding over the honest children’s sub-shares. Each parent then locally computes ∑︁ 𝜎𝑟′ = 𝜆𝑖 · 𝑔𝑖 (𝜔𝑟 ), (3) 𝑖 ∈ Cch

where {𝜆𝑖 } are the Lagrange coefficients interpolating 𝑓 (0) from {𝑓 (𝛼𝑖 )}𝑖 ∈ Cch . Since 𝑔𝑖 (0) = 𝑓 (𝛼𝑖 ), equation (3) evaluates a fresh Í degree-𝜏 polynomial at 𝜔𝑟 whose constant term is 𝑖 𝜆𝑖 𝑓 (𝛼𝑖 ) =

Giskard: Byzantine Robust and Confidential Aggregation for Large-Scale Decentralized Learning

Parent Cpa

𝑃 1′

𝑃 2′

𝑃 3′

𝑔𝑖,𝑑 (𝜔 1 )

𝑔𝑖,𝑑 (𝜔 2 )

𝑔𝑖,𝑑 (𝜔 3 )

𝑃2

𝑃𝑖

𝑃3

Child Cch

Figure 3: Share Resharing. Each 𝑃𝑖 ∈ Cch holds share 𝜎𝑑,𝑖 of the Í partial count b 𝑗 and samples polynomial 𝑔𝑖,𝑑 with 𝑔𝑖,𝑑 (0) = ′ ′ =Í 𝜆 𝑔 𝜎𝑑,𝑖 . Each 𝑃𝑟 ∈ Cpa recombines 𝜎𝑑,𝑟 𝑘 𝑘 𝑘,𝑑 (𝜔𝑟 ) into a fresh share of the same count.

𝑓 (0), the value shared by the child committee. We describe the protocol for a single coordinate; it runs in parallel across all 𝑑 ∈ [𝐷]. The full protocol is given in Appendix C.2.

3.3

Security Analysis of Giskard

We prove that Giskard securely realizes the coordinate-wise median functionality under UC security (Section 2.6.3). 3.3.1 Ideal Functionalities. Giskard relies on the following subprotocols defined with such ideal functionalities: • 𝐹 BA : Byzantine Agreement to ensure reliable broadcast during the setup and the output phase [14] • 𝐹 VSS-Share : BGW VSS scheme [12] • 𝐹 VSS-Reconst : Reconstruction in the BGW VSS scheme [12] • 𝐹 VSS-SubShare : The subshare functionality from Asharov and Lindell [7] • 𝐹 Multiply : Multiplication within the BGW VSS scheme from Asharov and Lindell [7] • 𝐹 InputShare : Described in Protocol 1 using VSS-Share for input sharing, and Multiply and VSS-Reconst for proof verification • 𝐹 Reshare : Verifiable resharing, described in Protocol 2 Leakage. By design, this protocol allows the global count used to update the threshold to be revealed to all parties but the individual inputs and intermediate counts stay hidden. This system must then not reveal anything more than what is permitted here. 3.3.2 Security Statements. To prove that Giskard is UC-Secure we must prove that all the defined protocols it calls are UC-Secure, which are the ones whose ideal functionalities were defined (BA, VSS-Share, VSS-Reconst, VSS-SubShare, Multiply, InputShare, Reshare). We assume that BuildTree was successfully performed before running the secure median computation. We prove that Giskard is secure under a hybrid model that uses those protocols as realized by a trusted party. We have the following results: Lemma 2. Protocols BA, VSS-Share, VSS-Reconst, VSS-SubShare, Multiply, VSS-Reconst and Reshare are UC-Secure.

Conference’17, July 2017, Washington, DC, USA

Proof. Using the BGW full security proof by Asharov and Lindell [7] already shows that VSS-Share, VSS-Reconst, VSS-SubShare, Multiply and VSS-Reconst are perfectly secure using a straightline black-box simulator. Using [33, Theorem 1.2], it proves that those protocols are UC-Secure. Furthermore, our Reshare protocol is identical to Movahedi et al. [42] Renew-Share protocol, that they show to be secure under the (𝐹 VSS-Share , 𝐹 VSS-SubShare )-hybrid model then invokes the modular theorem to prove that it is UC-Secure. □ Now we prove that InputShare is UC-Secure by proving its security in the (𝐹 VSS-Share , 𝐹 Multiply ,𝐹 VSS-Reconst )-hybrid model, as InputShare calls those two protocols. Then invoke the modular theorem and lemma 1 to Lemma 3. Protocol InputShare is UC-Secure Proof sketch. The ideal functionality 𝐹 InputShare (Appendix C.4.1) collects honest bits 1[𝑥 𝑗,𝑑 < 𝑝𝑡,𝑑 ], extracts adversarial bits from S after a {0, 1} check, and delivers fresh degree-𝜏 sharings of the aggregate. The simulator SInputShare (Appendix C.4.2) runs honest leaves on dummy input 0, invokes the ideal 𝐹 VSS-Share and 𝐹 Multiply , extracts adversarial bits from the corrupt-leaf 𝐹 VSS-Share calls, and patches the final aggregate with a correction polynomial 𝑔𝑑 satisfyÍ ing 𝑔𝑑 (0) = 𝜎𝑑 − 𝑗 ∈ Aleaf 𝑏 ∗𝑗,𝑑 and 𝑔𝑑 (𝛼𝑘 ) = 0 for 𝑘 ∈ 𝐼 . Indistinguishability follows from the information-theoretic privacy of Shamir sharing with |𝐼 | ≤ 𝑡: VSS shares, multiplication outputs, and the final aggregate shares are each uniformly distributed regardless of the underlying secret, so the joint view matches the hybrid execution. Full proof, functionality, and simulator in Appendix C.4. □ This brings to prove the security of our protocol: Theorem 4. Protocol Giskard is UC-Secure Proof sketch. By Lemmas 1 and 2, each sub-protocol (BA, VSS-Share, VSS-Reconst, VSS-SubShare, Multiply, InputShare, Reshare) is UC-secure against a static malicious adversary, so it suffices to prove security in the hybrid model where these are replaced by their ideal functionalities. Following Movahedi et al. [42], but replacing their induction over sorting-circuit gates with a double induction over tree level and median-search iteration, the simulator reproduces the adversary’s view layer by layer: Reshare outputs fresh uniform shares at each parent committee, linear homomorphism handles local aggregation, and Reconst opens only the public count cnt at the root. Across iterations, the broadcast count and deterministic threshold update make each iteration start from an identical public state, so the views compose. □

3.4

Robustness Properties Against Model Poisonning Attacks

We show that Giskard satisfies the (𝑓 , 𝜅)-robustness criterion of Allouah et al. [3], the same guarantee provided by coordinate-wise median against poisoning attacks [34]. We argue per coordinate, since the lift from scalar to R𝐷 robustness follows from Lemma 2 of [3]. Let H ⊆ [𝑛] be the honest set

Conference’17, July 2017, Washington, DC, USA

with |H | = 𝑛 − 𝑓 , and let ℎ (1) ≤ · · · ≤ ℎ (𝑛−𝑓 ) denote the sorted honest values, extended by ℎ (𝑘 ) := −𝑢 for 𝑘 ≤ 0 and ℎ (𝑘 ) := +𝑢 for 𝑘 > 𝑛 − 𝑓 . At iteration 𝑡, the protocol tests 𝑝𝑡 = (Left𝑡 + Right𝑡 )/2, and each party 𝑗 contributes a bit 𝑏 𝑗 (𝑝𝑡 ) = 1[𝑥 𝑗 ≤ 𝑝𝑡 ]. The aggregated count decomposes as 𝐶 (𝑝𝑡 ) = 𝐶𝐻 (𝑝𝑡 ) + 𝐶𝐵 (𝑝𝑡 ), where 𝐶𝐻 (𝑝𝑡 ) = |{ 𝑗 ∈ H : 𝑥 𝑗 ≤ 𝑝𝑡 }| is the honest contribution and 𝐶𝐵 (𝑝𝑡 ) ∈ [0, 𝑓 ] is the Byzantine contribution, bounded by the zeroknowledge bit-domain proof. After 𝑁 iter = ⌈log2 (2𝑢/𝑞)⌉ iterations, Right − Left ≤ 𝑞, and Giskard outputs 𝑀ˆ = (Left + Right)/2. Lemma 4 (Output Boundedness). Under 𝑓 < 𝑛/4, the output 𝑀ˆ satisfies ℎ (𝑘1 ) − 𝑞/2 ≤ 𝑀ˆ ≤ ℎ (𝑘2 ) + 𝑞/2, where 𝑘 1 = ⌊𝑛/2⌋ + 1 − 𝑓 and 𝑘 2 = ⌊𝑛/2⌋ + 1. Proof. Right was last updated at an iteration with 𝐶 (𝑝) > 𝑛/2. Since 𝐶𝐵 ≤ 𝑓 , 𝐶𝐻 (𝑝) ≥ 𝐶 (𝑝) − 𝑓 > 𝑛/2 − 𝑓 , so Right ≥ ℎ (𝑘1 ) . Left was last updated at an iteration with 𝐶 (𝑝) ≤ 𝑛/2. Since 𝐶𝐵 ≥ 0, 𝐶𝐻 (𝑝) ≤ 𝑛/2, so Left < ℎ (𝑘2 ) . With Right − Left ≤ 𝑞 and 𝑀ˆ = (Left + Right)/2, the claim follows. □ Theorem 5 ( (𝑓 , 𝜅)-robustness). Under 𝑓 < 𝑛/4 and termination 2 , Giskard robust aggregation function is (𝑓 , 𝜅)precision 𝑞 2 ≤ 𝜎 H robust with 2(𝑛 − 𝑓 ) + 12 . 𝜅 = ⌈𝑛/2⌉ − 𝑓 Proof sketch. Lemma 4 writes 𝑀ˆ = 𝑣 + 𝛿 with 𝑣 between the order statistics ℎ (𝑘1 ) and ℎ (𝑘2 ) (𝑘 1 = ⌊𝑛/2⌋ + 1 − 𝑓 , 𝑘 2 = ⌊𝑛/2⌋ + 1) and |𝛿 | ≤ 𝑞/2. A counting argument gives at least ⌈𝑛/2⌉ − 𝑓 honest 2 with 𝜅 = (𝑛 − values on each side of 𝑣, yielding (𝑣 − 𝑥¯H ) 2 ≤ 𝜅 0 𝜎 H 0 𝑓 )/( ⌈𝑛/2⌉ − 𝑓 ). Combining with |𝛿 | ≤ 𝑞/2 via (𝑎 + 𝑏) 2 ≤ 2𝑎 2 + 2𝑏 2 2 gives the stated 𝜅; see Appendix C.5. and 𝑞 2 ≤ 𝜎 H □ 3.4.1 Communication Complexity. Let 𝜈 (𝑚) = 𝑂 (𝑚 2 ) denote the per-party communication complexity of VSS-Share among 𝑚 parties (Theorem 2). The per-party costs of each sub-protocol taken in isolation are: • VSS-Share (single instance, 𝑚 parties): 𝑂 (𝑚 2 ). • Multiply (single instance, 𝜏 < 𝑚/4): 𝑂 (𝑚 2 ) per party via VSS-SubShare applied directly to the local products 𝑎𝑖 𝑏𝑖 (Asharov–Lindell, Appendix A); total network cost 𝑂 (𝑚 3 ). • InputShare (per base committee): a committee party handles 𝑛/𝑘 𝐿 leaves, each requiring one VSS-Share
and one Multiply for bit verification, giving 𝑂 (𝑛/𝑘 𝐿 ) · 𝑚 2 per party. Local aggregation of validated shares is free by additive homomorphism. • Reshare (child → parent): 𝑂 (𝑚 2 ) per party on both sides; a parent receiving from 𝑘 children pays 𝑂 (𝑘𝑚 2 ). • VSS-Reconst (committee output): 𝑂 (𝑚) per party. Theorem 6 (Communication Complexity of Giskard). Let 𝑁 iter denote the number of iterations for median search, and let 𝑑 denote the model dimension. Under the tree parameters of Theorem 3, with Multiply at threshold 𝜏 < 𝑚/4, constant branching factor 𝑘 = 𝑂 (1), and each party assigned to at most one committee per tree level: (i) Per-party cost per committee membership per iteration (single-coordinate): Δmax = 𝑂 (log2 𝑛). 3 (ii) Total per-party cost: Δeff max = 𝑂 (𝑑𝑁 iter log 𝑛).

Ousmane Touat, César Sabater, Mohamed Maouche, and Sonia Ben Mokhtar

(iii) Total network cost: Total = 𝑂 (𝑑𝑁 iter𝑛 log3 𝑛). Proof sketch. (i) Balancing the InputShare cost 𝑂 ((𝑛/𝑘 𝐿 )𝑚 2 ) at leaves against the Reshare cost 𝑂 (𝑘𝑚 2 ) at intermediate committees gives 𝑘 𝐿+1 = 𝑛; with 𝑘 = 𝑂 (1) and 𝑚 = 𝑂 (log 𝑛), Δmax = 𝑂 (log2 𝑛). (ii) Each party sits on at most 𝐿 = 𝑂 (log 𝑛) committees per 3 iteration, so Δeff max = 𝑂 (𝑑𝑁 iter 𝐿Δmax ) = 𝑂 (𝑑𝑁 iter log 𝑛), absorbing the smaller leaf term. (iii) Summing InputShare, bit verification, and the 𝑂 (𝑛) Reshare instances over 𝑑 coordinates and 𝑁 iter iterations with 𝑚 = 𝑂 (log 𝑛) yields 𝑂 (𝑑𝑁 iter𝑛 log3 𝑛). Full accounting in Appendix C.6. □ Comparison with baseline topologies. We compare three topologies for running the median-search iteration, all using the same VSS and Multiply primitives: All-to-all (A2A) as in Ghavamipour et al. [21], All-to-committee (A2C) used by AlphaFL [26] and the work from Franzese et al. [20], and Giskard. Per-party cost is reported as the maximum over all parties; for A2C this corresponds to a committee member. Both A2C and Giskard use committee size 𝑚 = 𝑂 (log 𝑛), sized via Chernoff and union bound to tolerate a constant fraction of corruptions. We use threshold of 𝜏 < 𝑚/4 for all topologies; Giskard uses constant branching factor 𝑘, the comparison is done assuming that all those topologies implement the binary search using BGW primitives. Table 1 summarizes the worst case per-party communication cost. Table 1: Worst-case per-party and total communication per median-search iteration.

A2A A2C Giskard

4

Per-party cost

Total network cost

Rounds

𝑂 (𝑑𝑛 2 )

𝑂 (𝑑𝑛 3 )

𝑂 (𝑑𝑛 log2 𝑛) 𝑂 (𝑑 log3 𝑛)

𝑂 (𝑑𝑛 log2 𝑛) 𝑂 (𝑑𝑛 log3 𝑛)

𝑂 (1) 𝑂 (1) 𝑂 (log 𝑛)

Experimental Study

In this section, we evaluate Giskard from two complementary angles. First, we study its scalability by comparing its communication and latency costs with MPC-based decentralized competitors (A2C and A2A). Second, we assess whether the binary search median formulation proposed for Giskard preserves model utility under Byzantine attacks. To evaluate Giskard, we implemented a prototype in Rust using the arkworks library [6]. Cleartext baselines were obtained with a modified version of the ByzFL framework in Python [22]. All experiments were run on a workstation with an Intel Core i9-13950HX (24 cores, 2.2 GHz base), 128 GB of DDR5 RAM, and an NVIDIA RTX 5000 Ada Generation GPU, running Ubuntu 24.04. Our evaluation is guided by the following research questions: • RQ1: What is the impact of using Giskard compared to A2A and A2C topologies on per-party communication cost? • RQ2: What is the impact of the network size 𝑛 on per-party cost and end-to-end latency for each topology?

Giskard: Byzantine Robust and Confidential Aggregation for Large-Scale Decentralized Learning

• RQ3: Is Giskard’s binary-search median competitive with state-of-the-art robust aggregators under model poisoning attacks? • RQ4: What is the impact of the median-search iteration count 𝑁 iter on the cost/robustness tradeoff?

4.1

Comparing Giskard per-party communication cost to A2A and A2C (RQ1)

To start our evaluation, we want to emphasize why we propose the Giskard tree topology for MPC-based robust aggregation. To do that, we show in Figure 4 the worst-case per-party communication cost as a function of the Byzantine fraction 𝑓 /𝑛, for A2A, A2C, and Giskard on networks of size 𝑛 ∈ {103, 104, 105, 106 }. Each point represents the bytes a single honest party must send and receive to complete one robust aggregation, with the x-axis showing 𝑓 /𝑛 and the y-axis showing the per-party cost in bytes on a log scale. Methodology: For each 𝑛 and Byzantine fraction 𝑓 /𝑛, we first choose the smallest committee size 𝑚 satisfying the target failure probability 𝛿 = 10−5 , then initialize the fixed tree topology for Giskard and the A2C single committee accordingly. A2A consists of 𝑛 fully connected parties regardless of 𝑓 . We estimate per-party communication cost in two steps. First, a Rust implementation over the arkworks library [6] measures the cost of each MPC building block (VSS-Share, Multiply, Reshare) by counting every field element sent, received, or broadcast. Second, we count how many times each topology invokes each block. For A2A with 𝑛 > 100, the MPC instance is too large to simulate, and we use its closed-form cost expression. Per-party cost composition: • A2A: every party is a member of the size-𝑛 committee and runs one full Boolean-check block over all 𝑛 bits per iteration. • A2C: the worst-case party is a committee member, running the same Boolean-check block among 𝑚 ≪ 𝑛 parties over all 𝑛 bits. Non-committee parties only act as input dealers and pay one VSS-Share per iteration. • Giskard: the worst-case party is simultaneously an input dealer (one VSS-Share), a member of one base committee (one Boolean-check block over the leaves of that cluster), a member of one committee at each of the 𝐿 − 2 intermediate levels (each lifts 𝑘 child shares into the parent via Reshare), and a member of the root committee (which performs the 𝑘 final Reshare calls and runs the global reconstruction). The total per-party cost is the sum of these contributions multiplied by 𝑁 iter . Note: We implement the distributed binary-search median for A2A and A2C, rather than the generic median circuit that could be applied in their original works (A2A from Ghavamipour et al. [21], A2C from AlphaFL [26] or Franzese et al. [20]). Our attempts to instantiate the median with generic MPC sorting and comparison circuits led to prohibitive cost blow-ups that would make the baselines look worse. We therefore give the baselines the same binary-search median formulation as Giskard, in order to show that even though this formulation reduces costs for all topologies, it benefits Giskard more because its tree structure distributes the resulting counting operations across many small committees.

Conference’17, July 2017, Washington, DC, USA

Parameters: We sweep 𝑛 ∈ {102, 103, 104, 105, 106 } and 𝑓 /𝑛 ∈ {0.05, 0.10, 0.20}. For each (𝑛, 𝑓 ), the committee size 𝑚 is the smallest value satisfying 𝛿 = 10−5 union-bounded across Giskard’s tree committees (and to generate one committee for A2C); tree parameters 𝑘, 𝐿 are chosen to minimize per-party cost. We fix 𝑁 iter = 10, the field element size at 32 bytes, and the aggregated dimension at one (scalar median). Results: Our results show that Giskard pays a per-party cost orders of magnitude lower than both baselines, especially when 𝑛 ≫ 𝑚. At 𝑓 /𝑛 = 0.10, Giskard’s per-party cost grows from 8.5 GB at 𝑛 = 103 to 77 GB at 𝑛 = 106 . It represents a 9× increase for a 103 × larger network, against ∼ 1200× for A2C and ∼ 109 × for A2A. Furthermore, at 𝑛 = 106 , the per-party cost of Giskard ranges from 3.5 GB to 870 TB across 𝑓 /𝑛 ∈ {0.05, 0.10, 0.20}, against 6.2 TB to 69 PB for A2C and above 4 · 1025 bytes for A2A. At 𝑓 /𝑛 = 0.05, this corresponds to a 1775× reduction of Giskard over A2C. We explain this advantage by the fact that Giskard distributes the MPC work across a tree of small committees, decoupling per-party cost from 𝑛 beyond a logarithmic factor, whereas A2C concentrates the load on a single committee and A2A scales committees with 𝑛.

Takeaway: Distributing the MPC work across a tree of small committees, as in Giskard, offers a better per-party communication profile than A2A or A2C.

4.2

Impact of Network Size on Total Cost and Latency (RQ2)

In this experiment, we aim to study how each topology scales with the network size 𝑛, both in total communication and in endto-end wall-clock time. The results are presented in Figure 5 for total bytes versus 𝑛 at 𝑓 /𝑛 ∈ {0.05, 0.10, 0.20}, and in Figure 6 for the corresponding minimum wall-clock time at 𝑓 /𝑛 = 0.10 under a 1 Gbps per-party bandwidth and a 1 s round-trip delay, adding in time from executed local computation. Each point in Figure 5 represents the total bytes exchanged across all parties for instance of the distributed median binary search, with the x-axis showing 𝑛 and the y-axis showing total bytes on a log scale. Each point in Figure 6 represents the minimum end-to-end latency under the assumption that compute and transfer overlap within a round and same-layer committees in Giskard execute concurrently, and that local computation is done with one thread, namely the boolean verification are done sequentially. Interestingly, in total bytes A2C is strictly below Giskard across the range, because A2C concentrates work on a small committee while Giskard distributes it across all 𝑛 parties. However the concentrated cost in A2C exceeds any practical per-committee bandwidth at 𝑛 = 106 (Figure 4). At 𝑓 /𝑛 = 0.10, our model places Giskard’s wall-clock in the minutes-to-hours range across the tested 𝑛, A2C in the multi-hour to multi-day range from 𝑛 = 105 on, and A2A beyond any practical horizon already at 𝑛 = 104 . At small 𝑛 (𝑛 = 102 ) the three topologies fall within a small constant factor of each other, reflecting that topology choice matters only when 𝑛 ≫ 𝑚.

Conference’17, July 2017, Washington, DC, USA

Ousmane Touat, César Sabater, Mohamed Maouche, and Sonia Ben Mokhtar

1018

(a) Worst-case per-party at f/n = 0.1 Estimated wall-clock (s)

Worst-case per-party bytes

1026 A2A

1023

A2C Giskard

1020 10

17

1014

A2A A2C Giskard

1015 1012 109 106 103

1 yr 1 mo 1d 1h

1011

102

108

104

103

105

106

103

104 105 Network size n

106

Network size n (b) A2C overhead vs.\ Giskard

A2C / Giskard ratio

f/n = 0.05

103

1775× 714×

f/n = 0.1 f/n = 0.2

102

Figure 6: Extrapolated wall-clock time to completion versus network size 𝑛 at 𝑓 /𝑛 = 0.10, under 1 Gbps per-party bandwidth and 1 s round-trip delay. Dashed lines mark sample durations at 1 hour, 1 day, 1 month, and 1 year.

81×

101

4.3 10

0

10−1

parity

10

3

10

4

10

5

10

6

Network size n

Figure 4: Per-party communication cost. (a) Absolute bytes at 𝑓 = 0.20 for the three topologies. (b) A2C overhead relative to Giskard across three Byzantine fractions. Giskard reduces per-party bandwidth by up to 1775× compared to A2C at 𝑛 = 106 with 𝑓 /𝑛 = 0.05, with the advantage growing as the network scales.

Total communication cost at f/n = 0.1 Total network bytes

1032 1029 1026

A2A A2C Giskard

1023 1020 1017 1014 103

104

105

106

Network size n

Figure 5: Total communication cost at 𝑓 /𝑛 = 0.10 for the three topologies.

Takeaway: Only Giskard keeps both per-party cost and end-to-end latency within practical budgets up to 𝑛 = 106 .

Comparing Giskard’s Median to Baseline Aggregators under Poisoning (RQ3)

In this experiment, we want to evaluate whether that Giskard’s binary-search median, tailored to an MPC implementation, does not sacrifice robustness compared to standard robust aggregators. We run this evaluation on a fork of the ByzFL Python framework [22] in the cleartext domain, with 𝑛 = 100 parties (𝑓 = 25 Byzantine) and a Dirichlet non-i.i.d. partition (𝛼 = 1.0). The party count is bounded by standard FL benchmark sizes. We show in Figures 7 and 8 the global test accuracy across training rounds for our binarysearch median and two state-of-the-art robust aggregators, under four model-poisoning attacks: Label Flipping [2], Sign Flipping [2], IPM [54], and ALIE [8]. Each curve in the plots represents the mean test accuracy across 5 independent seeds, with the x-axis showing the training round and the y-axis showing the global test accuracy. Our results show that, across both datasets and all four attacks, Giskard’s binary-search median tracks the accuracy of cleartext robust aggregators within a small final-round gap. On MNIST, the gap between Giskard robust aggregation function and the other stays below 0.4% on every attack. On CIFAR10, the gap stays below 1.5% for attacks such as Label Flipping and Sign Flipping, while on Label Flipping Giskard edges out the cleartext median by 0.8% and reaches at most 2.7% for optimized attacks such as ALIE and IPM, which craft updates close to the honest mean and therefore demand finer median precision. We explain this behavior by the fact that the binary-search median converges to the true coordinatewise median up to the search precision; once 𝑁 iter is sufficient, the residual error stays below the variance of honest updates, putting 2 identified in Theorem 5. the aggregator in the regime 𝑞 2 ≤ 𝜎 H

Takeaway: Giskard’s MPC-friendly binary-search median is competitive with cleartext robust aggregators under standard model-poisoning attacks.

Giskard: Byzantine Robust and Confidential Aggregation for Large-Scale Decentralized Learning

1.0

(a) SignFlipping

TrMean

Median

(b) Optimal InnerProductManipulation 0.75 0.50

0.5

Accuracy

0.25 0.00 200 400 600 8000.000 (c) Optimal ALittleIsEnough 1.0 1.0

800

200

800

0.5

0.5 0.00

200 400 600 (d) LabelFlipping

200

400

600

800 0.00

Round

400

600

crafted close to the honest mean (ALIE, IPM) requiring finer precision than coarser ones (Label Flipping, Sign Flipping). For 𝑁 iter ≥ 10 accuracy saturates near the no-attack baseline regardless of the 2 regime of Theorem 5. Interestingly, attack, matching the 𝑞 2 ≤ 𝜎 H the transition between collapse and saturation is sharp: a 3- to 4-iteration window separates chance accuracy from the saturated regime. We conclude that 𝑁 iter admits a well-defined operating point at around 𝑁 iter = 10 in the tested configuration, above which extra iterations only inflate communication cost without improving robustness. Takeaway: The cost/robustness tradeoff is governed by a sharp threshold on 𝑁 iter ; provisioning above it is strictly wasteful.

BinarySearchMedian 0.6

(a) SignFlipping

(b) Optimal InnerProductManipulation

0.2

0.2 0.00

500 1000 1500 2000 0.00 (c) Optimal ALittleIsEnough 0.6 0.4

1000 1500 2000 0.00

Round

500

SF

0.10 0.10 0.11 0.10 0.17 0.70 0.92 0.96 0.97 0.97

FoE

0.10 0.11 0.12 0.72 0.91 0.93 0.98 0.98 0.98 0.98

ALIE Attack

0.10 0.10 0.12 0.64 0.92 0.97 0.98 0.98 0.98 0.98

Inf

0.10 0.11 0.11 0.10 0.15 0.57 0.96 0.97 0.97 0.97

LF

1.0 0.8 0.6 0.4 0.2 0.0

1000 1500 2000

5 Figure 8: Global test accuracy under four Byzantine attacks on CIFAR-10 (𝑛 = 100 including 𝑓 = 25) in a non-i.i.d. setup (𝛼 = 1.0), comparing the Giskard binary-search median against two robust aggregation rules.

4.4

0.10 0.11 0.10 0.11 0.12 0.44 0.94 0.96 0.97 0.97

Figure 9: Heatmap of test accuracy as a function of the maximum number of iterations of Giskard’s binary-search median, on five Byzantine attacks on MNIST (𝑛 = 100 including 𝑓 = 25) in a non-i.i.d. setup (𝛼 = 1.0).

0.2 500

1 5 6 7 8 9 10 20 28 40

500 1000 1500 2000 (d) LabelFlipping

0.4

0.2 0.00

Median

0.4

0.4

Accuracy

TrMean

Number of iterations

Figure 7: Global test accuracy under four Byzantine attacks on MNIST (𝑛 = 100 including 𝑓 = 25) in a non-i.i.d. setup (𝛼 = 1.0), comparing the Giskard binary-search median against two robust aggregation rules.

Test Accuracy

BinarySearchMedian

Conference’17, July 2017, Washington, DC, USA

Impact of the Median-Search Iteration Count on the Cost/Robustness Tradeoff (RQ4)

In this experiment, we aim to study the impact of the median-search iteration count 𝑁 iter on Giskard’s cost/robustness tradeoff, since the per-party cost scales linearly in 𝑁 iter and over-provisioning this parameter wastes communication. The results are presented in Figure 9 as a heatmap of final test accuracy at round 800 on MNIST with 𝑛 = 100, 𝑓 = 25, and 𝛼 = 1.0. The x-axis shows 𝑁 iter ∈ {1, 5, . . . , 40}, the y-axis shows the attack type, and the cell color encodes the final test accuracy. The results show three regimes. For 𝑁 iter ≤ 6 the search has not converged and accuracy stays at chance level across all attacks. For 7 ≤ 𝑁 iter ≤ 9 accuracy depends on the attack type, with attacks

Related Work

Secure Aggregation. The challenge of achieving secure aggregation in a federated learning context arose shortly after the formalization of the latter, with the SecAgg protocol [13]. This protocol, which assumes honest-but-curious behavior, allows a server to compute the aggregated model from clients’ contributions without being able to discern individual contributions by obscuring them with randomly generated correlated masks. Building on this foundation, a whole line of work has emerged aimed at reducing communication costs, notably with SecAgg+ [10] and LightSecAgg [51]. However, these protocols assume the federator server follows the prescribed protocol: a malicious server could instead distribute malformed shares and prevent clients from correctly masking their updates. ELSA [46], AION [36], and AlphaFL [26] address this by building on verifiable secret sharing (VSS), which lets clients detect malformed shares, at the cost of a multi-server deployment. ELSA and AlphaFL adopt a two-server configuration with one honest server, while AION uses an 𝑛-aggregator setup under an honestsupermajority assumption, closer to Giskard’s threat model. These protocols implement plain averaging and offer no robustness against poisoning attacks. A follow-up line extends secure aggregation with input-validation mechanisms, ACORN [9],

Conference’17, July 2017, Washington, DC, USA

RoFL [37], EIFFeL [47], and AION, but the guarantees remain heuristic, typically reducing to norm bounds on client updates. General-Purpose MPC systems. Secure multi-party computation (MPC) allows 𝑛 parties to jointly compute an arbitrary function using their private inputs, without revealing anything beyond the output. Foundational schemes include Yao’s garbled circuits [56] for two parties, and BGW [12] using Shamir’s secret sharing for a group of arbitrary size with an honest majority. Today, specialized frameworks exist for different system sizes: replicated secret sharing and garbled circuits for 2–4 parties, and SPDZ [18] and MASCOT [30] for cases involving a dishonest majority. In all these schemes, evaluating additions is free, primarily due to the linear homomorphism of the secret-sharing scheme, but multiplications require additional communication, notably through the use of Beaver triples. This cost increases significantly when moving from an honest-but-curious threat model to a malicious one. Multiplication gates are the backbone of many arbitrary function implementations, such as comparison between a secret value and a constant or between two secrets. This makes implementing robust statistical functions very costly, as they require comparison and sorting gates. Furthermore, traditional MPC approaches require all-to-all communication, with per-party communication cost scaling at least linearly with the system size. Scalable MPC works [42, 58] addresses the scalability issue by distributing computation across small committees of size 𝑂 (log 𝑛) to achieve polylogarithmic cost. These results remain theoretical and have not been applied to distributed learning. Our work builds on such approaches by designing a hierarchical aggregation tree for median search, enabling confidential robust aggregation in a decentralized topology with sub-linear per-node communication cost. Byzantine-Robust and Privacy Preserving Decentralized Learning Systems. Early work on defending federated learning against model poisoning while preserving privacy combined independent components for each goal. Biscotti [49], for instance, builds on a blockchain substrate and pairs Multi-Krum aggregation and DP noise for robustness with secure aggregation for privacy. However, its Multi-Krum filtering step runs in cleartext. A subsequent line of work focuses on combining robust aggregation with differential privacy. Allouah et al. [4] show that achieving a meaningful DP guarantee from local DP on top of (𝑓 , 𝜅)-robust aggregation sharply degrades model utility. CafCor [5] resolves this trade-off by replacing local DP with a correlated-noise mechanism across parties, and introducing a new (𝑓 , 𝜅)-robust aggregator built on a covariance-bound-agnostic filter. It nonetheless operates in a classical FL setting with an honest-but-curious aggregation server. A second line of work directly implements robust aggregation rules, either through homomorphic encryption or via secret sharing. Sable [17], for instance, introduces somewhat-homomorphicencryption operators that realize the trimmed-mean aggregator directly, a known robust aggregation function. This keeps client-side communication low, but still assumes a single honest-but-curious server whose workload grows rapidly with the number of clients. AlphaFL [26] implements aggregation with input validation inside the UC-secure SPDZ2k framework in a two-server configuration, tolerating malicious clients and servers but relying on heuristic

Ousmane Touat, César Sabater, Mohamed Maouche, and Sonia Ben Mokhtar

input validation rather than formally robust aggregation. The twoserver assumption remain incompatible with fully decentralized settings. BREA [50] secret-shares each client’s quantized update via verifiable secret sharing; clients then locally compute pairwise distances over the shares and forward the results to the server, which reconstructs the distance matrix and runs a multi-Krumstyle selection. Per-client communication and computation scale as 𝑂 (𝑁 2 ) in the network size, and the server learns the full pairwise distance matrix. SHARE [52] adopts a clustering-based hybrid: clients are randomly clustered each round, pairwise-key secure aggregation runs within each cluster, and a robust aggregator is applied to the cluster means. Cluster size controls a trade-off between privacy granularity and robust-aggregator tolerance, but the server observes cluster means in the clear under an honest-but-curious assumption Removing the server assumption shifts robust aggregation entirely into the MPC layer. SecureDL [21] implements a cosinesimilarity model filtering mechanism on top of MASCOT, a fully connected MPC framework in which every participant contributes an input and participates in the computation via secret sharing, tolerating malicious nodes. This all-to-all topology scales poorly: communication costs grow at least quadratically in the number of participants. The reliance on cosine-similarity filtering, which offers no formal robustness guarantee, follows directly from this cost structure, as instantiating classical robust aggregators such as the median or trimmed mean would be prohibitively expensive. Franzese et al. [20] formalize robust serverless collaborative learning using an all-to-committee MPC setup, instantiating RSA [34], FLTrust [16], and CenteredClipping [28]. Their single-layer topology concentrates work on a small committee, yielding per-node costs close to multi-server approaches; the construction also leaves the underlying VSS scheme and a formally robust aggregator unspecified. Giskard addresses these gaps with a full protocol description, security proofs, and a formally robust aggregator that scales to a decentralized setting.

6

Conclusion

In this work, we presented Giskard, a system attempting to solve the per-party communication overhead issue while tackling the challenging threat model combining confidentiality and model poisoning attacks. We provide a fully decentralized learning system that has theoretical robustness guarantees against model poisoning attacks while keeping confidentiality guarantees. We provide a security proof for our system along with a communication cost analysis with practical implementation cost, and finally show that our robust aggregator is competitive with state-of-the-art approaches. As future work, we plan to explore computational variants based on cryptographic assumptions to further reduce communication costs.

Acknowledgments This work was supported by the French government managed by the Agence Nationale de la Recherche (ANR) through France 2030 program with the reference ANR-23-PEIA-005 (REDEEM project).

Giskard: Byzantine Robust and Confidential Aggregation for Large-Scale Decentralized Learning

References [1] Sulaiman A Alghunaim and Kun Yuan. 2022. A unified and refined convergence analysis for non-convex decentralized learning. IEEE Transactions on Signal Processing 70 (2022), 3264–3279. [2] Zeyuan Allen-Zhu, Faeze Ebrahimianghazani, Jerry Li, and Dan Alistarh. 2021. Byzantine-Resilient Non-Convex Stochastic Gradient Descent. In International Conference on Learning Representations. [3] Youssef Allouah, Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafaël Pinot, and John Stephan. 2023. Fixing by mixing: A recipe for optimal byzantine ml under heterogeneity. In International Conference on Artificial Intelligence and Statistics. PMLR, 1232–1300. [4] Youssef Allouah, Rachid Guerraoui, Nirupam Gupta, Rafaël Pinot, and John Stephan. 2023. On the privacy-robustness-utility trilemma in distributed learning. In International Conference on Machine Learning. PMLR, 569–626. [5] Youssef Allouah, Rachid Guerraoui, and John Stephan. 2025. Towards Trustworthy Federated Learning with Untrusted Participants. In Proceedings of the 42nd International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 267), Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu (Eds.). PMLR, 1184–1227. https://proceedings.mlr.press/v267/allouah25a.html [6] arkworks contributors. 2022. arkworks zkSNARK ecosystem. https://arkworks.rs [7] Gilad Asharov and Yehuda Lindell. 2011. A Full Proof of the BGW Protocol for Perfectly-Secure Multiparty Computation. IACR Cryptology ePrint Archive 2011 (01 2011), 136. [8] Gilad Baruch, Moran Baruch, and Yoav Goldberg. 2019. A little is enough: Circumventing defenses for distributed learning. Advances in Neural Information Processing Systems 32 (2019). [9] James Bell, Adrià Gascón, Tancrède Lepoint, Baiyu Li, Sarah Meiklejohn, Mariana Raykova, and Cathie Yun. 2023. ACORN: input validation for secure aggregation. In Proceedings of the 32nd USENIX Conference on Security Symposium (Anaheim, CA, USA) (SEC ’23). USENIX Association, USA, Article 269, 18 pages. [10] James Henry Bell, Kallista A. Bonawitz, Adrià Gascón, Tancrède Lepoint, and Mariana Raykova. 2020. Secure Single-Server Aggregation with (Poly)Logarithmic Overhead. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security (Virtual Event, USA) (CCS ’20). Association for Computing Machinery, New York, NY, USA, 1253–1269. doi:10.1145/3372297.3417885 [11] Aurélien Bellet, Rachid Guerraoui, Mahsa Taziki, and Marc Tommasi. 2017. Fast and differentially private algorithms for decentralized collaborative machine learning. Research Report. INRIA Lille. https://inria.hal.science/hal-01665410 [12] Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. 1988. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (Chicago, Illinois, USA) (STOC ’88). Association for Computing Machinery, New York, NY, USA, 1–10. doi:10.1145/62212.62213 [13] Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. 2017. Practical Secure Aggregation for Privacy-Preserving Machine Learning. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (Dallas, Texas, USA) (CCS ’17). Association for Computing Machinery, New York, NY, USA, 1175–1191. doi:10.1145/3133956.3133982 [14] Nicolas Braud-Santoni, Rachid Guerraoui, and Florian Huc. 2013. Fast byzantine agreement. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (Montréal, Québec, Canada) (PODC ’13). Association for Computing Machinery, New York, NY, USA, 57–64. doi:10.1145/2484239.2484243 [15] Ran Canetti. 2000. Universally Composable Security: A New Paradigm for Cryptographic Protocols. Cryptology ePrint Archive, Paper 2000/067. https: //eprint.iacr.org/2000/067 [16] Xiaoyu Cao, Minghong Fang, Jia Liu, and Neil Zhenqiang Gong. 2021. FLTrust: Byzantine-robust Federated Learning via Trust Bootstrapping. In Proceedings 2021 Network and Distributed System Security Symposium (Virtual). Internet Society. doi:10.14722/ndss.2021.24434 [17] Antoine Choffrut, Rachid Guerraoui, Rafael Pinot, Renaud Sirdey, John Stephan, and Martin Zuber. 2024. Towards Practical Homomorphic Aggregation in Byzantine-Resilient Distributed Learning. In Proceedings of the 25th International Middleware Conference (Hong Kong, Hong Kong) (Middleware ’24). Association for Computing Machinery, New York, NY, USA, 431–444. doi:10.1145/3652892. 3700783 [18] Ivan Damgård, Valerio Pastro, {Nigel P.} Smart, and Sarah Zakarias. 2012. Multiparty Computation from Somewhat Homomorphic Encryption. In Advances in Cryptology - CRYPTO 2012, Reihaneh Safavi-Naini and Ran Canetti (Eds.), Vol. 7417. Springer Berlin Heidelberg, Germany, 643–662. [19] Minghong Fang, Zifan Zhang, Hairi, Prashant Khanduri, Jia Liu, Songtao Lu, Yuchen Liu, and Neil Gong. 2024. Byzantine-robust decentralized federated learning. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security. 2874–2888. [20] Nicholas Franzese, Adam Dziedzic, Christopher A. Choquette-Choo, Mark R Thomas, Muhammad Ahmad Kaleem, Stephan Rabanser, Congyu Fang, Somesh

Conference’17, July 2017, Washington, DC, USA

Jha, Nicolas Papernot, and Xiao Wang. 2023. Robust and Actively Secure Serverless Collaborative Learning. In Advances in Neural Information Processing Systems, A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (Eds.), Vol. 36. Curran Associates, Inc., 39504–39528. https://proceedings.neurips.cc/paper_files/ paper/2023/file/7c5a4b7a31dffef8ce296deedb6214a9-Paper-Conference.pdf [21] Ali Reza Ghavamipour, Benjamin Zi Hao Zhao, Oguzhan Ersoy, and Fatih Turkmen. 2024. Privacy-Preserving Aggregation for Decentralized Learning with Byzantine-Robustness. doi:10.48550/arXiv.2404.17970 arXiv:2404.17970 [cs]. [22] Marc González, Rachid Guerraoui, Rafael Pinot, Geovani Rizk, John Stephan, and François Taïani. 2025. ByzFL: Research Framework for Robust Federated Learning. arXiv:2505.24802 [cs.LG] https://arxiv.org/abs/2505.24802 [23] István Hegedűs, Gábor Danner, and Márk Jelasity. 2019. Gossip learning as a decentralized alternative to federated learning. In Distributed Applications and Interoperable Systems: 19th IFIP WG 6.1 International Conference, DAIS 2019, Held as Part of the 14th International Federated Conference on Distributed Computing Techniques, DisCoTec 2019. Springer, Springer, Kongens Lyngby, Denmark, 74–90. [24] Wassily Hoeffding. 1963. Probability inequalities for sums of bounded random variables. Journal of the American statistical association 58, 301 (1963), 13–30. [25] Yangsibo Huang, Samyak Gupta, Zhao Song, Kai Li, and Sanjeev Arora. 2021. Evaluating gradient inversion attacks and defenses in federated learning. Advances in neural information processing systems 34 (2021), 7232–7241. [26] Yufan Jiang, Maryam Zarezadeh, Tianxiang Dai, and Stefan Köpsell. 2025. AlphaFL: Secure Aggregation with Malicious2 Security for Federated Learning against Dishonest Majority. Cryptology ePrint Archive, Paper 2025/1289. https://eprint.iacr.org/2025/1289 [27] Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. 2020. Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing. [28] Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. 2021. Learning from History for Byzantine Robust Optimization. In Proceedings of the 38th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 139), Marina Meila and Tong Zhang (Eds.). PMLR, 5311–5319. https://proceedings.mlr.press/v139/karimireddy21a.html [29] Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. 2022. Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing. In International Conference on Learning Representations. [30] Marcel Keller, Emmanuela Orsini, and Peter Scholl. 2016. MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer. Cryptology ePrint Archive, Paper 2016/505. doi:10.1145/2976749.2978357 [31] Valerie King, Steven Lonargan, Jared Saia, and Amitabh Trehan. 2011. Load balanced scalable Byzantine agreement through quorum building, with full information. In Proceedings of the 12th International Conference on Distributed Computing and Networking (Bangalore, India) (ICDCN’11). Springer-Verlag, Berlin, Heidelberg, 203–214. [32] Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. 2006. Towards Secure and Scalable Computation in Peer-to-Peer Networks. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’06). IEEE Computer Society, USA, 87–98. doi:10.1109/FOCS.2006.77 [33] Eyal Kushilevitz, Yehuda Lindell, and Tal Rabin. 2010. Information-Theoretically Secure Protocols and Security under Composition. SIAM J. Comput. 39, 5 (March 2010), 2090–2112. [34] Liping Li, Wei Xu, Tianyi Chen, Georgios B. Giannakis, and Qing Ling. 2019. RSA: Byzantine-robust stochastic aggregation methods for distributed learning from heterogeneous datasets. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence (Honolulu, Hawaii, USA) (AAAI’19/IAAI’19/EAAI’19). AAAI Press, Article 190, 8 pages. doi:10.1609/aaai.v33i01.33011544 [35] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. 2017. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Proceedings of the 31st International Conference on Neural Information Processing Systems (Long Beach, California, USA) (NIPS’17). Curran Associates Inc., Red Hook, NY, USA, 5336–5346. [36] Yizhong Liu, Zixiao Jia, Zian Jin, Xiao Chen, Song Bian, Runhua Xu, Dawei Li, Jianwei Liu, and Yuan Lu. 2025. Aion: robust and efficient multi-round singlemask secure aggregation against malicious participants. In Proceedings of the 34th USENIX Conference on Security Symposium (Seattle, WA, USA) (SEC ’25). USENIX Association, USA, Article 156, 20 pages. [37] Hidde Lycklama, Lukas Burkhalter, Alexander Viand, Nicolas Kuchler, and Anwar Hithnawi. 2023. RoFL: Robustness of Secure Federated Learning. In 2023 IEEE Symposium on Security and Privacy (SP). IEEE, Article 33, 33 pages. doi:10.1109/ SP46215.2023.10179400 [38] Mohamad Mansouri, Melek Önen, Wafa Ben Jaballah, and Mauro Conti. 2023. Sok: Secure aggregation based on cryptographic schemes for federated learning. Proceedings on Privacy Enhancing Technologies (2023). [39] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Y. Arcas. 2017. Communication-Efficient Learning of Deep Networks

Conference’17, July 2017, Washington, DC, USA

from Decentralized Data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research, Vol. 54), Aarti Singh and Jerry Zhu (Eds.). PMLR, Fort Lauderdale Florida, USA, 1273–1282. [40] Luca Melis, Congzheng Song, Emiliano De Cristofaro, and Vitaly Shmatikov. 2019. Exploiting unintended feature leakage in collaborative learning. In 2019 IEEE symposium on security and privacy (SP). IEEE, IEEE, San Francisco, CA, USA, 691–706. [41] Viraaji Mothukuri, Reza M Parizi, Seyedamin Pouriyeh, Yan Huang, Ali Dehghantanha, and Gautam Srivastava. 2021. A survey on security and privacy of federated learning. Future Generation Computer Systems 115 (2021), 619–640. [42] Mahnush Movahedi, Jared Saia, and Mahdi Zamani. 2015. Secure Multi-party Shuffling. In Post-Proceedings of the 22nd International Colloquium on Structural Information and Communication Complexity - Volume 9439 (Montserrat, Spain) (SIROCCO 2015). Springer-Verlag, Berlin, Heidelberg, 459–473. doi:10.1007/9783-319-25258-2_32 [43] Milad Nasr, Reza Shokri, and Amir Houmansadr. 2019. Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning. In 2019 IEEE symposium on security and privacy (SP). IEEE, IEEE, San Francisco, CA, USA, 739–753. [44] Blanchard Peva, El Mhamdi El Mahdi, Guerraoui Rachid, and Stainer Julien. 2017. Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, Guyon Isabelle, von Luxburg Ulrike, Bengio Samy, Wallach Hanna M., Fergus Rob, Vishwanathan S. V. N., and Garnett Roman (Eds.). The MIT Press, Long Beach, CA, USA, 119–129. [45] Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. 2022. Robust aggregation for federated learning. IEEE Transactions on Signal Processing 70 (2022), 1142– 1154. [46] Mayank Rathee, Conghao Shen, Sameer Wagh, and Raluca Ada Popa. 2023. ELSA: Secure Aggregation for Federated Learning with Malicious Actors . In 2023 IEEE Symposium on Security and Privacy (SP). IEEE Computer Society, Los Alamitos, CA, USA, 1961–1979. doi:10.1109/SP46215.2023.10179468 [47] Amrita Roy Chowdhury, Chuan Guo, Somesh Jha, and Laurens van der Maaten. 2022. EIFFeL: Ensuring Integrity for Federated Learning. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (Los Angeles, CA, USA) (CCS ’22). Association for Computing Machinery, New York, NY, USA, 2535–2549. doi:10.1145/3548606.3560611 [48] Adi Shamir. 1979. How to share a secret. Commun. ACM 22, 11 (Nov. 1979), 612–613. doi:10.1145/359168.359176 [49] Muhammad Shayan, Clement Fung, Chris J. M. Yoon, and Ivan Beschastnikh. 2021. Biscotti: A Blockchain System for Private and Secure Federated Learning. IEEE Transactions on Parallel and Distributed Systems 32, 7 (July 2021), 1513–1525. doi:10.1109/TPDS.2020.3044223 [50] Jinhyun So, Başak Güler, and A Salman Avestimehr. 2020. Byzantine-resilient secure federated learning. IEEE Journal on Selected Areas in Communications 39, 7 (2020), 2168–2181. [51] Jinhyun So, Chaoyang He, Chien-Sheng Yang, Songze Li, Qian Yu, Ramy E Ali, Basak Guler, and Salman Avestimehr. 2022. Lightsecagg: a lightweight and versatile design for secure aggregation in federated learning. Proceedings of Machine Learning and Systems 4 (2022), 694–720. [52] Raj Kiriti Velicheti, Derek Xia, and Sanmi Koyejo. 2021. Secure Byzantine-Robust Distributed Learning via Clustering. In NeurIPS Workshop New Frontiers in Federated Learning: Privacy, Fairness, Robustness, Personalization and Data Ownership. [53] Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. 2020. Federated learning with differential privacy: Algorithms and performance analysis. IEEE transactions on information forensics and security 15 (2020), 3454–3469. [54] Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. 2020. Fall of empires: Breaking byzantine-tolerant sgd by inner product manipulation. In Uncertainty in artificial intelligence. PMLR, 261–270. [55] Andrew C. Yao. 1982. Protocols for secure computations . In 23rd Annual Symposium on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, CA, USA, 160–164. doi:10.1109/SFCS.1982.38 [56] Andrew Chi Chih Yao. 1986. HOW TO GENERATE AND EXCHANGE SECRETS.. In Annual Symposium on Foundations of Computer Science (Proceedings) (Annual Symposium on Foundations of Computer Science (Proceedings)). IEEE, 162–167. doi:10.1109/sfcs.1986.25 [57] Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. 2018. Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates. In Proceedings of the 35th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 80), Jennifer Dy and Andreas Krause (Eds.). PMLR, Stockholm, Sweden, 5650–5659. [58] Mahdi Zamani, Mahnush Movahedi, and Jared Saia. 2014. Millions of Millionaires: Multiparty Computation in Large Networks. Cryptology ePrint Archive, Paper 2014/149. https://eprint.iacr.org/2014/149 [59] Chengliang Zhang, Suyi Li, Junzhe Xia, Wei Wang, Feng Yan, and Yang Liu. 2020. { BatchCrypt } : Efficient homomorphic encryption for { Cross-Silo } federated

Ousmane Touat, César Sabater, Mohamed Maouche, and Sonia Ben Mokhtar

learning. In 2020 USENIX annual technical conference (USENIX ATC 20). 493–506. [60] Jingwen Zhang, Jiale Zhang, Junjun Chen, and Shui Yu. 2020. GAN Enhanced Membership Inference: A Passive Local Attack in Federated Learning. In ICC 2020 - 2020 IEEE International Conference on Communications (ICC). IEEE, Dublin, Ireland, 1–6. doi:10.1109/ICC40277.2020.9148790

A

Open Science

We provide an artifact available in the following anonymized code repository using anonymous.4open.science: Giskard Repository2 . This artifact contains three elements: • A fork from the ByzFL repository to run the Collaborative Learning experiments unde model poisoning attacks. • A Rust PoC of the procotol using the arkworks library to run the communication cost experiment and compute estimated latency • Additional python module to generate remaining figures

B

Generative AI Usage

While writing this manuscript, AI tools (Claude from Anthropic, Gemini from Google) were used for the following purposes: editorial review and sentence rephrasing. Apart from this, the intellectual contributions of this paper, namely the protocol design, the integration with the threat model, the security proofs, and the complexity analysis, were carried out without the assistance of an LLM. The authors take full responsibility for the accuracy, originality, and integrity of all content in the paper (text, figures, experimental data, and references). Table 2: Notation. Symbol

Meaning

System and threat model 𝑛, P, H, A Parties; honest / adversarial sets 𝑓 ,𝜖 Corruption count, 𝑓 = (1/4 − 𝜖 )𝑛 Tree and committees T, 𝑘, 𝐿, ℓ Tree; branching, depth, level 𝑚, 𝜏 Committee size; threshold 𝜏 < 𝑚/4 Cℓ,𝑐 Committee 𝑐 at level ℓ C𝑗 Leaf 𝑗’s base committee Cch , Cpa , C𝐿 Child, parent, root committee 𝑃𝑖 , 𝑃𝑟′ Parties in child / parent Median search 𝐷, 𝑢, 𝑞 Dimension, value range, precision x 𝑗 , p𝑡 Leaf input; pivot at iter. 𝑡 Left, Right Binary-search bounds b𝑗 Bits, 𝑏 𝑗,𝑑 = 1[𝑥 𝑗,𝑑 < 𝑝𝑡,𝑑 ] count𝑑 , 𝑀ˆ Aggregated count; median 𝑁 iter Median Search iterations Secret sharing [ · ], 𝜎𝑖 , 𝜎𝑟′ Share: generic, child, parent 𝑓𝑑 ,𝜓𝑖 Sharing / resharing polynomial 𝛼𝑖 , 𝜔𝑟 , 𝜆𝑖 Eval. points; Lagrange coeff. 𝐹X Ideal functionality for X

2 https://anonymous.4open.science/r/Giskard-ByzRobustConfidentialDL-B3E9

Giskard: Byzantine Robust and Confidential Aggregation for Large-Scale Decentralized Learning

C

Giskard Sub-Protocols description and Security Analysis

This appendix details the sub-protocols that instantiate Giskard in the information-theoretic setting, together with the security analysis. The underlying primitives are from the BGW framework [7]; we recall only what is needed.

C.1

Background: BGW Primitives

VSS-Share. The protocol follows Shamir secret sharing, augmented with a bivariate commitment to enable verification. A dealer holding secret 𝑠 samples a random bivariate polynomial 𝐵(𝑥, 𝑦) ∈ F𝑝 [𝑥, 𝑦] of degree 𝑡 − 1 in each variable, under the constraint 𝐵(0, 𝑦) = 𝑞(𝑦) where 𝑞 is the underlying univariate sharing polynomial with 𝑞(0) = 𝑠. The dealer sends each party 𝑃𝑖 the two univariate polynomials 𝑓𝑖 (𝑥) = 𝐵(𝑥, 𝑖) and 𝑔𝑖 (𝑦) = 𝐵(𝑖, 𝑦). Every pair (𝑃𝑖 , 𝑃 𝑗 ) then performs a pairwise consistency exchange: ?

𝑃𝑖 sends 𝑓𝑖 ( 𝑗) and 𝑔𝑖 ( 𝑗) to 𝑃 𝑗 , which checks 𝑓𝑖 ( 𝑗) = 𝑔 𝑗 (𝑖) and ?

𝑔𝑖 ( 𝑗) = 𝑓 𝑗 (𝑖). A failed check triggers a broadcast complaint. For each complaint from 𝑃 𝑗 , the dealer may either broadcast the full polynomial pair (𝑓 𝑗 , 𝑔 𝑗 ) to resolve it publicly, or remain silent. Parties whose complaints were resolved broadcast Consistent. Each 𝑃𝑖 accepts 𝑓𝑖 (0) = 𝐵(0, 𝑖) as its share of 𝑠 if and only if at least 𝑛 − 𝑡 Consistent messages are received. Multiply. Given degree-(𝑡 − 1) sharings of 𝑎 and 𝑏, the protocol outputs a degree-(𝑡 − 1) sharing of 𝑎𝑏 in two steps: (1) Each party locally computes the product of its input shares, obtaining a point on a degree-2(𝑡 − 1) polynomial that hides 𝑎𝑏. (2) Each party subshares (i) its two original input shares and (ii) its local product, each via a fresh random degree-(𝑡 − 1) polynomial. The consistency of the input subshares certifies that the product subshare indeed corresponds to the product of those inputs. Once verified, parties locally compute a public linear combination of the product subshares to recover a fresh degree-(𝑡 − 1) sharing of 𝑎𝑏.

Conference’17, July 2017, Washington, DC, USA

Protocol 1: InputShare Input. Each leaf 𝑗 holds x 𝑗 ∈ [𝑢] 𝐷 and the public pivot p𝑡 ∈ R𝐷 . BuildTree has assigned 𝑗 to a base committee C𝑗 of size 𝑚 with threshold 𝜏 < 𝑚/4. Output. Each 𝑃𝑖 ∈ C𝑗 holds [𝜎𝑑 ] 𝑖 for every 𝑑 ∈ [𝐷], where Í 𝜎𝑑 = 𝑗 𝑏˜ 𝑗,𝑑 . 1. Leaf-side sharing. For each 𝑑 ∈ [𝐷], leaf 𝑗 computes 𝑏 𝑗,𝑑 = 1[𝑥 𝑗,𝑑 < 𝑝𝑡,𝑑 ] and invokes VSS-Share(𝑏 𝑗,𝑑 ) toward C𝑗 . 2. VSS verification. The committee completes VSS verification for each [𝑏 𝑗,𝑑 ]. If verification rejects, [𝑏 𝑗,𝑑 ] ← [0]. 3. Bit-domain check. The committee jointly runs Multiply([𝑏 𝑗,𝑑 ], [1 − 𝑏 𝑗,𝑑 ]) and opens the result via VSS-Reconst. If the opened value is nonzero, [𝑏 𝑗,𝑑 ] ← [0]. 4. Local aggregation. Each 𝑃𝑖 ∈ C𝑗 locally computes ∑︁ [𝜎𝑑 ] 𝑖 ← [𝑏 𝑗,𝑑 ] 𝑖 for every 𝑑 ∈ [𝐷]. 𝑗 : 𝑃𝑖 ∈ C𝑗

Protocol 2: Reshare Input. Each 𝑃𝑖 ∈ Cch holds 𝜎𝑖 = 𝑓 (𝛼𝑖 ), where 𝑓 is a degree𝜏 polynomial. Both committees have size 𝑚 with threshold 𝜏 < 𝑚/4; {𝛼𝑖 } and {𝜔𝑟 } are the public evaluation points of Cch and Cpa . Output. Each 𝑃𝑟′ ∈ Cpa holds 𝜎𝑟′ = 𝑓 ′ (𝜔𝑟 ), where 𝑓 ′ is a fresh degree-𝜏 polynomial with 𝑓 ′ (0) = 𝑓 (0). 1. Sub-sharing. Each 𝑃𝑖 ∈ Cch invokes VSS-SubShare(𝜎𝑖 ) toward Cpa . Each 𝑃𝑟′ ∈ Cpa receives 𝑔𝑖 (𝜔𝑟 ), where 𝑔𝑖 is a degree-𝜏 polynomial with 𝑔𝑖 (0) = 𝜎𝑖 . 2. Local recombination. Let {𝜆𝑖 }𝑖 ∈ Cch be the Lagrange coefficients interpolating 𝑓 (0) from {𝑓 (𝛼𝑖 )}. Each 𝑃𝑟′ ∈ Cpa locally computes ∑︁ 𝜎𝑟′ ← 𝜆𝑖 · 𝑔𝑖 (𝜔𝑟 ). 𝑖 ∈ Cch

Full details appear in Protocol A.1 of [7].

C.2

Giskard Sub-Protocols

We present here the sub-protocols used in Giskard: InputShare, Reshare, and Broadcast Down. The first two are invoked during the aggregation phase; Broadcast Down propagates the value held by the root committee down the committee tree, edge by edge, until it reaches the leaves.

C.3

Proof of Theorem 3

Proof. Corruption is static and fixed before seed is sampled. Since seed is unpredictable, each committee is a uniformly random 𝑚-subset of [𝑛], so its corruption count follows Hyp(𝑛, 𝑓 , 𝑚). By Hoeffding’s reduction [24], upper-tail bounds for this hypergeometric are majorized by those of 𝑋 ∼ Bin(𝑚, 𝑓 /𝑛). We bound Pr[𝑋 ≥ 𝑚/4] via a multiplicative Chernoff bound: !  2 𝑚(𝑛 − 𝑓 ) 3𝑛 Pr[𝑋 ≥ 𝑚/4] ≤ exp − 1 − . · 4(𝑛 − 𝑓 ) 2𝑛

Protocol 3: Broadcast Down (in the Tree) Input. Each 𝑃𝑟′ ∈ Cpa holds the same public value 𝑣 ∈ R (e.g., a reconstructed pivot coordinate). Both committees have size 𝑚 with threshold 𝜏 < 𝑚/4. Output. Each honest 𝑃𝑖 ∈ Cch holds 𝑣. 1. Send. Each 𝑃𝑟′ ∈ Cpa sends 𝑣 to every 𝑃𝑖 ∈ Cch over authenticated channels. 2. Majority vote. Each 𝑃𝑖 ∈ Cch collects the received values {𝑣𝑟 }𝑟 ∈ Cpa and outputs the value with multiplicity > 𝑚/2.

Substituting 𝑓 /𝑛 = 1/4 − 𝜖,   16𝜖 2 𝑚(3/4 + 𝜖) Pr[𝑋 ≥ 𝑚/4] ≤ exp − · (3 + 4𝜖) 2 2   2 2𝜖 𝑚 = exp − . 3 + 4𝜖

Conference’17, July 2017, Washington, DC, USA

Ousmane Touat, César Sabater, Mohamed Maouche, and Sonia Ben Mokhtar

The total number of committees is 𝑂 (𝑛), so a union bound gives:   2𝜖 2𝑚 Pr[failure] ≤ 𝑛 · exp − . 3 + 4𝜖 For Pr[failure] ≤ 𝑛 −𝑐 with any desired constant 𝑐 > 0, taking logarithms: ln 𝑛 −

2𝜖 2𝑚 ≤ −𝑐 ln 𝑛 3 + 4𝜖 (1 + 𝑐)(3 + 4𝜖) 𝑚≥ ln 𝑛. 2𝜖 2

Since 𝜖 ∈ (0, 1/4) is fixed, this gives 𝑚 = 𝑂 (𝜖 −2 ln 𝑛).

C.4

□

UC security of InputShare

The security of InputShare follows from the fact that it is a particular application of BGW. A detailed security proof this scheme can be found in [7, Corollary 8.2]. We adapt the proof to our protocol below. Proof. We provide the ideal functionality 𝐹 InputShare (Fig. 1) and the simulator SInputShare (Fig. 1). The adversary corrupts a set Aleaf of leaves and a set 𝐼 ⊆ C1,𝑐 of committee parties with |𝐼 | ≤ 𝜏. We prove indistinguishability of the adversary’s view between the (𝐹 VSS-Share, 𝐹 Multiply )-hybrid execution of Π InputShare and the ideal execution using 𝐹 InputShare and SInputShare . The adversary’s view consists of three parts: the shares received from 𝐹 VSS-Share , the bit-check outputs from the 𝐹 Multiply calls, and the aggregated shares. • 𝐹 VSS-Share produces shares of each secret via a uniformly random degree-𝜏 polynomial. Since |𝐼 | ≤ 𝜏, the corrupt committee parties receive at most 𝜏 evaluations, which by the information-theoretic privacy of Shamir secret sharing are uniformly distributed over F |𝐼 | and independent of the underlying secret. This holds whether the shared value is the honest input bit 1[𝑥 𝑗,𝑑 < 𝑝𝑡,𝑑 ] or the simulator’s dummy input 0. • The same property applies to the bit-verification call to 𝐹 Multiply . For every honest leaf, 𝑏 𝑗,𝑑 (1 − 𝑏 𝑗,𝑑 ) = 0 in F, so both executions open to 0 (the simulator uses dummy input 0, and the real protocol shares a genuine bit). For every corrupt leaf, both worlds open 𝑏 ∗𝑗,𝑑 (1 − 𝑏 ∗𝑗,𝑑 ), which is 0 iff 𝑏 ∗𝑗,𝑑 ∈ {0, 1}; the simulator and 𝐹 InputShare zero out the contribution in exactly the same cases. The corrupt shares of [𝛿 𝑗,𝑑 ] are therefore uniformly distributed and independent of the input in both worlds. • In both executions, each corrupt party 𝑃𝑘 ∈ 𝐼 holds 𝜎𝑑,𝑘 = Í 𝑗 𝑗 𝑠𝑑,𝑘 . In the hybrid execution this is the evaluation at 𝛼𝑘 Í hyb of the implicit aggregate polynomial 𝑓𝑑 = 𝑗 𝑓𝑑𝑗 , which has degree 𝜏 and constant term 𝜎𝑑 . In the ideal execution, 𝐹 InputShare samples 𝑓𝑑 uniformly among degree-𝜏 polynomials with 𝑓𝑑 (0) = 𝜎𝑑 ; the simulator’s correction 𝑔𝑑 (with 𝑔𝑑 (0) = Δ𝑑 and 𝑔𝑑 (𝛼𝑘 ) = 0 for 𝑘 ∈ 𝐼 ) reconciles the corrupt evaluations, so that in both worlds the joint distribution of
𝑗 {𝑠𝑑,𝑘 } 𝑗, 𝑘 ∈𝐼 , {𝑓𝑑 (𝛼𝑘 )}𝑘 ∈𝐼 is identical. Conditioned on |𝐼 | ≤ 𝜏 evaluations of a uniformly random degree-𝜏 polynomial with

fixed constant term, the polynomial is uniquely determined on those points and uniform on the rest. Each component is identically distributed in the hybrid and ideal executions, so the adversary’s joint view is identically distributed. Security of ΠInputShare in the (𝐹 VSS-Share, 𝐹 Multiply )-hybrid model follows. By the composition theorem of Canetti [15] and [33] applied to the UC-realizations of 𝐹 VSS-Share and 𝐹 Multiply , Π InputShare UC-realizes 𝐹 InputShare against the concrete sub-protocols. □

Functionality 1 𝐹 InputShare Parameters. Dimension 𝐷; leaf set [𝑛]; base committee C1,𝑐 of size 𝑚; corruption sets Aleaf ⊆ [𝑛] and 𝐼 ⊆ C1,𝑐 with |𝐼 | ≤ 𝜏; pivot p𝑡 ∈ R𝐷 . Interface. (1) Honest Input. For each honest leaf 𝑗 ∈ [𝑛] \ Aleaf , receive (Input, x 𝑗 ) from 𝑗 and notify S with (Input, 𝑗). (2) Adversarial Input. Receive (Bits, {𝑏 ∗𝑗,𝑑 } 𝑗 ∈ Aleaf , 𝑑 ∈ [𝐷 ] ) from S. For each ( 𝑗, 𝑑), if 𝑏 ∗𝑗,𝑑 ∉ {0, 1}, set 𝑏 ∗𝑗,𝑑 ← 0. (3) Output. For each 𝑑 ∈ [𝐷], compute ∑︁ ∑︁ 𝜎𝑑 ← 1[𝑥 𝑗,𝑑 < 𝑝𝑡,𝑑 ] + 𝑏 ∗𝑗,𝑑 . 𝑗 ∈ Aleaf

𝑗∉Aleaf

Send (Aggregate, {𝜎𝑑 }𝑑 ∈ [𝐷 ] ) to S. Upon (Deliver) from S: for each 𝑑, sample a uniformly random degree-𝜏 polynomial 𝑓𝑑 with 𝑓𝑑 (0) = 𝜎𝑑 , and deliver 𝑓𝑑 (𝛼𝑖 ) to each 𝑃𝑖 ∈ C1,𝑐 .

C.4.1

Ideal functionality 𝐹 InputShare .

C.4.2

Simulator SInputShare .

C.5

Proof of Theorem 5

2 := 1 Proof. Let 𝜎 H |H|

Í

𝑗 ∈ H (𝑥 𝑗 −𝑥¯ H )

2 and set 𝑘

1 = ⌊𝑛/2⌋ +1−𝑓 ,

𝑘 2 = ⌊𝑛/2⌋ + 1. By the output bracket of Lemma 4, write 𝑀ˆ = 𝑣 + 𝛿 with 𝑣 ∈ [ℎ (𝑘1 ) , ℎ (𝑘2 ) ] and |𝛿 | ≤ 𝑞/2. For any 𝑣 ∈ [ℎ (𝑘1 ) , ℎ (𝑘2 ) ], |{ 𝑗 ∈ H : 𝑥 𝑗 ≤ 𝑣 }| ≥ 𝑘 1, |{ 𝑗 ∈ H : 𝑥 𝑗 ≥ 𝑣 }| ≥ |H | − 𝑘 2 + 1 = ⌈𝑛/2⌉ − 𝑓 . If 𝑣 ≥ 𝑥¯H , each of the ⌈𝑛/2⌉ − 𝑓 values with 𝑥 𝑗 ≥ 𝑣 ≥ 𝑥¯H contributes (𝑥 𝑗 − 𝑥¯H ) 2 ≥ (𝑣 − 𝑥¯H ) 2 , so ∑︁ 2 (⌈𝑛/2⌉ − 𝑓 )(𝑣 − 𝑥¯H ) 2 ≤ (𝑥 𝑗 − 𝑥¯H ) 2 = |H | 𝜎 H . 𝑗 ∈H

The case 𝑣 ≤ 𝑥¯H is symmetric via 𝑘 1 ≥ ⌈𝑛/2⌉ − 𝑓 , which holds under 𝑓 < 𝑛/4 for both parities of 𝑛. Hence 2 (𝑣 − 𝑥¯H ) 2 ≤ 𝜅 0 𝜎 H ,

𝜅 0 :=

𝑛−𝑓 . ⌈𝑛/2⌉ − 𝑓

(4)

By (𝑎 + 𝑏) 2 ≤ 2𝑎 2 + 2𝑏 2 and (4), 𝑞2

2 ( 𝑀ˆ − 𝑥¯H ) 2 ≤ 2(𝑣 − 𝑥¯H ) 2 + 2𝛿 2 ≤ 2𝜅 0 𝜎 H + 2. 2 , Under 𝑞 2 ≤ 𝜎 H

2 2 ( 𝑀ˆ − 𝑥¯H ) 2 ≤ 2𝜅 0 + 12 𝜎 H = 𝜅 𝜎H .

□

Giskard: Byzantine Robust and Confidential Aggregation for Large-Scale Decentralized Learning

Conference’17, July 2017, Washington, DC, USA

Simulator 1 SInputShare

C.6

Inputs. Adversarial bits {𝑏 ∗𝑗,𝑑 } 𝑗 ∈ Aleaf , 𝑑 ∈ [𝐷 ] ; corrupt committee set 𝐼 ⊆ C1,𝑐 with |𝐼 | ≤ 𝜏.

Proof. Part (i) follows by combining the InputShare cost at level-1 committees, 𝑂 ((𝑛/𝑘 𝐿 ) · 𝑚 2 ), with the Reshare cost at intermediate committees, 𝑂 (𝑘𝑚 2 ), giving   2  Δmax = 𝑂 max 𝑛·𝑚 , 𝑘𝑚 2 . 𝑘𝐿

Simulation. (1) VSS sharing. For each honest leaf 𝑗 ∉ Aleaf and each 𝑑 ∈ [𝐷], invoke 𝐹 VSS-Share on dummy input 0; record the 𝑗 resulting share 𝑠𝑑,𝑘 for each 𝑃𝑘 ∈ 𝐼 . For each corrupt leaf 𝑗 ∈ Aleaf and each 𝑑, invoke 𝐹 VSS-Share on input 𝑏 ∗𝑗,𝑑 and record the corresponding shares. (2) Bit check. For each ( 𝑗, 𝑑), invoke 𝐹 Multiply on the shared values ( [𝑏 𝑗,𝑑 ], [1 −𝑏 𝑗,𝑑 ]) to obtain a sharing [𝛿 𝑗,𝑑 ]; record 𝑗 each corrupt party’s share 𝛿𝑑,𝑘 for 𝑘 ∈ 𝐼 . Simulate VSS-Reconst([𝛿 𝑗,𝑑 ]): for honest leaves the opened value is 0; for corrupt leaves the opened value is 𝑏 ∗𝑗,𝑑 (1 − 𝑏 ∗𝑗,𝑑 ). If the opened value is nonzero, treat leaf 𝑗’s contribution for coordinate 𝑑 as zero in what follows. (3) Extraction. Send (Bits, {𝑏 ∗𝑗,𝑑 } 𝑗 ∈ Aleaf , 𝑑 ∈ [𝐷 ] ) to 𝐹 InputShare and receive {𝜎𝑑 }𝑑 ∈ [𝐷 ] . (4) Corrected Aggregation. For each 𝑑 ∈ [𝐷], let Δ𝑑 = 𝜎𝑑 − Í ∗ 𝑗 ∈ Aleaf 𝑏 𝑗,𝑑 (accounting for bit-check zero-outs). Sample a uniformly random degree-𝜏 polynomial 𝑔𝑑 with 𝑔𝑑 (0) = Δ𝑑 and 𝑔𝑑 (𝛼𝑘 ) = 0 for all 𝑃𝑘 ∈ 𝐼 . For each 𝑃𝑘 ∈ 𝐼 , record Í 𝑗 𝜎𝑑,𝑘 ← 𝑗 𝑠𝑑,𝑘 as the corrupt party’s final aggregate share (which, by construction of 𝑔𝑑 , is consistent with a global polynomial 𝑓𝑑 of constant term 𝜎𝑑 ). (5) Deliver. Send (Deliver) to 𝐹 InputShare .

Proof of Theorem 6

Balancing (𝑛/𝑘 𝐿 ) · 𝑚 2 = 𝑘𝑚 2 gives 𝑘 𝐿+1 = 𝑛, and with 𝑘 = 𝑂 (1) and 𝑚 = 𝑂 (log 𝑛) we obtain Δmax = 𝑂 (log2 𝑛). Part (ii): since each party is assigned to at most one committee per level, it participates in at most 𝐿 = 𝑂 (log 𝑛) committees per iteration. Within a committee, a party pays Δmax per iteration per coordinate, giving Δeff max = Δleaf + 𝑑 · 𝐿 · 𝑁 iter · Δmax , where Δleaf = 𝑂 (𝑑𝑁 iter 𝑚 2 ) covers one VSS-Share boolean verification Multiply per coordinate. Summing, 𝑑 · 𝑁 iter · 𝐿 · Δmax = 𝑑 · 𝑁 iter · 𝑂 (log 𝑛) · 𝑂 (log2 𝑛) = 𝑂 (𝑑𝑅 log3 𝑛), and the leaf term is a factor log 𝑛 smaller and absorbed. Part (iii): InputShare costs 𝑂 (𝑑 𝑛𝑚 2 ) total (one VSS-Share per leaf per coordinate), bit verification costs 𝑂 (𝑑 𝑛𝑚 3 ) total (one Multiply per leaf per coordinate), and Reshare costs 𝑂 (𝑑 𝑚 3 ) per Í𝐿−1 𝐿−ℎ 𝑘 = 𝑂 (𝑛) instances (since 𝑘 = 𝑂 (1)), giving instance over ℎ=0 3 𝑂 (𝑛𝑚 ). Summing over 𝑁 iter iterations and applying 𝑚 = 𝑂 (log 𝑛) yields 𝑂 (𝑑𝑁 iter𝑛 log3 𝑛). □