Abstract
A secretsharing scheme enables a dealer, holding a secret string, to distribute shares to parties such that only predefined authorized subsets of parties can reconstruct the secret. The collection of authorized sets is called an access structure. There is a huge gap between the best known upper bounds on the share size of a secretsharing scheme realizing an arbitrary access structure and the best known lower bounds on the size of these shares. For an arbitrary nparty access structure, the best known upper bound on the share size is 2^{O(n)}. On the other hand, the best known lower bound on the total share size is much smaller, i.e., Ω(n²/log(n)) [Csirmaz, Studia Sci. Math. Hungar.]. This lower bound was proved more than 25 years ago and no major progress has been made since.
In this paper, we study secretsharing schemes for khypergraphs, i.e., for access structures where all minimal authorized sets are of size exactly k (however, unauthorized sets can be larger). We consider the case where k is small, i.e., constant or at most log(n). The trivial upper bound for these access structures is O(n⋅ binom(n1,k1)) and this can be slightly improved. If there were efficient secretsharing schemes for such khypergraphs (e.g., 2hypergraphs or 3hypergraphs), then we would be able to construct secretsharing schemes for arbitrary access structures that are better than the best known schemes. Thus, understanding the share size required for khypergraphs is important. Prior to our work, the best known lower bound for these access structures was Ω(n log(n)), which holds already for graphs (i.e., 2hypergraphs).
We improve this lower bound, proving a lower bound of Ω(n^{21/(k1)}/k) on the total share size for some explicit khypergraphs, where 3 ≤ k ≤ log(n). For example, for 3hypergraphs we prove a lower bound of Ω(n^{3/2}). For log(n)hypergraphs, we prove a lower bound of Ω(n²/log(n)), i.e., we show that the lower bound of Csirmaz holds already when all minimal authorized sets are of size log(n). Our proof is simple and shows that the lower bound of Csirmaz holds for a simple variant of the access structure considered by Csirmaz. Using our results, we prove a near quadratic separation between the required share size for realizing an explicit access structure and the monotone circuit size describing the access structure, i.e., the share size in Ω(n²/log(n)) and the monotone circuit size is O(nlog(n)) (where the circuit has depth 3).
BibTeX  Entry
@InProceedings{beimel:LIPIcs.ITC.2023.16,
author = {Beimel, Amos},
title = {{Lower Bounds for SecretSharing Schemes for kHypergraphs}},
booktitle = {4th Conference on InformationTheoretic Cryptography (ITC 2023)},
pages = {16:116:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772716},
ISSN = {18688969},
year = {2023},
volume = {267},
editor = {Chung, KaiMin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18344},
URN = {urn:nbn:de:0030drops183440},
doi = {10.4230/LIPIcs.ITC.2023.16},
annote = {Keywords: Secret Sharing, Share Size, Lower Bounds, Monotone Circuits}
}
Keywords: 

Secret Sharing, Share Size, Lower Bounds, Monotone Circuits 
Collection: 

4th Conference on InformationTheoretic Cryptography (ITC 2023) 
Issue Date: 

2023 
Date of publication: 

21.07.2023 