Paper 2018/143

Conjecturally Superpolynomial Lower Bound for Share Size

Shahram Khazaei

Abstract

Information ratio, which measures the maximum/average share size per shared bit, is a criterion of efficiency of a secret sharing scheme. It is generally believed that there exists a family of access structures such that the information ratio of any secret sharing scheme realizing it is $2^{\Omega(n)}$, where the parameter $n$ stands for the number of participants. The best known lower bound, due to Csirmaz (1994), is $\Omega(n/\log n)$. Closing this gap is a long-standing open problem in cryptology. In this paper, using a technique called \emph{substitution}, we recursively construct a family of access structures having information ratio $n^{\frac{\log n}{\log \log n}}$, assuming a well-stated information-theoretic conjecture is true. Our conjecture emerges after introducing the notion of \emph{convec set} for an access structure, a subset of $n$-dimensional real space. We prove some topological properties about convec sets and raise several open problems.

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
secret sharinginformation-theory
Contact author(s)
shahram khazaei @ gmail com
History
2018-02-14: revised
2018-02-08: received
See all versions
Short URL
https://ia.cr/2018/143
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/143,
      author = {Shahram Khazaei},
      title = {Conjecturally Superpolynomial Lower Bound for Share Size},
      howpublished = {Cryptology ePrint Archive, Paper 2018/143},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/143}},
      url = {https://eprint.iacr.org/2018/143}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.