acceptodds
Under review as a conference paper at ICLR 2027

CertiRank: Aligning Federated Rank Learning with Secure and Certified Aggregation

Abstract

Privacy-preserving Byzantine-robust Federated Learning (PBFL) aims to protect client updates while mitigating poisoning attacks. While homomorphic encryption (HE) has become a mainstream approach for PBFL, the combination of real-valued updates, robust aggregation, and encrypted computation often incurs substantial overhead. To address this challenge, we propose CertiRank, a rank-based PBFL that aligns federated rank learning with secure and certified aggregation. By leveraging integer-valued ranking updates and lightweight additive aggregation, CertiRank eliminates costly real-to-integer conversion and avoids complex ciphertext-domain similarity computations. To strengthen robustness against malicious clients, we introduce Certified Membership-gated Ranking Aggregation (CMGRA), which decouples subnetwork selection from fine-grained rank ordering and certifies membership changes using honest-support evidence. To securely realize CMGRA, we develop a customized secure aggregation mechanism that combines SEncode, RLWE-AHE, and privacy-preserving validity verification, enabling efficient additive aggregation and certification directly over encrypted ranking updates. Experiments demonstrate that CertiRank achieves strong robustness and competitive model utility while substantially reducing computation and communication overhead compared with existing HE-based PBFL schemes. Our code is available at https://anonymous.4open.science/r/CertiRank.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Federated Rank Learning, Byzantine Robustness, Homomorphic Encryption, Secure Aggregation, Poisoning Attacks

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_Fa8qOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposed a privacy-preserving, Byzantine-robust federated learning scheme. The authors replaced real-valued updates with integer-valued ranking updates and designed certified membership-gated ranking aggregation. Experimental results show that their solution is efficient.

Critical strengths
  • The solution appears to effectively integrate existing technologies to address efficiency issues.
Critical weaknesses
  • Lacking sufficient innovation.
  • Unfair comparison in Section 5.1.
Questions for authors
  1. Why choose a 60-bit ciphertext modulus? And what are the default moduli?
  2. What are the parameters specified in the assumptions of security proofs?
4 comments

Author Response (Reviewer Fa8q)

We sincerely thank you for your careful reading and valuable comments, which will help us improve the clarity and quality of this paper.


W1: Lacking sufficient innovation.

Response: The central contribution of CertiRank is not any single component but the co-design of the learning paradigm, robust aggregation, and privacy-preserving computation so that they fit together. Reviewers LaSY and 3WVX describe this design as "substantive ... rather than only an optimization of an existing encryption workflow."

At the learning layer, we build on FRL, a supermask-based framework in which clients communicate integer-valued rankings instead of real-valued gradients or model updates. Its integer representation and additive aggregation naturally suit encrypted computation, avoiding real-to-integer conversion and costly encrypted similarity calculations. To address FRL's vulnerability to ranking manipulation, including VEM attacks, we introduce CMGRA, a new aggregation rule. It separates subnetwork membership selection from fine-grained ranking and certifies membership changes with honest-support evidence, with a tight bound on the honest-membership utility gap (Theorem 1), while keeping the simple additive structure needed for efficient secure aggregation.

At the cryptographic layer, we tailor the encoding and protocol to these computational requirements. Our sign-aware encoding implements the prescribed cyclic shifts through monomial multiplication, which eliminates Galois keys and key switching without increasing the noise norm. We further combine cyclic shifts and block permutations in a two-stage obfuscation mechanism, which lets the verification server check ranking validity and top-K membership consistency on position-obfuscated submissions. Together, these mechanisms support the verification and secure aggregation that CMGRA requires.

The resulting benefits are substantial under the reported configurations: compared with BCPBFL, CertiRank reduces client and server processing time by up to 86.6% and 97.0%, respectively; compared with RVPFL, it reduces client upload and inter-server traffic by up to 96.9% and 98.9%, respectively, while remaining robust against the evaluated poisoning attacks.


W2 and Q1: Comparison fairness, and why a 60-bit ciphertext modulus? What are the default moduli?

Response: Thank you for raising these related concerns.

Fairness. Section 5.1 compares encoding and homomorphic operations on the same hardware at matching polynomial degrees. The comparison evaluates the combined efficiency benefits of CertiRank's coefficient encoding, monomial shifts, and task-specific modulus configuration against native SIMD-based HE implementations. The baseline moduli are specified below.

Modulus. CertiRank only needs additive aggregation and prescribed cyclic shifts, without ciphertext–ciphertext multiplication. Our sign-aware encoding realizes these shifts through monomial multiplication, which avoids Galois key switching and preserves the noise norm. Noise therefore grows only linearly in the number of clients, and a single 60-bit modulus suffices; it also fits native 64-bit arithmetic. With N=8192N=8192, z=235z=2^{35}, q=1152921092289986561q=1152921092289986561 (60-bit), and at most U=25U=25 clients, the aggregate error is bounded by

