pith. sign in

arxiv: 1906.11598 · v1 · pith:AIIANBRPnew · submitted 2019-06-27 · 💻 cs.CR · math.CO

Smallest graphs achieving the Stinson bound

Mate Gyarmati , Peter Ligeti This is my paper

Pith reviewed 2026-05-25 14:37 UTC · model grok-4.3

classification 💻 cs.CR math.CO
keywords secret sharinginformation ratioStinson boundgraph access structureperfect secret sharingδ-regular graphs
0
0 comments X

The pith

Graphs with maximum degree δ on c·2^δ vertices achieve the Stinson bound of (δ+1)/2 on information ratio for perfect secret sharing.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper improves the construction of graphs that attain the highest possible information ratio for perfect secret sharing schemes. Earlier work required graphs with at least c times 6 raised to δ vertices. The new family uses only c times 2 raised to δ vertices while still reaching the bound of (δ+1)/2 in both worst and average cases.

Core claim

The authors construct a family of δ-regular graphs on c·2^δ vertices whose information ratio equals (δ+1)/2, matching the Stinson upper bound and improving on the previous exponential base of 6.

What carries the argument

The new explicit construction of smaller δ-regular graphs that realize the information ratio bound.

If this is right

  • The Stinson bound is tight for these smaller graphs.
  • Both worst-case and average-case information ratios achieve the bound.
  • Smaller vertex sets make the schemes more efficient in terms of number of participants.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The size reduction might support secret sharing in settings with limited numbers of participants.
  • The technique could apply to other access structures beyond graphs.

Load-bearing premise

The new graph constructions actually attain an information ratio of exactly (δ+1)/2.

What would settle it

Computing the information ratio for the constructed graphs at a small value of δ, such as δ=2 or 3, and checking if it reaches (δ+1)/2.

read the original abstract

Perfect secret sharing scheme is a method of distribute a secret information $s$ among participants such that only predefined coalitions, called qualified subsets of the participants can recover the secret, whereas any other coalitions, the unqualified subsets cannot determine anything about the secret. The most important property is the efficiency of the system, which is measured by the information ratio. It can be shown that for graphs the information ratio is at most $(\delta+1)/2$ where $\delta$ is the maximal degree of the graph. Blundo et al. constructed a family of $\delta$-regular graphs with information ratio $(\delta+1)/2$ on at least $c\cdot 6^\delta$ vertices. We improve this result by constructing a significantly smaller graph family on $c\cdot 2^\delta$ vertices achieving the same upper bound both in the worst and the average case.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper constructs families of δ-regular graphs on c·2^δ vertices that achieve information ratio exactly (δ+1)/2 (matching the Stinson upper bound) in both the worst case and the average case. This improves on the earlier Blundo et al. construction, which required at least c·6^δ vertices for the same ratio.

Significance. If the explicit constructions and the accompanying ratio proofs are correct, the result tightens the known minimal order of graphs attaining the Stinson bound and supplies concrete, smaller examples usable in secret-sharing applications. The explicit, parameter-free nature of the new families (once verified) would be a clear technical contribution.

major comments (1)
  1. The central claim rests on the correctness of the new graph families and the proof that their information ratio meets (δ+1)/2 in both worst and average cases. The abstract asserts existence but the provided text supplies neither the explicit adjacency rules nor the ratio calculation; without these the claim cannot be verified.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review. We address the single major comment below.

read point-by-point responses

  1. Referee: The central claim rests on the correctness of the new graph families and the proof that their information ratio meets (δ+1)/2 in both worst and average cases. The abstract asserts existence but the provided text supplies neither the explicit adjacency rules nor the ratio calculation; without these the claim cannot be verified.

    Authors: We agree that the submitted version would benefit from a clearer, self-contained presentation of the constructions. In the revision we will add an explicit description of the adjacency rules for the new δ-regular families (currently only summarized) together with the key steps of the worst-case and average-case information-ratio proofs, so that the claims can be verified directly from the text. revision: yes

Circularity Check

0 steps flagged

No circularity: explicit constructions achieve Stinson bound independently

full rationale

The paper's central contribution is an explicit family of δ-regular graphs on c·2^δ vertices whose information ratio is proven to equal (δ+1)/2 in both worst and average case. This rests on direct graph definitions and ratio calculations that do not reduce to fitting the target ratio, self-citation of the result itself, or renaming. The Stinson upper bound is an external theorem; the new graphs are shown to meet it via construction, not by definition. No load-bearing step collapses to the inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the known Stinson upper bound and on the correctness of the new graph constructions; no free parameters, invented entities, or additional axioms are visible from the abstract.

