Cryptology ePrint Archive: Report 2019/181

Lower Bounds for Leakage-Resilient Secret Sharing

Jesper Buus Nielsen and Mark Simkin

Abstract: Threshold secret sharing allows a dealer to split a secret into $n$ shares such that any authorized subset of cardinality at least $t$ of those shares efficiently reveals the secret, while at the same time any unauthorized subset of cardinality less than $t$ contains no information about the secret. Leakage-resilience additionally requires that the secret remains hidden even if one is given a bounded amount of additional leakage from every share.

In this work, we study leakage-resilient secret sharing schemes and prove a lower bound on the share size and the required amount of randomness of any information-theoretically secure scheme. We prove that for any information-theoretically secure leakage-resilient secret sharing scheme either the amount of randomness across all shares or the share size has to be linear in $n$. More concretely, for a secret sharing scheme with $p$-bit long shares, $\ell$-bit leakage per share, where $\widehat{t}$ shares uniquely define the remaining $n - \widehat{t}$ shares, it has to hold that $$ p \ge \frac{\ell (n - t)}{\widehat{t}}\ . $$

We use this lower bound to gain further insights into a question that was recently posed by Benhamouda et al. (CRYPTO'18), who ask to what extend existing regular secret sharing schemes already provide protection against leakage. The authors proved that Shamir's secret sharing is $1$-bit leakage-resilient for reconstruction thresholds $t \geq 0.85n$ and conjectured that it is also $1$-bit leakage-resilient for any other threshold that is a constant fraction of the total number of shares. We do not disprove their conjecture, but show that it is the best one could possibly hope for. Concretely, we show that for large enough $n$ and any constant $0< c < 1$ it holds that Shamir's secret sharing scheme is \emph{not} leakage-resilient for $t \leq \frac{cn}{\log n}$.

In contrast to the setting with information-theoretic security, we show that our lower bound does not hold in the computational setting. That is, we show how to construct a leakage-resilient secret sharing scheme in the random oracle model that is secure against computationally bounded adversaries and violates the lower bound stated above.

Category / Keywords: foundations / Lower Bound, Secret Sharing, Leakage-Resilience

Date: received 19 Feb 2019, last revised 13 Dec 2019

Contact author: jbn at cs au dk, simkin at cs au dk

Available format(s): PDF | BibTeX Citation

Version: 20191213:152523 (All versions of this report)

Short URL: ia.cr/2019/181