∣Eagg∣∞≤21U(2N+1)+U+12=8,602,138<q2z≈16,777,210,\\|E_{\mathrm{agg}}\\|_\infty\le21U(2N+1)+\frac{U+1}{2}=8{,}602{,}138<\frac{q}{2z}\approx16{,}777{,}210,

which guarantees correct decryption of the aggregate (see our response to Reviewer LaSY (Q4) for details). A 60-bit modulus is also well below the maximum of 109 bits that the Homomorphic Encryption Standard [1] allows for 128-bit security at N=4096N=4096, so CertiRank's parameters provide at least 128-bit security.

Default moduli. The baselines use Microsoft SEAL's default coefficient-modulus chains, with total bit lengths of 109, 218, and 438 bits for N=4096N=4096, 8192, and 16384, respectively, following the 128-bit classical security recommendations for ternary secrets in the Homomorphic Encryption Standard [1]. These totals include the special prime used for key switching in Galois-key-based slot rotations, which CertiRank does not need. We have clarified these settings in the revised manuscript.

[1] Martin Albrecht et al. Homomorphic Encryption Standard. In Protecting Privacy through Homomorphic Encryption, pp. 31–62, 2021.

Q2: What are the parameters specified in the assumptions of the security proofs?

Response: Thank you for requesting this clarification. Our IND-CPA proof (Appendix F.1) relies on the one- and two-sample small-secret decisional RLWE assumptions over the ring

Rq=Zq[x]/(xN+1),R_q=\mathbb{Z}_q[x]/(x^N+1),

parameterized by the ring dimension NN, the ciphertext modulus qq, the secret distribution χkey\chi_{\mathrm{key}}, and the error distribution χerr\chi_{\mathrm{err}}. Concretely, N∈4096,8192,16384N\in\\{4096,8192,16384\\}, q=1152921092289986561q=1152921092289986561, and z=235z=2^{35}. Both the secret key ss and the encryption randomness rr have coefficients sampled independently and uniformly from −1,0,1\\{-1,0,1\\}. Each error coefficient is sampled as

X−Y,X,Y∼indBinomial⁡(21,12),X-Y,\qquad X,Y\overset{\mathrm{ind}}{\sim}\operatorname{Binomial}\left(21,\tfrac{1}{2}\right),

i.e., a centered binomial distribution with support [−21,21][-21,21] and standard deviation about 3.24. With a 60-bit qq, these parameters lie within the 128-bit security range of the Homomorphic Encryption Standard for all three ring dimensions.

Formally, for k∈1,2k\in\\{1,2\\}, the decisional RLWE assumption states that

(ai,,aiw+ei)i=1kand(ai,,ui)i=1k\left(a_i,\\,a_i w+e_i\right)_{i=1}^{k}\quad\text{and}\quad\left(a_i,\\,u_i\right)_{i=1}^{k}

are computationally indistinguishable, where w←χkeyw\leftarrow\chi_{\mathrm{key}} is shared across the kk samples, ai,uia_i,u_i are independent and uniform over RqR_q, and ei←χerre_i\leftarrow\chi_{\mathrm{err}} are independent. The two-sample assumption accounts for the dependence introduced by ciphertext components that share the same encryption randomness. Based on these assumptions, Theorem 7 bounds the IND-CPA advantage as

Adv⁡AIND-CPA≤Adv⁡D11-RLWE+Adv⁡D22-RLWE.\operatorname{Adv}^{\mathrm{IND\text{-}CPA}}_{\mathcal{A}}\le\operatorname{Adv}^{1\text{-}\mathrm{RLWE}}_{\mathcal{D}_1}+\operatorname{Adv}^{2\text{-}\mathrm{RLWE}}_{\mathcal{D}_2}.

Hence CertiRank is IND-CPA secure under these RLWE assumptions, and the noise analysis in our response to Reviewer LaSY (Q4) establishes decryption correctness for the evaluated configuration.

Thank you again for your constructive feedback on our paper. We would like to follow up on our rebuttal and ask whether you have any remaining questions or concerns. We would be happy to provide further clarification. If our responses have addressed your concerns, would you consider raising your score?

Dear Reviewer Fa8q,

Sorry to bother you again. With the discussion phase nearing the end, we would like to know whether the responses have addressed your concerns.

Should this be the case, we are encouraged that you raise the final rating to reflect this.

If there are any remaining concerns, please let us know. We are more than willing to engage in further discussion and address any remaining concerns to the best of our abilities.

We are looking forward to your reply. Thank you for your efforts in this manuscript.

Best regards,

Authors

Reviewer_LaSYOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

