{"id":"34d317b9-b92e-47de-8529-fed4d3041262","arxiv_id":"2506.09870","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"Nearest neighbor mixing can be composed with secure aggregation and private information retrieval to give information-theoretic privacy and Byzantine resilience for heterogeneous federated learning.","lead":"Federated learning systems with heterogeneous data need aggregation rules that are private and resistant to malicious participants. This paper proposes a protocol that combines nearest-neighbor mixing with secret sharing and private information retrieval to provide both properties, with tests on MNIST and language-model fine-tuning.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 is unproven, and the Step 5 'linear-combination PIR' on which the entire nearest-neighbor privacy mechanism rests is unspecified; the central privacy and robustness claims currently lack support.","rationale":"The paper's contribution is a protocol with a theorem. Without the proof, the central claim is an assertion. Among the unproven components, Step 5 is uniquely load-bearing because it is the only mechanism that prevents the federator's sum retrieval from revealing N_j to the clients and because it must remain Byzantine-resilient; every privacy guarantee in Theorem 1 conditions on N_j staying hidden, and the robustness guarantee depends on the mixtures being correctly reconstructed. I do not see an internal contradiction that forces rejection: the protocol outline is plausible, and the numerical results do provide independent evidence that NNM improves robustness in heterogeneous FL, which is the non-private substrate. But those experiments do not exercise the private aggregation steps. The reader's verdict of CONDITIONAL is therefore appropriate: the paper should be accepted only if the authors supply the proof of Theorem 1 and a complete, correct PIR construction for Step 5. My concern overlaps with the reader's weakest assumption (the PIR modification) but frames it as part of a broader missing-proof issue, hence 'partial' agreement.","tokens_in":12461,"tokens_out":14059,"duration_ms":164153,"concrete_test":"Provide the full specification of the Step 5 PIR scheme and prove that, for any |T|<=z, the joint query/response distribution at T is independent of N_j, and that z+2b+1 responses suffice to decode sum_{ell in N_j}(g_ell + m_j) with b Byzantine clients. A concrete analytic check: instantiate the scheme of [41] with the selection vector replaced by the indicator of N_j and verify the T-privacy condition of [41, Def. 2]; if the distribution depends on N_j for some T, privacy fails. As a complementary computational audit, brute-force n=5, z=1, b=1: enumerate all N_j and confirm that a single client's view is statistically identical across all N_j; any divergence falsifies the privacy claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Theorem 1 (Section III), but the paper states 'The proofs will be provided in an extended version'—no proof of privacy, Byzantine resilience, or robustness is given. The most concrete unverified load-bearing component is Step 5 of Section IV: to hide the nearest-neighbor set N_j from all clients, the federator must 'privately retrieve' the padded sum sum_{ell in N_j} (g_ell + m_j) using 'an extended symmetric PIR scheme,' and the text says 'we omit the details of the PIR scheme' and 'carefully modifying' Tajeddine et al. [41] to return linear combinations of files. This modification must simultaneously (i) allow decoding of the padded sum from z+2b+1 client responses despite b Byzantine clients, and (ii) keep every coalition of at most z clients ignorant of the coefficient vector (equivalently of N_j). No theorem or lemma establishes that [41]'s query distribution remains independent of the requested linear combination under any z servers, nor that Byzantine error correction still decodes when the desired object is a sum rather than a single file. If this fails, the privacy guarantee I(g_i,N_i; O_T |...) = 0 collapses, and the reconstructed mixtures in Step 7 are not trustworthy, so the (b, 8b/(n-b)(kappa+1))-robustness claim in Theorem 1 also lacks a foundation. The numerical evaluation compares NNM variants without simulating the secret-sharing/PIR machinery, so it does not test this step.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a multi-stage protocol that combines information-theoretic verifiable secret sharing, secure pair-wise distance computation, and a tailored symmetric private information retrieval (PIR) step to make nearest neighbor mixing (NNM) compatible with private and Byzantine-resilient federated learning under data heterogeneity. The stated goal is to let the federator compute the NNM pre-processing followed by a distance-based robust aggregation rule (Krum or Multi-Krum) while guaranteeing information-theoretic privacy from colluding clients and from the federator, and Byzantine resilience for n > max{3b, 2(z+b)}. Theorem 1 claims privacy in the sense of Definitions 3 and 4, corruption resilience against b Byzantine clients, (b, 8b/(n-b)(kappa+1))-robustness when composed with a distance-based (b,kappa)-robust rule, and communication costs O(dn^2+n^2) per user and O(dn^2+n^3) for the federator. The numerical section evaluates NNM with Krum and Multi-Krum under several attacks on MNIST and in a RoBERTa-large fine-tuning task, with and without zero-order gradient estimation, and reports consistent accuracy improvements from NNM.","tokens_in":12846,"tokens_out":5773,"duration_ms":65528,"significance":"If the protocol can be completed as claimed, the paper would close a genuine gap: NNM is known to make robust aggregation near-optimal under heterogeneity, but prior private and Byzantine-resilient aggregation schemes could not incorporate it. The paper also contributes a useful comparison with BREA, ByzSecAgg, and ByITFL, and shows empirically that NNM improves robustness across multiple attacks. The zero-order estimation component is a sensible step toward reducing the communication overhead of private aggregation. However, the main theorem is currently unsupported because the proof is deferred, the key PIR extension is unspecified, and the experiments do not instantiate the private protocol. The contribution is therefore conditional on completing the missing construction and proofs.","major_comments":[{"comment":"Theorem 1 is the central claim of the paper, yet the manuscript states 'The proofs will be provided in an extended version.' No proof is given for the privacy guarantees, the Byzantine resilience, the (b, 8b/(n-b)(kappa+1))-robustness bound, or the communication costs. A journal submission must provide these proofs in the manuscript itself; deferring the proof of the main theorem to an extended version is not acceptable.","section":"Section III, Theorem 1"},{"comment":"The entire privacy mechanism for the nearest-neighbor sets N_j relies on an unspecified extension of the coded PIR scheme of Tajeddine et al. [41]. The text says 'we omit the details of the PIR scheme' and refers to 'carefully modifying' the scheme to return linear combinations of files. There is no theorem or lemma establishing that the modified scheme keeps the query distribution independent of the requested linear combination under any coalition of at most z clients, nor that Reed-Solomon decoding still tolerates b Byzantine servers when the desired object is a sum of files rather than a single file. If this extension does not exist or leaks the coefficient vector, the mutual-information equalities in Theorem 1(1) collapse and the reconstructed mixtures in Steps 7 and 8 are not trustworthy. The authors need to provide the construction or a rigorous reduction to [41].","section":"Section IV, Step 5"},{"comment":"The communication bound in Theorem 1 appears inconsistent with the protocol description. Step 5 states that the per-client communication for one private sum retrieval is O(dn+n^2), and the protocol text says the retrieval steps 'should be repeated for each j in [n].' Repeating n times would give O(dn^2+n^3) per user, not the O(dn^2+n^2) claimed in Theorem 1(3). If the costs are amortized across all retrievals, or if the PIR queries for different j can be batched, the text should say so explicitly and the theorem statement should match the protocol.","section":"Section III, Theorem 1(3) vs. Section IV, Step 5"},{"comment":"The numerical evaluation does not implement the private protocol. It runs NNM followed by Krum or Multi-Krum on plaintext gradients (with SGD or zero-order estimates) and compares these with BREA and ByzSecAgg represented by SGD-MKR. No secret sharing, no PIR, no federator-side distance reconstruction, and no Byzantine share aggregation is simulated. Consequently, the experiments provide evidence only for the non-private NNM component and the zero-order estimation method; they do not validate the privacy or Byzantine-resilience claims of Theorem 1. The claims should be scoped accordingly.","section":"Section IV, Steps 5 and 8; Section V"},{"comment":"The robustness claim in Theorem 1(2) assumes that the (b,kappa)-robustness guarantee of the underlying distance-based rule transfers to the quantized finite-field setting and to the NNM definition that uses sums instead of averages. The paper cites [33] but gives no argument that stochastic quantization with mu levels and field size q preserves the distance ordering or the robustness constants, nor that the unnormalized NNM of Definition 2 satisfies the same robustness properties as the normalized version. This transfer is load-bearing for Theorem 1(2) and needs a proof or a precise reference with a stated adaptation.","section":"Section II, Definitions 1 and 2; Section III, Theorem 1(2)"}],"minor_comments":[{"comment":"The privacy guarantee in Theorem 1 is conditioned additionally on the set C* of clients declared honest, which is weaker than Definition 3. The text notes this and says the full guarantee can be restored, but the required modification is not described. Please clarify this gap explicitly in the theorem statement.","section":"Section III, Theorem 1(1) vs. Definition 3"},{"comment":"The main text says 'We provide in Fig. 1 the accuracy for SF over time,' but the Figure 1 caption refers to a 'label flipping attack.' Please align the caption and the text.","section":"Section V, Figure 1"},{"comment":"The re-encoding step writes g_j(x) with coefficients s_{i,t} indexed by i, but it is not immediately clear whether a separate polynomial is generated for each receiver i and each target j. Please rewrite the notation so that the dependence on both i and j is unambiguous.","section":"Section IV, Step 6"},{"comment":"The notation g_i is redefined to mean the quantized gradient after the paragraph on stochastic quantization, which can confuse readers comparing the original gradients with the quantized ones. Please use a distinct symbol such as q_i or tilde g_i for the quantized values.","section":"Section II and throughout"},{"comment":"The scheme relies on shared randomness among clients that is unknown to the federator and is said to be instantiated by a one-time use of a trusted random number generator. This is a system assumption that should be listed among the model assumptions in Section II, since it effectively introduces a trusted setup.","section":"Section IV, Step 1"}],"recommendation":"major_revision","confidential_remarks":"The paper is well motivated and the empirical NNM gains are clear, but the current version is essentially a protocol sketch: the main theorem is unproved and the central PIR-from-linear-combinations extension is missing. These are not presentation issues; they are load-bearing for every privacy and robustness claim. If the authors can supply complete proofs, a precise PIR construction (or a rigorous reduction), and an end-to-end simulation of at least a small instance of the protocol, the paper could become a solid contribution. As it stands, I would not recommend acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nYou should know about this paper because it is the first to compose nearest-neighbor mixing (NNM) with information-theoretic private aggregation for Byzantine-resilient federated learning under heterogeneity. That composition is genuinely new, and the protocol architecture is plausible: verifiable secret sharing, private distance computation, PIR to hide neighbor sets, re-encoding, and then robust aggregation. The communication cost analysis is careful, and the experiments do show NNM improves robustness across attacks and on LLM fine-tuning.\n\nThe soft spots are significant. Theorem 1, which contains the main privacy and robustness claims, is stated without proof; the paper says the proofs will be in an extended version. That is a real problem for a submission. Step 5 of the protocol, the 'private sum retrieval,' is load-bearing: it relies on modifying the coded PIR scheme of Tajeddine et al. to return linear combinations of files while preserving collusion resistance, Byzantine resilience, and information-theoretic privacy. The paper says 'we omit the details of the PIR scheme' and gives no theorem for this extension. If that modification does not exist or leaks partial sums, the entire privacy mechanism collapses. The experiments do not help here because they simulate only the robust aggregation part, not the secret sharing or PIR.\n\nSo the central claims currently lack support. That said, the paper is honest about its gaps—it flags the omitted proof and the omitted PIR details—and the high-level design is coherent. It is not a confused paper; it is an incomplete one.\n\nWho is this for? Researchers working on private and robust FL will find the architecture interesting and may want to see the proofs when they appear. As it stands, I would not cite it for its main theorems, but I would send it to a serious referee. The right outcome is major revision: the authors should supply the full proof of Theorem 1, a complete description or reference for the linear-combination PIR, and ideally an end-to-end implementation. If those are provided, this could become a solid contribution.\n\nMy recommendation: accept for peer review, with the clear expectation that the missing proofs and PIR details must be supplied before publication.","headline":"First attempt to compose NNM with information-theoretic private aggregation, but the central theorem is unproven and the key PIR step is unspecified; treat as a promising design proposal rather than a proven scheme.","tokens_in":13245,"tokens_out":2447,"would_cite":false,"duration_ms":25954,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A protocol that makes Byzantine-resilient federated learning information-theoretically private on heterogeneous data.","keywords":["federated learning","Byzantine resilience","information-theoretic privacy","nearest neighbor mixing","secure aggregation","private information retrieval","zero-order optimization","data heterogeneity"],"falsifier":"Instantiate the modified PIR for a small system, say $n=3$, $b=1$, $z=1$, and check whether the federator's queries let it distinguish between two different nearest-neighbor sets of size $2$; if any query transcript or the decoded sum reveals which clients were included beyond the sum itself, the claimed information-theoretic privacy fails. Conversely, a complete proof of the linear-combination PIR extension with collusion and Byzantine resistance would settle the claim.","tokens_in":12274,"feed_emoji":"🔒","tokens_out":6310,"duration_ms":59794,"temperature":0.7,"pith_summary":"This paper tries to establish that the two main obstacles to private Byzantine-resilient federated learning—data heterogeneity and information-theoretic privacy—can be handled simultaneously. The authors propose a multi-stage protocol that composes nearest neighbor mixing (NNM) preprocessing with robust aggregation such as Krum or Multi-Krum, while hiding individual gradients and neighbor sets from both the federator and colluding clients. The payoff is a single scheme that achieves information-theoretic privacy, Byzantine resilience under data heterogeneity, and communication costs made practical by zero-order gradient estimation. If the construction holds, it would be the first end-to-end private and robust aggregation method that does not degrade on heterogeneous data.","feed_headline":"Private Byzantine-safe FL now works on skewed client data","feed_subtitle":"Secret sharing plus private information retrieval keeps nearest-neighbor mixing private under attacks.","key_machinery":"The central object is the NNM preprocessing step, which replaces each client's gradient by the sum of its $n-b$ nearest neighbors before a distance-based robust aggregation rule is applied. The protocol's machinery is a co-design of (i) information-theoretic verifiable secret sharing [29] to distribute gradients among clients, (ii) shared-randomness padded shares and Reed-Solomon decoding to let the federator compute pairwise distances without seeing gradients, (iii) a symmetric private information retrieval scheme adapted from coded PIR [41] to retrieve a nearest-neighbor sum without revealing the neighbor set, and (iv) re-encoding of the retrieved mixtures so that clients cannot infer other clients' neighbor sets. The whole pipeline turns NNM into an operation that can be evaluated on secret-shared data, which is what makes Krum and Multi-Krum privately usable under heterogeneity.","core_discovery":"The paper's central claim is that the composition of NNM with any distance-based robust aggregation rule can be run inside a privacy-preserving protocol with information-theoretic guarantees. Concretely, Theorem 1 states that for $n > \\max\\{3b, 2(z+b)\\}$ clients, with at most $b$ Byzantine and $z$ colluding clients, the protocol satisfies the privacy conditions of Definitions 3 and 4, is corruption-resilient against $b$ Byzantine clients, and achieves $(b, \\frac{8b}{n-b}(\\kappa+1))$-robustness whenever the underlying rule is $(b, \\kappa)$-robust. The method works by verifiable secret sharing of gradients, private pairwise distance computation, a modified symmetric private information retrieval step that lets the federator recover sums of nearest-neighbor gradients without learning which clients were summed, re-encoding of mixtures, and a final robust aggregation on the shares. The authors report that on MNIST under several attacks and on SST-2 fine-tuning with RoBERTa-large, NNM improves accuracy over prior private schemes, and zero-order estimation slashes communication cost.","pith_inferences":["If the missing PIR-extension proof is supplied, the same co-design template—secret sharing, padded distance computation, and private sum retrieval—could be applied to other preprocessing steps that require the federator to learn only a selected sum, not the selection itself.","The zero-order results hint that the communication bottleneck of secure aggregation can be broken without hurting Byzantine robustness, but the privacy-utility trade-off of zero-order estimates under adaptive Byzantine attacks is not analyzed and is a natural next question.","The protocol relies on shared randomness between clients that is unknown to the federator; an interactive setup could remove this assumption, and the authors themselves flag this as out of scope.","The paper's allowance of distance leakage suggests a general principle: leaking low-sensitivity statistics such as pairwise distances may be the price for information-theoretic Byzantine resilience, and future work could characterize which statistics are safe to leak."],"forward_implications":["For any number of clients $n > \\max\\{3b, 2(z+b)\\}$, the protocol satisfies the privacy guarantees of Definitions 3 and 4 and remains robust against $b$ Byzantine clients, so NNM-based heterogeneous federated learning can be run with information-theoretic privacy.","When built on a $(b, \\kappa)$-robust distance-based aggregation rule such as Krum, the composition attains $(b, \\frac{8b}{n-b}(\\kappa+1))$-robustness, extending NNM's optimality guarantees to the private setting.","Per-user communication is $O(d n^2 + n^2)$ and federator communication is $O(d n^2 + n^3)$; coupling this with zero-order gradient estimation reduces the cost by large factors, pushing private aggregation toward practical LLM fine-tuning.","Numerical experiments show the protocol outperforms prior private Byzantine-resilient schemes (BREA, ByzSecAgg) on heterogeneous MNIST under ALIE, FOE, Sign Flipping, and Label Flipping attacks, and reaches state-of-the-art SST-2 accuracy under ALIE.","The privacy conditions can be relaxed from conditioning on the set of honest clients $C^*$ by adding one more private-sum-retrieval round, as the paper notes in Section IV, step 8."],"supporting_citations":[{"why":"Supplies the NNM preprocessing and the theoretical result that NNM makes robust aggregation optimal under heterogeneity, which the protocol makes private.","marker":"[33]"},{"why":"Provides the coded PIR scheme that the protocol modifies to retrieve sums of nearest-neighbor gradients; this adaptation is the load-bearing, unproven step.","marker":"[41]"},{"why":"Supplies the information-theoretic verifiable secret sharing used to share gradients and verify corrupt clients, enabling the protocol's privacy and Byzantine resilience.","marker":"[29]"},{"why":"Defines Krum and Multi-Krum, the robust aggregation rules that the protocol composes with NNM and evaluates.","marker":"[13]"},{"why":"Provides BREA, the prior private Byzantine-resilient scheme whose leakage model and robustness the paper compares against and extends.","marker":"[20]"},{"why":"Provides ByzSecAgg, another cryptographic private aggregation baseline that leaks pairwise distances and is outperformed in heterogeneous settings.","marker":"[23]"},{"why":"Establishes the first end-to-end information-theoretic private and robust FL protocol, which this paper builds on for the ITVSS and robustness framework.","marker":"[27]"},{"why":"Supplies the zero-order robust aggregation approach that the paper uses to reduce communication cost and demonstrates on LLM fine-tuning.","marker":"[35]"}],"fun_headline_variants":["Skewed data no longer blocks private robust FL","Heterogeneous FL: private and Byzantine-resilient","Secret sharing + PIR tame non-IID federated learning","Byzantine-resilient private aggregation for non-IID FL","Info-theoretic privacy and Byzantine safety for skewed data"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The protocol assumes that the coded private-information-retrieval scheme cited as [41] can be extended to return linear combinations of files—specifically the sum of a client's nearest-neighbor gradients—while still resisting collusion, Byzantine behavior, and information-theoretic leakage, and the paper provides no proof for this extension.","fun_headline_variants_meta":{"raw":{"variants":["Skewed data no longer blocks private robust FL","Heterogeneous FL: private and Byzantine-resilient","Secret sharing + PIR tame non-IID federated learning","Byzantine-resilient private aggregation for non-IID FL","Info-theoretic privacy and Byzantine safety for skewed data"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001376,"raw_usage":{"total_tokens":5584,"prompt_tokens":964,"completion_tokens":4620,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":580,"completion_tokens_details":{"reasoning_tokens":4538}},"tokens_in":580,"tokens_out":4620,"duration_ms":39116,"temperature":1.0,"reasoning_tokens":4538,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:39:37.351749+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Instantiate the modified PIR for a small system, say $n=3$, $b=1$, $z=1$, and check whether the federator's queries let it distinguish between two different nearest-neighbor sets of size $2$; if any query transcript or the decoded sum reveals which clients were included beyond the sum itself, the claimed information-theoretic privacy fails. Conversely, a complete proof of the linear-combination PIR extension with collusion and Byzantine resistance would settle the claim.","supporting_citations":[{"cited_title":"Fixing by mixing: A recipe for optimal byzantine ml under heterogeneity,","cited_arxiv_id":null,"evidence_quote":"Supplies the NNM preprocessing and the theoretical result that NNM makes robust aggregation optimal under heterogeneity, which the protocol makes private."},{"cited_title":"Private information retrieval from coded storage systems with colluding, byzantine, and unresponsive servers,","cited_arxiv_id":null,"evidence_quote":"Provides the coded PIR scheme that the protocol modifies to retrieve sums of nearest-neighbor gradients; this adaptation is the load-bearing, unproven step."},{"cited_title":"Completeness theorems for non-cryptographic fault-tolerant distributed computation,","cited_arxiv_id":null,"evidence_quote":"Supplies the information-theoretic verifiable secret sharing used to share gradients and verify corrupt clients, enabling the protocol's privacy and Byzantine resilience."},{"cited_title":"Byzantine-resilient secure fed- erated learning,","cited_arxiv_id":null,"evidence_quote":"Provides BREA, the prior private Byzantine-resilient scheme whose leakage model and robustness the paper compares against and extends."},{"cited_title":"ByzSecAgg: A Byzantine-Resistant Secure Aggregation Scheme for Federated Learning Based on Coded Computing and Vector Commitment","cited_arxiv_id":"2302.09913","evidence_quote":"Provides ByzSecAgg, another cryptographic private aggregation baseline that leaks pairwise distances and is outperformed in heterogeneous settings."},{"cited_title":"Byzantine-resilient secure aggregation for federated learning without privacy compromises,","cited_arxiv_id":null,"evidence_quote":"Establishes the first end-to-end information-theoretic private and robust FL protocol, which this paper builds on for the ITVSS and robustness framework."},{"cited_title":"Communication-Efficient Byzantine-Resilient Federated Zero-Order Optimization","cited_arxiv_id":"2406.14362","evidence_quote":"Supplies the zero-order robust aggregation approach that the paper uses to reduce communication cost and demonstrates on LLM fine-tuning."}],"review_version":1}