{"id":"d1c850c1-3a0c-451e-bea8-580235f246cf","arxiv_id":"2505.12453","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"SecEmb is a two-server protocol using function secret sharing that privately retrieves and aggregates only sparse item-embedding updates in federated recommender systems, cutting user communication and computation.","lead":"Researchers built SecEmb, a secure training protocol for federated recommender systems that lets devices send only the embedding gradients for the items they actually rated. It uses function secret sharing to hide which items were rated and to cut per-user communication by up to 90x in experiments.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Truncation in PadOrTruncEmb breaks the advertised lossless aggregation for users with m'_u > m'.","rationale":"The reader's weakest_assumption is the server-side full-domain evaluation and path storage cost, which I agree is a real omission from the headline complexity analysis. However, the more load-bearing concern is the lossless property itself: the paper's own Appendix C truncates updates for heavy users, so the protocol is lossless only for users with m'_u <= m'. Since the central contribution is explicitly a lossless secure recommender, this internal inconsistency should be resolved before acceptance. The FSS-based retrieval and aggregation appear sound for the bounded case, and the security model is standard for two non-colluding servers. My verdict therefore remains CONDITIONAL: the authors should either prove or scope the lossless claim (e.g., by bounding the truncation error or switching to a lossless variant), and should report server-side computation and memory as part of the protocol complexity. I found no reason to reject the cryptographic core, and no ad hominem is implied.","tokens_in":27826,"tokens_out":10499,"duration_ms":108826,"concrete_test":"Run one round of SecEmb on ML10M with m'=300 as configured in Appendix I, recording the exact aggregated item-gradient matrix produced by Algorithm 3. Separately compute the true aggregated gradient from all users' full local updates without truncation, and compute the relative L2 error between the two; repeat with m'=1000 and compare. If the error is non-zero and grows as m' shrinks, the lossless claim is false and the paper must state the accuracy trade-off instead. As an additional check, instrument the server peak memory for Yelp (m=93,386, m'=500, 100 users, lambda=128) to test the O(n m' m lambda)-bit storage assumption in Algorithm 3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central lossless claim fails for users whose rating count exceeds the configured m'. Appendix C's Algorithm 2 (PadOrTruncEmb) randomly samples m' rows from the local gradient when m'_u > m', and Algorithm 1 discards the remaining rated-item indices; the server aggregates these truncated updates via Eq. (8). The resulting aggregate is not the sum of all users' full local gradients, so training is not equivalent to the uncompressed secure FedRec. This contradicts Section 1's lossless message compression and Table 11's lossless checkmark. Datasets such as ML10M have a long-tailed rating distribution (Figure 2a), so a non-negligible fraction of users exceed the chosen m'=300; the paper does not quantify the resulting bias. A second, related efficiency gap is that the headline complexity in Table 1 covers only user-side cost. Algorithm 3 requires each server to evaluate every point function at all j in I (O(m' m d) per user) and to store path values (t_{u,i,j}, s_{u,i,j}) for every user, item, and catalog element, an O(n m' m lambda)-bit server memory footprint absent from the complexity analysis.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes SecEmb, a two-server protocol for federated recommender training that (i) privately retrieves only the embeddings of items a user has rated, using function secret sharing (FSS) point functions, and (ii) securely aggregates the sparse embedding gradients while hiding rated-item indices and update values from the server. The authors claim the protocol is lossless, with per-user upload O(m'(λ log m + bd) + |θ|b) and download O(m'bd + |θ|b), and report up to 90x communication and 70x computation savings over a two-server additive-secret-sharing secure FedRec, plus utility advantages over quantization and low-rank compression baselines. The empirical study covers five datasets and four recommender models, and the appendices contain formal security proofs and additional efficiency comparisons.","tokens_in":28037,"tokens_out":6649,"duration_ms":66411,"significance":"If the correctness and complexity claims held in full, SecEmb would be a practically meaningful contribution: it combines FSS-based private retrieval with row-wise sparse aggregation so that the item-catalog size is removed from the user's per-round payload, and the code is publicly available. The security argument follows the standard two-server FSS hybrid proof with additive secret sharing, and the user-side communication formulas are internally consistent. The empirical evaluation is extensive and includes an ablation study demonstrating the value of the path-sharing optimization. The main claims, however, are currently overstated: the protocol is not lossless as written, and the reported complexity is incomplete on the server side, so the paper needs substantive revision before the contribution can be accepted as stated.","major_comments":[{"comment":"The paper advertises SecEmb as lossless (Section 1, Table 11) and states that padding/truncation keeps the 'entire sparse update matrix' hidden (§4.2.3). However, Algorithm 2 (PadOrTruncEmb) randomly samples m' rows when the user's actual rating count m'_u exceeds m', and Algorithm 3 then generates FSS keys only for these m' rows. Consequently, the aggregate computed in Eq. (8) is a sum over truncated, randomly subsampled per-user gradients, not a sum of the full local gradients. This biases the aggregated model update, so training is not equivalent to the uncompressed secure FedRec, and the 'Lossless' checkmark for SecEmb in Table 11 is inaccurate. Since Figure 2(a) shows a long-tailed rating distribution and the chosen m' values in Appendix I are 200–500, a non-negligible fraction of users in ML10M, ML25M, and Yelp exceed m'; the paper does not quantify the induced bias or its effect on the reported RMSE values. The authors should either revise the lossless claim and provide a bias/utility analysis of the truncation, or choose m' as a per-dataset maximum and re-derive the communication benefits.","section":"§4.2.3, Appendix C (Algorithms 1–2), Eq. (8), Table 11"},{"comment":"The headline complexity in Table 1 and Section 4.4.1 is explicitly user-side, but the paper's overall efficiency claims (e.g., 'cost independent of item size m for downloads and logarithmic in m for uploads' in Section 6) are presented without the server-side counterpart. In Algorithm 3, each server evaluates FSS.Eval or FSS.ConvertEval for every u in A_t, every i in [m'], and every j in I, i.e., O(n m' m log m · AES) operations per round, and must store the path values (t_{u,i,j}, s_{u,i,j}) for every user, item, and catalog element, an O(n m' m λ)-bit memory footprint. These costs scale linearly or worse in the catalog size m and are absent from the complexity analysis and from the memory/storage evaluation in Appendix K.2, which measures only the user side. The authors should state the server-side complexity and memory explicitly and, when comparing against secure FedRec as an end-to-end system, present the total system cost fairly.","section":"§4.4.1, Table 1, Algorithm 3"}],"minor_comments":[{"comment":"Algorithm 6 assigns the same left-branch values in both the x_i = 0 and x_i = 1 cases; the else branch should select s_R and t_R instead of s_L and t_L. As printed, the pseudocode cannot correctly evaluate the point function, so this typo should be fixed.","section":"Appendix E, Algorithm 6 (FSS.PathEval)"},{"comment":"Algorithm 3 stores the intermediate values as (t^1_{u,i}, s^0_{u,i}, s^1_{u,i}), while FSS.PathGen in Algorithm 7 returns (t^{(n)}_1, s^{(n)}_0, s^{(n)}_1); the superscript/subscript notation should be aligned to avoid ambiguity.","section":"Algorithm 3 vs Algorithm 7"},{"comment":"The phrase 'encode rated item with a point function, giu→fu,i' is garbled notation and should be rewritten for clarity.","section":"§4.2.1, Step 1"},{"comment":"The per-dataset m' values (200, 300, 300, 500, 500) appear only in Appendix I; they should be stated in the main experiments section because they directly determine the reported reduction ratios.","section":"§5.1 and Appendix I"}],"recommendation":"major_revision","confidential_remarks":"The paper is a well-executed systems/crypto hybrid with a clear empirical story, but the central 'lossless' claim is contradicted by the truncation in Appendix C, and the server-side cost is omitted from the complexity analysis. Both issues are fixable in revision rather than fatal. The Algorithm 6 pseudocode typo should also be corrected before publication. I would not reject the paper; the underlying FSS construction and user-side formulas are sound, and the empirical evaluation is thorough."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"SecEmb is a solid application of function secret sharing to a real problem: secure federated recommendation with large catalogs. The path-sharing optimization between private embedding retrieval and update aggregation is a legitimate new idea, and the user-side numbers are good (up to 90x communication savings). The security proof is a standard FSS/ASS hybrid and I don't see an internal contradiction. Code is available, and the ablations are careful. This deserves a serious referee.\n\nThe trouble is the word 'lossless.' The protocol sets a unified m' and truncates users who rate more than m' items (Algorithm 2, Appendix C). The paper's own Figure 2a says nearly 90% of ML10M users rate up to 300 items, so around 10% of users exceed m'=300 and are having their gradients randomly sub-sampled before aggregation. The resulting global model is not the same as the uncompressed secure FedRec, and Table 11's 'Lossless' checkmark is wrong. This is fixable: either set m' to cover the tail, add a separate mechanism for overflow users, or drop the claim and quantify the bias. As written, the central claim is overstated.\n\nSecond, the complexity story is incomplete. Table 1 only counts user-side communication and computation. Algorithm 3 requires each server to evaluate every FSS point function over the full item domain and store intermediate path values (t_{u,i,j}, s_{u,i,j}) for every user, every encoded item, and every catalog item. That is O(n m' m) storage per server and O(m' m d) computation per server per user. For Yelp-scale catalogs this could swamp the user-side savings. The paper includes an empirical server computation table, but no complexity formula or memory bound. A reader cannot tell whether the server can keep up.\n\nThe security model (two non-colluding servers) is standard and stated up front; I don't count it as a flaw.\n\nWho would benefit: anyone designing secure aggregation for sparse embeddings, or working on communication-efficient federated learning. Even with the lossless issue, the path-sharing idea is worth citing. I would send this to peer review, but the authors should be pushed to either prove losslessness for a defined user population or re-label the protocol, and to provide server-side complexity and memory analysis.","headline":"A genuinely clever FSS-based protocol for secure federated recommendation with strong user-side savings, but the 'lossless' claim is broken for heavy users and the server-side cost is not analyzed.","tokens_in":28553,"tokens_out":4897,"would_cite":true,"duration_ms":46799,"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":"SecEmb shows that a federated recommender can hide which items a user rated while shrinking per-user traffic to depend on the user's own item count rather than the catalog size.","keywords":["function secret sharing","federated recommender systems","secure aggregation","sparse embedding updates","private embedding retrieval","communication efficiency","privacy-preserving machine learning","point functions"],"falsifier":"Run one training round with two servers that are allowed to pool their keys and intermediate path values for a user with $m'=1$; if they can recover the hidden rated item index with probability meaningfully above $1/m$, the security theorem fails. On the efficiency side, measure the server's wall-clock time for full-catalogue function-secret-sharing evaluation at a catalog size of $m=90{,}000$; if that server cost dominates the user-side reduction, the practical efficiency claim is scope-limited.","tokens_in":27637,"feed_emoji":"🔒","tokens_out":7409,"duration_ms":79453,"temperature":0.7,"pith_summary":"SecEmb claims that a federated recommender can be made communication-efficient by exploiting the sparsity of embedding updates without sacrificing security or accuracy. The paper's central assertion is that rated item indices and individual user gradients can be hidden from the server while each user's per-round traffic depends on the number of items they rated ($m'$) rather than the full catalog size ($m$). On standard public datasets this makes upload and download roughly 4x to 90x smaller than secure federated recommenders and user-side computation up to 70x lower, while remaining lossless — unlike compression methods that trade accuracy for bandwidth. The result matters because the embedding table dominates model size in large-catalog recommenders, so making secure training sparse is what makes on-device participation feasible.","feed_headline":"Secure federated recommender cuts traffic up to 90x","feed_subtitle":"Sparse embedding updates hide rated items from servers while keeping training lossless.","key_machinery":"The load-bearing object is the function-secret-sharing key for a point function: a compact randomized description that lets each of two servers evaluate a function that is zero everywhere except at one hidden index, where it equals a value. Each user encodes every rated item row as such a point function; the servers evaluate the keys over the full item domain, obtaining additive shares of the embedding in the retrieval module and additive shares of the aggregated gradient in the aggregation module. The protocol's second key mechanism exploits the structure of these keys: the binary-tree path that selects the hidden index can be reused from the retrieval stage, so the aggregation stage needs only the final correction word that converts that path into the gradient value, cutting key size and the number of AES operations per update.","core_discovery":"The paper's central claim is a protocol in which each user encodes their non-zero embedding updates as secret-shared point functions, so two non-colluding servers can retrieve the relevant embeddings and aggregate the updates without ever learning which items the user rated or what the individual gradient values were. Because only the rated rows are downloaded and only compact function-secret-sharing keys are uploaded, per-user communication is $O(m'(\\lambda \\log m + bd) + |\\theta|b)$ for upload and $O(m'bd + |\\theta|b)$ for download, and the aggregation is exact: no quantization, low-rank approximation, or top-k sparsification is needed. The paper gives a simulation-based security argument that the servers' joint view reveals nothing beyond the aggregated model, and it reports communication reductions up to 90x and user-side computation reductions up to 70x against a two-server additive-secret-sharing baseline.","pith_inferences":["A general recipe suggested by this design: any federated task where the same sparse coordinates are used for both retrieval and update can reuse the function-secret-sharing path between stages, reducing the second transmission to one correction word per coordinate.","The user-side savings are partly a transfer of computation to the server; full-domain evaluation of secret-shared point functions over millions of items is a hidden cost that deserves its own benchmark before large-scale deployment.","A testable extension is to vary the padding multiplier that sets $m'$ from the average number of rated items and measure downstream utility; the paper fixes $m'$ empirically, and an automatic rule would make the protocol easier to deploy.","Federated language-model fine-tuning has the same sparse structure in token embeddings, so the same two-module protocol could apply to private token-embedding updates; the paper sketches this direction but does not implement it."],"forward_implications":["Federated recommenders can be made secure and sparse at the same time without loss: users send compact keys only for the rows they updated, and the server still reconstructs the exact aggregate.","Device download no longer scales with catalog size; it scales with the number of items the user rated, which is what makes large-catalog datasets (tens to hundreds of thousands of items) practical on bandwidth-limited devices.","Because no information about non-zero positions or values reaches either server, the protocol is compatible with adding differential privacy noise to the aggregate, giving a better privacy-utility trade-off than local differential privacy.","The same mechanism extends to sequential recommendation, where the paper measures a roughly 2500x upload reduction on a dataset with more than nine million items."],"supporting_citations":[{"why":"Supplies the function secret sharing scheme for point functions whose key size and evaluation cost underwrite the protocol's complexity claims.","marker":"Boyle et al., 2016"},{"why":"Introduces function secret sharing and the two-party point-function construction that the protocol builds on.","marker":"Boyle et al., 2015"},{"why":"Provides the two-server additive secret sharing baseline that serves as the secure FedRec comparison point.","marker":"Xiong et al., 2020"},{"why":"Provides the MovieLens datasets used for the communication, computation, and utility experiments.","marker":"Harper & Konstan, 2015"},{"why":"Defines the matrix factorization model class whose sparse embedding gradients SecEmb is designed to optimize.","marker":"Koren et al., 2009"}],"fun_headline_variants":["Lossless secure FedRec cuts traffic 90x","Sparse secure FedRec hides ratings, 90x less traffic","SecEmb: sparse secure FedRec, 90x less communication","Sparsity-aware secure FedRec: 90x less traffic","Hide rated items, slash FedRec traffic 90x"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The security guarantee collapses if the two servers work together, and the headline savings assume the server can afford to evaluate every user's secret-shared marker over the entire item catalogue and store intermediate values for all catalogue items — server-side costs that grow with catalogue size and are not counted in the per-user complexity headline.","fun_headline_variants_meta":{"raw":{"variants":["Lossless secure FedRec cuts traffic 90x","Sparse secure FedRec hides ratings, 90x less traffic","SecEmb: sparse secure FedRec, 90x less communication","Sparsity-aware secure FedRec: 90x less traffic","Hide rated items, slash FedRec traffic 90x"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000752,"raw_usage":{"total_tokens":3353,"prompt_tokens":956,"completion_tokens":2397,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":572,"completion_tokens_details":{"reasoning_tokens":2310}},"tokens_in":572,"tokens_out":2397,"duration_ms":17867,"temperature":1.0,"reasoning_tokens":2310,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:34:46.747536+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run one training round with two servers that are allowed to pool their keys and intermediate path values for a user with $m'=1$; if they can recover the hidden rated item index with probability meaningfully above $1/m$, the security theorem fails. On the efficiency side, measure the server's wall-clock time for full-catalogue function-secret-sharing evaluation at a catalog size of $m=90{,}000$; if that server cost dominates the user-side reduction, the practical efficiency claim is scope-limited.","supporting_citations":[{"cited_title":"Function secret sharing: Improvements and extensions","cited_arxiv_id":null,"evidence_quote":"Supplies the function secret sharing scheme for point functions whose key size and evaluation cost underwrite the protocol's complexity claims."},{"cited_title":"Function secret sharing","cited_arxiv_id":null,"evidence_quote":"Introduces function secret sharing and the two-party point-function construction that the protocol builds on."}],"review_version":1}