CertiRank replaces real-valued FL updates with integer rankings of model connections, making encrypted aggregation simpler. Its main contribution is CMGRA, which uses clients’ top-KK membership votes to control which connections enter the model while using rank sums to order them. The paper also presents an encoding scheme and a two-server protocol for validating and aggregating encrypted rankings. Experiments evaluate four poisoning attacks and report stronger robustness than standard federated rank learning, alongside lower computation and communication costs than the tested encrypted federated learning baselines.

Critical strengths
  1. The learning and encryption designs fit together. Replacing real-valued updates with integer rankings lets the protocol aggregate encrypted submissions largely through addition. This is a substantive design contribution, rather than only an optimization of an existing encryption workflow.
  2. The proposed aggregation rule shows meaningful gains over standard federated rank learning. CMGRA substantially improves accuracy under several tested attacks while leaving no-attack accuracy nearly unchanged. This suggests that its membership gate addresses a real weakness of rank-based learning.
Critical weaknesses
  1. Validation does not establish correct aggregation of malicious submissions. The protocol checks that each ciphertext decrypts to a valid ranking, but does not bound its decryption noise. Malicious ciphertexts can pass individually yet accumulate enough error to change the decrypted aggregate. The robustness proofs assume correct membership counts, so this gap affects the paper’s central end-to-end claim.
  2. CMGRA’s decision rule depends on B, but the simulator supplies the actual number of malicious clients in each round. A deployed system would generally have to estimate or conservatively set this value. Without testing underestimation and overestimation, the experiments do not show whether the reported robustness holds in practice.
  3. The stated collusion model permits substantial ranking leakage. If the decryption server colludes with a client, it learns the encoding shifts. For the single-block layers used in the experiments, it can then recover an honest client’s edge-aligned ranking from the verification plaintext. This limits the privacy claim for a setting the paper explicitly allows.
Questions for authors
  1. What prevents an accepted client from submitting a ciphertext that decrypts to a valid ranking individually but causes a decryption error after aggregation? Is ciphertext noise or well-formedness checked anywhere in the protocol?
  2. Under the permitted S2S_2-client collusion, what protects an honest client’s edge-aligned ranking in a single-block layer once the colluding client reveals the shift?
  3. How would BB be chosen without knowing the actual malicious-client count? Are results available for a fixed bound chosen before each round?
  4. What exact ciphertext modulus, error distribution, and measured noise budget were used? These details are needed to assess decryption correctness at the reported client counts.
5 comments

Author Response (Reviewer LaSY)

We sincerely thank you for your careful reading and for identifying these technical gaps. Addressing them has strengthened both the protocol and its analysis.


Q1: What prevents an accepted client from submitting a ciphertext that decrypts to a valid ranking individually but causes a decryption error after aggregation?

Response: We agree that individual plaintext validity alone does not guarantee correct aggregate decryption. The original protocol verifies ranking validity and top-KK consistency but does not explicitly detect aggregation errors caused by maliciously constructed ciphertexts. We have therefore introduced a lightweight low-bit consistency check (Section 4.3.2).

In the original scheme, each client packs an edge's rank rr and membership bit μ∈0,1\mu\in\\{0,1\\} as h=λr+μh=\lambda r+\mu, where λ>U\lambda>U. We now encode hh as GhGh, where G=2gG=2^g is the smallest power of two exceeding ⌈U/2⌉\lceil U/2\rceil, reserving the lowest gg bits for error detection. We require G∣zG\mid z, q mod z=1q\bmod z=1, q>2zq>2z, and z>G[λU(d−1)+U]z>G[\lambda U(d-1)+U] to prevent integer overflow.

For any individually accepted ciphertext, including a maliciously constructed one, the normalized decryption-rounding residual is bounded by 1/21/2 per coefficient. Signed permutations preserve this bound, while plaintext masking introduces an additional scaling error of at most (z−1)/q<1/2(z-1)/q<1/2. Thus, aggregating at most UU accepted ciphertexts yields

|\delta_i|\le\lceil U/2\rceil<G.$$ $S_2$ checks that the lowest $g$ bits are zero before running the original validity checks, and clients run the same check after unmasking and decoding the aggregate. Since $G\mid z$ and $|\delta_i|<G$, **passing the final check forces $\delta_i=0$, which guarantees that the recovered aggregate exactly equals the sum of the plaintexts individually validated by $S_2$, even for maliciously constructed ciphertexts.** Otherwise, the round is aborted before CMGRA. This guarantee does not require an explicit bound on the encryption noise of malicious ciphertexts. In our experiments ($U=25$), $G=16$ fits within the existing plaintext modulus $z=2^{35}$, and $q$ remains 60-bit. **The modification requires no additional ciphertexts, homomorphic operations, or communication rounds**; it adds only inexpensive bit checks and shifts. We have updated the protocol, the correctness analysis, and the premise of Theorem 1 accordingly, so that the end-to-end robustness guarantee now holds for maliciously constructed ciphertexts. --- **Q2**: Under the permitted $S_2$-client collusion, what protects an honest client's edge-aligned ranking in a single-block layer once the colluding client reveals the shift? **Response**: We agree that revealing the shift exposes the edge-aligned ranking of a single-block layer. To mitigate this leakage, we have revised the protocol by introducing periodic multi-block packing **(Section 4.3.1)**. Specifically, we divide affected layers into multiple blocks and periodically insert zeros between valid entries. Each block contains $b$ valid entries, where $b\mid N$, with a spacing of $s=N/b$. Shifts are restricted to multiples of $s$, so the padding pattern is unchanged by any shift. As a toy example, with $N=8$ and four entries $h_1,\ldots,h_4$, we encode two blocks: $$[h_1,0,0,0,h_2,0,0,0],\quad [h_3,0,0,0,h_4,0,0,0].$$ Both blocks keep identical padding patterns under shifts $\\{0,4\\}$. Therefore, even if the shifts are disclosed, $S_1$'s private inter-block permutation prevents $S_2$ from using them to determine which block originally came first. For $m$ such blocks, knowing the shifts still leaves $m!$ possible original block orders. To avoid excessive padding for some layer dimensions, we also allow different block capacities, and require at least two blocks with identical padding patterns for each capacity. The same construction handles **partially filled tail blocks**, which suffer from the same limitation: there is no other block with an identical visible layout to permute with. In addition, $S_1$ assigns fresh random client identifiers in each round and shuffles submissions before forwarding them to $S_2$. The identifier mapping stays private to $S_1$, which prevents direct cross-round linkage through persistent client identifiers. We note that this construction hides the assignment of blocks to edge positions, not the relative order of entries within a block. In the revised leakage theorem, we state precisely what $S_2$ learns under $S_2$–client collusion. The overhead is modest: the total number of ciphertext blocks increases from 207 to 213 for Conv2, from 646 to 655 for Conv8, and from 1,366 to 1,379 for ResNet18, i.e., by only 2.90%, 1.39%, and 0.95%, respectively.

Q3: How would BB be chosen without knowing the actual malicious-client count? Are results available for a fixed bound chosen before each round?

Response: Thank you for highlighting this practical concern. CMGRA only needs an upper bound on the number of Byzantine submissions, not the exact count. We now fix B=⌈0.30×25⌉=8B=\lceil 0.30\times25\rceil=8, which corresponds to the highest evaluated attack fraction, before training, and keep it unchanged across all rounds and attack settings. We also added two random seeds, so each result is now averaged over three runs. The complete results are included in the revised manuscript (Section 5.2.3).

MNIST

SettingCMGRA (Orig.)CMGRA (B=8)
No attack98.51±0.1097.83±0.29
LF 10%97.66±0.4997.43±0.02
LF 20%97.39±0.1797.12±0.26
LF 30%96.82±0.5296.20±1.07
GA 10%97.58±0.3697.00±0.22
GA 20%96.45±0.4595.86±0.35
GA 30%95.10±0.5195.23±0.41
PB 10%98.29±0.26 / 13.60±0.2697.61±0.12 / 13.94±0.56
PB 20%97.63±0.93 / 21.20±1.4797.88±0.21 / 22.64±2.41
PB 30%98.01±0.81 / 24.74±1.1697.74±0.52 / 24.43±1.85
VEM 10%96.69±0.4696.56±0.45
VEM 20%96.91±0.2396.33±0.29
VEM 30%95.82±0.1396.30±0.37

SVHN

SettingCMGRA (Orig.)CMGRA (B=8)
No attack93.18±0.1893.09±0.24
LF 10%93.13±0.1893.26±0.40
LF 20%93.07±0.8792.76±0.07
LF 30%92.45±0.6892.94±0.52
GA 10%92.83±0.3191.90±0.70
GA 20%88.89±1.0188.62±0.82
GA 30%86.58±1.1686.22±0.89
PB 10%93.46±0.46 / 2.73±0.7092.71±0.55 / 2.29±0.96
PB 20%93.90±0.56 / 12.66±0.2693.50±0.74 / 13.13±0.69
PB 30%92.95±0.54 / 18.58±0.8893.40±0.52 / 18.45±0.82
VEM 10%89.47±0.4989.62±0.09
VEM 20%89.08±0.4888.88±0.69
VEM 30%86.63±0.8486.97±0.64

CIFAR-10

