{"id":"83155c32-48b6-4e26-b40b-870175bc803b","arxiv_id":"2511.18887","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Hi-SAFE privately computes the signSGD majority vote using a Fermat-based indicator polynomial evaluated with Beaver triples, and uses subgrouping to keep per-user cost independent of n.","lead":"This paper describes a cryptographic protocol that lets federated-learning clients submit one-bit gradient signs and still lets a server compute the private majority vote without seeing individual signs. It then divides clients into subgroups so the per-client overhead stays bounded as the network grows.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Communication-cost model is internally inconsistent with the protocol and Appendix A, undermining the claimed 94% per-user reduction.","rationale":"The reader's weakest assumption concerns the convergence theorem's reliance on an unproven q>1/2 supposition. That is a genuine weakness, but the theorem is an auxiliary theoretical analysis; the paper's headline contribution is communication efficiency. The cost model is the direct evidence for that headline, and it is internally inconsistent with the protocol's own worked example. The appendix is authoritative for the protocol's execution, so if the table values disagree, the claimed reductions are not reproducible. Even if the convergence assumption were fixed, the communication claim would remain unsupported. Hence I identify the cost model as the most load-bearing concern. The core Fermat-polynomial construction appears correct, and the hierarchical idea is reasonable, so a conditional revision (fix the cost model and reconcile with the appendix) is appropriate. The reader's rationale already flags the cost model, though it was not the selected weakest assumption; hence partial agreement.","tokens_in":22919,"tokens_out":15588,"duration_ms":144572,"concrete_test":"Implement Algorithm 1 exactly as written for a single subgroup of size n1=3 (field F5, F(x)=2x^3+4x) and for n1=4, recording the number of Beaver triples consumed and the number of field elements each user transmits and receives. Compare with Table VIII (R=4 for n1=3, R=6 for n1=4) and with the Appendix A transcript (which uses R=2). Also recompute Cu for the n=24 optimal subgroup (ℓ=8, n1=3) using the measured counts, including the final share and broadcast traffic. If the measured R or per-user bit count differs from the table, the 94% reduction must be re-derived.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The headline quantitative claims rest on the cost model in Sec. V-C, which defines Cu = R·⌈log p1⌉ with R the number of secure multiplications. But R is never derived and the values in Tables VII–IX are inconsistent with the protocol. For n1=3, the worked example in Appendix A evaluates F(x)=2x^3+4x using exactly two Beaver triples (for x^2 and x^3), i.e., R=2. Table VIII lists R=4 for n1=3; for n1=4 the polynomial has degree 4 (Table III), requiring at most 3 multiplications, yet Table VIII lists R=6. Moreover, each multiplication in Algorithm 1 requires each user to send two masked values to the server (Step 4) and receive two broadcast values, and the user additionally sends its final share Enc(x_i) (Step 7 of Alg. 2). The cost model counts only R field elements per user, omitting the factor-of-two in both directions, the downlink, the final share, and all offline Beaver-triple generation. Because the 94% per-user and 52% total communication reductions are computed from these R values, they are not reproducible. If the appendix is correct, the true per-user uplink for n1=3 is (2·2+1)=5 field elements (15 bits with p1=5), not 12 bits; the corrected percentages may change, and the claimed constant ≤6 multiplications per user may also be off by a constant factor. This directly affects the central claim of communication efficiency.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Hi-SAFE, a secure aggregation framework for sign-based federated learning (SIGNSGD-MV). It constructs a majority-vote polynomial over a finite field using Fermat's Little Theorem, evaluates it securely with Beaver triples under additive secret sharing, and introduces a hierarchical subgrouping scheme intended to bound per-user communication and multiplicative depth. The flat (non-subgrouped) protocol is claimed to reproduce standard SIGNSGD-MV while revealing only the final majority vote. The hierarchical variant aggregates subgroup majority votes, and the paper provides a convergence theorem under a per-subgroup success-probability assumption, a simulation-based security theorem, and experiments on MNIST, FMNIST, and CIFAR-10 reporting large communication reductions.","tokens_in":23258,"tokens_out":7011,"duration_ms":63697,"significance":"If the claims held, the paper would be a useful contribution: the Fermat-based majority polynomial is an elegant construction, Lemma 1 is correct, and the flat secure-evaluation protocol is a sensible application of Beaver triples to sign aggregation. The paper also provides a concrete worked example (Appendix A), an explicit conditional convergence theorem, and a security proof with a stated leakage model. However, the main advertised advances—hierarchical equivalence to flat SIGNSGD-MV, constant bounded communication, and 'only final majority vote' privacy—are weakened by internal inconsistencies in the aggregation definition, the communication-cost accounting, and the privacy leakage. The core polynomial idea is sound, but the hierarchical and quantitative claims need substantial rework before the paper is publishable.","major_comments":[{"comment":"The hierarchical aggregation computes sign(Σ_j sign(Σ_i x_{i,j})), i.e., a majority of subgroup majorities. This is not equal to the flat majority sign(Σ_i x_i) in general. For example, with 3 subgroups of size 3 having votes (++-), (++-), (---), the hierarchical result is +1 while the flat majority is -1. The contribution bullet in §I-A and §III-A claim equivalence to standard SIGNSGD-MV; that equivalence holds only in the flat (ℓ=1) case. Section V compares hierarchical results with flat as if preserving the same aggregation rule. Please either remove the equivalence claim and present hierarchical majority as a distinct rule, or prove conditions under which it coincides with flat majority and align the experiments and claims.","section":"§III-D, Eq. (8)"},{"comment":"R, the number of secure multiplications, is never derived and is inconsistent with the protocol. Appendix A evaluates F(x)=2x^3+4x with exactly two Beaver multiplications (for x^2 and x^3), i.e., R=2, yet Tables VII and VIII list R=4 for n1=3. For n1=4, deg(F)=4 requires at most three multiplications, but Table VIII lists R=6. Moreover, Algorithm 1 Step 4 requires each user to send two masked field elements per multiplication, and Algorithm 2 Step 7 requires an additional final share; the cost model Cu=R⌈log p1⌉ omits this factor of two, the downlink, the final share, and all offline Beaver-triple generation. The headline reductions of 94% per-user and 52% total communication are computed from these R values and are not reproducible from the manuscript. Please re-derive R, include all online messages (and state offline assumptions), and recompute the communication comparisons.","section":"§V-C, Tables VII–IX; Appendix A"},{"comment":"The abstract and §III-C state that the protocol reveals only the final majority vote, but Algorithm 3 Step 9 reconstructs each subgroup majority F(x_j) and Theorem 2 explicitly lists the leakage {s_1,...,s_ℓ,s}. This is a weaker privacy guarantee and contradicts the stated contribution. If subgroup-level leakage is an accepted part of the model, the privacy claims and the 'only final majority vote' bullet must be revised accordingly; otherwise an additional secure inter-subgroup aggregation step is needed to hide subgroup majorities.","section":"§IV-B, Theorem 2; §III-C"},{"comment":"The theorem assumes each subgroup majority is correct with probability q>1/2, independently across subgroups, but this condition is not derived from Assumptions 3–4. For small subgroups (n1=3 or 4) near convergence, per-user sign accuracy can fall below 1/2, so q>1/2 may fail and the e^{-c2ℓ} bound in Eq. (14) does not control the global error. The convergence guarantee for the hierarchical protocol is therefore conditional on an unverified property of the data/noise distribution. Please provide an analytic or empirical justification of q>1/2 in the regimes used in Section V, or state explicitly that convergence is conditional on this additional assumption.","section":"§IV-A, Theorem 1; Appendix B"}],"minor_comments":[{"comment":"The notation v_k, δ^k_{k-v_k}, and ϵ^k_{v_k} is not defined carefully, and the relationship between the loop index k and the Beaver-triple index r is unclear. Please clarify with a consistent index convention.","section":"§III-B2, Eq. (2)"},{"comment":"In subround 1 of Appendix A, only User 1 computes and broadcasts (x−a1)(x−b1), whereas Algorithm 1 Step 4 has each user send masked differences to the server. This inconsistency should be resolved by specifying whether the product is public or computed by all users.","section":"Appendix A vs. Algorithm 1"},{"comment":"The table headers list both ⌈log p1⌉ and ⌈log p1 −1⌉, but the definitions in §V-C mention only ⌈log p1⌉. The values in the 'R' column do not follow from any stated formula or from the polynomial degrees. Add a precise definition of R and recompute the entries.","section":"Tables VII–IX"},{"comment":"Reference [42] is cited as 'J. Smith, Applications of Fermat’s Little Theorem in Cryptography, Journal of Theoretical Cryptography' but has no volume, page, or standard venue information. Please replace it with an established textbook or article on finite-field arithmetic and Fermat's Little Theorem.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The polynomial construction is correct and the flat protocol is a reasonable secure-evaluation scheme, but the paper's central hierarchical claims are compromised: Eq. (8) computes a different aggregation rule than flat SIGNSGD-MV, and the communication tables are inconsistent with the protocol and the worked example. The privacy claim also overstates what is proven. These are load-bearing issues, so I recommend major revision rather than rejection, as the core idea can be salvaged with a corrected problem statement, honest leakage model, and recomputed communication numbers."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the Fermat-based majority-vote polynomial is a real trick, and the flat secure-evaluation protocol is a clean, correct application of Beaver triples. That part should survive peer review. The problems are in the hierarchical extension and the communication-cost accounting.\n\nWhat's genuinely new: representing the sign majority vote as a low-degree polynomial over F_p and evaluating it with additive secret sharing is a neat way to give sign-based FL a cryptographic privacy layer. Lemma 1 is correct, and the flat protocol in Algorithms 1–2 does compute exactly the SIGNSGD-MV result. Credit where due: that is a solid, useful construction.\n\nSoft spots, in rough order of importance:\n\n1. The hierarchical protocol in Eq. (8) computes sign of the sum of subgroup majority signs. That's majority-of-majorities, not the global majority vote. The abstract and contribution bullets claim the secure evaluation is 'equivalent to the standard SIGNSGD-MV,' which is only true for the non-subgrouped case. The experiments compare against the flat method, so accuracy preservation is an empirical claim about a different aggregation rule, not a consequence of equivalence.\n\n2. The communication-cost model is internally inconsistent. Appendix A, for n1=3, evaluates F(x)=2x^3+4x with exactly two Beaver-triple multiplications (R=2). Table VIII lists R=4 for n1=3. For n1=4 the polynomial has degree 4 and needs at most 3 multiplications, yet Table VIII lists R=6. Moreover, each secure multiplication requires each user to send two masked values to the server and receive two broadcast values, plus the final share. The cost model counts only R field elements per user, so the claimed 94% per-user and 52% total reductions are not reproducible from the protocol as written. The appendix example alone gives a per-user uplink of 2·2+1=5 field elements for n1=3, not the 4 that the table implies.\n\n3. Theorem 1 assumes each subgroup's majority is correct with probability q>1/2, stated as a supposition rather than derived from the noise assumptions. For small subgroups near convergence, per-user sign accuracy can fall below 1/2, so the exponentially suppressed global error term e^{-c2ℓ} is not guaranteed. The bound may still be true, but as written it is conditional on an unverified premise.\n\nThe security analysis is a standard simulation argument and looks plausible, given the explicit leakage of subgroup majority votes. The experiments are fine as sanity checks but do not validate the cost model.\n\nBottom line: the core construction deserves a serious referee and could become a publishable contribution after major revision. The authors need to fix the communication-cost accounting, state clearly that the hierarchical variant is a different aggregation rule, and either prove q>1/2 or present the convergence result as conditional. I would send it to peer review, but with a strong request for these revisions.","headline":"Sound core construction, but the headline efficiency numbers are not reproducible from the protocol as written, and the hierarchical variant silently changes the aggregation semantics.","tokens_in":23726,"tokens_out":4473,"would_cite":false,"duration_ms":39455,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Majority voting in 1-bit federated learning can be done as a low-degree polynomial that hides every sign.","keywords":["federated learning","secure aggregation","sign SGD","majority vote","communication efficiency","privacy-preserving machine learning","finite field polynomial","hierarchical subgrouping"],"falsifier":"For a fixed n and a chosen tie-break rule, enumerate every possible coordinate sum in {-n,-n+2,...,n}, evaluate the proposed polynomial over F_p with p the smallest prime greater than n, and compare each output to the true majority sign; any mismatch falsifies the claimed exact equivalence. The privacy claim could be tested by attempting to recover a single user's sign from a full transcript plus the final vote, which would contradict the stated simulator-based security guarantee.","tokens_in":22806,"feed_emoji":"🔒","tokens_out":5572,"duration_ms":61701,"temperature":0.7,"pith_summary":"Hi-SAFE claims that the majority vote of 1-bit gradient signs in federated learning can be written exactly as a low-degree polynomial over a finite prime field, making it possible to run SIGNSGD-MV under secure aggregation without exposing individual signs. The polynomial uses a classical number-theoretic indicator identity so that each possible sum selects exactly one term, reproducing the standard majority vote exactly. The paper then partitions users into subgroups so that each secure polynomial stays small, bounding per-user secure multiplications at six and latency at about two subrounds regardless of the total number of users, and cutting per-user communication by over 94 percent for n>=24. A convergence theorem shows the hierarchical vote's error decays exponentially with the number of subgroups when each subgroup's majority is correct with probability above 1/2, and a security theorem shows a semi-honest server learns only subgroup and global majority signs.","feed_headline":"Hides every sign, returns only the majority vote","feed_subtitle":"Splitting clients into small groups caps secure multiplications at six and cuts per-user traffic by over 94 percent.","key_machinery":"The load-bearing object is the majority-vote polynomial F(x) = sum over m of sign(m)*(1-(x-m)^(p-1)) over F_p, where p is the smallest prime above n; the exponent p-1 maps x=m to 0 and every other field element to 1, so exactly one term survives. Its bounded degree lets the protocol evaluate the vote through correlated multiplication triples with additive secret sharing. In the hierarchical variant, the same polynomial is applied inside subgroups of size n1 and then subgroup votes are combined, bounding the degree, prime size, and per-user cost independently of the total number of users.","core_discovery":"The central claim is that the majority vote of n sign values can be represented exactly, over the prime field F_p with p>n, as a degree-(p-1) polynomial whose terms are indicator functions: each term vanishes for every sum except the one matching its target, so the polynomial returns the sign of the true sum. This is established in Lemma 1, and it means the nonlinear majority-vote operation of SIGNSGD-MV becomes a polynomial that can be evaluated by a sequence of field additions and multiplications. The paper then shows that evaluating this polynomial with additive secret sharing and correlated random multiplication triples reveals only the final vote, and that partitioning users into subgro","pith_inferences":["A natural extension not pursued by the paper is applying the same finite-field indicator construction to other finite-input aggregation rules, such as top-k selection or thresholded sums, whenever the output depends only on symbol counts.","The privacy-efficiency trade-off is explicitly tunable: shrinking subgroup size n1 cuts communication but increases the residual-leakage probability (2^{-(n1-1)})^d, so a deployment could choose n1 according to its threat tolerance.","Because the reported online secure-aggregation cost is under 0.03 seconds per round, the protocol could plausibly be combined with additional privacy mechanisms such as local differential privacy for stronger guarantees, though the paper does not test that combination.","The formal guarantee is relative to the leakage of subgroup majority votes; an adversary would likely use those aggregates to narrow down individual signs, so the practical privacy gain over masking depends on whether such aggregate-level inference is acceptable in the target application."],"forward_implications":["Users send only one bit per parameter, yet the server can compute the global sign vote securely, removing the need for ciphertext-heavy homomorphic encryption in sign-based federated learning.","The per-user secure-multiplication count stays at or below six for the optimal subgroup sizes, independent of total user count, making the protocol suitable for bandwidth- and compute-constrained IoT devices.","Per-user communication drops by more than 94 percent for n>=24, and total communication drops by up to 52 percent at n=24, compared with flat secure evaluation.","Reported experiments on MNIST, FMNIST, and CIFAR-10, including non-IID splits, show model accuracy comparable to plain SIGNSGD-MV.","Under a semi-honest server, the protocol discloses subgroup majority votes and the final majority vote, but not individual sign gradients or intermediate arithmetic values."],"fun_headline_variants":["Hide every sign, show only the vote","Private signs, public majority vote","Secure sign aggregation with low cost","Majority vote without sign leakage"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The convergence proof assumes every subgroup's majority vote is correct with probability strictly above 1/2 and that these events are independent across subgroups; with very small subgroups near convergence, per-user sign accuracy can fall below 1/2, which would break the exponential error term.","fun_headline_variants_meta":{"raw":{"variants":["Hide every sign, show only the vote","Private signs, public majority vote","Secure sign aggregation with low cost","Majority vote without sign leakage"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000149,"raw_usage":{"total_tokens":1008,"prompt_tokens":699,"completion_tokens":309,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":443,"completion_tokens_details":{"reasoning_tokens":269}},"tokens_in":443,"tokens_out":309,"duration_ms":4395,"temperature":1.0,"reasoning_tokens":269,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T20:37:19.724144+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a fixed n and a chosen tie-break rule, enumerate every possible coordinate sum in {-n,-n+2,...,n}, evaluate the proposed polynomial over F_p with p the smallest prime greater than n, and compare each output to the true majority sign; any mismatch falsifies the claimed exact equivalence. The privacy claim could be tested by attempting to recover a single user's sign from a full transcript plus the final vote, which would contradict the stated simulator-based security guarantee.","supporting_citations":[],"review_version":1}