{"id":"2dbd98f9-d17d-4d8d-afad-6ec07dbded2e","arxiv_id":"1908.05021","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For a universal access structure with n minimal qualified sets, the optimal share size grows at least as n/log2 n and at most as n/2.7182.","lead":"This paper studies secret sharing, where allowed groups of participants can recover a hidden secret. It proves new asymptotic bounds for the richest possible group structure with n entry-level groups, placing the best share size between n/log2 n and n/2.7182.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 8's lower bound applies Lemma 7 with A0=X, but X is unqualified in the constructed access structure, so the n/log2 n lower bound is not proved as written.","rationale":"The reader's weakest assumption identifies exactly the same load-bearing gap: Lemma 7 is applied with A0=X even though the access structure constructed in Theorem 8 has no minimal qualified set contained in X, so X is unqualified. This is not a stylistic or presentational issue; it invalidates the derivation of f(X) >= n and hence the n/k lower bound, leaving the n/log2 n asymptotic lower bound unproven. The upper bound n/e appears sound, and the reduction/equivalence results are independent of the lower bound. The concern is therefore specifically about the lower-bound half of the headline result, and it is significant enough that the paper cannot be accepted as providing both claimed asymptotic bounds. However, because the gap is localized to one lemma application and a repair seems plausible, CONDITIONAL is an appropriate verdict. The reader already reached CONDITIONAL, so no adjustment is needed.","tokens_in":5708,"tokens_out":9666,"duration_ms":103841,"concrete_test":"Verify the exact application of Lemma 7 by checking its first hypothesis for the proof's choice A0=X. For each minimal qualified set M_i = B_i C_{i-1}, note that b_i is in M_i but not in X, so no M_i is a subset of X; therefore X is unqualified. To make this concrete, instantiate n=2, k=2: X={a1,a2}, M1={b1,a1}, M2={b1,b2,a2}; {a1,a2} contains no M_i and is not qualified. This single check shows that the lower-bound proof as written does not go through.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that the universal access structure has complexity at least n/log2 n rests on Theorem 8. There, after defining the minimal qualified sets M_i = B_i C_{i-1} for i=1..n, the proof says 'we can apply Lemma 7 with A0 = X giving f(X) >= n.' Lemma 7 explicitly requires A0 to be a qualified set. In the constructed structure, every M_i contains b_i, while X contains no b_i, so no M_i is contained in X. Hence X contains no minimal qualified set and is unqualified, and Lemma 7 cannot be invoked. Without f(X) >= n, the subsequent step f(a_1)+...+f(a_k) >= f(X) >= n, and therefore the lower bound n/k on the complexity of the constructed structure, has no support. Since the lower bound for U_n is derived solely from this construction, the asymptotic lower bound n/log2 n is not established as written. The upper-bound analysis and the reduction steps are unaffected; only the lower half of the claimed interval is unsupported. A repair may be possible, but it is not present in the manuscript.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the complexity (normalized information ratio) of the universal access structure U_n with n minimal qualified sets, i.e., the structure in which every Boolean combination of the n minimal qualified sets is nonempty. The main claim is that the complexity of U_n is asymptotically at least n/log_2 n and at most n/e (≈ n/2.7182). The upper bound is obtained by an explicit recursive secret sharing scheme based on Stinson's decomposition, leading to the closed form f_n(i) = (n-i)(h(n)-h(n-i)) whose maximum is analyzed as n/e + O(1). The lower bound is attempted via the independent-sequence method: the paper constructs an access structure with n minimal qualified sets and applies Lemma 7 with A0 = X, a set of k elements, to conclude that some participant has share size at least n/k, giving the n/(1+log_2 n) bound. The paper also proves that all universal structures with n minimal qualified sets have the same complexity and notes the known exact values for n = 2 and n = 3.","tokens_in":5848,"tokens_out":4961,"duration_ms":49790,"significance":"If the lower bound were valid, the paper would give the first general asymptotic bounds for the hardest access structures with n minimal qualified sets, a natural and previously open problem. The upper-bound construction is a genuine strength: it is explicit, elementary, and yields a clean asymptotic constant of 1/e, and the symmetrization and decomposition arguments are convincing. The lower-bound strategy is also appropriate in spirit, but the proof as written contains a load-bearing gap: Lemma 7 is invoked with an unqualified set A0 = X, so the independent-sequence method cannot be applied. As written, the contribution establishes only the upper bound; the lower half of the claimed interval is unsupported and needs repair.","major_comments":[{"comment":"The proof of Theorem 8 states 'we can apply Lemma 7 with A0 = X giving f(X) ≥ n'. Lemma 7 explicitly assumes that A0 is a qualified set. In the access structure constructed in the theorem, the minimal qualified sets are B_i C_{i-1} for i = 1,...,n, and each of them contains the participant b_i. Since X is defined as a set of k elements a_1,...,a_k and contains no b_i, no minimal qualified set is contained in X; hence X is unqualified. The hypotheses of Lemma 7 are therefore not satisfied, and the inequality f(X) ≥ n is unsupported. Since this inequality is the only source of the subsequent bound f(a_1)+...+f(a_k) ≥ n, the lower bound n/k for the constructed structure, and consequently the asymptotic lower bound n/log_2 n for U_n, are not established by the argument as written.","section":"§4, Theorem 8"},{"comment":"The necessity of A0 being qualified is not a cosmetic condition. In the proof of Lemma 6, the equality f(A) = f(As) is used for the qualified set A, and f(C) = f(Cs) + 1 for the independent set C; both equalities fail if A0 is unqualified. Thus the independent-sequence method cannot be adapted to the constructed structure simply by ignoring this requirement. The manuscript needs either a different choice of A0 that is qualified while still allowing Lemma 7 to run (for instance, a set containing some b_i), or a substantially revised lower-bound proof.","section":"§4, Lemmas 6 and 7"}],"minor_comments":[{"comment":"The notation C_i is used both for the intermediate sets in Lemma 7 and for the enumeration of proper subsets of X in Theorem 8, which makes the proof harder to follow. Renaming one of the two families would improve clarity.","section":"§4, Theorem 8"},{"comment":"In the displayed line 'f(C) + b(Bp) ≥ f(Cp) + f(B)', the term 'b(Bp)' should be 'f(Bp)'.","section":"§4, Lemma 6 proof"},{"comment":"There is a duplicated word in 'or any any other subset'; it should read 'or any other subset'.","section":"§2, Claim 1"}],"recommendation":"major_revision","confidential_remarks":"The lower-bound gap is substantial because it is the only proof of the lower half of the main result. I recommend major revision rather than rejection: the upper bound is sound, and the lower-bound construction is close to repairable (e.g., one might try A0 = X ∪ {b_1} and re-index the independent sequence, then re-check the independence and qualified conditions). The revision should either provide a correct proof of the lower bound or clearly state the lower bound as conditional on a repaired argument."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The upper bound is real; the lower bound has a hole. In Theorem 8, Lemma 7 is invoked with A0 = X, but X is not a qualified set in the constructed access structure. Every minimal qualified set is B_i C_{i-1} and contains some b_j; X contains no b_j, so X contains no minimal qualified set. Lemma 7 explicitly requires A0 qualified, and its proof uses that to apply Lemma 6. As a result, the claimed f(X) ≥ n and the subsequent n/k bound are unsupported. That is not a cosmetic issue; it takes away the lower half of the main theorem.\n\nWhat is good: the paper gives the first bounds for arbitrary n for the complexity of universal access structures. The upper-bound part is solid. The recursive construction from Stinson's decomposition, the closed form f_n(i) = (n-i)(h(n)-h(n-i)), and the asymptotic maximization around n/e are all correctly derived. The normalization reduction in Claim 1 is also clean. The harmonic-number estimate is applied properly.\n\nThe lower-bound idea is not crazy: the independent sequence method is the right tool, and the construction of the minimal qualified sets B_i C_{i-1} with the decreasing enumeration of subsets of X has the right combinatorial flavor. The independence of the intermediate sets B_i C_i checks out. But the application of the method is invalid as written because the initial set must be qualified. A repair might be possible—for instance, starting from a qualified set that includes some b's and adjusting the size bound—but it is not present in this manuscript.\n\nCitations are fine and on point. The paper is aimed at researchers in information-theoretic secret sharing; the upper bound alone is a useful contribution.\n\nMy take: it deserves a serious referee, but the lower bound must be fixed or the claims weakened before I'd accept it. The upper bound is publishable; the interval claim is not yet proven.","headline":"Upper bound is solid; lower bound has a load-bearing gap that makes the asymptotic interval claim unproven as written.","tokens_in":6382,"tokens_out":6378,"would_cite":true,"duration_ms":59772,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A62","90C25","05B35"],"pacs":[],"model":"deepseek-v4-flash","headline":"Universal secret-sharing complexity with n minimal qualified sets is asymptotically between n/log₂ n and n/e.","keywords":["secret sharing","access structure","universal access structure","minimal qualified sets","complexity","entropy method","harmonic series"],"falsifier":"Take the smallest nontrivial case of Theorem 8 with $k=2$ and $n=2$: the participants are $X=\\{a_1,a_2\\}$ together with $b_1,b_2$, and the minimal qualified sets are $\\{b_1\\}\\cup C_0$ and $\\{b_1,b_2\\}\\cup C_1$, with $X$ itself unqualified. Solve the entropy inequalities for this access structure and check whether a valid relative-entropy function $f$ can satisfy $f(X)\\ge 2$; if the maximum achievable value is below $2$, the claimed lower bound fails exactly at the step where Lemma 7 is applied to $X$.","tokens_in":5445,"feed_emoji":"🔐","tokens_out":10581,"duration_ms":102736,"temperature":0.7,"pith_summary":"The paper studies the universal access structure with $n$ minimal qualified sets, the access structure that puts at least one participant in every Boolean combination of those sets. Since every access structure with $n$ minimal qualified sets sits inside this one, the universal structure is the hardest case for secret sharing with a fixed number of minimal qualified groups. The paper claims that its complexity—the ratio of total share size to secret size in an optimal scheme—is asymptotically at least $n/\\log_2 n$ and at most $n/e$, with $e \\approx 2.7182$. If true, these are the first general asymptotic bounds for the worst-case cost of secret sharing when only the number of minimal qualified sets is known, and the upper bound is supplied by an explicit recursive scheme.","feed_headline":"Universal secret-sharing complexity lies between n/log₂ n and n/e","feed_subtitle":"For n minimal qualified groups, the hardest secret-sharing structure costs at least n/log₂ n and at most n/e in share size.","key_machinery":"The load-bearing object is the normalized universal structure $U^*_n$ together with the symmetric share-size function $f_n(i)$, defined as the common normalized share size of every participant who belongs to exactly $i$ of the $n$ minimal qualified sets, with $f_n(0)=0$ and $f_n(n)=1$. Starting from any scheme for $U^*_n$, Stinson's decomposition technique yields a scheme for $U^*_{n+1}$ whose share sizes satisfy $n\\,f_{n+1}(i) = (n+1-i)\\,f_n(i) + i\\,f_n(i-1)$. Lemma 4 solves this recurrence in closed form using harmonic numbers, $f_n(i) = (n-i)(h(n)-h(n-i))$, and Theorem 5 locates the maximum at $n/e$. For the lower bound, the independent-sequence method (Lemma 7) is the mechanism: it converts a chain of sets that become qualified only after adding external participants into the inequality $f(A_0)\\ge n$ for a qualified starting set $A_0$.","core_discovery":"The central claim is that the normalized universal structure $U^*_n$—one participant in each non-trivial Boolean class of the $n$ minimal qualified sets—has complexity $\\sigma(U^*_n)$ asymptotically at least $n/(1+\\log_2 n)$ and at most $n/e + O(1)$. Because $\\sigma(U_n)=\\sigma(U^*_n)$ and every access structure with $n$ minimal qualified sets is a substructure of $U_n$, the same bounds carry over to the universal structure and give an upper bound for all access structures with $n$ minimal qualified sets. The upper bound is shown by building a recursive, fully symmetrized scheme whose share sizes obey a harmonic-number formula; the lower bound is claimed through the independent-sequence method.","pith_inferences":["If the lower-bound proof is repaired, the most natural fix is to apply Lemma 7 to a qualified set inside the construction—for instance $B_1C_0$—and then transfer the resulting $f$ bound to the participants of $X$ with subadditivity inequality (5); the rate $n/\\log_2 n$ would survive only if the repair keeps the starting set small.","The recurrence (1) is not tied to the full Boolean universe: replacing $U^*_n$ by a structure with some Boolean classes empty would yield a similar harmonic-number profile, so the same machinery could estimate complexity for intermediate access structures between graphs and universal structures.","A concrete computational check of the lower bound is feasible: for small $k$ and $n$, solve the entropy linear program for the access structure built in Theorem 8 and compare the optimum of $f(X)$ with $n$; if the optimum falls below $n$ for any instance, the current proof cannot be repaired by a small change to the starting set."],"forward_implications":["Every access structure with $n$ minimal qualified sets admits a perfect scheme with total share size at most $(n/e + O(1))$ times the secret size, because such structures embed into $U_n$.","The universal structure itself has complexity at least $n/(1+\\log_2 n)$, so, if the lower bound stands, the worst-case cost of secret sharing cannot be bounded by any constant independent of $n$.","The upper-bound construction is recursive and explicit, so for every $n$ it produces concrete share sizes rather than merely proving existence.","The gap between the lower bound $n/\\log_2 n$ and the upper bound $n/e$ means the exact asymptotic growth rate is not settled; only its position between a sublinear and a linear bound is known."],"supporting_citations":[{"why":"Supplies the independent-sequence method and the entropy inequalities that the lower-bound argument uses.","marker":"[1]"},{"why":"Provides Stinson's decomposition construction that yields the recursion for the upper-bound scheme.","marker":"[7]"},{"why":"Supplies the harmonic-number approximation used to locate the maximum of $f_n(i)$ near $n/e$.","marker":"[6]"},{"why":"Establishes the normalized-structure reduction and the earlier four-minimal-qualified-set bounds that the paper extends.","marker":"[5]"},{"why":"Provides the earlier investigation of universal structures with two and three minimal qualified sets and the exact complexity values used as context.","marker":"[4]"}],"fun_headline_variants":["Secret sharing hardest case: n/log n to n/e","Universal access complexity: n/log n to n/e","Secret sharing bounds: n/log n to n/e for universal structures","Hardest secret-sharing structures scale as n/log n to n/e","Complexity of universal access: between n/log n and n/e"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lower bound depends on Lemma 7, which requires the starting set $A_0$ to be qualified, but in Theorem 8 the starting set is $X$, and $X$ contains no minimal qualified set because every minimal qualified set contains one of the new participants $b_i$; the premise is therefore not actually met.","fun_headline_variants_meta":{"raw":{"variants":["Secret sharing hardest case: n/log n to n/e","Universal access complexity: n/log n to n/e","Secret sharing bounds: n/log n to n/e for universal structures","Hardest secret-sharing structures scale as n/log n to n/e","Complexity of universal access: between n/log n and n/e"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000219,"raw_usage":{"total_tokens":1368,"prompt_tokens":797,"completion_tokens":571,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":413,"completion_tokens_details":{"reasoning_tokens":485}},"tokens_in":413,"tokens_out":571,"duration_ms":5425,"temperature":1.0,"reasoning_tokens":485,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:29:07.491363+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the smallest nontrivial case of Theorem 8 with $k=2$ and $n=2$: the participants are $X=\\{a_1,a_2\\}$ together with $b_1,b_2$, and the minimal qualified sets are $\\{b_1\\}\\cup C_0$ and $\\{b_1,b_2\\}\\cup C_1$, with $X$ itself unqualified. Solve the entropy inequalities for this access structure and check whether a valid relative-entropy function $f$ can satisfy $f(X)\\ge 2$; if the maximum achievable value is below $2$, the claimed lower bound fails exactly at the step where Lemma 7 is applied to $X$.","supporting_citations":[{"cited_title":"Blundo, A","cited_arxiv_id":null,"evidence_quote":"Supplies the independent-sequence method and the entropy inequalities that the lower-bound argument uses."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides Stinson's decomposition construction that yields the recursion for the upper-bound scheme."},{"cited_title":"Sondow, E","cited_arxiv_id":null,"evidence_quote":"Supplies the harmonic-number approximation used to locate the maximum of $f_n(i)$ near $n/e$."},{"cited_title":"Mart ´ ı-Farr´ e, C","cited_arxiv_id":null,"evidence_quote":"Establishes the normalized-structure reduction and the earlier four-minimal-qualified-set bounds that the paper extends."},{"cited_title":"Mart ´ ı-Farr´ e, C","cited_arxiv_id":null,"evidence_quote":"Provides the earlier investigation of universal structures with two and three minimal qualified sets and the exact complexity values used as context."}],"review_version":1}