Progressive-Resolution Secure Aggregation for Federated Learning

1

Progressive-Resolution Secure Aggregation for Federated Learning

arXiv:2610.00695v1 [cs.CR] 30 Sep 2026

Seyed Mohammad Azimi-Abarghouyi, Member, IEEE

Abstract—Secure aggregation lets a server recover an aggregate of client updates without observing any individual update, but conventional protocols fix the aggregate precision when clients upload. We introduce and formulate a new progressive-resolution secure-aggregation functionality in which clients upload once and successively finer resolutions of the same aggregate can later be authorized without renewed client participation. To realize this functionality, we propose progressive-resolution secure aggregation (PSA): each clipped, dithered update is represented by compatible nested-lattice digits; separately releasable layers are protected by secure aggregation and an additional aggregate pad that remains unavailable to the server until a non-colluding release controller authorizes that layer. Separate modular sums create an overflow risk, for which we derive worst-case and concentration-based margin rules. Under independent zero-mean √ layer symbols and normalized aggregate-noise scale O( K), the 1 sufficient margin for K clients and radix ρ is 2 logρ K + O(1) radix steps. Under an i.i.d. uniform-digit prior, a matching converse shows that the same order is necessary within the class of interfaces that expose each separately authorized release through one modular sum; equivalently, each additional release carries an arithmetic-payload premium of order 12 log2 K bits per model dimension relative to a single-stage interface. We also give release-by-release differential-privacy accounting and resolutiondependent distortion bounds. Exact finite-alphabet calculations exhibit margin scaling consistent with the analysis. Federated experiments on MNIST and CIFAR-10 show that PSA coincides with a flat secure sum when progressive release is not used and quantify the accuracy–payload trade-off against distributed discrete-Gaussian and Skellam mechanisms at matched privacy. Index Terms—Federated learning, secure aggregation, differential privacy, lattice codes, nested lattices, quantization, private summation.

I. I NTRODUCTION

F

EDERATED learning (FL) keeps raw data at clients and exposes model updates through aggregation [1]. Secure aggregation (SecAgg) cryptographically restricts the server to a prescribed aggregate, while distributed differential privacy (DP) can limit what the released aggregate reveals by adding client-side noise before aggregation [2]–[5]. These mechanisms control the content of an aggregate but not the precision at which it is disclosed. Once a fine-precision aggregate has been decoded, rounding it afterward cannot undo the finer disclosure. This matters when the precision required by an approved analysis is not known when clients upload, particularly in cross-device settings where participants may be unavailable for a second upload. Committing every query to the finest potentially useful precision can therefore disclose more than the eventual purpose requires. For example, a coarse hospital statistic may already determine on which side of a The author is with the Department of Electrical Engineering, Chalmers University of Technology, Gothenburg, Sweden (Email: azimimo@chalmers.se).

decision threshold the population lies, making a finer value unnecessary. Disclosure-control guidance similarly cautions against publishing more precision than a purpose requires [6], the data-minimization principle of the EU General Data Protection Regulation limits processing to what is necessary for the stated purpose [7], and tiered data-access agreements operationalize the same idea by granting an analyst the coarsest view sufficient for an approved analysis. The resulting design goal is a minimum-necessary-resolution policy: release a coarse aggregate first and refine it only when justified, without recalling the clients. Existing approaches do not provide this combination. Lattice quantizers for FL provide fixed-resolution compression and may incorporate privacy noise [8]–[11]; threshold or splittrust systems can delay aggregate decryption [12], [13]; and distributed DP under SecAgg controls the information released by an aggregate [4], [5]. None of these mechanisms by itself gives mutually consistent coarse and fine parts that can be authorized separately after one client upload. To realize this interface, we propose progressive-resolution secure aggregation (PSA). PSA combines two logically distinct components. First, a compatible nested-lattice representation decomposes each quantized update into bounded refinement layers such that every newly released layer refines the same quantized value rather than replacing it by an independently quantized surrogate. Second, a sealed-release gate adds data-independent pad shares whose aggregate remains unknown to the server until a non-colluding controller or trustee set authorizes the corresponding layer. Ordinary SecAgg still protects individual uploads. The gate is treated as an abstract functionality rather than a new threshold cryptosystem: its realization is delegated to standard threshold or multi-server tools [12], [13], and the contribution of this paper is the progressively refinable representation presented to that gate together with a characterization of the costs induced by making its layers separately releasable. Thus, PSA separates the algebraic mechanism that enables consistent coarse-to-fine reconstruction from the release mechanism that controls when each refinement becomes visible. The structured representation is needed because independently releasable pieces must remain closed under aggregation and admit controlled modular reduction. A compatible lattice chain supplies both properties: layer sums remain on the corresponding lattice, and successive released layers reconstruct a consistent coarse-to-fine sequence. A gate without such a representation would only delay an all-or-nothing value, while the representation without a gate would not enforce delayed disclosure. To our knowledge, this is the first formulation of

2

secure aggregation that enables post-upload progressive authorization of successively finer resolutions of the same aggregate without renewed client participation. We further characterize the overflow, communication, privacy, and distortion costs induced by making these refinements separately releasable. A. Contributions The paper makes the following contributions. 1) We formalize progressive-resolution aggregate release after a single client upload and give a PSA architecture based on compatible nested-lattice layers, modular SecAgg, and aggregate release pads. 2) For K clients and radix ρ, we characterize the carries induced by separate modular reductions. We derive a worstcase-data margin of order logρ K and, under independent zero-mean √ layer symbols with normalized aggregate-noise scale O( K), a margin 12 logρ K + O(1). 3) For interfaces exposing each separately authorized release only through one modular sum, we prove the same 1 2 logρ K margin order necessary under an i.i.d. uniformdigit prior. This converse is interface-specific and is not a lower bound for arbitrary interactive or jointly encoded protocols. 4) We give release-by-release Rényi-DP composition, instantiate it with product discrete-Gaussian noise, and compare its leading sensitivity cost with a matched flat representation. When the admissible range fills the balanced digit alphabet in every coordinate, the leading bound is neutral rather than strictly better. 5) We derive exact full-resolution dithered-quantization meansquared error (MSE), distribution-free truncation bounds, and geometric truncation scaling under an explicit uniformresidue condition. 6) We evaluate the claims in the regimes in which they are stated: exact finite-alphabet calculations examine carry and arithmetic-payload scaling, while federated experiments on MNIST and CIFAR-10 compare PSA with distributed discrete-Gaussian and Skellam mechanisms at matched differential-privacy targets and use a compression-only lattice baseline to isolate representation cost. II. R ELATED W ORK Secure aggregation and distributed DP. Pairwise-masked SecAgg reveals a sum while hiding individual inputs [2], with later protocols reducing its overhead [3]. The distributed discrete-Gaussian [4] and Skellam [5] mechanisms add clientside integer noise and account for quantization and modular wraparound of a single released sum. PSA differs in functionality: several mutually consistent resolutions must remain separately releasable after one upload, so each separately sealed sum requires its own overflow protection. Delayed decryption and split trust. Additively homomorphic and threshold encryption [12], and multi-server systems such as Prio [13], can withhold decryption capability until an authorized party or quorum acts. PSA can use such mechanisms to realize its release controller, but does not claim a new decryption primitive. Its contribution is the object presented

to that gate: a coarse-to-fine decomposition whose authorized parts reconstruct one consistent aggregate. Quantization for FL. UVeQFed [8] uses subtractive-dithered lattice quantization of model updates; JoPEQ [9] combines lattice quantization with privacy noise; compressed private aggregation [10] uses nested quantizers for rate refinement within a release; and OLALa [11] adapts lattices to heterogeneous clients. In these methods, nesting primarily serves rate–distortion or adaptation. PSA instead assigns nesting to an authorization order, which requires successive pieces to reconstruct one another exactly rather than merely reduce distortion. ScionFL [14] addresses malicious inputs to modular secure aggregation, a threat excluded by the present honestbut-curious model and therefore complementary to PSA. Nested lattices and computation. Nested lattices are established structured-coding tools [15], including for multi-layer computation [16] and lattice-coded FL [17], [18]. Those works exploit closure under integer combinations. PSA uses the same algebraic property for secure aggregation, but additionally requires a digit-compatibility condition so that successive quantizer differences are valid bounded representatives. The canonical construction used here is the balanced odd-radix integer chain. III. P RELIMINARIES A. Lattice Notation and Compatible Digits For a block dimension nb ≥ 1, let a full-rank lattice Λ ⊂ Rnb have nearest-neighbor quantizer QΛ (x) ∈ arg minλ∈Λ ∥x − λ∥. Its centered Voronoi region is V, with boundary ties fixed deterministically, and centered reduction is [x] mod Λ = x − QΛ (x). Denote its covering radius, packing radius, and per-dimension second moment by rcov (Λ), rpack (Λ), and σ 2 (Λ), respectively. Fix a number of layers L ≥ 1 and an odd integer radix ρ ≥ 3. Consider the self-similar chain Λℓ+1 = ρΛℓ , ΛL+1 ⊂ · · · ⊂ Λ1 , ℓ ∈ {1, . . . , L}.

(1)

