Improved Bounds on the Threshold Gap in Ramp Secret Sharing

Ignacio Cascudo; Jaron Skovsted Gundersen; Diego Ruano

Paper 2018/099

Improved Bounds on the Threshold Gap in Ramp Secret Sharing

Ignacio Cascudo, Jaron Skovsted Gundersen, and Diego Ruano

Abstract

In this paper we consider linear secret sharing schemes over a finite field $\mathbb{F}_q$, where the secret is a vector in $\mathbb{F}_q^\ell$ and each of the $n$ shares is a single element of $\mathbb{F}_q$. We obtain lower bounds on the so-called threshold gap $g$ of such schemes, defined as the quantity $r-t$ where $r$ is the smallest number such that any subset of $r$ shares uniquely determines the secret and $t$ is the largest number such that any subset of $t$ shares provides no information about the secret. Our main result establishes a family of bounds which are tighter than previously known bounds for $\ell\geq 2$. Furthermore, we also provide bounds, in terms of $n$ and $q$, on the partial reconstruction and privacy thresholds, a more fine-grained notion that considers the amount of information about the secret that can be contained in a set of shares of a given size. Finally, we compare our lower bounds with known upper bounds in the asymptotic setting.

Note: Accepted at IEEE Transactions on Information Theory. IEEE early access version available at https://ieeexplore.ieee.org/document/8654006

Metadata

Available format(s): PDF
Publication info: Published elsewhere. IEEE Transactions on Information Theory
DOI: 10.1109/TIT.2019.2902151
Keywords: Secret Sharing
Contact author(s): jaron @ math aau dk
History: 2019-03-04: revised; 2018-01-29: received; See all versions
Short URL: https://ia.cr/2018/099
License: CC BY

BibTeX

@misc{cryptoeprint:2018/099,
      author = {Ignacio Cascudo and Jaron Skovsted Gundersen and Diego Ruano},
      title = {Improved Bounds on the Threshold Gap in Ramp Secret Sharing},
      howpublished = {Cryptology ePrint Archive, Paper 2018/099},
      year = {2018},
      doi = {10.1109/TIT.2019.2902151},
      note = {\url{https://eprint.iacr.org/2018/099}},
      url = {https://eprint.iacr.org/2018/099}
}