Welcome to the resource topic for 2023/805
Title:
New Bounds on the Local Leakage Resilience of Shamir’s Secret Sharing Scheme
Authors: Ohad Klein, Ilan Komargodski
Abstract:We study the local leakage resilience of Shamir’s secret sharing scheme. In Shamir’s scheme, a random polynomial f of degree t is sampled over a field of size p>n, conditioned on f(0)=s for a secret s. Any t shares (i, f(i)) can be used to fully recover f and thereby f(0). But, any t-1 evaluations of f at non-zero coordinates are completely independent of f(0). Recent works ask whether the secret remains hidden even if say only 1 bit of information is leaked from each share, independently. This question is well motivated due to the wide range of applications of Shamir’s scheme. For instance, it is known that if Shamir’s scheme is leakage resilient in some range of parameters, then known secure computation protocols are secure in a local leakage model.
Over characteristic 2 fields, the answer is known to be negative (e.g., Guruswami and Wootters, STOC '16). Benhamouda, Degwekar, Ishai, and Rabin (CRYPTO '18) were the first to give a positive answer assuming computation is done over prime-order fields. They showed that if t \ge 0.907n, then Shamir’s scheme is leakage resilient. Since then, there has been extensive efforts to improve the above threshold and after a series of works, the current record shows leakage resilience for t\ge 0.78n (Maji et al., ISIT '22). All existing analyses of Shamir’s leakage resilience for general leakage functions follow a single framework for which there is a known barrier for any t \le 0.5 n.
In this work, we a develop a new analytical framework that allows us to significantly improve upon the previous record and obtain additional new results. Specifically, we show:
\bullet Shamir’s scheme is leakage resilient for any t \ge 0.69n.
\bullet If the leakage functions are guaranteed to be balanced'' (i.e., splitting the domain of possible shares into 2 roughly equal-size parts), then Shamir's scheme is leakage resilient for any $t \ge 0.58n$. $\bullet$ If the leakage functions are guaranteed to be unbalanced’’ (i.e., splitting the domain of possible shares into 2 parts of very different sizes), then Shamir’s scheme is leakage resilient as long as t \ge 0.01 n. Such a result is provably impossible to obtain using the previously known technique.
All of the above apply more generally to any MDS codes-based secret sharing scheme.
Confirming leakage resilience is most important in the range t \leq n/2, as in many applications, Shamir’s scheme is used with thresholds t\leq n/2. As opposed to the previous approach, ours does not seem to have a barrier at t=n/2, as demonstrated by our third contribution.
ePrint: https://eprint.iacr.org/2023/805
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .