Improved Bounds on the Threshold Gap in Ramp Secret Sharing

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

4 Downloads (Pure)

Resumé

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.

OriginalsprogEngelsk
Artikelnummer8654006
TidsskriftI E E E Transactions on Information Theory
Vol/bind65
Udgave nummer7
Sider (fra-til)4620-4633
Antal sider14
ISSN0018-9448
DOI
StatusUdgivet - 1 jul. 2019

Fingerprint

privacy
reconstruction

Citer dette

@article{524125cb726348a6ac429018c1f0486c,
title = "Improved Bounds on the Threshold Gap in Ramp Secret Sharing",
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.",
keywords = "Cryptography, linear codes, secret sharing, threshold gap",
author = "Ignacio Cascudo and Gundersen, {Jaron Skovsted} and Diego Ruano",
year = "2019",
month = "7",
day = "1",
doi = "10.1109/TIT.2019.2902151",
language = "English",
volume = "65",
pages = "4620--4633",
journal = "I E E E Transactions on Information Theory",
issn = "0018-9448",
publisher = "IEEE",
number = "7",

}

Improved Bounds on the Threshold Gap in Ramp Secret Sharing. / Cascudo, Ignacio; Gundersen, Jaron Skovsted; Ruano, Diego.

I: I E E E Transactions on Information Theory, Bind 65, Nr. 7, 8654006, 01.07.2019, s. 4620-4633.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

TY - JOUR

T1 - Improved Bounds on the Threshold Gap in Ramp Secret Sharing

AU - Cascudo, Ignacio

AU - Gundersen, Jaron Skovsted

AU - Ruano, Diego

PY - 2019/7/1

Y1 - 2019/7/1

N2 - 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.

AB - 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.

KW - Cryptography

KW - linear codes

KW - secret sharing

KW - threshold gap

UR - http://www.scopus.com/inward/record.url?scp=85067632060&partnerID=8YFLogxK

U2 - 10.1109/TIT.2019.2902151

DO - 10.1109/TIT.2019.2902151

M3 - Journal article

VL - 65

SP - 4620

EP - 4633

JO - I E E E Transactions on Information Theory

JF - I E E E Transactions on Information Theory

SN - 0018-9448

IS - 7

M1 - 8654006

ER -