Paper 2023/1017

Stronger Lower Bounds for Leakage-Resilient Secret Sharing

Charlotte Hoffmann, Institute of Science and Technology Austria
Mark Simkin, Ethereum Foundation

Threshold secret sharing allows a dealer to split a secret $s$ into $n$ shares, such that any $t$ shares allow for reconstructing $s$, but no $t-1$ shares reveal any information about $s$. Leakage-resilient secret sharing requires that the secret remains hidden, even when an adversary additionally obtains a limited amount of leakage from every share. Benhamouda et al. (CRYPTO'18) proved that Shamir's secret sharing scheme is one bit leakage-resilient for reconstruction threshold $t\geq0.85n$ and conjectured that the same holds for $t=c\cdot n$ for any constant $0\leq c\leq1$. Nielsen and Simkin (EUROCRYPT'20) showed that this is the best one can hope for by proving that Shamir's scheme is not secure against one-bit leakage when $t=c\cdot n/\log(n)$. In this work, we strengthen the lower bound of Nielsen and Simkin. We consider noisy leakage-resilience, where a random subset of leakages is replaced by uniformly random noise. We prove a lower bound for Shamir's secret sharing, similar to that of Nielsen and Simkin, which holds even when a constant fraction of leakages is replaced by random noise. To this end, we first prove a lower bound on the share size of any noisy-leakage-resilient sharing scheme. We then use this lower bound to show that there exist universal constants $c_1,c_2$, such that for infinitely many $n$, it holds that Shamir's secret sharing scheme is not noisy-leakage-resilient for $t\leq c_1\cdot n/\log(n)$, even when a $c_2$ fraction of leakages are replaced by random noise.

Available format(s)
Publication info
Published elsewhere. Minor revision. LATINCRYPT 2023
Threshold Secret SharingNoisy Leakage-ResilienceLower BoundsShamir’s Secret Sharing Scheme
Contact author(s)
charlotte hoffmann @ ist ac at
mark simkin @ ethereum org
2023-09-15: revised
2023-06-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Charlotte Hoffmann and Mark Simkin},
      title = {Stronger Lower Bounds for Leakage-Resilient Secret Sharing},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1017},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.