{"id":"9d1e249b-a718-499f-a0ec-d80f6b122adc","arxiv_id":"2509.09107","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"CryptGNN lets a client run a third-party GNN model on sensitive graph data using secret-shared computations across multiple cloud servers, keeping both data and model private.","lead":"CryptGNN is a secure multi-party computation system for running graph neural network inference in the cloud without exposing client data or model weights to any single party. It promises privacy for both the data owner and the model owner, even if all but one of the cloud servers collude.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Batched relative-index encoding in CryptMPL (Sec. 4.4) makes Theorem 2's N^{-2R} graph-reconstruction bound unsupported: the offsets are public and correlated across batches, so the true graph is identifiable with probability far above N^{-2R}.","rationale":"The paper makes two main technical contributions: CryptMPL and CryptMUL. The correctness of the message-passing arithmetic appears coherent, and the performance numbers, while not reproducible without code, are plausible and supported by a prototype. I am not questioning those parts. The central claim that makes the system 'provably secure' is that the input graph structure is protected under P-1 collusion. That claim rests on Theorem 2's N^{-2R} bound for batched relative-index encoding. Section 4.4 explicitly says the parties may infer graph structure from relative indices and defers to Section 6; Section 6's proof is a heuristic independence argument. The proof does not account for the information in the plaintext offsets themselves, for cross-batch node overlap, or for simple-graph constraints. The load-bearing concern is not a disagreement with consensus; it is an internal gap in the security argument. The concrete test would settle it by enumerating the adversary's view for small graphs and comparing consistent-graph count with N^{2R}. If the test shows C << N^{2R}, the bound is false and the claimed privacy guarantee collapses. Because this is exactly the reader's weakest-assumption, my read does not change the REJECT verdict.","tokens_in":40370,"tokens_out":10899,"duration_ms":121324,"concrete_test":"Run an exact enumeration attack on small random graphs. Fix N=8, M=16, batch size B=4 (R=4). For 100 random simple graphs, generate the public view exactly as in Sec. 4.4: for each batch, output the plaintext relative offsets Sr, Dr and treat JSfK, JDfK as unknown. Enumerate all anchor assignments (s_r,d_r) in [1,N]^2 for r=1..R, keeping only those that produce a simple graph on N nodes with no self-loops/duplicates. Let C be the number of distinct edge sets consistent with the view (collapsing assignments that yield the same edge set). If the median of C over the 100 graphs is below N^{2R}=8^8≈1.68e7, then a uniform guess over consistent graphs succeeds with probability 1/C > N^{-2R}, directly contradicting Theorem 2. Also report the posterior probability of the true graph; if it exceeds N^{-2R}, the graph-structure guarantee is refuted. A simpler auxiliary check: for each pair of batch","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4.4's batching optimization uploads the relative source/destination offsets Sr, Dr in plaintext for every batch; only the first index of each batch (JSfK, JDfK) is secret-shared. Theorem 2 claims the probability of reconstructing the graph is at most N^{-2R}, treating the R anchor pairs as independent uniform secrets. That model is wrong. The public offsets are not just an additive shift: within a batch they reveal relative adjacency patterns, and across batches they are linked because nodes appear in multiple edges. For instance, if batch 1 has offsets {0,1} and batch 2 has {0,-1}, the anchor difference is constrained to a small set. More generally, the adversary can enumerate anchor assignments and discard those producing self-loops, duplicate edges, or endpoints outside [1,N]; the number of distinct graphs consistent with the public view is far smaller than N^{2R}. A uniform guess among consistent graphs then succeeds with probability 1/C > N^{-2R}. The proof in Theorem 2 analyzes one batch in isolation and never writes the adversary's joint view across batches; the statement in Sec. 4.4 that 'the parties may infer the graph structure' is waved away by the unproven bound. Since the abstract and Section 1 rest the entire contribution on 'provably secure' graph-structure protection, this is the load-bearing vulnerability. If the bound fails, CryptMPL leaks structural information (shared nodes, degree correlations, and potentially the full edge set) under the stated threat model.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents CryptGNN, a secure multi-party computation (SMPC) system for GNN inference in an MLaaS setting. The system has two main components: CryptMPL, which performs secure message passing over secret-shared edge lists using client-side noise masking and batched processing, and CryptMUL, which implements secure matrix and element-wise multiplications using Beaver triples with a claimed preprocessing optimization. The paper claims correctness, security against collusion of up to P-1 out of P parties, and efficiency, and reports experiments on GIN models over several graph datasets showing lower latency than CrypTen and SecGNN baselines. The central security claim is that both node features and graph structure are protected, with the graph-structure reconstruction probability bounded by N^{-2R}.","tokens_in":40806,"tokens_out":16162,"duration_ms":200229,"significance":"If the security guarantees were sound, this would be a useful contribution: it targets a realistic threat model without a trusted third party, supports an arbitrary number of SMPC parties, and provides an end-to-end implementation with performance numbers. The empirical comparison and the system design are valuable. However, the paper's central graph-structure privacy claim is not established and, as argued below, is contradicted by the protocol's own design: the batching optimization uploads relative source/destination offsets in plaintext. Since the abstract and introduction rest the contribution on 'provably secure' protection of graph structure, this is a load-bearing flaw. The paper also provides no security experiments, only accuracy and runtime measurements.","major_comments":[{"comment":"The claimed N^{-2R} bound on graph reconstruction is unsupported and appears false. In the batching protocol, the relative index vectors S_r and D_r are uploaded in plaintext; only the first indices of each batch, JS_fK and JD_fK, are secret-shared. The proof of Theorem 2 says 'Processing multiple edges in CryptMPL does not reveal additional information,' but this is exactly the claim to be proved. The adversary's joint view across batches is never analyzed. Because a node can appear in multiple edges in different batches, the public offsets impose linear constraints on the anchor indices; the number of anchor assignments consistent with the public offsets is generally far smaller than N^{2R}, so a uniform guess among consistent assignments succeeds with probability much larger than N^{-2R}. The theorem analyzes one batch in isolation and does not account for cross-batch correlations. Th","section":"§4.4, §6.1, Theorem 2"},{"comment":"The proof that F_MatMul preserves privacy is incomplete. In the online phase, U = X - A' is revealed, where A' is not a freshly sampled random matrix but a public random row-combination of the same initial Beaver matrix A. Lemma 1 only shows that a linear combination of secret-shared values does not reveal the shares; it does not establish that the revealed U is indistinguishable from a value simulated without knowledge of X. If A does not have full column rank (e.g., when the number of nodes N is smaller than the feature dimension K, which can occur for small graphs with wide hidden layers), then A' is supported on a proper subspace of R^{N×K}, and U's distribution depends on X through the coset X - span(A'). The proof must either use genuinely fresh independent A' for every request or prove that row-combining A preserves uniformity over the full matrix space; neither is done. This affe","section":"§5.1, §6.1 (Theorem 3)"}],"minor_comments":[{"comment":"Axiom 1 is not an axiom; it is a standard information-theoretic property of additive secret sharing and should be stated as a lemma with a proof or a citation.","section":"§6.1"},{"comment":"The probability notation is confusing: the proof starts with per-edge probability 1/(N(N-1)), but the theorem states N^{-2R}. These are not consistent unless the batch size and number of edges are specified. The probability should be defined with respect to the adversary's random coins and the client's random choices.","section":"§6.1, Theorem 2"},{"comment":"References [1] and [2] are duplicates of the same Beaver paper; one should be removed and citations updated.","section":"References"},{"comment":"The text says 'the batch size is set to group all edges in 20 batches'; this should be stated as the number of batches R=20, not 'batch size', which is ambiguous.","section":"§7"},{"comment":"The example 'a batch of 3 nodes' is unclear: the batch contains edges, not nodes. The relative-index encoding should be explained more carefully in terms of source and destination arrays.","section":"§4.4"}],"recommendation":"reject","confidential_remarks":"The central security claim is not established, and the graph-structure leakage from plaintext relative offsets is a protocol-level flaw that cannot be fixed within the scope of the current manuscript. The performance results may be salvageable in a redesigned system, but the present version does not meet the bar for publication. The CryptMUL security proof also requires substantial revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper has a genuinely new mechanism for private GNN message passing, but the main security claim isn't established. CryptMPL's rotate-and-shift read/write with client-side noise is clever, and the batched relative-index trick is the kind of thing that could make secure GNN inference practical. CryptMUL's row-combination reuse of a Beaver triple is a modest but real optimization. To their credit, the Discussion section honestly lists several limitations, including lack of support for complex MPLs and active adversaries.\n\nThe problem sits in Section 4.4 and Theorem 2. The client uploads the relative source and destination offsets in plaintext; only the first index of each batch is secret-shared. The paper asserts that the probability of reconstructing the graph is at most N^{-2R}, but the proof just says processing multiple edges \"does not reveal additional information\" and then multiplies per-edge guessing probabilities. That is not a derivation. The adversary sees correlated offsets across batches: nodes appear in multiple edges, and that links the secret anchors. The set of graphs consistent with the public offsets is far smaller than N^{2R}, so uniform guessing succeeds with probability much larger than N^{-2R}. The paper itself concedes the parties may infer the graph structure and then waves it away with the unproven bound. That is the load-bearing assumption, and it collapses.\n\nThe rest of the security analysis is also thin. The simulation-based proofs are sketches rather than full arguments, and the reuse of the same B in CryptMUL across requests needs a proper composition analysis. The experiments report timing but no accuracy numbers and no code, so the \"same accuracy\" claim is hard to verify. That said, the correctness argument for the message-passing itself is coherent, and the overhead results look plausible.\n\nWho should read this? Researchers working on privacy-preserving GNN inference who want to see a concrete alternative to adjacency-matrix approaches. It is a good starting point for discussion, but not a result to build on as-is.\n\nRecommendation: send it to peer review, because the protocols deserve careful scrutiny and the security gap needs to be laid out publicly. But the reviewer should insist on a real proof for the batching leakage, or the graph-structure privacy claim should be downgraded to heuristic.","headline":"Clever protocol engineering but the load-bearing graph-structure privacy bound is unproven and likely wrong; the batching leaks too much.","tokens_in":41232,"tokens_out":3202,"would_cite":false,"duration_ms":36039,"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":"CryptGNN claims to be the first system that enables secure inference for graph neural networks in the cloud, protecting the client's graph structure and node features and the model owner's parameters even if P-1 of P cloud parties collude.","keywords":["Secure multi-party computation","Graph neural networks","Privacy-preserving inference","Machine learning as a service","Secret sharing","Beaver triples","Message passing","Graph structure privacy"],"falsifier":"Construct a 3-party simulation of CryptMPL for a graph known to the adversary except for the edge list, collect the plaintext relative indices S_r and D_r for all batches, and attempt to recover the true edge list by using the public first-index shares and the node degrees inferred from the aggregation pattern. If the success probability exceeds N^(-2R) for the claimed N and R, or if the adversary can recover any edge with certainty after observing all batches for one inference request, then Theorem 2 is false.","tokens_in":40274,"feed_emoji":"🔐","tokens_out":2165,"duration_ms":25538,"temperature":0.7,"pith_summary":"CryptGNN is a new SMPC-based inference system for graph neural networks offered as MLaaS. It allows a client to upload encrypted graph data and a model owner to upload encrypted model parameters, and lets a set of cloud parties compute the GNN forward pass without learning the graph structure, node features, intermediate results, or model weights. The paper claims this is the first approach to achieve strong privacy (P-1 colluding parties, no trusted server) while remaining practical for medium and large graphs. The two key protocols are CryptMPL for secure message passing and CryptMUL for secure feature transformations.","feed_headline":"CryptGNN claims secure GNN inference with P-1 colluding servers","feed_subtitle":"Node features, graph structure, and model weights stay hidden while inference runs on shared clouds.","key_machinery":"The core mechanism is the combination of additive secret sharing (A-SS) and multiplicative secret sharing (M-SS) with a client-side noise masking step. For message passing, CryptMPL uses a batched relative-index encoding: the client uploads the first index of each batch in secret-shared form and the relative offsets for the other edges in plaintext, while the parties rotate matrices by random amounts and add noise so that neither source nor destination indices are revealed. For feature transformations, CryptMUL reuses a per-client initial Beaver triple by applying pseudorandom linear combinations to the rows of the A and C matrices for each inference request, and generates fresh Beaver tripl","core_discovery":"The paper introduces CryptGNN, a privacy-preserving GNN inference system built from two protocols. CryptMPL securely performs message passing by having the client precompute and share a noise matrix, then having the parties rotate, shift, and mask secret-shared feature matrices and indices so that read and write operations on edges reveal neither the features nor the graph structure. CryptMUL enables secure matrix and element-wise multiplications for feature transformation layers by reusing a per-client initial Beaver triple through random row combinations for linear layers, and by generating fresh Beaver triples via an additive-to-multiplicative share conversion for non-linear layers. The s","pith_inferences":["The claim that graph structure privacy scales as N^(-2R) rests on the assumption that the plaintext relative indices in each batch are independent and reveal nothing across batches; if an adversary can collect multiple batches for the same graph, they may correlate relative offsets to eliminate candidate shifts and recover the graph with far less work, which would invalidate the security bound.","A concrete testable extension is to implement an attack that observes the relative indices and the order of edge processing across multiple batches and attempts to reconstruct the source-destination pairs; the success probability versus N and R would directly confirm or refute Theorem 2.","CryptGNN's security is stated for the honest-but-curious model; extending it to active adversaries would require MACs or zero-knowledge proofs, as the paper acknowledges, and the current protocols would likely fail under malicious behavior.","The client-side noise computation assumes the client knows the exact graph structure and noise effect; if the client is computationally weak or the graph changes frequently, the preprocessing cost may negate the efficiency gains claimed for large graphs."],"forward_implications":["If CryptGNN is correct, MLaaS providers can offer pretrained GNN models to clients without exposing proprietary model weights or learning the client's graph data, including the existence of edges between nodes.","CryptGNN eliminates the trusted third party required by prior SMPC-based GNN approaches such as SecGNN, and works with any number of parties, tolerating all but one colluding.","The batched edge processing reduces communication and computation overhead compared to adjacency-matrix-based secure message passing, especially for sparse large graphs.","CryptMUL's reuse of Beaver triples through random row combinations enables low online latency for linear layers, making repeated inference requests from the same client practical.","The security model covers collusion with the model owner or a fake data owner, going beyond the standard honest-but-curious party collusion assumption."],"fun_headline_variants":["CryptGNN: GNN inference secure even if most servers collude","CryptGNN hides graph, features, and model from colluding clouds","Secure GNN inference without a trusted third party","CryptGNN: P-1 colluders can't crack your GNN data","GNN inference stays private against up to P-1 colluding servers"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The security of the graph structure relies on the claim that an adversary who observes the plaintext relative source and destination indices for each batch, along with the encrypted first indices, cannot reconstruct the graph with probability higher than N^(-2R); if this bound fails, the whole graph-privacy guarantee collapses.","fun_headline_variants_meta":{"raw":{"variants":["CryptGNN: GNN inference secure even if most servers collude","CryptGNN hides graph, features, and model from colluding clouds","Secure GNN inference without a trusted third party","CryptGNN: P-1 colluders can't crack your GNN data","GNN inference stays private against up to P-1 colluding servers"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000563,"raw_usage":{"total_tokens":2459,"prompt_tokens":646,"completion_tokens":1813,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":390,"completion_tokens_details":{"reasoning_tokens":1719}},"tokens_in":390,"tokens_out":1813,"duration_ms":13163,"temperature":1.0,"reasoning_tokens":1719,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T19:42:10.815320+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a 3-party simulation of CryptMPL for a graph known to the adversary except for the edge list, collect the plaintext relative indices S_r and D_r for all batches, and attempt to recover the true edge list by using the public first-index shares and the node degrees inferred from the aggregation pattern. If the success probability exceeds N^(-2R) for the claimed N and R, or if the adversary can recover any edge with certainty after observing all batches for one inference request, then Theorem 2 is false.","supporting_citations":[],"review_version":1}