SettingCMGRA (Orig.)CMGRA (B=8)
No attack80.24±0.2880.08±0.69
LF 10%79.10±0.1878.51±0.06
LF 20%78.63±1.3378.35±0.68
LF 30%70.24±1.1770.18±1.83
GA 10%78.49±0.6878.02±0.29
GA 20%77.23±0.3276.97±0.71
GA 30%75.00±0.9174.85±1.05
PB 10%80.98±0.90 / 3.19±0.4380.92±0.65 / 4.32±0.70
PB 20%80.11±0.62 / 7.21±1.1979.58±0.66 / 5.74±1.52
PB 30%79.67±1.33 / 16.48±2.6678.89±0.29 / 16.41±1.19
VEM 10%77.88±0.1177.28±0.15
VEM 20%74.60±1.4174.55±1.60
VEM 30%74.72±0.2274.34±0.65

CMGRA keeps comparable accuracy when BB is fixed at 8, even when the actual number of malicious clients is lower (10% and 20%), i.e., when BB is overestimated. Overestimating BB only makes membership exchanges more conservative: since honest clients largely agree on the most useful edges, their membership-count gaps usually still exceed B+1B+1, so most strongly supported updates still go through. Underestimating BB, in contrast, voids the certificate, because Byzantine submissions could then outweigh the required count gap. We therefore recommend setting BB conservatively to the largest malicious fraction the deployment must tolerate, and the results above show that this choice costs little accuracy. We have added this guidance to the revised manuscript.

Q4: What exact ciphertext modulus, error distribution, and measured noise budget were used?

Response: Thank you for highlighting the importance of these details. We have added the exact cryptographic parameters and a detailed noise analysis to the revised manuscript (Section 4.3.5).

We use a plaintext modulus z=235z=2^{35} and a 60-bit prime ciphertext modulus q=1152921092289986561q=1152921092289986561, satisfying q≡1(modz)q\equiv1\pmod z. The coefficients of the secret key ss and of the encryption randomness rr are sampled independently and uniformly from −1,0,1\\{-1,0,1\\}. The error polynomials e,e1,e2e,e_1,e_2 follow a centered binomial distribution: each coefficient is X−YX-Y with independent X,Y∼Binomial⁡(21,1/2)X,Y\sim\operatorname{Binomial}(21,1/2), so its magnitude is at most 21 and its standard deviation is 10.5≈3.24\sqrt{10.5}\approx3.24, matching the σ≈3.2\sigma\approx3.2 recommended by the Homomorphic Encryption Standard.

For an honestly generated ciphertext, the encryption noise is

η=re+e1+e2s.\eta=re+e_1+e_2s.

Each coefficient of rere and e2se_2s is a signed sum of NN products. Since the coefficients of rr and ss have magnitude at most 1 and those of e,e1,e2e,e_1,e_2 at most 21,

∣η∣∞≤21N+21+21N=21(2N+1).\\|\eta\\|_\infty\le 21N+21+21N=21(2N+1).

Aggregating at most UU ciphertexts gives ∣ηagg∣∞≤21U(2N+1)\\|\eta_{\mathrm{agg}}\\|_\infty\le21U(2N+1). The cyclic rotations enabled by our sign-aware encoding add no noise: multiplication by xvx^v only permutes and sign-flips coefficients, which preserves the infinity norm. With nearest-integer plaintext scaling round⁡(qm/z)\operatorname{round}(qm/z), each encrypted message adds at most 1/21/2 rounding error per coefficient, and the server's plaintext mask adds at most another 1/21/2. Hence the total effective error after aggregation and masking satisfies

∣Eagg∣∞≤21U(2N+1)+U+12.\\|E_{\mathrm{agg}}\\|_\infty\le21U(2N+1)+\frac{U+1}{2}.

Correct decryption is guaranteed when ∣Eagg∣∞<q/(2z)\\|E_{\mathrm{agg}}\\|_\infty<q/(2z). For our setting with N=8192N=8192 and at most U=25U=25 clients,

∣Eagg∣∞≤8,602,138<q2z≈16,777,210,\\|E_{\mathrm{agg}}\\|_\infty\le8{,}602{,}138<\frac{q}{2z}\approx16{,}777{,}210,

so the worst-case bound leaves a margin of about one bit. But this bound assumes every one of the 2NU2NU products takes its maximal value simultaneously, the actual aggregate noise has standard deviation about 2.4×1032.4\times10^3, so q/(2z)q/(2z) lies roughly 7,0007{,}000 standard deviations away and the probability of a decryption error is negligible.

Therefore, ciphertexts generated according to the specification decrypt correctly after aggregation, and for maliciously constructed ciphertexts, the low-bit consistency check in our response to Q1 detects incorrect aggregates before they affect CMGRA.

Reviewer_3WVXOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes CertiRank, a privacy-preserving Byzantine-robust federated learning (PBFL) framework built on federated rank learning (FRL). Instead of exchanging real-valued updates, clients train Edge-Popup ranking scores over fixed model weights and submit integer-valued rankings, which the authors argue are naturally aligned with integer-ring homomorphic encryption.