For each layer, the quotient group Gℓ = Λℓ /Λℓ+1 has |Gℓ | = ρnb . Let Cℓ ≜ Λℓ ∩Vℓ+1 under the same boundary convention. Then Cℓ is a complete set of coset representatives for Gℓ , so every element of Λℓ is congruent modulo Λℓ+1 to exactly one element of Cℓ . Nesting alone does not ensure that consecutive quantizers produce one of these representatives. PSA therefore uses the following structural condition. Assumption 1 (Digit-compatible chain). For every x ∈ Λ1 ∩ VL+1 and every ℓ ∈ {1, . . . , L}, QΛℓ (x) − QΛℓ+1 (x) ∈ Cℓ .

(2)

The canonical construction satisfying Assumption 1 is Λ1 = hZnb ,

Λℓ = hρℓ−1 Znb ,

(3)

where h > 0. Coordinatewise nearest-integer rounding gives the balanced radix-ρ alphabet n  ρ−1 b ρ−1 ℓ−1 ,..., , (4) Cℓ = hρ − 2 2

3

and (2) follows from balanced Euclidean division. For this integer chain with odd ρ, no point of Λℓ lies on the boundary of Vℓ+1 , so the alphabet needs no boundary tie-breaking and satisfies Cℓ = −Cℓ . Thus odd ρ makes the representative alphabet symmetric about the origin. If c is uniform on Cℓ , then E∥c∥2 = nb h2 ρ2(ℓ−1)

ρ2 − 1 . 12

(5)

Equation (5) is a property of a uniform digit model; it is not implied by subtractive dithering or by Assumption 1. IV. P ROGRESSIVE -R ESOLUTION S ECURE AGGREGATION A. Setting There are K ≥ 1 clients indexed by k ∈ {1, . . . , K}. Client k holds an update uk ∈ Rd , where d is the model dimension. Let µ0 ∈ Rd be a shared reference and let ∆ > 0 be the clipping radius. Writing clip∆ for clipping to Euclidean norm at most ∆, define s∆ = Kµ0 +

K X

gk ,

gk = clip∆ (uk − µ0 ),

(6)

k=1

so ∥gk ∥ ≤ ∆.PThe protocol targets s∆ ; when clipping is inactive, s∆ = k uk . Each d-dimensional vector is processed in J = ⌈d/nb ⌉ lattice blocks, zero-filled in the last block if necessary. Recentering on µ0 , typically the previous global model, reduces the range that the lattice chain must cover. B. Threat Model and Scope For individual-update privacy, PSA retains the honest-butcurious SecAgg model: the aggregation server may collude with a bounded number of clients, and dropouts are handled by the underlying SecAgg recovery protocol [2], [3]. For delayed aggregate release, PSA additionally assumes that the aggregation server does not collude before authorization with the release controller or with a threshold of trustees. The controller handles only data-independent gate material and receives neither individual updates nor an unmasked aggregate. Each separately authorizable layer will be sealed by an aggregate release pad. The information-theoretic delayed-release statements require that pad, for every unreleased layer and realized active set, to be uniform and unknown to the server; pseudorandom pads replace perfect hiding by computational indistinguishability. If the controller colludes with the server before a release, delayed authorization for that release is lost, while the underlying SecAgg protection of individual uploads remains. The analysis excludes active poisoning, malformed lattice symbols, verifiable authorization policy, and traffic analysis; participation metadata and the identities of released layers are public. Robust input validation such as [14] is complementary; because each PSA symbol is a bounded digit, such validation reduces to per-layer range checks on the modular uploads, at a cost that scales with the number of separately sealed sums. The release pad and DP noise serve different purposes: the pad hides an unauthorized layer aggregate, whereas DP limits what an authorized aggregate reveals. The gate does not remove information about a withheld refinement that is already implied by authorized outputs.

C. Client Encoding 1) Scaling and subtractive dithering. A public gain a > 0 maps the clipped update into the lattice range. The formulas below describe one nb -dimensional block; to avoid an additional block index, that block of gk is denoted again by gk . Client k sets vk = agk and draws an independent public dither dk ∼ Unif(V1 ), independent of the update. Define ek = QΛ1 (vk + dk ) − dk − vk . Under the standard subtractive-dither model [15], ek is independent of vk , has zero mean, E∥ek ∥2 = nb σ 2 (Λ1 ), and satisfies ∥ek ∥ ≤ rcov (Λ1 ) almost surely. The client forms xk = QΛ1 (vk + dk ) ∈ Λ1 , hence xk = vk + dk + ek and ∥xk ∥ ≤ B ≜ a∆ + 2rcov (Λ1 ). The sufficient range condition B < rpack (ΛL+1 ) = ρL rpack (Λ1 ) places every xk inside VL+1 and gives QΛL+1 (xk ) = 0. 2) Compatible telescoping decomposition. Under Assumption 1, for each ℓ ∈ {1, . . . , L} define xℓk = QΛℓ (xk ) − QΛℓ+1 (xk ) ∈ Cℓ , xk =

L X

xℓk .

(7) (8)

ℓ=1

For any ℓ0 ∈ {1, . . . , L}, telescoping also gives L X

xℓk = QΛℓ0 (xk ),

(9)

ℓ=ℓ0

so larger layer indices are coarser and decreasing ℓ0 adds finer refinements of the same quantized point. 3) Per-layer DP noise. Client k draws zero-mean lattice noise zℓk ∈ Λℓ , independently across clients and layers and independently of the data and dithers, and transmits the noisy eℓk = xℓk + zℓk . For the integer-chain DP layer symbol x instantiation, each coordinate has probability mass   (hρℓ−1 j)2 ℓ−1 , j ∈ Z, (10) P[Z = hρ j] ∝ exp − 2s2ℓ where sℓ > 0 is the discrete-Gaussian scale in physical lattice units. Its actual per-coordinate variance is denoted s̄2ℓ . This is the discrete Gaussian analyzed in [19]. D. Per-Layer Secure Aggregation and Sealed Release A single-client digit lies in Cℓ , whereas the sum of K such digits has a larger dynamic range. For each layer choose an integer overflow margin mℓ ≥ 0 and define the modulus lattice and finite quotient Λ(ℓ) = ρmℓ Λℓ+1 , Ḡℓ = Λℓ /Λ(ℓ) ∼ = (Z/ρ1+mℓ Z)nb .

(11) (12)

Let Aℓ ⊆ {1, . . . , K} denote the realized active set for layer ℓ. Client k ∈ Aℓ contributes a release-pad share bℓk ∈ Ḡℓ . The shares are independent across clients, layers, and rounds. If at least one active honest client contributes a share that

4

is uniform on Ḡℓ , independent of the remaining shares, and unknown to the server, then the aggregate pad " # X ℓ Bℓ = bk mod Λ(ℓ) (13) k∈Aℓ

coarsened integer chain Λ′r+1 = ρbr Λ′r for r ∈ {1, . . . , R}, with Λ′1 = Λ1 . Balanced Euclidean division therefore gives a compatible stage symbol X xℓk = QΛℓ− (xk ) − QΛℓ+ +1 (xk ) ∈ Λℓ− ∩ Vℓ+ xrk = . r r +1 ℓ∈Gr

is uniform on Ḡℓ from the server’s view. The release controller is assumed able to recover Bℓ for the realized active set without renewed client participation, for example from per-client keys or trustee-held shares. This capability is assumed rather than constructed. With true onetime pad shares the resulting ciphertext hiding is informationtheoretic; pseudorandom-generator (PRG) or key-derivationfunction (KDF) shares provide the corresponding computational property and require domain separation across layers and rounds. Let mℓkj ∈ Ḡℓ denote the standard pairwise SecAgg mask shared by clients k and j, with mℓkj = −mℓjk . Client k submits h i X eℓk + bℓk + mℓkj mod Λ(ℓ) . (14) ykℓ = x j̸=k

After the ordinary SecAgg masks cancel over the active set, the server holds only the sealed aggregate h X i eℓk + Bℓ mod Λ(ℓ) . uℓ = x (15) k∈Aℓ

When layer ℓ is authorized, the controller supplies Bℓ and the server obtains h X i   eℓk mod Λ(ℓ) . (16) tℓ = uℓ − Bℓ mod Λ(ℓ) = x k∈Aℓ

Thus SecAgg masks protect individual uploads and cancel at aggregation, whereas the aggregate release pad remains until authorization. For the homogeneous active set Aℓ = {1, . . . , K} at every released layer, let ℓ0 ∈ {1, . . . , L} be the finest authorized layer, so the authorized suffix is {ℓ0 , . . . , L}. Using (9), the server reconstructs ! L K X 1 X b tℓ − dk . (17) s∆,ℓ0 = Kµ0 + a ℓ=ℓ0

k=1

