Paper 2018/099
Improved Bounds on the Threshold Gap in Ramp Secret Sharing
Ignacio Cascudo and 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)
- 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