The framework has three main components:

  1. CMGRA (Certified Membership-gated Ranking Aggregation), a robust aggregation rule that decouples top-K subnetwork (edge) selection from fine-grained rank ordering. It maintains an incumbent subnetwork and accepts challenger-incumbent exchanges only when backed by an integer "certificate" of honest support (a count gap exceeding the total number of Byzantine submissions B+1), with a fallback Borda-style exchange rule under tie-breaking.
  2. A customized cryptographic layer consisting of SEncode (sign-aware coefficient packing that handles signed integers without extra encoding transforms), RLWE-AHE (an RLWE-based additively homomorphic scheme over polynomial coefficient rings that replaces Galois-key slot rotations with cheap monomial shifts), and a two-server protocol with position-obfuscated validity verification and masked aggregate recovery.
  3. Theorem 1 bounds the honest-membership utility gap of the final selected set by m(B+b_t) for every allowable (adaptive, colluding) Byzantine strategy, with exact recovery when the honest top-K margin exceeds B+b_t; a tightness example shows the bound is attained. Theorem 2 bounds cumulative subnetwork changes by m(1+V_T) and gives eventual stabilization under a finite-variation condition. The cryptographic analysis proves IND-CPA security of RLWE-AHE under a small-secret RLWE assumption, gives an exact characterization of what the verification channel discloses to the decrypting server, and proves uniform masking of the recovered aggregate.
Critical strengths
  1. Rather than patching an existing HE-based PBFL scheme, the paper redesigns the client representation (integer rankings), the aggregation rule (additive membership counts), and the crypto layer (coefficient-packed additive HE with monomial shifts) so that they fit together. The result is a 6–30× reduction in client/server time and 4–32× reduction in traffic relative to BCPBFL, and orders of magnitude relative to RVPFL, at comparable robustness. This is consequential because efficiency is the main obstacle to practical PBFL, and the paper demonstrates the gains where they matter (per-round system costs), not only in microbenchmarks.
  2. The paper provides simple-but-tight robustness theory (with an explicit tightness example and worst-case progress analysis), an IND-CPA proof for the customized scheme, a leakage/masking analysis of the two-server protocol, robustness experiments against four attacks including the rank-adaptive VEM attack, a reproduction manifest (168 runs with seeds and per-method hyperparameters), and released code. This level of verifiability materially raises my confidence in the claimed results.
Critical weaknesses
  1. The efficiency gains are partly purchased with a per-client leakage channel that the compared baselines do not have. By design, the secret-key server decrypts per-client verification plaintexts that expose every rank value, membership bit, and block grouping of each submission; the disclosed validity masks align partial blocks in their original coordinates, and once the shared offsets are learned by a coalition of the secret-key server with a single malicious client (permitted by the threat model), only F! inter-block ambiguity remains — and none at all for the single-block layers that all three evaluated models contain.
  2. The learning-side contribution and the generality of the approach are limited. CertiRank requires the FL workload to be expressed in FRL form (Edge-Popup rankings over fixed weights), which restricts applicability to rank-based training and inherits its accuracy ceiling; on CIFAR10/ResNet18 the no-attack accuracy (80.01%) trails plaintext FedAvg (83.36%), and BatchNorm affine parameters/running statistics had to be removed to fit the rank representation. The "alignment" is thus achieved by restricting the learning problem to what cheap cryptography supports — a legitimate engineering trade-off, but one that narrows the paper's scope, and the paper does not characterize when this restriction is acceptable. The single-run robustness tables with an oracle adversarial budget (detailed under Soundness) further temper the empirical claims that motivate the "certified" branding.
Questions for authors
  • How are client dropouts mid-round handled in the two-server protocol (does the masked-aggregate recovery require a fixed participant set per round)?
  • What is the accuracy/robustness cost of the rank-form restriction on larger models (e.g., CIFAR100 or a small ImageNet subset), where FRL-style training is known to degrade relative to dense training?
  • The theory certifies membership counts only, but the aggregated Borda scores initialize the next round of local training. Did you evaluate a VEM variant that preserves top-K membership while manipulating within-group ordering or ranks just below the selection boundary, i.e., attacking through the uncertified score channel?
3 comments

Author Response (Reviewer 3WVX)

We sincerely thank you for your positive evaluation of our work and for your constructive comments, which have helped us strengthen the paper.


W1: Privacy leakage in single-block layers and partial tail blocks when S2S_2 colludes with a malicious client.

Response: We agree that revealing the shift exposes the edge-aligned ranking of a single-block layer. To mitigate this leakage, we have revised the protocol by introducing periodic multi-block packing (Section 4.3.1).