Authorizing one finer layer requires one additional controller token but no new client upload. An optional common orthogonal rotation may be applied to the clipped updates before block quantization to spread update energy across coordinates and reduce the per-coordinate dynamic range; it is inverted inside the parentheses of (17) and changes neither the subsequent algebra nor the privacy accounting. Remark 1 (Authorization schedules). The per-layer construction gives the finest authorization granularity. For the canonical integer chain (3), contiguous layers can instead be grouped into R ∈ {1, . . . , L} stages. Index the stages in fineto-coarse arithmetic order as an ordered partition G1 , . . . , GR of {1, . . . , L}, with each Gr contiguous; policy releases them in the reverse order GR , . . . , G1 . For r ∈ {1, . . . , R}, let + ′ br = |Gr |, ℓ− r = min Gr , and ℓr = max Gr . Define Λr ≜ Λℓ− r ′ for r ∈ {1, . . . , R} and ΛR+1 ≜ ΛL+1 . These lattices form the

r

r

A stage uses one pad and one independent noise draw zrk ∈ Λℓ− , with actual per-coordinate variance s̄2r , and a r (r) modulus Λ = ρmr Λℓ+ . The corresponding quotient has r +1 ρnb (br +mr ) elements. The per-layer statements apply to a stage through this coarsened integer chain. Expressed in the original radix, a concentration margin of 21 logρbr K+O(1) coarsenedchain steps corresponds to br times as many original-radix exponents, hence to 21 logρ K + O(1) original-radix margin steps. The extremes are R = L (one layer per stage) and R = 1 (one flat stage). Remark 2 (Relation to a flat secure sum). With one layer, or with one stage containing all L layers, PSA reduces to one quantized modular sum plus an optional release gate. If immediate disclosure is allowed, setting the release pads to zero recovers ordinary SecAgg arithmetic. E. Secrecy of an Unreleased Layer Proposition 1 (Ciphertext hiding for an unreleased layer). Fix a layer ℓ and condition on its active set and all public randomness. Let Wℓ denote the true noisy modular sum and let V denote any other server-side information that may be correlated with Wℓ . Assume, as in the pad-uniformity condition of Section IV-D, that Bℓ is uniform and independent of (Wℓ , V ) from the server’s view. Define the sealed random variable Uℓ = [Wℓ + Bℓ ] mod Λ(ℓ) . Then I(Wℓ ; Uℓ | V ) = 0, where I(·; · | ·) denotes conditional mutual information. Thus the sealed ciphertext adds no information about the withheld layer beyond the server’s pre-existing side information. After Bℓ is released, the server learns exactly Wℓ . With PRGgenerated pads, the corresponding statement is computational rather than information-theoretic. Proof. For every fixed pair (w, v), addition of an independent uniform pad maps w to a uniform element of Ḡℓ . Hence Uℓ is conditionally uniform and independent of Wℓ given V . Standard SecAgg separately protects the individual uploads. V. E XACTNESS , C ARRIES , AND OVERLOAD After authorization, a layer still provides only a centered modular residue. To characterize when that residue equals the true noisy sum, assume in this section that client Pevery K ℓ contributes to every layer and define Sℓ = x k=1 k and PK Zℓ = k=1 zℓk . Lemma 1 (Carry structure). For each released layer there is a unique cℓ = QΛ(ℓ) (Sℓ + Zℓ ) ∈ Λ(ℓ)

(18)

such that Sℓ + Zℓ = tℓ + cℓ . The carry is zero if and only if Sℓ + Zℓ lies in the centered Voronoi region of Λ(ℓ) . If it is nonzero, then ∥cℓ ∥ ≥ 2rpack (Λ(ℓ) ).

5

Proof. This is the definition of centered reduction modulo Λ(ℓ) ; a nonzero point of that lattice has norm at least its minimum distance, 2rpack (Λ(ℓ) ). Carries also localize by scale. If B is the set of layers with nonzero carries, their contribution to the reconstruction error at P resolution ℓ0 is −a−1 ℓ∈B, ℓ≥ℓ0 cℓ ; a carry on an unreleased finer layer ℓ < ℓ0 cannot alter that coarser authorized output. This localization does not make a carry on a coarse layer small. A nonzero carry is therefore not a small perturbation; overflow margins are designed to make it absent with high probability. Because the DP noise is unbounded, zero carry is necessarily probabilistic when DP is enabled. We use δw ∈ (0, 1) for concentration failure of the data term and δz ∈ (0, 1) for the noise tail. We therefore give a worst-case rule that makes no distributional assumption on layer symbols and a smaller-margin rule under an explicit zero-mean and independence assumption. Assumption 2 (Zero-mean layer symbols). For every layer on which the concentration rule is used, the vectors {xℓk }K k=1 are independent across clients and satisfy E[xℓk ] = 0. Subtractive dithering makes the quantization error unbiased but does not imply Assumption 2. For the integer chain, the assumption holds under the i.i.d. uniform balanced-digit model used in the converse; its suitability for federated updates is an empirical workload question. For both margin rules, the left-hand side is ρmℓ pℓ+1 = rpack (Λ(ℓ) ): a point of smaller norm lies in the zero cell, so its carry vanishes by Lemma 1. Each rule bounds ∥Sℓ + Zℓ ∥ and makes the margin exceed it. Theorem 1 (Margin rules). Fix δw , δz ∈ (0, 1). Let rℓ+1 = rcov (Λℓ+1 ), pℓ+1 = rpack (Λℓ+1 ), and choose any uℓ such that P[∥Zℓ ∥ > uℓ ] ≤ δz /L. For the product discrete Gaussian on the integer chain, one valid choice is r 2nb L , (19) uℓ = sℓ 2Knb log δz valid whenever seℓ ≜ sℓ /(hρℓ−1 ) ≥ 1/2. Under this condition each coordinate of zℓk is sub-Gaussian √ with proxy sℓ [20], so each coordinate of Zℓ has proxy sℓ K, and (19) follows by a union bound over coordinates. Then: (a) Worst-case data. If ρmℓ pℓ+1 > Krℓ+1 + uℓ ,

(20)

then P[cℓ ̸= 0] ≤ δz /L. (b) Concentrated data. Under Assumption 2, define the total P layer second moment Vℓ = k E∥xℓk ∥2 . If r 4L 2 4L mℓ ρ pℓ+1 > 2Vℓ log + rℓ+1 log + uℓ , (21) δw 3 δw then P[cℓ ̸= 0] ≤ (δw + δz )/L. If part (b) is used on all layers, a union bound gives total carry probability at most δw + δz ; if part (a) is used √ on all 1/2 layers, the√corresponding bound is δz . If Vℓ /(pℓ+1 K) and uℓ /(pℓ+1 K) are bounded uniformly in K and ℓ, part (b) yields mℓ = 12 logρ K + O(1); part (a) yields mℓ = logρ K +

O(1) under the analogous K-scaling, its data term growing √ as K rather than K. For i.i.d. client layers, Vℓ = K ς¯ℓ2 with ς¯ℓ2 = E∥xℓk ∥2 ; under the uniform balanced-digit model, (5) gives this second moment explicitly. Proof. Appendix A. VI. C OMMUNICATION ACCOUNTING Preserving the option of later refinement requires every separately sealed stage to be represented in the initial upload. We first count the resulting arithmetic payload and then give a converse for the modular interface used by PSA. The count below is not total cryptographic traffic: it excludes SecAgg key exchange, authentication, dropout-recovery communication, and any controller/trustee key-management traffic. Proposition 2 (Client upload rate). Fix an authorization schedule of R stages {Gr } as in Remark 1. A protocol run that preserves the option of later refinement uploads one message per stage, each an element of that stage’s extended quotient, so per model dimension the arithmetic payload is RPSA =

R X

R   X
|Gr | + mr log2 ρ = L + mr log2 ρ,

r=1

r=1

(22) since the stages partition the L layers. The payload therefore scales with the number of separately sealed moduli, not with the number of layers: the cost is driven by refinement granularity. Let Rflat denote the corresponding onestage flat payload. Before its single overflow margin, that representation contributes L log2 ρ. Margins are exponents of ρ, so a margin m costs m log2 ρ bits. With worst-case provisioning Theorem 1(a) gives mr = logρ K + O(1) for every modulus, that is log2 K + O(1) bits each, and hence the gap (R − 1) log2 K + O(R). Under the zero-mean √ concentration assumptions, with aggregate-noise scales O( K) in normalized units, Theorem 1(b) gives mr = 21 logρ K + O(1), that is 12 log2 K + O(1) bits each, and R−1 log2 K + O(R). (23) 2 The finest schedule R = L recovers L−1 2 log2 K + O(L), and R = 1 gives no gap. These are asymptotics in K for fixed ρ and L; if L grows, the log L terms from the failure allocation must be retained. RPSA − Rflat =

Proof. A stage Gr takes ρnb |Gr | values, so its extended quotient element has nb (|Gr |+mr ) log2 ρ bits, against nb L log2 ρ for the unextended fine index. The margin orders follow from Theorem 1, applied per stage and, for the flat index, to its single modular sum; dividing by nb gives the per-dimension rates. The penalty is the price of protecting every layer against its own wraparound within this arithmetic interface, not a universal lower bound: interactive coding or a joint cross-layer encoding exposes a different sufficient statistic. A converse must therefore fix an interface before claiming necessity. The next result fixes the one PSA uses, in which each authorized stage is exposed through a single modular sum, and shows the order is unavoidable within it.

6

