Splitting the Field: Small-Alphabet Arithmetic for Quantum-Safe, Byzantine-Robust Secure Aggregation

Federated learning lets many devices train one model without sending raw data. Two standard defenses pull against each other. Secure aggregation hides each device's update from the server. Byzantine filtering, meaning the detection of devices that send poisoned updates, needs the server to inspect those updates. One scheme breaks this deadlock and does so with information-theoretic privacy: the privacy guarantee holds even against an attacker with unbounded computing power, so a quantum computer does not threaten it. That scheme is ByITFL. Each update is cut into shares that are evaluations of a random polynomial, a technique called Lagrange coded computing. The server then evaluates a polynomial approximation of a trust-scoring rule directly on the shares. The cost of all this sits in one number that is easy to overlook: the size of the finite field the shares live in. That field must have enough distinct points to give every participant a share. It must also be large enough that a degree-$k$ polynomial of fixed-point gradients, summed over all users, never wraps around modulo the field size. On edge hardware, a wide field means wide multipliers. Wide multipliers are exactly where side-channel protection becomes expensive.

This proposal claims that the single large field in coded secure aggregation actually does two separate jobs, and that the two jobs can be paid for separately with much smaller arithmetic. The numeric range requirement can be met by a residue number system (RNS), which runs the computation in parallel over several small primes and recombines the results by the Chinese remainder theorem. The supply of evaluation points can be met by moving to an extension field over a small base field. This is the same scalar-versus-vector trade studied in network coding. We will build this decomposition, prove that it keeps ByITFL's privacy and Byzantine guarantees, and measure what it buys: bits per share, client and worker compute, and FPGA area for the encoder with and without masking.

Core Claim

Assume clients quantize updates to $b$ bits, the trust-scoring rule is approximated by a degree-$k$ polynomial with $c$-bit coefficients, and $n$ users participate. A scalar prime field $\mathbb{F}_P$ must then satisfy

$$ \log_2 P \gtrsim kb + c + \log_2 n \quad \text{and} \quad P > n. $$

The first condition comes from bit growth: a product of $k$ values of $b$ bits each has about $kb$ bits, and summing $n$ terms adds $\log_2 n$ more. The second condition comes from needing $n$ distinct evaluation points. For realistic $k$ and $b$, the first condition dominates by a wide margin.

We propose running the protocol over $r$ small primes $p_1,\dots,p_r$ whose product covers the range requirement. Each channel shares its residue with independent randomness. If some prime $p_i$ is smaller than $n$ (we want primes of 8 to 13 bits so that the multipliers are cheap), that channel draws its evaluation points from $\mathbb{F}_{p_i^t}$ with $t = \lceil \log_{p_i} n \rceil$. The polynomial's coefficients and the secrets stay in the base field $\mathbb{F}_{p_i}$, so the decoded result is still correct modulo $p_i$. Shares grow by a factor of $t$ in that channel, but every multiplication is narrow.

The new part is not RNS by itself. HRaccoon already split a 49-bit lattice modulus into 24-bit and 25-bit channels to save DSP blocks. What is new is three things. First, we recognize that coded Byzantine-robust aggregation has a separable two-part field requirement. Second, we use alphabet-reduction ideas to keep each channel small even when it has fewer elements than there are users. Third, we show that the resulting narrow arithmetic is what makes masked client hardware affordable.

Grounding in Prior Work

Several papers motivate the field-size concern. On the Gap between Scalar and Vector Solutions of Generalized Combination Networks shows that scalar network codes need an extra 6 to 9 bits per symbol compared with vector codes, and that this gap grows with the number of intermediate nodes. Network-Coding Solutions for Minimal Combination Networks and Their Sub-Networks proves that the gap is strictly positive even with two sources. Vector Network Coding Based on Subspace Codes Outperforms Scalar Linear Network Coding builds the vector solutions explicitly. All three study faithful relaying of linear combinations. None of them computes nonlinear functions on shares or considers Byzantine senders. Our setting needs both.

The rank-metric survey Rank-Metric Codes and Their Applications constrains the design. Gabidulin codes reach the MDS-style bound over a tiny base field, but they are built from linearized polynomials, which are linear over the base field. They can therefore carry the linear summation step but not the degree-$k$ products that the trust score needs. For that reason we use rank-metric and vector constructions only for the purely linear final aggregation. We use extension-field Lagrange evaluation for the nonlinear scoring.