Specifically, we divide affected layers into multiple blocks and periodically insert zeros between valid entries. Each block contains bb valid entries, where b∣Nb\mid N, with a spacing of s=N/bs=N/b. Shifts are restricted to multiples of ss, so the padding pattern is unchanged by any shift. As a toy example, with N=8N=8 and four entries h1,…,h4h_1,\ldots,h_4, we encode two blocks:

[h_3,0,0,0,h_4,0,0,0].$$ Both blocks keep identical padding patterns under shifts $\\{0,4\\}$. Therefore, even if the shifts are disclosed, $S_1$'s private inter-block permutation prevents $S_2$ from using them to determine which block originally came first. For $m$ such blocks, knowing the shifts still leaves $m!$ possible original block orders. To avoid excessive padding for some layer dimensions, we also allow different block capacities, and require at least two blocks with identical padding patterns for each capacity. The same construction handles **partially filled tail blocks**, which suffer from the same limitation: there is no other block with an identical visible layout to permute with. In addition, $S_1$ assigns fresh random client identifiers in each round and shuffles submissions before forwarding them to $S_2$. The identifier mapping stays private to $S_1$, which prevents direct cross-round linkage through persistent client identifiers. We note that this construction hides the assignment of blocks to edge positions, not the relative order of entries within a block. In the revised leakage theorem, we state precisely what $S_2$ learns under $S_2$–client collusion. The overhead is modest: the total number of ciphertext blocks increases from 207 to 213 for Conv2, from 646 to 655 for Conv8, and from 1,366 to 1,379 for ResNet18, i.e., by only 2.90%, 1.39%, and 0.95%, respectively.

W2: Single-run robustness tables with an oracle adversarial budget.

Response: Thank you for highlighting this practical concern. We now fix B=⌈0.30×25⌉=8B=\lceil 0.30\times25\rceil=8, which corresponds to the highest evaluated attack fraction, before training, and keep it unchanged across all rounds and attack settings. We also added two random seeds, so each result is now averaged over three runs. For brevity, we report the original CMGRA and CMGRA with fixed B=8B=8 below; the complete results are included in the revised manuscript (Section 5.2.3).

MNIST

SettingCMGRA (Orig.)CMGRA (B=8)
No attack98.51±0.1097.83±0.29
LF 10%97.66±0.4997.43±0.02
LF 20%97.39±0.1797.12±0.26
LF 30%96.82±0.5296.20±1.07
GA 10%97.58±0.3697.00±0.22
GA 20%96.45±0.4595.86±0.35
GA 30%95.10±0.5195.23±0.41
PB 10%98.29±0.26 / 13.60±0.2697.61±0.12 / 13.94±0.56
PB 20%97.63±0.93 / 21.20±1.4797.88±0.21 / 22.64±2.41
PB 30%98.01±0.81 / 24.74±1.1697.74±0.52 / 24.43±1.85
VEM 10%96.69±0.4696.56±0.45
VEM 20%96.91±0.2396.33±0.29
VEM 30%95.82±0.1396.30±0.37

SVHN

SettingCMGRA (Orig.)CMGRA (B=8)
No attack93.18±0.1893.09±0.24
LF 10%93.13±0.1893.26±0.40
LF 20%93.07±0.8792.76±0.07
LF 30%92.45±0.6892.94±0.52
GA 10%92.83±0.3191.90±0.70
GA 20%88.89±1.0188.62±0.82
GA 30%86.58±1.1686.22±0.89
PB 10%93.46±0.46 / 2.73±0.7092.71±0.55 / 2.29±0.96
PB 20%93.90±0.56 / 12.66±0.2693.50±0.74 / 13.13±0.69
PB 30%92.95±0.54 / 18.58±0.8893.40±0.52 / 18.45±0.82
VEM 10%89.47±0.4989.62±0.09
VEM 20%89.08±0.4888.88±0.69
VEM 30%86.63±0.8486.97±0.64

CIFAR-10

SettingCMGRA (Orig.)CMGRA (B=8)
No attack80.24±0.2880.08±0.69
LF 10%79.10±0.1878.51±0.06
LF 20%78.63±1.3378.35±0.68
LF 30%70.24±1.1770.18±1.83
GA 10%78.49±0.6878.02±0.29
GA 20%77.23±0.3276.97±0.71
GA 30%75.00±0.9174.85±1.05
PB 10%80.98±0.90 / 3.19±0.4380.92±0.65 / 4.32±0.70
PB 20%80.11±0.62 / 7.21±1.1979.58±0.66 / 5.74±1.52
PB 30%79.67±1.33 / 16.48±2.6678.89±0.29 / 16.41±1.19
VEM 10%77.88±0.1177.28±0.15
VEM 20%74.60±1.4174.55±1.60
VEM 30%74.72±0.2274.34±0.65

