Paper 2023/1017
Stronger Lower Bounds for LeakageResilient Secret Sharing
Abstract
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 $t1$ shares reveal any information about $s$. Leakageresilient 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 leakageresilient 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 onebit leakage when $t=c\cdot n/\log(n)$. In this work, we strengthen the lower bound of Nielsen and Simkin. We consider noisy leakageresilience, 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 noisyleakageresilient 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 noisyleakageresilient for $t\leq c_1\cdot n/\log(n)$, even when a $c_2$ fraction of leakages are replaced by random noise.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Minor revision. LATINCRYPT 2023
 Keywords
 Threshold Secret SharingNoisy LeakageResilienceLower BoundsShamir’s Secret Sharing Scheme
 Contact author(s)

charlotte hoffmann @ ist ac at
mark simkin @ ethereum org  History
 20230915: revised
 20230630: received
 See all versions
 Short URL
 https://ia.cr/2023/1017
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/1017, author = {Charlotte Hoffmann and Mark Simkin}, title = {Stronger Lower Bounds for LeakageResilient Secret Sharing}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1017}, year = {2023}, url = {https://eprint.iacr.org/2023/1017} }