ByITFL supplies the protocol we modify. That includes its polynomial approximation of FLTrust's ReLU-based score, its use of information-theoretic verifiable secret sharing (a check that catches users who hand out inconsistent shares), and its user budget $n \ge 2b' + (k+2)(m+t'-1)+p+1$. Here $b'$ counts Byzantine users, $m$ is the number of coded data partitions, $t'$ is the colluder threshold, and $p$ is a dropout allowance; we prime the symbols to avoid clashing with quantization bits $b$. ByITFL was evaluated on a shallow CNN on MNIST with 40 users and runs over one scalar field.

Beskar shows how to make the channels post-quantum with Kyber and Dilithium and offline precomputation, but it protects only against an honest-but-curious server. We use its approach for one specific job. Information-theoretic sharing is only quantum-safe if the pairwise channels that carry shares are also quantum-safe. Otherwise an adversary can record the share traffic now and decrypt it later, once quantum computers exist. Post-Quantum Cryptography (PQC) Network Instrument documents that this record-now-decrypt-later threat is current: it measured only 0.029% post-quantum adoption across 20.5 million SSH connections.

Two hardware papers set the cost model. BoMaNet reports that full Boolean masking costs 5.3× the LUTs and 6.8× the flip-flops. It also warns that masking multibit arithmetic causes area blow-up and routing congestion. That warning is the reason narrow channels should matter.

Research Program

The work has three parts.

Theory. We will prove that CRT-split, extension-evaluated Lagrange sharing keeps ByITFL's privacy against $t'$ colluders and its detection guarantees against $b'$ Byzantine users. One subtlety needs care. A Byzantine user could send residues that are each valid on their own channel but inconsistent across channels. Per-channel verifiable secret sharing does not catch this, so we need either a cross-channel consistency check or an argument that the trust score is computed per channel and is robust to such inconsistency. We will also derive the total share size. It is the sum over channels of $t_i \log_2 p_i$ bits. The scalar baseline uses $\log_2 P$ bits. The analysis should show where the split design wins: small primes plus extension fields win when $n$ is large and $k$ is high, and plain RNS suffices when $n$ is small.

Systems. We will implement both designs in software at 40 to 1,000 simulated users. For hardware, we will build the client encoder and a worker's share-evaluation unit on an AMD Artix-7 FPGA, the platform HRaccoon used, in three versions: a wide prime field, RNS only, and RNS plus extension fields. Each version will be built unmasked and with first-order arithmetic masking. The encoder only computes a linear map of the secret plus randomness, so masking it should cost close to twice the logic, not the multiples BoMaNet saw for nonlinear logic. Our hypothesis is that the remaining overhead tracks multiplier width.

Physical leakage. We will check a property that coded computation suggests: a worker holds one share, and one share is independent of the data. Physical leakage at a single worker should therefore be equivalent to corrupting that worker, which the colluder threshold $t'$ already absorbs, so workers would need no gate-level masking. We will test this empirically rather than assume it.

Baselines

The naive reference point is FLTrust with no privacy, together with plain averaging (FedAvg) under the same attacks. These bound the accuracy we can hope for and show the damage poisoning does without any filter.

The strongest existing method on this exact question is ByITFL as published, over a single scalar prime field. It reports "near 90%" accuracy on MNIST under trim and label-flipping attacks with 50% Byzantine users among 40 clients (ByITFL). No reported result was found on Lacuna for ByITFL's field size, bits per share, or hardware cost. We will therefore re-implement it with the same polynomial degree, quantization, user count, attacks, and training schedule, and measure those quantities ourselves. Beating it means matching its accuracy within one percentage point while cutting total bits per share and FPGA encoder area under masking, at equal throughput.

The hardware-isolation competitor is SEAR. It runs Byzantine filtering inside an Intel SGX enclave and reports aggregating 1,000 clients in 4 to 7 seconds on a LAN. We will run it on the same MNIST and CIFAR-10 models. We expect it to win on raw speed. The comparison is meant to show the price of a guarantee that does not rest on the enclave or on classical attestation.

Beskar is the post-quantum but semi-honest reference. Under poisoning it should lose accuracy, and that loss justifies paying for Byzantine robustness at all.

Two ablations isolate the key ingredients: RNS without extension-field points, and an extension field without RNS splitting. Each runs on the same configurations as the full design.

Why not just…?

Why not just apply HRaccoon-style RNS to ByITFL and stop? This is a real threat. At 40 users, any prime above 40 supplies enough evaluation points, so plain RNS may capture nearly all the gain. The extension-field component only pays off when the target prime is smaller than the number of users. That happens with roughly 8-bit primes, which are attractive for compact masked multipliers, at hundreds to thousands of users. The RNS-only ablation, swept over $n$ from 40 to 1,000 and prime width from 8 to 16 bits, will locate the crossover. If no crossover appears in realistic regimes, we will report RNS-only as the recommended design and drop the extension component.

Why not just lower the polynomial degree or quantize more coarsely? The range term $kb$ shrinks directly when either goes down, with no new machinery. The cost is that a cruder ReLU approximation or coarser gradients may weaken Byzantine filtering, and ByITFL gives no data on this trade. We will sweep $k$ and $b$ and plot attack accuracy against total share bits. Our design must sit on a better frontier than the scalar design does at reduced $k$ and $b$, not merely beat the scalar design at fixed $k$ and $b$.

Why not just use a trusted enclave as SEAR does? SEAR's guarantee depends on the enclave's microarchitecture not leaking and on classical remote attestation. DDM and PREFENDER document cache and SMT leakage channels of the kind that threaten it. Our worker leakage experiment tests the opposite claim for coded shares: that leakage from one machine reveals nothing about the data.

Why not just add differential privacy to Beskar? Noise does not detect poisoned updates. Beskar itself reports that local differential privacy reaches 0.78 accuracy against 0.87 for central differential privacy at $\epsilon=10$ on MNIST, with a sharper decline on CIFAR-100.

Proposed Experiments

Accuracy experiments use MNIST and CIFAR-10. We follow ByITFL's attack settings (trim attack and label flipping, up to 50% Byzantine users) and scale from 40 to 1,000 users. Systems metrics are bits per share, per-round communication, client encoding time, and server scoring time.

On the FPGA we measure LUTs, flip-flops, DSP blocks, and latency for every combination of field design and masking. We run test vector leakage assessment (TVLA), a statistical test for whether power traces depend on secret data, on the masked encoder. On an unmasked worker we run a correlation power attack that tries to recover the client's gradient from that worker's traces. The prediction is a TVLA t-statistic that fails to show leakage of the share, and an attack whose success stays at chance however many traces it uses.

Three outcomes settle the claim. First, the full design must match ByITFL's accuracy within one point. Second, it must reduce masked encoder area relative to the wide-field design at equal throughput. Third, the crossover sweep must show at least one realistic regime where the extension-field component beats RNS alone. If the second outcome fails, the hardware motivation fails. If only the third fails, we narrow the contribution to an RNS redesign of coded Byzantine-robust aggregation.