axioms (1)
  • domain assumption Stinson bound: information ratio of any graph is at most (δ+1)/2 where δ is maximum degree
    Invoked as established prior result that the constructions attain.

pith-pipeline@v0.9.0 · 5667 in / 1073 out tokens · 22765 ms · 2026-05-25T14:37:50.909131+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    G. R. Blakley, Safeguarding cryptographic keys, in: Proc. of the Nat. Comp. Conf. , 48, (1979) pp. 313–317. 8

    work page 1979

  2. [2]

    Blundo, A

    C. Blundo, A. De Santis, R. De Simone, U. Vaccaro, Tight bo unds on the information rate of secret sharing schemes, Des., Codes and Crypt. 11 (2) (1997) pp. 107–110

    work page 1997

  3. [3]

    Blundo, A

    C. Blundo, A. De Santis, L. Gargano, U. Vaccaro, On the inf ormation rate of secret sharing schemes, Theor. Comp. Sci. 154 (2) (1996) pp. 283–306

    work page 1996

  4. [4]

    Blundo, A

    C. Blundo, A. De Santis, D. R. Stinson and U. Vaccaro, Grap h decomposition and secret sharing schemes, J. of Crypt. 8 (1995), 39–64

    work page 1995

  5. [5]

    E. F. Brickell and D. R. Stinson, Some improved bounds on t he information rate of perfect secret sharing schemes, J. of Crypt. 5 (1992), 153–166

    work page 1992

  6. [6]

    Csirmaz, Secret sharing schemes on graphs, Studia Math

    L. Csirmaz, Secret sharing schemes on graphs, Studia Math. Hung. 44 (2007), 297–306

    work page 2007

  7. [7]

    Csirmaz, L.: Secret sharing on the d-dimensional cube. Des. Codes Cryptogr. 74, 719–729 (2015)

    work page 2015

  8. [8]

    Csirmaz and P

    L. Csirmaz and P. Ligeti, Secret sharing on large girth gr aphs, submitted to Crypt. and Comm. (2018)

    work page 2018

  9. [9]

    Csirmaz and G

    L. Csirmaz and G. Tardos, Optimal information rate of sec ret sharing schemes on trees, IEEE Tr. on Inf. Theory 59 (2013), 2527–2630

    work page 2013

  10. [10]

    van Dijk, On the information rate of perfect secret sh aring schemes, Des., Codes and Crypt

    M. van Dijk, On the information rate of perfect secret sh aring schemes, Des., Codes and Crypt. 6 (1995), 143–160

    work page 1995

  11. [11]

    Farràs, T

    O. Farràs, T. Kaced, S. Martin, C. Padró, Improving the L inear Programming Tech- nique in the Search for Lower Bounds in Secret Sharing. Cryptology ePrint Archive, Report 2017/919,2017; available at https://eprint.iacr.org/20 17/919

    work page 2017

  12. [12]

    Fu, H.-C

    H.-L. Fu, H.-C. Lu, The exact values of the average infor mation ratio for tree-based access structures of perfect secret sharing schemes, Des., Codes and Crypt. 73 (1) (2014), 37–46

    work page 2014

  13. [13]

    Fu, H.-C

    H.-L. Fu, H.-C. Lu, The optimal average information rat io of secret-sharing schemes for the access structures based on unicycle graphs and bipar tite graphs, Disc. Appl. Math. 233 (2017), 131–142

    work page 2017

  14. [14]

    Jackson and K

    W. Jackson and K. M. Martin, Perfect secret sharing sche mes on five participants, Des., Codes and Crypt. 9 (1996), 233–250

    work page 1996

  15. [15]

    Shamir, How to share a secret, Comm

    A. Shamir, How to share a secret, Comm. of the ACM 22 (1979), 612–613

    work page 1979

  16. [16]

    D. R. Stinson, Decomposition construction for secret s haring schemes, IEEE Trans. on Inf. Theory, 40 (1) (1994) pp. 118–125

    work page 1994

  17. [17]

    Sun and B.L

    H.L. Sun and B.L. Chen, Weighted decomposition constru ction for perfect secret sharing schemes, Comp. and Math. with Appl. 43 (2002), 877–887. 9

    work page 2002