{"id":"851cbd91-2867-4cd4-9568-d6f6e16dbf82","arxiv_id":"2412.17003","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Existence of Reed-Solomon codes robust to permutation plus n-2k+1 insertions and deletions implies fully anonymous (k-1,2k-1,n) ramp secret-sharing schemes.","lead":"This paper proves that Reed-Solomon codes can survive an adversary who scrambles the codeword and then deletes or inserts symbols, provided the field is large enough. This yields the first gap-threshold secret-sharing schemes that are fully anonymous and reconstruct perfectly.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; after scrutiny, Proposition 3.10's induction is sound, so Theorem 1.18 and Corollary 1.19 stand.","rationale":"The reader's weakest assumption correctly identifies Proposition 3.10 as the keystone of the existence proof, and I agree that it deserves careful verification. My read, however, is that the induction is valid: the minimal-equal-sub-pair structure is a simple directed cycle, the deletion argument preserves the needed invariant, and the unique ±1 monomial conclusion follows. I therefore do not share a medium correctness risk arising from that lemma. I do share the reader's mild concern that Section 5.2 is a sketch deferring to CST23, and I note two small unstated fixes (nonzero evaluation points for Corollary 1.19, and prime quantification in Propositions 3.11/3.14). These are not load-bearing for the main existence theorem, so I would keep the reader's CONDITIONAL verdict unchanged rather than escalate to rejection or move to full acceptance.","tokens_in":24679,"tokens_out":39133,"duration_ms":367798,"concrete_test":"Use a computer algebra system to exhaustively enumerate all distinct-element sequences I, J of length 2k−1 for k = 3, 4 (n = 5, 7), compute their minimal-equal-sub-pair decomposition, and verify over Q that every pair with t ≤ k has det(V_{I,J}) ≠ 0; additionally verify in every Case-1 configuration that deleting any matched pair (i, j) from a minimal equal sub-pair leaves A\\{i,j} free of equalities. A counterexample in either part would falsify Proposition 3.10.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I could not identify a load-bearing flaw in the central existence theorem. The reader's weakest point, Proposition 3.10, is the right place to look: the Schwarz-Zippel argument in Theorem 1.18 collapses if det(V_{I,J}) can vanish for a pair with at most k minimal equal sub-pairs. I checked the induction, especially the delicate deletion step in Case 1. A minimal equal sub-pair is a single directed cycle on values; deleting one outgoing edge from a vertex and one incoming edge to that same vertex leaves a directed path, so the remaining index set is free of equalities, and Claim 3.6 prevents new minimal pairs from forming across A' ∪ B. Thus the invariant t' ≤ k−1 is preserved and the unique ±1 monomial argument is valid. Minor exposition gaps remain: Propositions 3.11 and 3.14 select one prime in [200C, 400C] rather than proving the polynomial is nonzero modulo every prime q, although this follows because each determinant has a ±1 coefficient; and Corollary 1.19 needs α_i ≠ 0, which is not enforced by Theorem 1.18 but is an immediate union-bound fix. These are addressable and do not change the central claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies Reed–Solomon codes under an adversarial model that first permutes the codeword and then performs insertions and deletions, and applies these codes to fully anonymous ramp secret sharing. The main technical work is an algebraic condition on evaluation points (Section 2), a determinant-nonvanishing lemma for V-matrices whose index pairs have at most k minimal equal sub-pairs (Proposition 3.10), and two Schwarz–Zippel arguments (Propositions 3.11 and 3.14) that yield evaluation points satisfying the required rank/determinant conditions. From this, the author derives Theorem 1.18, the existence of [n,k] RS codes robust against the (n-2k+1)-permutation-insdel adversary over fields of size q >= 200 * (binom(n,2k-1) * (2k)!)^2, and Corollary 1.19, a fully anonymous (k-1,2k-1,n) ramp secret-sharing scheme with perfect reconstruction. The paper also claims explicit schemes using the evaluation points of [CST24] and [CST23].","tokens_in":24850,"tokens_out":24069,"duration_ms":215311,"significance":"If the main theorem and corollary are established, this is a meaningful step: it gives the first gap-threshold secret-sharing schemes satisfying the strongest anonymity notion (uniform, independent shares for unauthorized sets) together with perfect anonymous reconstruction, thereby addressing an open question from [BGI+24] in the ramp regime. It also extends the insdel analysis of RS codes to a permutation-then-insdel adversary. The core determinant lemma, Proposition 3.10, is carefully argued by induction with a unique-monomial technique, and the algebraic conditions are explicit and falsifiable. The two-dimensional explicit construction over O(n^3) fields is a useful concrete instantiation. However, the present proof contains field-size gaps that need repair before the claims are fully established.","major_comments":[{"comment":"The field-size inequality used to apply Propositions 3.11 and 3.14 is false for all parameters stated in Theorem 1.18. The proof claims q >= 200 * (binom(n,2k-1) * (2k)!)^2 >= 200 * max{ k^2 * binom(n,2k-1)^2 * (2k-1)!, k^3 * (en)^(2k-1) }. For n = 3 and k = 2 the left side is 115,200, while the right side (using the k^3 term that the proof of Proposition 3.14 actually derives) is 200 * max{24, 8 * (3e)^3} = 867,720. Hence the field size guaranteed by Theorem 1.18 does not satisfy the hypotheses of the propositions as stated, and the Schwarz-Zippel step is unjustified for these parameters. Moreover, Proposition 3.14's statement requires only q >= 200 * k^2 * (en)^(2k-1), but its proof establishes the stronger condition q >= 200 * k^3 * (en)^(2k-1); these two bounds are inconsistent. This is repairable by a sharper count of the determinants in Proposition 3.14 or by treating small n, k separately, but as written the main existence proof is incomplete.","section":"Section 4, proof of Theorem 1.18, with Proposition 3.14"},{"comment":"The proof begins 'Let alpha_1, ..., alpha_n be nonzero elements such that RS_{n,k}(alpha_1,...,alpha_n) is robust...', but Theorem 1.18 only guarantees distinct evaluation points; it does not guarantee that any of them is nonzero. If some alpha_i = 0, then the share of participant i equals the secret f(0) = s, so for k > 1 a single share is not uniform over F_q and the full-anonymity condition in Definition 1.13 fails. The gap is easily fixed by adding the n events alpha_i = 0 to the union bound in Proposition 3.11, but the current statement asserts nonzeroness without proof.","section":"Section 1.3, Corollary 1.19"}],"minor_comments":[{"comment":"The first sentence of the proof says 'Assume for contradiction that A1 ∩ A2 = ∅'; the intended contradiction hypothesis is A1 ∩ A2 ≠ ∅. As written the sentence is nonsensical.","section":"Claim 3.6"},{"comment":"The displayed unique monomial is written as X_{I_i}^{2k-2} m, but in cases 2 and 3 the variables I_i and J_j are distinct, so the monomial should be X_{I_i}^{k-1} X_{J_j}^{k-1} m. The preceding text is consistent with the corrected expression.","section":"Proposition 3.10, cases 2 and 3"},{"comment":"The determinant computation for the case in which I and J agree on two coordinates is only sketched; the formula det(V_{I,J}) = (alpha_{J3} - alpha_{I3})(alpha_{J2} - alpha_{J1}) should be derived explicitly, since the signed expression depends on the choice of the two agreeing coordinates.","section":"Section 5.1, Theorem 5.1"},{"comment":"The remark correctly explains why the reconstruction threshold of this RS-based construction cannot go below 2k-1, but the opening phrase 'the gap ... is necessary and cannot be improved' could be misread as a general impossibility for all fully anonymous ramp schemes. The restriction to this construction should be stated more prominently.","section":"Remark 1.20"}],"recommendation":"major_revision","confidential_remarks":"The main mathematical idea is sound and the gaps are local; I would not reject. The field-size mismatch in the proof of Theorem 1.18 is the main concern and should be fixed before publication. The paper leans heavily on [CST23,CST24], but it clearly identifies the new contributions: permutation-insdel robustness, the minimal-equal-subpair determinant lemma, and the anonymity application. The 'explicit' constructions are explicit only in the evaluation points, not in the reconstruction algorithm; the paper is honest about this. I recommend major revision rather than minor because the proof of the central theorem does not currently justify the stated field-size regime, and Corollary 1.19 needs the nonzero-evaluation-points fix."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this paper delivers what it promises. The main theorem, existence of RS codes robust against the permutation-insdel adversary at the half-Singleton bound, is proven carefully and the proof holds up. The corollary, fully anonymous (k-1, 2k-1, n) ramp secret sharing with perfect reconstruction, follows cleanly from the code robustness. That answers the open question from BGI+24 for ramp thresholds, which is a real step.\n\nWhat's new: the permutation-insdel model for RS codes is a genuine extension of the insdel-only setting; the observation that permutation robustness is exactly what you need for anonymous reconstruction is simple but right. The algebraic core is Proposition 3.10, an induction showing the V-matrix determinant does not vanish when the pair has at most k minimal equal sub-pairs. I went through that induction and it works. The deletion step in Case 1 is the delicate point, but the minimal equal sub-pair structure plus Claim 3.6 keeps the invariant intact. The Schwarz-Zippel applications then give random evaluation points with high probability, and the prime-selection argument (find a prime in [200C,400C] not dividing some integer coefficient) is correct, if slightly indirect.\n\nThe soft spots are real but not load-bearing. First, the explicit construction in Section 5.2 is a sketch: it says the proof of CST23 goes through with Proposition 3.11 swapped in, without re-deriving the details. For a reader who wants to actually use those evaluation points, that's frustrating. Second, Corollary 1.19 silently needs the alpha_i to be nonzero; Theorem 1.18 doesn't enforce that, but it's a trivial union-bound fix since you can avoid zero in the random draw. Third, reconstruction is brute-force; the author acknowledges this. The field size in the existential result is large but not surprising for this kind of argument.\n\nCitation pattern is fine. The paper leans on CST23/CST24, but uses them as tools and proves the new algebraic conditions independently. No circularity, no fitted parameters. The main limitation is conceptual: the factor-of-two gap between privacy and reconstruction thresholds is likely inherent for the RS-based approach, and the author says so.\n\nWho should read this: anyone working on insdel-correcting codes or anonymous secret sharing. It deserves a serious referee; the central claim is correct and the writeup is mostly clear, though Section 5.2 needs tightening. I'd send it to an editor for full review.","headline":"Solid existence proof for fully anonymous ramp secret sharing via permutation-insdel-robust RS codes; the main theorem holds up, though the explicit construction section is sketchy.","tokens_in":25416,"tokens_out":2043,"would_cite":true,"duration_ms":18711,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B05","94B35","94A62"],"pacs":[],"model":"deepseek-v4-flash","headline":"Reed-Solomon codes that withstand permutation-plus-deletion attacks yield fully anonymous secret sharing with perfect reconstruction.","keywords":["Reed-Solomon codes","insertions and deletions","anonymous secret sharing","permutation-insdel adversary","ramp secret sharing","fully anonymous","Vandermonde matrices","Schwarz-Zippel lemma"],"falsifier":"For a small k (say k=3) and n>=2k-1, symbolically expand $\\det V_{I,J}(X)$ for every pair of distinct-element sequences $I,J$ of length $2k-1$ whose decomposition has at most $k$ minimal equal sub-pairs; if any of these determinants is identically zero as a polynomial, the central existence argument collapses.","tokens_in":24417,"feed_emoji":"🔐","tokens_out":9561,"duration_ms":79849,"temperature":0.7,"pith_summary":"The paper establishes a bridge between error-correcting codes and anonymous cryptography: it argues that a Reed-Solomon code robust against an adversary who permutes a codeword and then inserts or deletes symbols can be turned into a secret-sharing scheme in which unauthorized shares leak neither the secret nor the identities of their holders. The main result claims that for any k,n with 2k-1 <= n, over a sufficiently large prime field there exist such codes, and hence a fully anonymous (k-1,2k-1,n) ramp secret-sharing scheme with perfect reconstruction. This matters because earlier anonymous schemes either sacrificed perfect reconstruction or only hid identities statistically, and the paper's construction gives the first gap-threshold schemes that are fully anonymous in the strongest sense. The proof is algebraic: it shows that the evaluation points can be chosen so that, for any two distinct low-degree polynomials, no two length-(2k-1) subsequences of their evaluations can coincide after an arbitrary permutation.","feed_headline":"Permutation-proof Reed-Solomon codes unlock anonymous secret sharing","feed_subtitle":"When shuffling plus deletions can't fool a code, any k-1 shares hide the secret and the holder's identity.","key_machinery":"The load-bearing object is the V-matrix $V_{I,J}(X)$, the $(2k-1)\\times(2k-1)$ matrix whose $s$-th row is $(1,X_{I_s},\\ldots,X_{I_s}^{k-1},X_{J_s},\\ldots,X_{J_s}^{k-1})$ for two distinct-element sequences $I,J\\in[n]^{2k-1}$. A collision of two codewords under permutation-plus-insdel is exactly a nonzero vector in the right kernel of $V_{I,J}(\\alpha)$ that does not have the form $(0,f_1,\\ldots,f_{k-1},-f_1,\\ldots,-f_{k-1})$. The proof decomposes $(I,J)$ into minimal equal sub-pairs (maximal disjoint index blocks on which the two sequences contain the same set of symbols) and proves, by induction with a uniquely realized monomial, that $\\det V_{I,J}(X)$ is a nonzero polynomial whenever there are at most $k$ such blocks. For pairs with $k+1$ blocks, a second family of matrices $A_{I_1,\\ldots,I_k}(X)$ with full-rank conditions forces any kernel vector to come from a single polynomial. The Schwarz-Zippel lemma then shows that random evaluation points over a large field satisfy both algebraic conditions simultaneously.","core_discovery":"The central claim is Theorem 1.18: for integers k,n with 2k-1 <= n and any prime q >= 200 * (\\binom{n}{2k-1} \\cdot (2k)!)^2, there exists an RS_{n,k}(\\alpha_1,\\ldots,\\alpha_n) code that is robust against the (n-2k+1)-permutation-insdel adversary. Equivalently, no two distinct codewords can be mapped to the same string by first applying an arbitrary permutation and then at most n-2k+1 insertions and deletions. Corollary 1.19 then obtains a fully anonymous (k-1,2k-1,n) ramp secret-sharing scheme over F_q: any k-1 shares are uniform and independent, so they hide the secret and the participants' identities, while any 2k-1 shares, presented in any order, determine the secret exactly. The author also shows that earlier explicit Reed-Solomon constructions for insertions and deletions already give such codes in the two-dimensional case with q=O($n^{3}$) and in general dimension with q=$n^{{O(k^2((2k)!)^2)}}$.","pith_inferences":["The algebraic kernel condition is what really matters, so codes other than Reed-Solomon whose evaluation matrices satisfy the same rank property would also yield fully anonymous schemes; the connection seems transferable.","Because the half-Singleton bound rules out linear-code routes to the exact threshold, closing the gap to k would require either nonlinear codes or a fundamentally different secret-sharing construction.","A concrete next step would be to seek evaluation sets with algebraic structure that allows reconstructing from any 2k-1 unordered evaluations in polynomial time; the paper's brute-force reconstruction is the main practical bottleneck.","For non-constant k the field-size bound is dominated by ((2k)!)^2, so the existential and explicit schemes are mainly of theoretical interest; practical use would need a different trade-off."],"forward_implications":["For every k,n with 2k-1 <= n and q satisfying the theorem's bound, a fully anonymous (k-1,2k-1,n) ramp secret-sharing scheme exists with perfect reconstruction and shares of size O(k log n) bits for constant k.","The two-dimensional explicit construction yields a fully anonymous (1,3,n) ramp scheme over q=O(n^3), so even the smallest non-trivial gap is covered explicitly.","The gap between k-1 and 2k-1 is forced by the half-Singleton bound: a reconstruction threshold below 2k-1 would require the underlying linear code to correct more than n-2k+1 insdel errors, which is impossible.","The general explicit construction gives a deterministic fully anonymous scheme for all k,n with 2k<=n over q=n^{O(k^2((2k)!)^2)}, though the bit-length of shares is polynomial in n only for very slowly growing k."],"supporting_citations":[{"why":"Supplies the V-matrix framework, the nonvanishing determinant criterion for increasing index sequences, and Construction 27 that the explicit general construction adapts.","marker":"[CST23]"},{"why":"Supplies the explicit two-dimensional Reed-Solomon evaluation points that yield the fully anonymous (1,3,n) scheme over q=O(n^3).","marker":"[CST24]"},{"why":"Defines the strongest share-anonymity notion (uniform unauthorized shares) and poses the question this paper answers affirmatively for ramp schemes.","marker":"[BGI+24]"},{"why":"Provides the earlier anonymous Shamir variant whose non-perfect reconstruction and weaker anonymity the paper compares against.","marker":"[EBG+24]"},{"why":"Defines Shamir's secret sharing as polynomial evaluations, the scheme being made anonymous.","marker":"[Sha79]"},{"why":"The Schwarz-Zippel-DeMillo-Lipton lemma used to prove evaluation points satisfying both algebraic conditions exist.","marker":"[Sch80, Zip79, DL78]"},{"why":"Half-Singleton bound used to show the reconstruction threshold 2k-1 cannot be lowered within this linear-code construction.","marker":"[CGHL23]"},{"why":"Defines the permutation-channel model with insertions and deletions that the paper's adversary formalizes.","marker":"[KT18]"}],"fun_headline_variants":["RS codes survive shuffle and edits, enabling anonymous secrets","Shuffle-resistant codes hide both secret and shareholder identity","Reed-Solomon vs permutation-InsDel: anonymous ramp sharing","Codes that beat shuffle-and-edit attacks give anonymous sharing"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing step is the claim that a certain determinant polynomial stays nonzero for every pair of index sequences that share at most k small matching blocks; if that claim ever fails, the random evaluation points that the existence proof needs cannot be guaranteed.","fun_headline_variants_meta":{"raw":{"variants":["RS codes survive shuffle and edits, enabling anonymous secrets","Shuffle-resistant codes hide both secret and shareholder identity","Reed-Solomon vs permutation-InsDel: anonymous ramp sharing","Codes that beat shuffle-and-edit attacks give anonymous sharing"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000193,"raw_usage":{"total_tokens":1455,"prompt_tokens":1154,"completion_tokens":301,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":770,"completion_tokens_details":{"reasoning_tokens":233}},"tokens_in":770,"tokens_out":301,"duration_ms":3366,"temperature":1.0,"reasoning_tokens":233,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T05:56:27.316520+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a small k (say k=3) and n>=2k-1, symbolically expand $\\det V_{I,J}(X)$ for every pair of distinct-element sequences $I,J$ of length $2k-1$ whose decomposition has at most $k$ minimal equal sub-pairs; if any of these determinants is identically zero as a polynomial, the central existence argument collapses.","supporting_citations":[],"review_version":1}