A. Converse for Layerwise Modular Interfaces Definition 1 (Layerwise modular interface). Fix one coordinate j of the balanced integer chain and normalize its layer digit as aℓk ≜ xℓk,j /(hρℓ−1 ), so aℓk ∈ {−(ρ − 1)/2, . . . , (ρ − PK ℓ 1+mℓ 1)/2}. Let Sℓ = . A decoder k=1 ak and Mℓ = ρ has a layerwise modular interface if its only data-dependent observation from layer ℓ, after that layer is authorized, is tℓ = Sℓ mod Mℓ , together with arbitrary data-independent randomness. This includes PSA’s masks and release pads, which are data-independent from the decoder’s viewpoint. Under √ a uniform digit prior, Sℓ has standard deviation of order K and no single value has probability larger than order K −1/2 . Consequently a residue modulo Mℓ can identify the exact sum with constant√probability only if the modulus itself grows on the order of K. Theorem 2 (Anti-concentration converse). Under the i.i.d. uniform balanced-digit prior, let the normalized digits aℓk of Definition 1 be independent across clients and layers, and define Sℓ =

K X

aℓk ,

k=1

X=

L X

ρℓ−1 Sℓ .

(24)

ℓ=1

Suppose the data-dependent observation from layer ℓ is only tℓ = Sℓ mod Mℓ , where Mℓ = ρ1+mℓ . There are constants C and K0 , depending at most on the fixed radix, such that b every decoder of X from the modular tuple, with estimate X, satisfies, for K ≥ K0 and every ℓ, ( ) CM ρ2 − 1 ℓ b = X] ≤ min 1, √ P[X , σρ2 = . (25) 12 σρ K Therefore, for any δ ∈ (0, 1), exact recovery with probability at least 1 − δ requires mℓ ≥

1 (1 − δ)σρ logρ K + logρ 2 Cρ

(26)

for every layer. Proof. Appendix B. Corollary 1 (Rate within the layerwise modular class). Fix L and ρ, and consider a one-symbol-per-client interface exposing one modular sum per stage. A stage of width br has per-coordinate modulus ρbr +mr , so Theorem 2 applied to the coarsened chain of Remark 1 gives br +mr ≥ 12 logρ K+O(1), hence mr ≥ 12 logρ K + O(1) since br ≤ L is fixed. Under the uniform-digit prior and constant target success probability, the minimal per-dimension rate is R⋆mod (R) = L log2 ρ + R 2 log2 K + O(R). Relative to the same interface with a single stage, R⋆mod (R) − R⋆mod (1) =

R−1 log2 K + O(R), 2

(27)

which matches (23) in order. Proposition 1 and Corollary 1 together isolate the role of the overhead. Separate pads enforce coarse-only authorization without recontacting clients; under the uniform-digit prior and within the layerwise modular class of Definition 1, the

associated arithmetic-payload order is unavoidable. No claim is made for protocols that jointly encode layers, interact across them, or expose a richer sufficient statistic. VII. D IFFERENTIAL P RIVACY OF AUTHORIZED R ELEASES The release gate controls when a stage becomes visible; DP controls what an authorized release reveals. We use clientlevel replacement adjacency. For q > 1, a mechanism is (q, ε)-Rényi differential private (RDP) if the order-q Rényi divergence between its outputs on every pair of neighboring datasets is at most ε [21]. RDP composes additively at a fixed order and is preserved by post-processing. A. Layer Sensitivity Condition on the public dithers. Let Φℓ map one admissible client update to its concatenated d-dimensional layer-ℓ symbol across the J = ⌈d/nb ⌉ blocks. Its full-vector replacement sensitivity is Dℓ = supu,u′ ∥Φℓ (u) − Φℓ (u′ )∥2 , where the supremum is over two admissible client updates; let Dℓ denote the corresponding single-block sensitivity. Since xℓ ∈ Cℓ , √ Dℓ ≤ diam(Cℓ ) ≤ 2rcov (Λℓ+1 ), Dℓ ≤ J Dℓ . (28) √ The J factor is a worst-case product bound. Under global ℓ2 clipping, the admissible set can make the actual fullvector sensitivity smaller, in which case that smaller sensitivity should be used. Remark 3P(Layer sensitivities do not telescope). It is P tempting to bound ℓ Dℓ by the sensitivity of the total, since ℓ xℓ = x. This fails, and for a concrete reason: an arbitrarily small change of x can alter every layer symbol at once, exactly as incrementing 0999 to 1000 changes every decimal digit. Layer sensitivities must therefore be summed rather than telescoped, which is why the composition cost of separately authorized layers does not vanish as the layers become fine. For the integer chain (3), whenever the admissible block domain can attain the full balanced digit alphabet, Dℓ = √ h(ρ − 1)ρℓ−1 nb . If B < rpack (Λℓ ), then both QΛℓ (x) and QΛℓ+1 (x) are zero for every admissible x, so the effective sensitivity of that layer is zero. We therefore omit inactive layers from the privacy sum. B. Composition Across Authorized Layers For an authorized set, only the mechanisms whose tokens are released enter the privacy composition. Theorem 3 (Progressive RDP accounting). Condition on all public randomness and the realized active sets. Suppose that, under client-level replacement adjacency, the authorized modular mechanism for layer ℓ is (q, εℓ (q))-RDP. Then every authorized set P is X (q, εP (q)) -RDP, εP (q) ≤ εℓ (q). (29) ℓ∈P

Before its token is released, a uniformly sealed layer contributes no additional leakage to the server transcript in the sense of Proposition 1. Modular reduction, unsealing by a data-independent token, and affine reconstruction are postprocessing. Under an authorization schedule the mechanisms

7

are the stages rather than the layers, and the statement applies verbatim to the coarsened chain of Remark 1, with P a set of stages. Proof. RDP composes additively, including for schedules selected from public information or prior DP outputs, and is preserved by post-processing. A release decision based directly on additional private information would need its own privacy analysis. The sealed transcript of every unreleased layer is conditionally independent of its noisy sum by Proposition 1. For a concrete integer-chain instantiation, all blocks are concatenated and each honest client adds product discrete Gaussian noise as in (10). Only honest clients contribute noise the accounting may rely on, a colluding or dropped client’s share being known to the server or absent; let Keff,ℓ lowerbound their number, set seℓ = sℓ /(hρℓ−1 ) ≥ 1/2. A sum of discrete Gaussians is not exactly a discrete Gaussian; the following term accounts for the residual. Define the convolution correction   Keff,ℓ −1 X j . (30) τℓ = 10 exp −2π 2 se2ℓ j+1 j=1 After rescaling the layer to Zd , the distributed-discreteGaussian analysis [4] supplies an explicit per-layer RDP bound. A conservative form of its ℓ2 branch, sufficient for the comparisons below, is εℓ (q) ≤

qDℓ2 + qτℓ d. 2Keff,ℓ s2ℓ

(31)

Replacing (31) with the full minimum-of-branches RDP bound from [4] gives a sharper numerical accountant; the enlarged coefficient on the exponentially small correction keeps (31) independent of concentrated-DP normalization conventions. For a chosen DP failure probability δ ∈ (0, 1), reported (ε, δ) values are obtained from εP (q) by the standard Rényi conversion, minimized over the order q > 1, and the noise scales are calibrated by bisection on that minimized ε at fixed δ. The same RDP-to-(ε, δ) conversion and calibration criterion are applied to the private mechanisms in the numerical evaluation, with each mechanism using its stated RDP bound. Thus the reported comparisons are at matched (ε, δ) rather than at matched Rényi order. No carry-margin event is required for privacy. The mechanism always releases a finite-group value, and any centered unwrapping rule is post-processing. Carries affect utility, not the validity of the RDP accounting. Remark 4 (General lattices). Equation (31) uses a productinteger discrete Gaussian. Extending its constants to a nonproduct lattice such as A2 , D4 , or E8 requires a corresponding convolution analysis and a noise scale above the lattice smoothing parameter [22]; self-similarity alone is insufficient. The geometric carry results, in contrast, apply to every chain satisfying Assumption 1. C. Leading Privacy Cost of Layering By Theorem 3, separately authorizable layers compose. To isolate the leading sensitivity term, ignore the exponentially

small τℓ corrections, suppose the same Keff applies to all active layers, and the nominal per-coordinate noise-scale P fix 2 budget V ≜ ℓ sℓ . This is an accounting comparison at fixed V ; because a discrete Gaussian’s actual variance is s̄2ℓ rather than exactly s2ℓ , it should not be read as an exact equaldistortion statement at finite parameters. Proposition 3 (Leading composition cost at full release). Let Dℓ be the actual full-vector replacement sensitivity of layer ℓ. Each layer contributes Dℓ2 /s2ℓ , so the budget should be spent where a client can move the output furthest. The allocation minimizing the leading term of (31) is V Dℓ , s2ℓ = P j Dj

(32)

and yields 2 ℓ Dℓ )

P

