SESAME: Communication-Optimal Secure Aggregation for Sign-Based Federated Learning

Sign-based federated learning, where each client sends a binary gradient $g_i \in \{-1,+1\}^L$ instead of full-precision weights, compresses per-client communication to just $L$ bits. Applying LWE-based secure aggregation (OPA \citep{C:KarPol25}) naively inflates this back to $L\log_2 q$ bits, a $\log_2 q$-fold *SecAgg Tax*. We introduce **SESAME**, which eliminates this tax by treating the LWE modulus as a *plaintext capacity budget* rather than only a security parameter. Three composable primitives spend that capacity entirely in the plaintext domain, before encryption. - **Positional Plaintext Packing (PPP)** encodes $k$ Count-Sketch bucket values as digits of a single integer, reducing ciphertext elements by $k\times$. - **RHT + Count-Mean** spreads gradient energy via a Randomized Hadamard Transform, so a single sketch row ($r=1$) matches the accuracy of five. - **Noise-Tolerant Packing (SNT)** observes that LWE decryption failures produce only $\pm 1$ bucket errors, absorbed by the sketch estimator (changing ${\approx}0.05\%$ of aggregate signs at a $5\%$ failure rate), permitting a ${\approx}2.5\times$ tighter noise margin. On CIFAR-10 ($n=100$, ResNet-20), **SESAME** transmits a **23.5 KB** gradient payload, $45\times$ below float32 FedAvg with naive OPA, plus a fixed $50.0$ KB share cost, for **$14\times$** total reduction over plaintext FedAvg. End-to-end on ResNet-50 ($23.7$M parameters), we measure a **$315\times$** total reduction with no accuracy cost from the privacy layer. The construction is UC-secure against a malicious server by reduction to OPA.