REVIEW 2 major objections 3 minor 7 references
Complexity of universal access structures
T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Universal secret-sharing complexity with n minimal qualified sets is asymptotically between n/log₂ n and n/e.
desk verdict Upper bound is solid; lower bound has a load-bearing gap that makes the asymptotic interval claim unproven as written. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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$.
What would settle it
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$.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (2)
- [§4, Theorem 8] 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.
- [§4, Lemmas 6 and 7] 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.
minor comments (3)
- [§4, Theorem 8] 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.
- [§4, Lemma 6 proof] In the displayed line 'f(C) + b(Bp) ≥ f(Cp) + f(B)', the term 'b(Bp)' should be 'f(Bp)'.
- [§2, Claim 1] There is a duplicated word in 'or any any other subset'; it should read 'or any other subset'.
Circularity Check
No circularity: the complexity bounds are derived from an explicit recursive construction and an independent-sequence lower-bound argument.
full rationale
The paper's central claim is not circular. The upper bound (Theorem 5) is obtained by explicitly constructing a scheme via Stinson's decomposition (Lemma 3), solving the resulting recurrence (Lemma 4), and estimating the maximum of the closed-form share sizes; the ingredients are stated and proved in the manuscript or cited to external, non-overlapping sources (Stinson [7], harmonic-number approximation [6]). The lower bound (Theorem 8) uses the independent sequence method, whose key lemmas (Lemmas 6 and 7) are proved in the paper rather than imported from the author's prior work, and is applied to a freshly constructed access structure rather than fitted to the universal structure's own complexity. No parameter is fitted to a subset of data and then relabeled as a prediction, and no uniqueness claim is imported from a self-citation. The only substantive concern is a correctness issue: Lemma 7 requires A0 to be qualified, while in Theorem 8 the chosen A0=X plausibly contains no minimal qualified set (each minimal qualified set Bi C_{i-1} contains a b_i, and X contains no b_i). If correct, that would invalidate the lower-bound proof as written, but it would be a mathematical flaw rather than circular reasoning. The derivation does not reduce to its own inputs, so the circularity score is 0.
Assumptions & free parameters
assumptions (4)
- domain assumption The relative entropy function f for a secret sharing scheme is submodular, monotone, and satisfies f(B)+1 <= f(A) whenever B is unqualified, B subset A, and A is qualified.
- domain assumption Perfect ideal k-out-of-k threshold schemes exist with share size equal to the secret size.
- domain assumption Stinson's decomposition technique yields a composite scheme whose share sizes combine by the stated recursion.
- standard math The harmonic number h(x) satisfies h(x) = gamma + log(x - 1/2) + O(x^-2).
Cite this review
Pith. "Pith review of Complexity of universal access structures." pith.science (2026). https://pith.science/paper/HBK3KFLF
@misc{pith2026190805021,
author = {Pith},
title = {Pith review of: Complexity of universal access structures},
year = {2026},
howpublished = {\url{https://pith.science/paper/HBK3KFLF}},
note = {Machine review of arXiv:1908.05021}
}
abstract
An important parameter in a secret sharing scheme is the number of minimal qualified sets. Given this number, the universal access structure is the richest possible structure, namely the one in which there are one or more participants in every possible Boolean combination of the minimal qualified sets. Every access structure is a substructure of the universal structure for the same number of minimal qualified subsets, thus universal access structures have the highest complexity given the number of minimal qualified sets. We show that the complexity of the universal structure with $n$ minimal qualified sets is between $n/\log_2 n$ and $n/2.7182$ asymptotically.
Reference graph
Works this paper leans on
- [1]
-
[2]
L. Csirmaz: An impossibility result on graph secret sharing, Designs, Codes and Cryptography , vol 53 (2009), pp 195–209
work page 2009
-
[3]
I. Csisz´ ar and J. K¨ orner: Information Theory. Coding Theorems for Dis- crete Memoryless Systems , Academic Press, New York, 1981. 7
work page 1981
-
[4]
J. Mart ´ ı-Farr´ e, C. Padr´ o. Secret sharing schemes with three or four minimal qualified subsets. Designs, Codes and Cryptography 34 (2005) 17-34
work page 2005
-
[5]
J. Mart ´ ı-Farr´ e, C. Padr´ o, L. Vzquez. Optimal Complexity ofSecret Shar- ing Schemes with Four Minimal Qualified Subsets. Designs, Codes and Cryptography, vol 61 (2011), pp 167–186
work page 2011
- [6]
-
[7]
D. R. Stinson: Decomposition Constructions for Secret-Sharin g Schemes IEEE Transactions on Information Theory , vol 40(1) (1994) pp. 118–125 8
work page 1994
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.