{"id":"9a9f4b38-647a-4b1a-a9a9-72ecef0f9402","arxiv_id":"2607.20890","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A secure aggregation protocol for sign-based federated learning computes the majority vote in one round with linear offline cost, but the claimed degree-halving simplification breaks at zero inputs and for inverse terms.","lead":"A federated-learning paper proposes a privacy-preserving aggregation protocol that lets many devices compute the majority of their one-bit gradient signs without revealing individual votes. It claims large communication and latency savings plus dropout and adversary resilience, but a core algebraic simplification fails for zero inputs and for negative exponents.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The inverse-form exponent reduction is invalid at x=0 and Algorithm 6 cannot evaluate negative powers, so the core MV polynomial computation fails in exactly the tie case the protocol must handle.","rationale":"The paper's central claim is that Algorithm 7 securely aggregates sign gradients by evaluating the MV polynomial F(x) with Method B in one round, with inverse-form reduction halving degree. For that claim to hold, the reduction in Eq. (5) must be a valid polynomial identity over F_p, and Algorithm 6 must realize it. Both fail. The identity x^j ≡ x^{-(p-1-j)} is only valid away from 0 and cannot be extended by continuity because division by zero is undefined. x=0 is exactly the tie input for even n; Section III-C makes tie-breaking a first-class part of the protocol. The reader's weakest assumption identifies this precisely. Algorithm 6's correctness proof (Lemma 1/Theorem 2) expands only nonnegative powers; it lacks any inverse computation. Thus as written the protocol either aborts or returns a value that does not match F(0), making the claimed end-to-end correctness false. The efficiency numbers (up to 99.5% communication reduction, Table IV and Fig. 2) depend on N′=(p-1)/2; without the invalid reduction, degree remains p-1 and these numbers are not derived. This is a load-bearing flaw. A corrected protocol could possibly avoid inverse reduction and still use single-mask binomial evaluation, but the paper's claimed contribution and experiments do not establish that. The check — evaluating the reduced form at x=0, or implementing Algorithm 6 for n=4/p=5 — would settle the issue immediately. No change to the reader's REJECT verdict is needed.","tokens_in":21113,"tokens_out":5189,"duration_ms":49681,"concrete_test":"Implement Algorithm 6 exactly on F_5 with n=4 using the inverse-reduced polynomial produced by Algorithm 4 (e.g., replace x^4 by x^{-1}) and run the online phase on inputs whose true sum is x=0 (two +1 and two -1 signs). The protocol has no procedure for computing [x^{-1}] from the opened x̂ and nonnegative power sharings; if it instead drops the inverse monomial, the reconstructed output differs from the true MV value F(0)=1 (for sign(0)=1) in Table II. A minimal algebraic check: evaluate both sides of Eq. (5) at x=0 for any j>(p-1)/2 — the left is 0, the right is undefined — which alone falsifies Theorem 1's claimed identity over F_p.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section V-A/Theorem 1 rewrites every monomial c_j x^j with j>(p-1)/2 as c_j x^{-(p-1-j)} using x^{p-1}=1. That identity holds only on F_p^×, not at x=0, and negative powers are undefined in F_p. The tie case x=0 is not a corner case: for even n it is the MV output the tie-breaking rule in Section III-C must decide. Method B (Section V-B2, Algorithm 6) does not implement negative exponents anywhere. Its binomial expansion (Eq. 8) is (x̂+a)^k = Σ_r binom(k,r) x̂^r a^{k-r}; this only makes sense for nonnegative integer k. Offline only computes [a^j] for j=0..N′, online only opens x̂=x-a and computes nonnegative powers x̂^r, then forms Σ_r x̂^r [P_r]. A reduced polynomial such as the n=4 example (x+3x^{-1}, or the Table II polynomial with x^4 reduced) cannot be expanded this way; Algorithm 6 would silently omit the inverse term. Moreover Theorem 1's proof says 'trivial for x=0,' but c_j·0^j = 0 ≠ c_j·0^{-e} (undefined). Thus the protocol as written does not compute F(0), and the headline communication/latency reductions, which rely on N′=(p-1)/2, are unsupported. This is a correctness flaw in the central construction, not a stylistic or consensus disagreement.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an information-theoretically secure aggregation framework for signSGD-based federated learning. It represents the majority-vote function as a polynomial over a prime field, applies an 'inverse-form exponent reduction' to lower the polynomial degree to about half, and evaluates the reduced polynomial by one of two single-round secure-multiplication methods: Method A (DN + N-BTE) or Method B (single-mask power sharing). The authors claim end-to-end privacy under an honest-majority assumption, resilience to dropouts and adversarial users via MDS decoding, and large reductions in online communication and latency. The core technical claim is that the inverse-form reduction preserves the majority-vote polynomial; the paper's central protocol is built on this reduction.","tokens_in":21482,"tokens_out":8701,"duration_ms":81714,"significance":"The paper identifies a genuinely useful structural property of MV polynomials — all monomials are powers of a single aggregated value — and the single-mask binomial-expansion approach (Method B) would be elegant and efficient for polynomials with only nonnegative exponents. The honest-majority, information-theoretic framing and the MDS-based robustness discussion in Section VI-A are coherent and could be valuable in a corrected design. However, the inverse-form exponent reduction is load-bearing for every efficiency claim in the abstract, Section V, and Table IV, and it is invalid at x=0 and cannot be evaluated by either proposed method. Since the central protocol as written does not compute the majority vote, the convergence and security theorems do not apply to the executed computation. The contribution, as stated, is not sound.","major_comments":[{"comment":"The identity x^j ≡ x^{-(p-1-j)} is asserted for all x∈F_p, with the proof saying it is 'trivial for x=0'. This is false: Fermat's Little Theorem gives x^{p-1}=1 only on F_p^×, and 0^{-e} is undefined in F_p. The point x=0 is not a corner case for this application because Section III-C defines tie-breaking for x=0 when n is even. Concretely, for n=4, p=5, Table II gives F(x)=x^4+3x^3+x+4, with F(0)=4 (sign(0)=-1); the inverse-form reduction in Section V-A rewrites this as 3x^{-1}+x, which is undefined at 0 (and equals 0 if one substitutes x^{-1}=x^{p-2}), not 4. The reduction therefore does not preserve F(x) on the domain required by the MV problem.","section":"Section V-A, Theorem 1"},{"comment":"Method B evaluates only polynomials with nonnegative exponents. Eq. (8) expands (x̂+a)^k for k∈Z_{\\ge0}; Algorithm 6 precomputes [a^j] and [P_r] for j,r=0..N', opens x̂=x-a, computes public powers x̂^0,...,x̂^{N'}, and forms [F(x)]_t = Σ_{r=0}^{N'} x̂^r[P_r]_t. There is no term anywhere that computes (x̂+a)^{-e} or x^{-e}. Thus for the n=4 reduced polynomial 3x^{-1}+x, the inverse term is silently omitted, because its exponent is not in {0,...,N'} with N'=2. The same holds for Method A in Section V-B1, which only multiplies formal copies x^k for k≥0. Negative exponents cannot be produced by the binomial expansion used.","section":"Section V-B2, Eq. (8), Algorithm 6"},{"comment":"The headline reductions (up to 99.5% online communication, 85.7% latency) and the linear offline complexity O(N') with N'=(p-1)/2 all depend on the inverse-form exponent reduction. Since that reduction is invalid at x=0 and cannot be evaluated by either secure-multiplication method, these claims are unsupported. The protocol as written does not compute the MV polynomial; consequently Theorem 3 and Theorem 4 are proved for a functionality that Algorithm 6 does not actually implement. The paper needs either a negative-exponent secure-evaluation mechanism that also handles x=0 correctly, or a return to the unreduced degree-(p-2) polynomial with a matching evaluation method.","section":"Abstract, Section V, Table IV"}],"minor_comments":[{"comment":"The line '[z]t ← QN l=1 u_l {public value}' mixes a public value with t-sharings; the constant should be explicitly embedded, e.g., as [1]_t or by adding it to one party's share.","section":"Algorithm 5, step 14"},{"comment":"The notation n_t = W^2 is unexplained; W is not defined in the theorem statement, and the relationship between n_t and the active-user count n is unclear. The proof sketch also simply substitutes α=0 into [14] without a self-contained derivation.","section":"Section VI-B, Theorem 3"},{"comment":"The row for the proposed method lists 'Very High' scalability while Method A has exponential offline cost; the table would benefit from distinguishing Method A and Method B, since only Method B achieves the reported linear offline complexity.","section":"Table I"}],"recommendation":"reject","confidential_remarks":"The stress-test concern is correct and lands squarely on the central construction. The inverse-form reduction is not merely an edge-case annoyance: x=0 is the tie case that Section III-C explicitly needs to resolve, and the reduced polynomial with inverse powers cannot be evaluated by the proposed Algorithm 5 or Algorithm 6. I see no local repair that preserves the claimed complexity; either the reduction is abandoned, destroying the main efficiency claims, or a new secure inversion primitive with correct zero handling must be designed. Hence reject."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague — this one has a real problem. The central construction, as written, does not compute the majority-vote polynomial. The inverse-form reduction in Theorem 1 rewrites terms like x^j as x^{-(p-1-j)} using Fermat's little theorem. That identity only holds for x≠0, and negative exponents aren't defined in F_p. The tie case x=0 (which for even n is exactly the case the tie-breaking rule must resolve) is precisely where the reduction fails. Worse, Method B's Algorithm 6 evaluates only nonnegative powers via binomial expansion (x̂+a)^k; nothing in the protocol computes x^{-1} or any negative exponent. The paper's own n=4, p=5 example: F(x)=3x^3+x reduces to x+3x^{-1}, and Algorithm 6 with N'=2 would simply drop the inverse term. The claimed 99.5% communication reduction and 85.7% latency reduction rest on this broken reduction, so those numbers are not supported.\n\nThere is something worth keeping here. The observation that MV polynomials are single-base — all monomials are powers of one aggregated sum — is genuinely nice, and the single-mask power-sharing idea is a sensible way to exploit it. The offline complexity being linear in the degree is a real improvement over exponential subset-mask tables. The MDS-code-based dropout/adversary analysis is standard DN material, accurately applied, and the experiments show the expected robustness gains in FL accuracy. The paper is not a parody; the ingredients are real and the writing is clear.\n\nBut the soft spots are load-bearing. The reduction is invalid at zero, negative powers are not implemented, and the correctness proof (Theorem 2) silently assumes the polynomial has only nonnegative exponents. The convergence analysis is a sketch that substitutes α=0 into Bernstein et al.'s bound; the security proof is a simulation sketch that doesn't handle the input-sharing step. Also, the per-user communication counts ignore the cost of distributing shares of each sign gradient to the other users in the first place — that's an omitted round and per-user cost that would eat into the headline reductions.\n\nWho is this for? A reader interested in applying MPC to sign-based FL would find the single-base observation useful as a building block, but the paper as written is not a usable protocol. It deserves a serious referee because the underlying idea might be repairable — one could, for example, avoid the inverse-form reduction and accept degree p-2 with a different algorithm, or handle x=0 separately. But as it stands, I would not cite it, and I would recommend reject-and-resubmit, not accept. If you send it to review, give the refs the specific zero/negative-exponent issue; it should be resolvable quickly.","headline":"The core reduction breaks at x=0 and Method B cannot evaluate negative powers, so the headline efficiency claims don't follow — but the single-base structural idea is worth salvaging.","tokens_in":21960,"tokens_out":4431,"would_cite":false,"duration_ms":42135,"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 single masked opening suffices to compute the federated majority vote with information-theoretic privacy.","keywords":["information-theoretic security","federated learning","signSGD","majority vote polynomial","secure aggregation","single-round multiplication","dropout resilience","MDS codes"],"falsifier":"Pick n even, say n = 4 with p = 5, where the MV polynomial with tie-break sign(0) = 0 reduces to something containing x^(-1) after inverse-form reduction. Simulate the protocol on a round where two users send +1 and two send -1, so x = 0. The online phase opens x_hat = x - a, and the polynomial evaluation step must handle a negative exponent; when x = 0, x_hat = -a, so the term x^(-1) would require computing (-a)^(-1), which is undefined if a = 0 and invalid at x = 0 even if a ≠ 0. The concrete check is whether the protocol's reconstruction yields the tie-breaking value F(0) or fails to decode","tokens_in":20962,"feed_emoji":"🔒","tokens_out":5657,"duration_ms":108385,"temperature":0.7,"pith_summary":"The paper asks whether sign-based federated learning—where each device sends one bit, the sign of its gradient, and the server takes a majority vote—can be aggregated without revealing any individual sign. It answers yes under an honest-majority assumption, by viewing the majority vote as a polynomial in a single aggregated value and evaluating that polynomial with secure multiparty computation in a single round. The central construction uses one random mask: the devices open only the masked sum, from which the majority vote polynomial is reconstructed on secret-shared coefficients. If correct, this gives information-theoretic privacy (security against unbounded adversaries) rather than computational security, while cutting online communication by up to 99.5% and latency by 85.7% relative to Beaver-triple approaches. The paper also claims that the same MDS-code machinery that opens the masked value lets the server recover dropped users' contributions and correct corrupted shares, so accuracy is preserved even with 35.7% dropouts or 23.9% adversarial shares.","feed_headline":"One masked opening secures majority-vote aggregation","feed_subtitle":"A single random mask hides every device's gradient sign while cutting online communication by up to 99.5%.","key_machinery":"The single-base structure of the majority-vote polynomial, combined with Fermat's Little Theorem. The MV polynomial is univariate in x = sum_i sign(g_i). Method B (Single-Mask Power Sharing) exploits this: for one random mask a, precompute secret-shared powers [a^j] and coefficient-weighted bundles [P_r] = sum_j c_j * binom(j,r) * [a^(j-r)]; in the online round, open only x_hat = x - a, then everyone computes [F(x)] = sum_r x_hat^r [P_r]. The binomial expansion turns one opening into all powers of x. Inverse-form exponent reduction replaces exponents j > (p-1)/2 with -(p-1-j), halving the polynomial degree. MDS-code-based decoding of the single opening is what provides dropout recovery and a","core_discovery":"The paper's central claim is that the majority-vote polynomial F(x) = sum_m sign(m)(1-(x-m)^(p-1)) over F_p — the polynomial whose value at x is the majority sign of n one-bit gradients — can be evaluated securely in a single communication round. The key observation is that every monomial is a power of one base value x = sum_i sign(g_i), rather than a product of distinct inputs. Therefore, instead of generically multiplying many inputs, the protocol masks x once with a random value a and opens only x_hat = x - a; using the binomial expansion (x_hat + a)^j and precomputed secret shares of powers of a, each party computes a share of F(x) locally. The opened value is statistically independent o","pith_inferences":["The same single-mask polynomial evaluation extends beyond majority vote to any univariate function of the aggregated sum x — for example, top-k indicators, ternary thresholds, or clipped means — as long as it can be written as a polynomial over F_p of degree below p. That would give a general recipe for private aggregation of one-bit updates.","If the inverse-form reduction is restricted to inputs where x ≠ 0, the tie case must be handled separately; a testable fix is to split F(x) into a nonzero-domain part plus an explicit tie-breaking constant, so that no negative exponent is ever evaluated at zero.","Choosing a deliberately small privacy threshold t (e.g., n/4 instead of n/2) enlarges the MDS decoding region, trading some collusion resistance for much higher dropout and adversary tolerance — a tunable knob the paper quantifies but does not fully explore in its experiments.","The method could combine with hierarchical or clustered federated learning: if each subgroup's majority vote is a univariate polynomial, the same one-opening trick applies per subgroup, keeping per-subgroup communication constant and making the overhead scale gracefully with system size."],"forward_implications":["Sign-based federated learning can get information-theoretic privacy with a single online field element per user, making secure aggregation practical for lightweight devices.","The protocol reduces online communication by up to 99.5% and latency by up to 85.7% versus Beaver-triple-based secure aggregation, while keeping offline storage linear in the polynomial degree rather than exponential.","Because the opening is MDS-coded, the server can recover the exact majority vote even when users drop out or send corrupted shares, up to the decoding bound 2e + s ≤ n - 2t - 1.","The server learns only the final majority sign; individual gradient signs are statistically hidden from the server and from any coalition of fewer than n/2 users.","The convergence guarantees of signSGD with majority vote are preserved whenever the error-erasure condition holds, because the decoded aggregate equals the benign majority vote."],"fun_headline_variants":["One random mask secures sign-based FL in a single round","Single-round secure majority vote for one-bit gradients","One mask, one round, 99.5% less communication","Secure aggregation that survives dropouts and adversaries","Information-theoretic privacy for lightweight federated learning"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The whole efficiency gain relies on replacing high-degree terms x^j with x^(-(p-1-j)) using x^(p-1) ≡ 1, which holds only for nonzero x; at x = 0 — exactly a tied majority vote — the inverse is undefined, and the paper does not show how Method B evaluates negative powers of the masked value.","fun_headline_variants_meta":{"raw":{"variants":["One random mask secures sign-based FL in a single round","Single-round secure majority vote for one-bit gradients","One mask, one round, 99.5% less communication","Secure aggregation that survives dropouts and adversaries","Information-theoretic privacy for lightweight federated learning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000775,"raw_usage":{"total_tokens":3307,"prompt_tokens":827,"completion_tokens":2480,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":571,"completion_tokens_details":{"reasoning_tokens":2403}},"tokens_in":571,"tokens_out":2480,"duration_ms":19381,"temperature":1.0,"reasoning_tokens":2403,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T09:07:15.639958+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Pick n even, say n = 4 with p = 5, where the MV polynomial with tie-break sign(0) = 0 reduces to something containing x^(-1) after inverse-form reduction. Simulate the protocol on a round where two users send +1 and two send -1, so x = 0. The online phase opens x_hat = x - a, and the polynomial evaluation step must handle a negative exponent; when x = 0, x_hat = -a, so the term x^(-1) would require computing (-a)^(-1), which is undefined if a = 0 and invalid at x = 0 even if a ≠ 0. The concrete check is whether the protocol's reconstruction yields the tie-breaking value F(0) or fails to decode","supporting_citations":[],"review_version":1}