Improved Bounds on the Threshold Gap in Ramp Secret Sharing

In this paper, we consider linear secret sharing schemes over a finite field F q , where the secret is a vector in Fℓ q and each of the n shares is a single element of 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 ℓ ≳ 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.This work is supported by the Danish Council for Independent Research, grant DFF-4002- 00367, the Spanish Ministry of Economy/FEDER: grants MTM2015-65764-C3-2-P, MTM2015-69138- REDT, and RYC-2016-20208 (AEI/FSE/UE), and Junta de CyL (Spain): grant VA166G1