Secret sharing schemes work without nearly uniform random bits
Secret Sharing from Non-Extractable Randomness
Cryptography and Security
Summary
Traditionally, sharing secret information securely required randomness that you could extract nearly uniformly. This paper challenges that assumption by showing it’s possible to build secret sharing schemes using imperfect random sources where no single bit looks close to random. The authors construct secret sharing methods that are perfectly private and correct, even when the underlying randomness is not extractable. This means secure sharing of secrets doesn’t always demand perfect randomness.
What this means in practice
- •For cryptographic engineers: Design secret sharing protocols that guarantee perfect privacy using imperfect randomness sources that do not yield nearly uniform bits.
- •For hardware security teams: Build cryptographic modules that implement secret sharing without needing high-quality randomness extractors, easing hardware constraints on random number generation.
A theory result. No direct application yet.
Authors
Divesh Aggarwal
Abstract
Bosley and Dodis (TCC 2007) proved that a class of imperfect randomness sources that suffices for information-theoretic encryption of messages longer than the logarithm of the key length must admit deterministic extraction of nearly uniform bits, and asked whether the same is true of two-out-of-two secret sharing. Aggarwal, Chung, Obremski, and Ribeiro (TCC 2022) gave a positive answer for schemes that are in addition leakage-resilient or non-malleable; the original question remained open. We answer it in the negative. For every $b\ge2$ we construct a class of flat sources on $\{0,1\}^{b+2}$, each of min-entropy at least $b$, together with a perfectly correct and perfectly private two-out-of-two scheme that shares a $b$-bit secret into two $(b+1)$-bit shares using any source in the class, and we show that every deterministic map from $\{0,1\}^{b+2}$ to $\{0,1\}$ is at statistical distance at least $1/6$ from uniform on some source in the class. This implies that sharing a long enough secret does not require extractable randomness. The proof is a short parity argument. The idea of the construction extends to other thresholds: for two-out-of-$n$ and $r$-out-of-$r$ sharing we give perfect schemes with $(b+1)$-bit shares, private for classes of flat sources from which no single bit can be extracted with error below $1/(4n-2)$ and $1/(2(2^r-1))$, respectively.