CMGRA keeps comparable accuracy when BB is fixed at 8, even when the actual number of malicious clients is lower. Overestimating BB only makes membership exchanges more conservative: since honest clients largely agree on the most useful edges, their membership-count gaps usually still exceed B+1B+1, so most strongly supported updates still go through, and the loss in clean accuracy is below 0.8 points.


Q1: How are client dropouts mid-round handled? Does masked-aggregate recovery require a fixed participant set per round?

Response: No. The mask is generated by S1S_1 after it homomorphically aggregates the accepted submissions, and it does not depend on which clients participate. For each block, S1S_1 adds a fresh mask ρ\rho to the aggregate ciphertext and sends ρ\rho directly to the clients. S2S_2 sees only the masked aggregate, which hides the aggregate from S2S_2 in the absence of server–client collusion. After decryption, S2S_2 sends the masked aggregate plaintext p+ρ mod zp+\rho \bmod z to the clients, and each client subtracts ρ\rho modulo zz and decodes the result.

Therefore, recovery requires neither a fixed, preselected participant set nor that all selected clients stay online. A client that disconnects after uploading does not prevent the servers from processing its submission, and it does not prevent other clients from retrieving the aggregate. A client that drops out before uploading is simply excluded from the accepted set of that round.

Q2: Accuracy and robustness cost of the rank-form restriction on larger tasks (e.g., CIFAR-100 or ImageNet).

Response: Thank you for highlighting this trade-off. We agree that rank-based learning can lose accuracy compared with dense training on harder tasks, and CMGRA does not remove this inherent limitation.

To quantify the cost, we evaluated CIFAR-100 with ResNet-34, comparing FedAvg, FRL, and CMGRA(fix BB to 8) under the same data partition and training budget (25 clients, 300 rounds). FRL and CMGRA use a 10% subnetwork keep ratio. We evaluate the attack-free setting and label flipping with 20% malicious clients, over three random seeds.

MethodClean ACC (%)Attack ACC (%)
FedAvg61.2 ± 0.535.5 ± 1.8
FRL50.8 ± 0.738.9 ± 1.4
CMGRA50.3 ± 0.642.4 ± 0.8

FRL loses 10.4 points of clean accuracy relative to dense training, and CMGRA adds only a further 0.5-point loss. Under attack, CMGRA is 3.5 points more accurate than FRL and 6.9 points more accurate than FedAvg. In the revised manuscript (Section 6), we state the scope of CertiRank explicitly: it improves robustness and efficiency within rank-based FL but does not close the utility gap to dense training, so it is most suitable when privacy and Byzantine robustness requirements outweigh this gap.


Q3: Robustness against VEM attacks that preserve top-K membership but manipulate the uncertified Borda scores.

Response: Thank you for raising this concern. We agree that, even when top-K membership is unchanged, manipulating the relative ranks of edges can affect subsequent training through the aggregated Borda scores.

To evaluate this, we implemented VEM-MP, a variant of VEM that keeps the selected top-K edges unchanged but manipulates their relative ranks and the ranks of unselected edges near the selection boundary. The attacker chooses these changes to maximize the loss of subsequent local training while satisfying CMGRA's membership constraints. We ran VEM-MP on MNIST, SVHN, and CIFAR-10 with 25 clients over 500 rounds, with 10%, 20%, and 30% malicious clients and a fixed budget B=8B=8, over three random seeds.

DatasetSettingACC (%)
MNISTNo Attack97.83 ± 0.29
VEM 10% / VEM-MP 10%96.56 ± 0.45 / 96.55 ± 0.45
VEM 20% / VEM-MP 20%96.33 ± 0.29 / 96.65 ± 0.38
VEM 30% / VEM-MP 30%96.30 ± 0.37 / 95.88 ± 0.35
SVHNNo Attack93.09 ± 0.24
VEM 10% / VEM-MP 10%89.62 ± 0.09 / 89.22 ± 0.57
VEM 20% / VEM-MP 20%88.88 ± 0.69 / 88.94 ± 0.63
VEM 30% / VEM-MP 30%86.97 ± 0.64 / 85.96 ± 0.81
CIFAR-10No Attack80.08 ± 0.69
VEM 10% / VEM-MP 10%77.28 ± 0.15 / 77.72 ± 0.28
VEM 20% / VEM-MP 20%74.55 ± 1.60 / 74.28 ± 1.34
VEM 30% / VEM-MP 30%74.34 ± 0.65 / 72.96 ± 0.48

VEM-MP is slightly stronger than VEM, but its effect is bounded: with 30% malicious clients, CMGRA still reaches 95.88%, 85.96%, and 72.96% on MNIST, SVHN, and CIFAR-10, only 0.42, 1.01, and 1.38 points below the original VEM. This is consistent with our analysis: because membership is certified, the score channel can only affect the initialization of the next round and cannot directly change which edges are selected. We have added this attack and its results to the revised manuscript (Section 5.2.3).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.