q( εlead lay (q) =

2Keff V

.

(33)

If a matched flat representation has replacement sensitivity Dflat and the same noise-scale budget, then P 2 εlead lay ℓ Dℓ = . (34) Dflat εlead flat For one full-range integer block, or a product of such blocks under coordinate-wise range constraints, √ Dℓ = h(ρ − 1)ρℓ−1 d, (35) √ L Dflat = h(ρ − 1) d, (36) P so ℓ Dℓ = Dflat and the leading ratio is exactly 1. More generally, if Dℓ ≤ c1 ρℓ−1 and Dflat ≥ c2 ρL−1 with positive constants independent of L, then  2 εlead c1 ρ lay ≤ , (37) c2 ρ − 1 εlead flat which is independent of L. P 2 2 P Proof. Minimizing /sℓ at fixedP ℓ s2ℓ = V is Cauchy– ℓ DℓP P Schwarz: ( ℓ Dℓ )2 ≤ ( ℓ Dℓ2 /s2ℓ ) ℓ s2ℓ , with equality if 2 and only For the full√ product do√ (32)–(34). P P if sℓ ∝ Dℓ , giving = h(ρL −1) d = Dflat . main, ℓ Dℓ = h(ρ−1) d ℓ ρℓ−1P L In general geometric growth gives ℓ Dℓ ≤ c1 ρ /(ρ − 1) while Dflat ≥ c2 ρL−1 ; dividing and squaring yields (37). Layering is therefore not automatically a privacy improvement: in the tightly matched balanced integer case the leading composition upper bound is neutral under this budget comparison. The constraint seℓ ≥ 1/2, the convolution corrections, and actual output variances can shift the finite-parameter optimum. The caveat concerns the admissible domain, not the adjacency relation, which is client-level replacement in both cases. The neutral case assumes a product box that fills the digit alphabet coordinatewise. Under global ℓ2 clipping, the admissible set is a ball and the layer sensitivities need not sum to the flat sensitivity. Proposition 3 therefore identifies a regime in which the leading composition bound is neutral; it does not claim neutrality for general clipped workloads.

8

VIII. D ISTORTION A NALYSIS so their inner product is bounded rather than evaluated. They are distribution-free once the actual Tℓ0 is used, and Fix a finest authorized layer ℓ0 ∈ {1, . . . , L}. Under a apply to non-identically distributed clients with Tk,ℓ0 = grouped authorization schedule, ℓ0 is restricted to the mini(ℓ ) E∥rk 0 ∥2 per summand. Always Tℓ0 ≤ rcov (Λℓ0 )2 . mum layer index of the finest authorized stage. For a quantized block x ∈ Λ1 ∩ VL+1 , define the refinement withheld below (c) Scaling under uniform residues. For the integer chain under the additional uniform-residue condition, which ℓ0 by leads to (39), the two sides of (43) are Θ(ρ2(ℓ0 −1) ) for r(ℓ0 ) ≜ x − QΛℓ0 (x) ∈ Λ1 ∩ Vℓ0 , (38) ℓ0 ≥ 2 (with fixed odd ρ). Without that condition, only the universal upper scaling O(ρ2(ℓ0 −1) ) follows from the (ℓ0 ) 2 and, under the actual data-and-dither law, let Tℓ0 ≜ E∥r ∥ . support bound; a matching lower scaling need not hold. Always T ≤ r (Λ )2 . For the integer chain, if this residue ℓ0

cov

ℓ0

is additionally uniform on the balanced set Λ1 ∩ Vℓ0 , then
Tℓ0 = nb σ 2 (Λℓ0 ) 1 − ρ−2(ℓ0 −1) , (39) with T1 = 0. For client k, define the one-block reconstruction error before DP noise as (ℓ )

Ek 0 = QΛℓ0 (xk ) − dk − vk (ℓ )

= ek − rk 0 .

Thus Λ1 fixes the full-resolution quantization floor, while coarser releases add a truncation term whose geometric scaling requires the stated uniform-residue condition. DP noise contributes separately through every authorized stage.

(40)

IX. N UMERICAL E VALUATION

(41)

The evaluation separates claims that hold for the code alone from claims that depend on the data. Exact finitealphabet computation settles the carry margins and the digitcompatibility condition; controlled sources settle the distortion bounds and the privacy accounting; federated experiments on MNIST and CIFAR-10 settle the digit model and the oneupload trade-off against matched baselines.

P (ℓ ) ℓ By (7), rk 0 = ℓ<ℓ0 xk , so the residue is exactly the withheld refinement. Theorem 4 (End-to-end MSE). Let e s∆,ℓ0 be the ideal estimator obtained from (17) by replacing every authorized modular residue by its true noisy lattice sum. By Lemma 1, this ideal estimator equals the actual estimator on the zerocarry event. Under the concentration rule of Theorem 1(b), that event has probability at least 1 − δw − δz when the rule is applied to all released layers; the moments below are moments of the ideal estimator, not unconditional moments of the modular estimator outside that event. Suppose client data-and-dither pairs are independent across clients and, for ℓ0 > 1, the skipped refinement of each client has zero mean, (ℓ ) so E[Ek 0 ] = 0. At full resolution the residue is zero and this condition follows from subtractive dithering alone. Together with the independent zero-mean DP noises specified in the construction, these assumptions make the cross terms vanish. For one block, " K 1 X (ℓ ) 2 E∥Ek 0 ∥2 E∥e s∆,ℓ0 − s∆ ∥ = 2 a k=1 # X 2 +K nb s̄r . (42) r: Gr authorized

The per-client error term behaves as follows under truncation: (1) (a) Full resolution. For ℓ0 = 1, E∥Ek ∥2 = nb σ 2 (Λ1 ) exactly, without a distributional assumption on the update. (b) Any truncation. For identically distributed client blocks, with Tℓ0 defined above, 2 p p (ℓ ) Tℓ0 − nb σ 2 (Λ1 ) ≤ E∥Ek 0 ∥2 p 2 p ≤ Tℓ0 + nb σ 2 (Λ1 ) . (43) (ℓ )

Proof. Appendix C.

The bounds are two-sided because ek and rk 0 are functions of the same data and dither pair, hence correlated in general; only their individual second moments are known,

A. Carries, Margins, and Digit Compatibility The scalar chain uses ρ = 3, L = 4 and client digits i.i.d. uniform on {−1, 0, 1}, matching the prior of Theorem 2; digit-sum distributions are computed by exact polynomial convolution, so the carry probabilities carry no Monte Carlo error. Fig. 1(a) shows the smallest feasible margin. It grows from 2 at K = 8 to 5 at K = 4096 in integer steps, and regressing it on log3 K gives slope 0.548 against the predicted 1/2. Theorem 1(b) asserts 12 logρ K + O(1), so it is the slope and not the value that the measurement tests: the margins lie about 1.1 steps above 12 logρ K, and the reference line is drawn with slope 1/2 through the data for that reason. Realized carry probabilities never exceed 9.75×10−6 . Because the rate premium of Proposition 2 is (L − 1)mℓ log2 ρ, it is this staircase up to a constant and is not plotted separately; numerically it is 19.02 bit per dimension at K = 1000 against the asymptotic L−1 2 log2 K = 15.00, the offset being integrality rather than a failure of the prediction. Fig. 1(b) tests Assumption 1 directly. Over 2 × 105 random representable points the integer chain satisfies telescoping, alphabet membership and the quantizer-difference form of (7) without a violation. On a self-similar hexagonal A2 chain the telescoping identity still holds, being algebraic, but membership fails from the second layer onward, at 14.4%, 14.8% and 13.1% of 2 × 104 trials. Self-similarity therefore does not deliver digit compatibility. B. When Layering Is Free, and When It Is Not Proposition 3 predicts neutrality only when the admissible domain fills the digit alphabet in every coordinate. Fig. 2(a) measures the leading ratio as that condition is relaxed, and the behaviour is not monotone. The ratio is 0.975 at full fill,

9

(a) margin scaling

self-similar A2 chain (2 × 104 trials)

20

outside ℓ [%]

5

minimal margin mℓ

(b) digit compatibility

measured mℓ slope 1/2

4

3

integer chain (0 of 2 × 105 )

14.8

14.4

15

13.1

10 5

2 2

3

4

5

6

logρ K

7

0.0 0.0

0

8

0.0

1

2

0.0

layer ℓ

0.0

3

4

Fig. 1. Exact finite-alphabet validation, ρ = 3, L = 4. (a) Smallest feasible per-layer margin at carry probability at most 10−3 against logρ K; the staircase reflects integrality of mℓ , and a linear fit to it has slope 0.548 against the predicted 1/2. (b) Rate at which QΛℓ − QΛℓ+1 leaves the centered alphabet Cℓ , over 2 × 105 random representable points for the integer chain and 2 × 104 for the A2 chain: identically zero for the odd-radix integer chain (annotated zeros), nonzero from layer 2 for a merely self-similar A2 chain. (a) product domain

3.5

3.26

3.18

3.0

4 active 3 active

2 active 1 active 2.62

2.5 2.0 1.5 1.0 0.5

neutral 0.98

1.03

0.97 0.61

1

0.3

0.1

0.03

fill Γ of the digit alphabet (decreasing → )

(b) ℓ2 -clipped domain

30

leading composition ratio

leading composition ratio

4.0

25.1

25

26.7

27.3

5

6

20.8

20 15

10.9

10 5 0

neutral

2

3

4

chain depth L

lead Fig. 2. Leading composition ratio εlead lay /εflat at equal noise budget. (a) Product domain as the fill Γ of the digit alphabet is reduced; markers give the number of layers still active, and arrows mark the transitions at which a layer empties. (b) Globally ℓ2 -clipped domain against chain depth, where no layer ever becomes inactive.

confirming the predicted neutrality, then rises to 3.26 as the fill drops to 0.40 with all four layers active. At that point the coarsest layer becomes inactive, its sensitivity vanishes, it leaves the privacy sum, and the ratio falls back to 1.03. The pattern repeats twice more, at 3.18 → 0.97 and 2.62 → 0.61, until a single layer remains and the ratio is trivially 1 because one stage is the flat mechanism. The penalty of layering is therefore governed not by how restricted the domain is but by how poorly the active layers are filled. A chain whose depth is matched to the data sits near the bottom of a tooth rather than the top, which is a design lever the analysis does not expose and which the occupancy measurements below make actionable. The globally ℓ2 -clipped domain assumed by [4], [5] is a different regime, Fig. 2(b). A ball never fills the coarse alphabets, no layer becomes inactive, and the ratio grows with depth to 25.1 at L = 4, saturating near 27. This factor, not the rate premium, is the dominant practical cost of layering under the clipping the standard baselines use. The caveat concerns the admissible domain, not the adjacency relation, which is client-level replacement throughout. C. Distortion and the Two Error Sources Fig. 3(a) places the measured per-client error against Theorem 4(b). Every measurement lies inside the bounds and the error falls by close to ρ2 = 9 per refinement level, from

5.28 × 101 (uniform) and 2.50 × 101 (Gaussian) at ℓ0 = 4 to 8.3 × 10−2 at ℓ0 = 1. That the bounds hold for a Gaussian source, which violates the uniform-residue condition, is the point: they are distribution-free. The closed form for Tℓ0 needs that condition and deviates from the measured second moment by 13.0% (uniform) and 58.6% (Gaussian) at the coarsest level, so accuracy statements should use the measured T or the bounds.

Fig. 3(b) recalibrates every depth to a common ε = 4 and separates the two contributions. The quantization component falls monotonically by nearly three orders of magnitude, from 0.214 to 3 × 10−4 , exactly as (a) predicts. The total error moves the other way, rising from 9.52 at ℓ0 = 4 to 19.48 at ℓ0 = 2 and then saturating; the final step to 19.58 lies within the ±0.61 confidence interval, so the last refinement neither helps nor measurably hurts. Each additional authorized stage contributes an independent noise draw whose variance exceeds the truncation error it removes, until the truncation term is small enough that neither dominates. Refinement improves fidelity only once the privacy budget is loosened. This is a property of the independent-stage-noise construction, not a lower bound on progressive release. No carry occurred at the provisioned margins in any run.

10

(a) truncation error and Thm. 4(b) bounds

101

10

0

bounds coincide, Thm. 4(a) exact

10−1 4

3

2

authorized resolution ℓ0 (coarse → fine)

1

(b) error sources at common ε = 4

102

MSE of the mean estimate

per-client squared error

10

measured, uniform measured, gaussian Thm. 4(b) bounds, uniform Thm. 4(b) bounds, gaussian

2

101 100 10−1 10−2 10−3 10−4

quantization component total MSE of the mean

4

3

2

authorized resolution ℓ0 (coarse → fine)

1

Fig. 3. (a) Per-client truncation error against the two-sided bounds of Theorem 4(b), drawn as shaded bands for ℓ0 ≥ 2 where they have width; at ℓ0 = 1 the bounds coincide and Theorem 4(a) is exact. (b) Mean-square error of the mean estimate with every depth recalibrated to ε = 4, separated into its total and its quantization component. Bars are 95% confidence intervals; where not visible they are smaller than the markers.

D. Federated Evaluation Setup. MNIST and CIFAR-10 are used with their standard splits, processed by the unsupervised convolutional feature pipeline of Coates et al. [23]: whitened random patches, a k-means dictionary, triangle activation, spatial pooling and PCA. MNIST uses 256 centroids, 2×2 pooling and PCA-128; CIFAR-10 uses 512 centroids, 3 × 3 pooling and PCA-384. The model is multinomial logistic regression, so d = 1290 and d = 3850, and the chain is ρ = 3, L = 4. The scale is deliberate: the claims under test concern the aggregation mechanism rather than the learner, and a convex model at full participation isolates the privacy accounting from optimization effects while keeping every run reproducible on CPU. Training is FedSGD with server momentum 0.9 [24], K = 1000 clients at full participation, non-IID Dirichlet(0.5) partitioning, 150 rounds and per-client clipping at C = 1. Reported ε values are run totals: the per-round mechanism is composed T = 150 times in the Rényi accountant before conversion, with no subsampling amplification since participation is full. Results are means over three seeds. Baselines. The non-private arm is plain FedSGD [24]; the compression-only arm is single-layer subtractive-dithered lattice quantization after UVeQFed [8] with no DP noise, isolating the cost of the representation. The private arms are the distributed discrete Gaussian [4] and Skellam [5] mechanisms under SecAgg [2], Skellam credited with its leading Rényi term only, which favors that baseline. All private arms share the lattice granularity h, so resolution is matched and every accuracy difference is attributable to the privacy accounting rather than to the lattice code. Matched functionality. The only baseline serving R independently authorized resolutions is repeated flat SecAgg, run once per resolution at the granularity that resolution requires. An execution serving ℓ0 transmits (L − ℓ0 + 1 + m) log2 ρ bit per dimension rather than (L + m) log2 ρ, and the R mechanisms compose, so the baseline delivers the same R numbers only by re-executing and recontacting the clients. We sweep R ∈ {1, 2, 4} with stages {4, 3, 2, 1}, {4, 3}, {2, 1}, and one layer per stage, at equal (ε, δ) with δ = 10−6 . The digit model. Assumption 2 is the one modeling assumption in the achievability argument, and it concerns the

TABLE I M ATCHED FUNCTIONALITY AT δ = 10−6 : ONE PSA UPLOAD SERVING R AUTHORIZED RESOLUTIONS VERSUS R REPEATED FLAT EXECUTIONS . ACCURACY IS THE MEAN OVER THREE SEEDS ; PAYLOAD IS BIT PER DIMENSION AT K = 1000.

ε 6

R 1 2 4 30 1 2 4 payload R = 1 payload R = 2 payload R = 4

MNIST PSA flat ×R 0.771 0.771 0.650 0.718 0.492 0.626 0.910 0.910 0.854 0.883 0.709 0.839 12.68 12.68 19.02 22.19 31.70 41.21

CIFAR-10 PSA flat ×R 0.274 0.274 0.195 0.227 0.154 0.206 0.429 0.429 0.354 0.389 0.248 0.365 12.68 12.68 19.02 22.19 31.70 41.21

data. On real clipped gradients the largest normalized digit bias |E[aℓ ]|/sd(aℓ ) is 0.031 on MNIST and 0.023 on CIFAR10 across all four layers, so its zero-mean part is accurate for gradient-type updates around a shared reference. It does not test independence, since clients in a round share the current model; the worst-case rule of Theorem 1(a) needs √ neither part, at a margin growing as K rather than K. Layer occupancy, the fraction of coordinates with a nonzero digit, is (0.165, 0.015, 1.6 × 10−3 , 1.9 × 10−4 ) on MNIST and (0.124, 0.003, 3.9 × 10−4 , 6.8 × 10−5 ) on CIFAR-10. On CIFAR-10 the finest provisioned layer is essentially unoccupied, so three of the four layers carry the information; on MNIST all four are occupied, the finest only barely. By Fig. 2(a) an unoccupied layer is not merely wasted rate but also moves the chain up a tooth of the privacy cost: depth should be provisioned from measured occupancy, not from the nominal dynamic range. Results. Table I reports the comparison. At R = 1 PSA and the flat mechanism agree to three decimals at every privacy level on both datasets, and the payloads coincide at 12.68 bit per dimension: with one authorization stage PSA provisions one modulus, exactly as the flat mechanism does. This is the falsification test of Section IX-D and it passes; any advantage here would have indicated an accounting error rather than a property of the scheme. Fig. 4 shows that the R = 1 curves

11

PSA and DDG×R coincide at R = 1

0.8 0.7 0.6 0.5 0.4

20

40

60

FedSGD, no DP PSA, R = 1 PSA, R = 4 Skellam, R = 1

80

round

100

120

(a) exact leading ratio

30

0

ℓ2 -clipped domain 10.9

agree at every logged round, not merely at convergence, so the neutrality is structural. The Skellam arm, which serves a single release, tracks the R = 1 pair at matched budgets, reaching 0.779, 0.847 and 0.913 on MNIST and 0.229, 0.352 and 0.430 on CIFAR-10 at ε = 6, 12, 30; at ε = 6 its unprovisioned modulus wraps (4.7 × 103 carry events on MNIST, 5.3 × 104 on CIFAR-10), which costs it four accuracy points on CIFAR10, whereas PSA’s provisioned margins admit no carry in any run. For R > 1 the two directions separate. PSA’s finest consumer reconstructs the sum of all authorized stages and accumulates the noise of every one, whereas a consumer of the repeated flat pipeline reads a single execution and sees one noise draw; stage sensitivities do not shrink proportionally, because a small change of the input can alter every layer symbol (Remark 3). At ε = 30 PSA reaches 0.854 against 0.883 at R = 2 and 0.709 against 0.839 at R = 4. Communication runs the other way: PSA uploads once with one modulus per stage, giving 12.68, 19.02 and 31.70 bit per dimension at R = 1, 2, 4, against 12.68, 22.19 and 41.21 for the repeated pipeline, so PSA is cheaper for every R > 1, at 0.86× the payload for R = 2 and 0.77× for R = 4. Privacy composition runs the same way: serving four resolutions costs ε = 2.00 for one PSA execution against ε = 4.29 for four flat executions, a factor 2.14, with the flat totals 2.00, 2.92, 3.65 and 4.29 across R = 1, 2, 3, 4 while the PSA total stays at 2.00. The asymmetry is structural: PSA is charged for the layers it reveals, and a coarser resolution is a prefix of layers already revealed, so serving it costs nothing further, whereas each flat resolution is a separate execution composed in its own right. The representation itself is nearly free. The compressiononly arm attains 0.9804 ± 0.0003 against 0.9806 ± 0.0003 for the uncompressed non-private reference on MNIST, and 0.6073 ± 0.0005 against 0.6086 ± 0.0010 on CIFAR-10, so every accuracy difference among the private arms is attributable

rotated coord. clip, γ = 2

2.6

3.4

2

3

4.0

3.9

3.8

neutral

4

chain depth L

5

6

(b) MNIST, R = 4 authorized resolutions

lattice quantized, no DP DDG×R, R = 1 DDG×R, R = 4

Fig. 4. MNIST federated training at matched ε = 30, δ = 10−6 , three seeds (shaded: one standard deviation, below line width except at R = 4). Solid curves are PSA, dashed the distributed discrete Gaussian re-executed once per resolution (DDG×R), dash-dotted the Skellam mechanism, which serves a single release; the extremes R = 1 and R = 4 are shown, with R = 2 in Table I. Two coincidences are results rather than plotting artifacts: the lattice-quantized arm tracks the non-private reference, and at R = 1 the dashed curve lies on the solid one at every logged round.

27.3

20.8

20 10

26.7

25.1

140

test accuracy

test accuracy

0.9

leading composition ratio

1.0

0.8 0.6 0.4 0.2 6

12

30

privacy budget ε (matched, δ = 10−6 ) PSA, ℓ2 ball DDG×R, ℓ2 ball

PSA, rotated DDG×R, rotated

Fig. 5. The operating regime as a design choice, γ = 2. (a) Exact leading composition ratio of the ℓ2 -clipped domain against the rotated coordinatewiseclipped domain, with the surviving ℓ2 bound retained in the sensitivity accounting. (b) Federated accuracy at R = 4 authorized resolutions and matched (ε, δ), three seeds (bars: one standard deviation), with the same rotation granted to the repeated flat baseline; the unrotated PSA arm uses this experiment’s conservative stage bounds and is a within-experiment reference (see text).

to the privacy accounting rather than to the lattice code. The absolute accuracies identify the operating region in which progressive release is inexpensive. The configuration is deliberately conservative: full participation over 150 rounds admits no amplification by subsampling, so every arm, including the flat baseline at 0.771 for ε = 6, sits well below the non-private reference of 0.981; amplification or fewer rounds would raise all arms together. Within this setting R = 1 is free by construction and R = 2 costs between 3 and 7 accuracy points on MNIST, narrowing as the budget loosens. The cost of the finest release grows with the number of independent authorizations, so serving four is best matched to looser budgets. Taken together with the payload and composition figures, the case for PSA rests on the enforcement guarantee it provides, not on a drop-in accuracy or bandwidth improvement. E. The Rotated Domain: Closing the Layering Penalty The penalty of Fig. 2(b) is a property of the operating regime, and the regime is a protocol choice. Instantiating the public common rotation of Section IV in randomizedHadamard form, the standard flattening transform also used √ by [4], and then clipping each rotated coordinate at γC/ d makes the admissible set a product box that nearly fills the digit alphabet. Retaining the surviving ℓ2 bound in the sensitivity accounting, the leading composition ratio at L = 4 falls from 25.1 to 3.8 at γ = 2 (Fig. 5(a)), while the measured coordinate-clipping rate stays below 10−4 . Fig. 5(b) reports

12

matched-(ε, δ) training under this instantiation, with the same transform granted to the baseline. At ε = 30 and R = 4, rotated PSA attains 0.859 on MNIST against 0.714 for the repeated flat pipeline, and 0.380 on CIFAR-10 against 0.245; over the full (ε, dataset) sweep this margin exceeds 0.08 in every cell and every seed. Against the rotated variant of the baseline (0.841 and 0.370) the paired per-seed differences are positive on MNIST but small and of mixed sign on CIFAR10, so we claim statistical parity rather than superiority: in this regime one PSA upload serves four resolutions at no accuracy cost relative to matched functionality. The unrotated PSA arm (0.472 at ε = 30 on MNIST) is a within-experiment reference only: this experiment’s accountant bounds each ballregime stage conservatively, with an effective layered-to-flat noise-variance ratio near 180 against the per-layer value 25.1 of Fig. 2(b), so its level understates ball-regime PSA and is not comparable to the 0.709 of Table I, whose accountant uses the tighter per-layer sensitivities. The R = 1 consistency check of Section IX-D holds bitwise in the rotated regime as well, no carry occurred in any of the 156 runs, and the payload and composition advantages of Table I are unchanged. These runs use an independent re-implementation of the feature pipeline, with non-private references 0.949 (MNIST) and 0.607 (CIFAR-10), so all comparisons are within the experiment. X. D ISCUSSION AND L IMITATIONS PSA separates three guarantees. SecAgg hides individual client uploads; DP limits what an authorized aggregate reveals; and the release gate controls when a stage aggregate becomes available. If the gate is compromised, delayed authorization is lost and the construction reduces to ordinary DP-secure aggregation of the stage sums. If DP is omitted, staged disclosure remains but each authorized aggregate receives no DP guarantee. Pairwise SecAgg masks cannot replace the release gate because they cancel in the aggregate. The arithmetic-payload cost is tied to authorization granularity. A one-upload protocol must carry every stage that may later be authorized, and PSA provisions one overflow margin per such modular sum. Under the i.i.d. uniform-digit prior, Corollary 1 shows that the 12 logρ K concentration-order margin is unavoidable within the layerwise modular interface. This is not a lower bound on jointly encoded, interactive, or richer interfaces. A deployment can trade release granularity against arithmetic payload through the number of stages R. The guarantees also have distinct scope restrictions. Exact layered reconstruction requires Assumption 1; the canonical integer chain is a proved instance, whereas self-similarity alone is insufficient. The smaller concentration margin additionally requires Assumption 2; without it the worst-case rule of Theorem 1(a) applies. The product-integer discreteGaussian RDP bound does not automatically extend to nonproduct lattices: such an extension requires the corresponding convolution and smoothing analysis described in Remark 4. Finally, Proposition 3 is a leading accounting comparison whose neutral case depends on the admissible domain. Production realization of the abstract release gate requires mechanisms not constructed here, including binding pad re-

covery to the realized active set, audited key derivation and domain separation, rollback protection, and malicious-input validation. These are interface requirements rather than consequences of the lattice analysis. The multi-stage accuracy loss observed with independent stage noise under ℓ2 clipping is likewise construction-specific rather than a lower bound: the rotated-domain instantiation of Section IX-E removes it empirically at R = 4, and correlating noise across progressive releases remains a further candidate. XI. C ONCLUSION We introduced and formalized progressive-resolution secure aggregation as a one-upload functionality that enables successively finer resolutions of the same federated aggregate to be authorized after the clients have uploaded, without renewed client participation. Under independent zero-mean √ layer symbols and normalized aggregate-noise scale O( K), its sufficient overflow margin is 12 logρ K + O(1) radix steps. Under the separate i.i.d. uniform-digit prior, the converse establishes the same necessary order within the layerwise modular interface; it is not a universal lower bound on other protocol interfaces. Separate release pads hide unauthorized stage sums, while the arithmetic-payload cost grows with the number of separately sealed moduli. The numerical results support these qualified claims. Exact finite-alphabet calculations exhibit the predicted margin and payload scaling; the R = 1 federated consistency check makes PSA coincide with the matched flat mechanism; and the compression-only lattice representation changes accuracy by at most 0.13 percentage points in the reported runs. With several authorized resolutions under ℓ2 clipping, independent stage noise lowers finest-resolution accuracy while the one-upload construction reduces arithmetic payload relative to repeated flat executions. In the rotated coordinatewise-clipped regime of Section IX-E, PSA reaches statistical parity with the matched rotated baseline while retaining the one-upload progressiverelease functionality. The exact layered construction is proved for the balanced integer chain and does not follow from self-similarity alone, as illustrated by the observed A2 compatibility failures. Extending the discrete-Gaussian privacy constants to nonproduct lattices, handling malicious inputs, and realizing production key management for the release gate remain open. The multistage accuracy gap associated with independent stage noise under ℓ2 clipping also remains a limitation of the present construction and motivates the investigation of alternative noise couplings across progressive releases. A PPENDIX A P ROOF OF T HEOREM 1 Fix ℓ. A point of Λℓ with norm below rpack (Λ(ℓ) ) = ρ pℓ+1 lies in the Voronoi cell of the modulus lattice, so by Lemma 1 it suffices to bound ∥Sℓ + Zℓ ∥. For (a), every xℓk ∈ Cℓ has norm at most rℓ+1 , so ∥Sℓ ∥ ≤ Krℓ+1 ; on ∥Zℓ ∥ ≤ uℓ condition (20) forces zero carry, the complement having probability at most δz /L. For (b), Assumption 2 gives independent zero-mean summands in Rnb bounded by rℓ+1 mℓ

13

with total second moment Vℓ , and the vector Bernstein bound of Pinelis [25] gives   t2 P[∥Sℓ ∥ ≥ t] ≤ 2 exp − . (44) 2Vℓ + 23 rℓ+1 t The bound has no closed-form inverse, but a sufficient t covers its variance- and range-dominated regimes by its two terms: r 4L 2 4L t = 2Vℓ log + rℓ+1 log , (45) δw 3 δw where 4L rather than 2L absorbs the leading factor 2, making P[∥Sℓ ∥ ≥ t] ≤ δw /L; with the noise-tail condition and the triangle inequality this yields (21). A union bound gives δw + δz when part (b) is used on all layers; part (a) uses only the δz budget. The choice (19) serves both parts, following from the sub-Gaussian proxy by a two-sided scalar tail bound at level √ ■ δz /(nb L) per coordinate and ∥z∥2 ≤ nb ∥z∥∞ . A PPENDIX B P ROOF OF T HEOREM 2 Fix ℓ and give the decoder, as genie information, the exact sums {Sj : j ̸= ℓ}, which P can only increase its success probability. Since X = j ρj−1 Sj and every other term is now known, recovering X is equivalent to recovering Sℓ . Digits are independent across layers, so the genie leaves the law of Sℓ unchanged and its only data-dependent observation remains tℓ = Sℓ mod Mℓ ; bounding that single-layer problem bounds the original. Let pK (s) = P[Sℓ = s]. For any decoder based on the residue, the optimal success probability is X max pK (s) ≤ Mℓ sup pK (s). (46) r∈Z/Mℓ Z

s: s≡r (mod Mℓ )

s

The balanced digit law is bounded, has variance σρ2 , and is aperiodic, its support lying in no proper sublattice of Z, as required for the lattice local limit theorem at spacing one [26]. Hence there are constants C, K0 with sups pK (s) ≤ √ C/(σρ K) for K ≥ K0 . Capping at one proves (25), and a success probability of at least 1 − δ forces the bound itself to be at least 1 − δ; substituting Mℓ = ρ1+mℓ gives (26). ■ A PPENDIX C P ROOF OF T HEOREM 4 Write (17) over the authorized stages, as licensed by Remark 1. Every released stage is unwrapped to its true integer sum, so subtracting (6) from (17) gives X (ℓ ) X X a(e s∆,ℓ0 − s∆ ) = Ek 0 + zrk . (47) k

k r: Gr authorized

Cross terms vanish as noted with the theorem, giving (42); (1) part (a) is the case ℓ0 = 1, where rk = 0. For general ℓ0 , (ℓ )

E∥ek − rk 0 ∥2 = nb σ 2 (Λ1 ) + Tℓ0 (ℓ ) − 2E⟨ek , rk 0 ⟩.

(48)

(49) p Cauchy–Schwarz bounds the last term by 2 nb σ 2 (Λ1 )Tℓ0 , (ℓ ) proving (43), and the support bound follows from rk 0 ∈ Vℓ0 .

Under the uniform-residue law (39) follows coordinatewise from the variance of the balanced set of ρℓ0 −1 integers, and since σ 2 (Λℓ0 ) = ρ2(ℓ0 −1) σ 2 (Λ1 ) both bounds have geometric order for ℓ0 ≥ 2; without it the support bound gives O(ρ2(ℓ0 −1) ) but no matching lower bound. ■ R EFERENCES [1] P. Kairouz et al., “Advances and open problems in federated learning,” Found. Trends Mach. Learn., vol. 14, no. 1–2, pp. 1–210, 2021. [2] K. A. Bonawitz et al., “Practical secure aggregation for privacypreserving machine learning,” in Proc. ACM CCS, 2017. [3] J. H. Bell, K. A. Bonawitz, A. Gascón, T. Lepoint, and M. Raykova, “Secure single-server aggregation with (poly)logarithmic overhead,” in Proc. ACM CCS, 2020. [4] P. Kairouz, Z. Liu, and T. Steinke, “The distributed discrete Gaussian mechanism for federated learning with secure aggregation,” in Proc. ICML, 2021. [5] N. Agarwal, P. Kairouz, and Z. Liu, “The Skellam mechanism for differentially private federated learning,” in Proc. NeurIPS, 2021. [6] Office for National Statistics, “Policy on protecting confidentiality in tables of birth and death statistics,” [Online]. Available: https://www.ons.gov.uk/methodology/ methodologytopicsandstatisticalconcepts/disclosurecontrol/ policyonprotectingconfidentialityintablesofbirthanddeathstatistics. [7] European Parliament and Council of the European Union, “Regulation (EU) 2016/679 of the European Parliament and of the Council of 27 April 2016 (General Data Protection Regulation),” Art. 5(1)(c), Official Journal of the European Union, L119, pp. 1–88, 2016. [8] N. Shlezinger, M. Chen, Y. C. Eldar, H. V. Poor, and S. Cui, “UVeQFed: Universal vector quantization for federated learning,” IEEE Trans. Signal Process., vol. 69, pp. 500–514, 2021. [9] N. Lang, E. Sofer, T. Shaked, and N. Shlezinger, “Joint privacy enhancement and quantization in federated learning,” IEEE Trans. Signal Process., vol. 71, pp. 295–310, 2023. [10] N. Lang, N. Shlezinger, R. G. L. D’Oliveira, and S. El Rouayheb, “Compressed private aggregation for scalable and robust federated learning over massive networks,” IEEE Trans. Mobile Comput., vol. 24, no. 10, pp. 9934–9950, 2025. [11] N. Lang, M. Simhi, and N. Shlezinger, “OLALa: Online learned adaptive lattice codes for heterogeneous federated learning,” arXiv:2506.20297. [12] P. Paillier, “Public-key cryptosystems based on composite degree residuosity classes,” in Proc. EUROCRYPT, 1999. [13] H. Corrigan-Gibbs and D. Boneh, “Prio: Private, robust, and scalable computation of aggregate statistics,” in Proc. USENIX NSDI, 2017. [14] Y. Ben-Itzhak et al., “ScionFL: Efficient and robust secure quantized aggregation,” in Proc. IEEE Conf. Secure and Trustworthy Machine Learning (SaTML), 2024. [15] R. Zamir, Lattice Coding for Signals and Networks. Cambridge Univ. Press, 2014. [16] S. M. Azimi-Abarghouyi, “Out-of-air computation: Enabling structured extraction from wireless superposition,” arXiv:2604.04312. [17] S. M. Azimi-Abarghouyi and L. R. Varshney, “Compute-update federated learning: A lattice coding approach,” IEEE Trans. Signal Process., vol. 72, pp. 5213–5227, 2024. [18] S. M. Azimi-Abarghouyi and L. R. Varshney, “Federated learning via lattice joint source-channel coding,” in Proc. IEEE ISIT, 2024. [19] C. L. Canonne, G. Kamath, and T. Steinke, “The discrete Gaussian for differential privacy,” in Proc. NeurIPS, vol. 33, 2020. [20] D. Micciancio and C. Peikert, “Hardness of SIS and LWE with small parameters,” in Proc. CRYPTO, 2013. [21] I. Mironov, “Rényi differential privacy,” in Proc. IEEE CSF, 2017. [22] D. Micciancio and O. Regev, “Worst-case to average-case reductions based on Gaussian measures,” SIAM J. Comput., vol. 37, no. 1, pp. 267–302, 2007. [23] A. Coates, H. Lee, and A. Y. Ng, “An analysis of single-layer networks in unsupervised feature learning,” in Proc. AISTATS, 2011. [24] H. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. Agüera y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in Proc. AISTATS, 2017. [25] I. Pinelis, “Optimum bounds for the distributions of martingales in Banach spaces,” Ann. Probab., vol. 22, no. 4, pp. 1679–1706, 1994. [26] B. V. Gnedenko and A. N. Kolmogorov, Limit Distributions for Sums of Independent Random Variables. Addison-Wesley, 1954.

Related documents

• Progressive-Resolution Secure Aggregation for Federated Learning#1155630
• Privacy Preservation for Federated Learning With Robust Aggregation in Edge Computing#177312
• FLIBD: A Federated Learning-Based IoT Big Data Management Approach for Privacy-Preserving over Apache Spark with FATE#177329
• PoCQ: Proof of Contribution Quality as a Lightweight Blockchain Consensus for Secure Federated Learning#259423
• Remote Rowhammer Attack using Adversarial Observations on Federated Learning Clients#155570