{"id":"02c16e39-437a-4630-9f1f-1c024f5e8431","arxiv_id":"1908.05570","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Splitting a message into coded chunks dropped off and picked up during random walks can hide communication from a patrolling warden, and the paper derives the covertness-delay tradeoff.","lead":"Alice and Bob pass a secret message through relay nodes while moving randomly on a graph, and avoid a patrolling warden by splitting and coding the message. The paper derives formulas for how redundancy and chunk size trade off covertness against transfer delay.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The covertness formula Pc=(1-Pd)^(n+k) requires an independence assumption about Willie's patrols that the warden model in Section II-C never states; correlated patrols break the product form.","rationale":"The reader identified the same weakest assumption: Willie's patrols are treated as independent across transmissions and vertices. This is indeed the most load-bearing concern because Eq. (1) is the only quantitative statement of the paper's covertness guarantee, and the warden model in Section II-C does not justify the independence needed for the product form. The Model 2 delay formula inconsistency noted by the reader is genuine, but it affects a secondary model and can be repaired by aligning the text with the formula; the independence gap, if real, would invalidate the headline covertness probability under an equally natural patrol model. The paper's own Section VII admits that richer warden models are future work, which supports the view that the present result is conditional on the simple, independence-style patrol interpretation. For that reason the reader's conditional verdict remains appropriate; no change in verdict is needed, but the authors should state the independence assumption explicitly and ideally test the product formula under a non-adaptive correlated patrol.","tokens_in":8069,"tokens_out":13000,"duration_ms":133849,"concrete_test":"Simulate a single Willie on a fixed periodic patrol with period W and one uniformly random phase, and generate the n+k transmission start times from the paper's random-walk protocol. Compute the exact joint survival probability as the fraction of phases for which Willie misses every transmission interval [t_i, t_i+ttr_i], and compare it with the product (1-Pd)^(n+k). Use the paper's parameters s=50, r=10, n=k=3, W=50, λ=1, m=10. If the joint survival probability differs from the product by more than a few percent, the independence assumption in Eq. (1) is load-bearing and must be stated explicitly or replaced by a correlated-patrol model.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central covertness result is Eq. (1): Pc=(1-Pd)^(n+k), obtained by multiplying single-transmission survival probabilities. Multiplication is valid only if the n+k detection events are independent and share the same detection probability Pd. Section II-C states only that \"when the transmission starts, the warden's (monitoring) time follows a uniform distribution U(0,W)\" and that a check during a transmission detects it with probability 1. No joint distribution for Willie's checks across the n+k transmissions or across different vertices is specified. A single non-adaptive Willie on a periodic patrol induces correlations between detection events: a common patrol phase makes the events dependent even though each marginal detection probability is Pd. The paper's Section VII defers adaptive Willies, but correlation is not a matter of adaptivity; a fixed periodic schedule with one random phase already breaks the product form. Since Theorem 1 and Eq. (1) are the sole support for the covertness axis of the claimed covertness-delay tradeoff, this unstated independence assumption is load-bearing. The Model 2 dwell-time inconsistency is real but fixable and secondary; the independence gap directly threatens the headline covertness probability.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper introduces a stylized model of covert message passing on complete graphs. Alice walks randomly, deposits n coded chunks (derived from k message chunks) at the first n distinct relays she encounters, and Bob walks and collects any k chunks to recover the message. Willie patrols vertices; if he checks a vertex while a chunk transmission is taking place, the transmission is detected. The transmission time is modeled as shifted exponential with mean 1/λ + m/k, and Willie's check time for a transmission is taken to be uniform on [0,W]. The paper derives the per-transmission detection probability (Theorem 1), the covertness probability under a product-form assumption (Eq. (1)), and expected dissemination/collection/total delays for two warden models (Theorems 2 and 3), using coupon-collector arguments. Section VI reports simulations that match the theoretical delay expressions.","tokens_in":8312,"tokens_out":11002,"duration_ms":102847,"significance":"If the assumptions are made explicit and the technical errors are corrected, the paper provides a clean, closed-form illustration of a covertness-delay tradeoff in a mobile relay protocol: chunking and erasure redundancy can reduce delay but increase the number of transmission opportunities visible to Willie. The derivations are elementary but transparent; no parameters are fit to data, and the coupon-collector delay expressions in Model 1 (Lemmas 1–3) are correct as stated, with the reported simulation-theory agreement in Figures 2–4 as supporting evidence. The paper is honest about the simplicity of its warden models and explicitly defers adaptive wardens to future work. Its main value is as a baseline model for covert mobile message passing rather than as a new information-theoretic bound.","major_comments":[{"comment":"The covertness probability Pc=(1-Pd)^(n+k) is obtained by multiplying per-transmission survival probabilities, but the paper never specifies a joint distribution for Willie's checks across the n+k transmissions. The model states only that 'when the transmission starts, the warden's (monitoring) time follows a uniform distribution U(0,W)'; it does not say that these checks are independent across transmissions. A single non-adaptive warden on a fixed periodic patrol with one random phase has marginal check times that can be uniform, yet the detection events for consecutive transmissions are dependent because the same patrol phase is shared, so the product form fails. As Eq. (1) is the sole support for the covertness axis of the claimed tradeoff, this missing independence assumption is load-bearing. The revision should either explicitly assume i.i.d. monitoring opportunities for each transmission and state that as part of the warden model, or derive a correlated-warden covertness probability or bound.","section":"Section II-C, Eq. (1)"},{"comment":"The prose states that in the second model 'every node visited by Alice or Bob takes 1 + m/k units of time,' but the delay expressions multiply the expected number of node visits by (1/λ + m/k + 1). The shifted-exponential transmission time has expected value 1/λ + m/k, so the prose omits the 1/λ term. If the intended model is that Alice and Bob transmit a dummy signal at every visited node with the same shifted-exponential duration, the prose should read 1 + 1/λ + m/k; if the intended model is a fixed dwell time of 1 + m/k at every node, then Lemmas 4–5 and Theorem 3 should use (1 + m/k) instead of (1/λ + m/k + 1). As written, the Model 2 expectation formulas do not correspond to the process described in the text.","section":"Section V-B, Lemmas 4–5 and Theorem 3"},{"comment":"The threshold for the optimal n does not follow from the displayed inequality. The derivation gives (n+1)^2 > k(r+1), so the correct condition is n > sqrt(k(r+1)) − 1, not n > sqrt(rk+k−1) as typeset. The stated formula is also inconsistent with the reported numerical optimum n=5 for r=10, k=3: sqrt(rk+k−1) is about 5.66, whereas sqrt(k(r+1)) − 1 is about 4.74. This algebra error occurs in the only closed-form optimization result in the paper and should be corrected together with the subsequent ceiling/floor prescription.","section":"Section V-B.3 (optimal n derivation)"}],"minor_comments":[{"comment":"The first sentence says 'the covertness probability increases with the redundancy n,' which contradicts Eq. (1), where (1-Pd)^(n+k) decreases in n for 0<Pd<1; the following discussion and Figure 1 correctly treat n=1 as the maximum-covertness case.","section":"Section VI-A"},{"comment":"The geometric-probability notation in Eq. (2) is mangled: it should read (1-p)^a p, and the sentence 'there aren stores' should read 'there are n stores.'","section":"Section III-A and Lemma 1"},{"comment":"The definition of A_n omits the constant H_r that appears in Theorem 3's full expression; omitting it is harmless for optimization, but the text should say so to avoid confusion.","section":"Section V-B.3"},{"comment":"No simulation details (number of independent runs, confidence intervals, or random-walk implementation) are provided, even though the close match between simulation and theory is a central part of the numerical validation.","section":"Section VI-B"},{"comment":"The manuscript contains numerous typographical and grammatical errors (e.g., 'tradoofs', the broken sentence about n=2 or n=3 in Section VI-A, and several missing superscripts); a careful proofreading pass is needed.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"For the editor: the paper's contribution is a simple baseline model, and its main correctness risk is the unsupported product-form covertness formula in Eq. (1). If the authors make the i.i.d. monitoring assumption explicit, the central tradeoff claim becomes defensible; the Model 2 dwell-time inconsistency and the optimal-n algebra error are fixable in revision. I would not reject on the basis of the current issues, but the independence assumption must be stated and the technical errors corrected before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear [Colleague],\n\nQuick take: this is a modest, mostly correct paper. The central idea is that in a mobile relay network, Alice can pass a message covertly by splitting it into chunks and using erasure-coding redundancy, at the cost of delay; a patrolling warden Willie creates the covertness constraint. The model is simple, and the derivations in Model 1 hold up.\n\nWhat's genuinely new: I don't see this exact construction in the cited literature. The covertness metric as a product of per-transmission detection probabilities, and the use of redundancy to trade off delay against covertness in a random-walk setting, appears to be original. Theorem 1's detection probability formula is a standard shifted-exponential/uniform integral, and I checked it; it's correct. Lemmas 1-3 are standard coupon-collector calculations and are also correct. The simulations in Figs. 2-3 match the analytical expressions, which suggests the implementation is faithful. For a designer wanting to pick chunk count and redundancy in an IoT/battlefield scenario, these formulas provide a quick handle.\n\nThe soft spots are real but not fatal. The headline formula Pc=(1-Pd)^(n+k) treats the n+k detection events as independent. The warden model in Section II-C only specifies a marginal uniform arrival time for a check; it never states independence across transmissions or vertices. If Willie runs a fixed periodic patrol with one random phase, the checks are correlated and the product form breaks. Since this formula drives the paper's main tradeoff, the assumption should be stated or the joint warden model analyzed. Also, Model 2's prose says each node visit takes 1+m/k units, while Lemma 4 uses 1+m/k+1/λ; that should be reconciled. And in Section VI-A there's a sentence saying covertness probability increases with redundancy n, which contradicts Eq. (1). These are the kinds of issues a referee would catch, and they are fixable.\n\nNo code is shipped, but the simulations are simple enough to reproduce.\n\nWho should read this: people working on covert communication or mobile relay protocols who want an analytic starting point. It's not a breakthrough, but it's honest progress. It deserves a serious referee, and after the independence assumption is made explicit and the small inconsistencies cleaned up, it would be a solid workshop or short-conference paper. I'd recommend engaging with it if you're in the area.\n\nBest,\n[name]","headline":"Correct, modest covert-messaging model; the headline covertness formula needs an explicit independence assumption about the warden, and Model 2 has a small internal inconsistency, but the core analysis is sound.","tokens_in":8804,"tokens_out":9361,"would_cite":false,"duration_ms":81601,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C81","68M20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Splitting and coding a message lets covert relay passers trade detection risk against delivery time.","keywords":["covert communication","random walk","complete graph","coupon collector","erasure coding","communication delay","warden detection","redundancy"],"falsifier":"Run the described protocol on a 50-vertex complete graph with $r=10$ relays, message length $m=10$, rate $\\lambda=1$, warden window $W=50$, and parameters $k=3$, $n=5$; if the measured fraction of chunk transmissions Willie detects differs from $1/(\\lambda W)+m/(kW)-e^{-\\lambda(W-m/k)}/(\\lambda W)$ beyond sampling error, or the mean total time differs from $(n+k)/\\lambda+(n/k+1)m+s(H_r+H_n-H_{r-n}-H_{n-k})$, the paper's core formulas fail.","tokens_in":7915,"feed_emoji":"🕵️","tokens_out":14312,"duration_ms":127947,"temperature":0.7,"pith_summary":"This paper introduces a mobile multi-agent protocol for covert message passing: Alice splits a message into $k$ chunks, encodes them into $n$ redundant pieces, leaves pieces with different relays on a city graph, and Bob recovers the message by collecting any $k$ pieces. The authors derive explicit formulas for the probability that a patrolling warden detects any chunk, and for the expected time until delivery, in two warden models. The central finding is a tunable tradeoff: redundancy and chunking can reduce expected delivery time, because Bob can stop once he meets any $k$ of $n$ holders, but every extra transmission increases the chance Willie sees something. The paper computes where the optimal balance lies and confirms the formulas by simulation.","feed_headline":"Redundancy shortens covert message delay but raises detection odds","feed_subtitle":"New formulas show how to split and encode a message to balance a roving warden's detection against delivery time.","key_machinery":"The machinery is a pairing of a shifted-exponential transmission-time model (a transmission of a chunk lasts at least $m/k$ plus an exponentially distributed extra amount of rate $\\lambda$) with coupon-collector random-walk counting on a complete graph (a graph in which every pair of vertices is connected). For detection, the key step is integrating the probability that the warden's uniform arrival time falls inside the shifted-exponential transmission, which gives the per-chunk $P_d$ and then the product formula $P_c=(1-P_d)^{n+k}$. For delay, the key step is the coupon-collector count $s(H_r-H_{r-n})$ for Alice to visit $n$ of $r$ relays and $s(H_n-H_{n-k})$ for Bob to visit $k$ of $n$ holders; these harmonic-number terms carry the whole delay analysis. The pairing is what makes redundancy useful: Bob only needs any $k$ of the $n$ stored chunks, so increasing $n$ shortens his collecting walk even though it lengthens Alice's dissemination walk.","core_discovery":"The paper's central claim is that the covertness-delay tradeoff of the relay protocol is exactly described by two formulas. If a chunk transmission lasts a shifted exponential time with shift $m/k$ and tail rate $\\lambda$, and Willie's check of a vertex arrives uniformly in $[0,W]$, then a single transmission is detected with probability $P_d = 1/(\\lambda W) + m/(kW) - e^{-\\lambda(W - m/k)}/(\\lambda W)$ when $W \\ge m/k$, and with probability 1 otherwise. Because Alice uploads $n$ chunks and Bob downloads $k$, the whole message stays covert with probability $P_c = (1-P_d)^{n+k}$. In the first warden model, the expected total transfer time is $E[T_{\\mathrm{tot}}] = (n+k)/\\lambda + (n/k+1)m + s(H_r + H_n - H_{r-n} - H_{n-k})$; in the second, where Willie can watch movements and agents spend equal time at every vertex, it is $((1/\\lambda)+m/k+1)s(H_r+H_n-H_{r-n}-H_{n-k})$, minimized near $n = \\sqrt{rk+k}-1$. These expressions show that $n$ and $k$ control a genuine tradeoff: redundancy and chunking can speed up delivery, but they add transmissions that Willie can catch.","pith_inferences":["An optimization rule the paper leaves implicit: for a fixed covertness floor, choose the smallest $n+k$ that meets the delay target, since $P_c$ decays exponentially in $n+k$ while delay is non-monotone; the closed-form delay can be used to solve for that frontier directly.","The complete-graph formulas can be read as a fast-mixing approximation for any graph with short mixing time; on sparse or hub-based graphs the harmonic-number terms become hitting-time quantities, so the optimal redundancy would shift and the paper's curves are a best-case delay estimate.","Because the protocol only needs any $k$ of $n$ pieces to recover the message, rateless or fountain codes fit the same model; the covertness-delay formulas should apply without committing to a fixed code rate.","The warden-independence assumption is the main stress point: an adaptive Willie who learns which vertices never hold data would shrink the effective graph size, raise per-check detection probabilities, and break the product form $P_c=(1-P_d)^{n+k}$; the paper's own future-work section names this possibility."],"forward_implications":["Extra coded redundancy ($n>k$) can lower the expected end-to-end delay, because Bob's collection time falls as $s(H_n-H_{n-k})$; simulations in the paper show an optimal $n$ that balances Alice's longer dissemination against Bob's shorter collection.","Covertness decreases exponentially in the total number of chunk transmissions $n+k$, so every added coded chunk buys delay at a predictable cost in detection probability.","If Willie's monitoring window $W$ is shorter than the per-chunk transmission time $m/k$, each chunk is detected with probability 1; splitting the message into smaller chunks is therefore a precondition for covertness in that regime.","When Willie can observe agent movements, the delay-minimizing number of coded chunks is approximately $\\sqrt{rk+k}-1$, giving a closed-form design rule rather than a simulation search.","The delay-covertness tradeoff is not monotone: for small $n$, increasing $k$ helps covertness; for large $n$, there is an optimal $k$ beyond which further splitting lowers covertness."],"supporting_citations":[{"why":"frames the information-theoretic covert-communication problem of hiding transmissions from a warden, which this mobile-relay protocol complements.","marker":"[1]"},{"why":"introduces deniable and hideable communication over multipath networks, the lineage this covert relay scheme extends.","marker":"[3]"},{"why":"supplies the graph-based information-gathering and dissemination setting that motivates the random-walk and coupon-collector delay analysis for Alice and Bob.","marker":"[8]"},{"why":"provides the prior result that coding redundancy can speed up content download, motivating why $n>k$ can reduce total delivery time here.","marker":"[9]"}],"fun_headline_variants":["Straggling cuts covert delay but boosts detection odds","Warden risk vs. delivery time: new covert tradeoff","Chunked covert messages: faster but easier to catch","Straggling protocol quantifies stealth-speed balance","Covert relay: redundancy quickens, detection rises"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that Willie's patrols are independent and random -- his arrival time at any checked vertex is uniform over a window of length $W$, and each chunk transmission is detected independently with the same probability -- so the overall covertness probability factors as $(1-P_d)^{n+k}$, and if Willie can correlate checks with movements or learn which vertices hold data, that factorization and the derived tradeoff break down.","fun_headline_variants_meta":{"raw":{"variants":["Straggling cuts covert delay but boosts detection odds","Warden risk vs. delivery time: new covert tradeoff","Chunked covert messages: faster but easier to catch","Straggling protocol quantifies stealth-speed balance","Covert relay: redundancy quickens, detection rises"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000328,"raw_usage":{"total_tokens":1802,"prompt_tokens":886,"completion_tokens":916,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":502,"completion_tokens_details":{"reasoning_tokens":838}},"tokens_in":502,"tokens_out":916,"duration_ms":8931,"temperature":1.0,"reasoning_tokens":838,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:09:42.534354+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the described protocol on a 50-vertex complete graph with $r=10$ relays, message length $m=10$, rate $\\lambda=1$, warden window $W=50$, and parameters $k=3$, $n=5$; if the measured fraction of chunk transmissions Willie detects differs from $1/(\\lambda W)+m/(kW)-e^{-\\lambda(W-m/k)}/(\\lambda W)$ beyond sampling error, or the mean total time differs from $(n+k)/\\lambda+(n/k+1)m+s(H_r+H_n-H_{r-n}-H_{n-k})$, the paper's core formulas fail.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"frames the information-theoretic covert-communication problem of hiding transmissions from a warden, which this mobile-relay protocol complements."},{"cited_title":"Kadhe, S","cited_arxiv_id":null,"evidence_quote":"introduces deniable and hideable communication over multipath networks, the lineage this covert relay scheme extends."},{"cited_title":"Tripathi, R","cited_arxiv_id":null,"evidence_quote":"supplies the graph-based information-gathering and dissemination setting that motivates the random-walk and coupon-collector delay analysis for Alice and Bob."},{"cited_title":"Joshi, Y","cited_arxiv_id":null,"evidence_quote":"provides the prior result that coding redundancy can speed up content download, motivating why $n>k$ can reduce total delivery time here."}],"review_version":1}