Secret sharing with weak privacy
Deniability instead of secrecy, as a tractable proxy for stuck share-size bounds
Motivation
The central quantitative question about secret sharing has barely moved in thirty years. For a general monotone access structure on \(n\) parties, the best known lower bound on share size is \(\Omega(n/\log n)\) and the best known upper bounds are exponentially larger, and recent progress has narrowed the gap only at the upper end. The same is true for information-theoretic MPC: exponential gaps between what is provably necessary and what is achievable.
One response is to weaken the security requirement until the question becomes combinatorial, and see whether the gap closes there. Weak privacy is that weakening: an unauthorized set must not be able to rule any secret out — every view it can see must have probability at least \(p\) times its probability under any other secret — but it may learn a great deal short of that. Lower bounds in this model are typically easy when they exist, so a strong upper bound rules out the combinatorial route to a perfect-privacy lower bound, and a stubborn absence of upper bounds suggests the barrier is combinatorial after all.
Provenance and history
Weak privacy for secret sharing goes back to Beimel and Franklin (TCC 2007), who showed that \(2\)-out-of-\(n\) threshold sharing of a one-bit secret needs \(\Theta(\log n)\) bits per share with perfect privacy but only \(2\) bits with \(1/n\)-weak privacy — a whole logarithmic factor bought by the relaxation. The notion is the same as pure differential privacy up to reparameterization (\(p\)-WP is \(\varepsilon\)-DP with \(\varepsilon = \ln(1/p)\)), except that all pairs of secrets are compared rather than neighbouring ones, and the interesting regime is small \(p\) rather than constant.
Beimel, Ishai, Kushilevitz and Li, Cryptography with Weak Privacy (IACR ePrint 2025/1978), make it a systematic programme across secret sharing, decomposable randomized encodings and MPC. They give WP constructions for general access structures and for restricted families, a matching negative result for decomposable randomized encodings, and — perhaps the most surprising part — a boosting theorem: under standard LPN, any \(p\)-WP scheme with inverse-polynomial \(p\) yields a computationally secure scheme for a related access structure, which turns their WP upper bounds into a super-polynomial share-size improvement for a natural family. Their open-problems list is where the threshold question below comes from.
Parameter lattice
Threshold against privacy notion, sharing a one-bit secret.
| Perfect privacy | Weak privacy | |
|---|---|---|
| \(2\)-out-of-\(n\) | \(\Theta(\log n)\) | \(2\) bits at \(p = 1/n\) (Beimel–Franklin) |
| \(3 \le t \le n-2\) | \(\Theta(\log n)\) | unstated: the source records only that large thresholds are open |
| \((n-1)\)-out-of-\(n\) | \(\Theta(\log n)\) | c/0075 — open whether \(o(\log n)\) is possible |
| General access structures | \(\Omega(n/\log n)\) lower bound, exponential upper bounds | polynomial share size known; \(o(n)\) open, and the largest admissible \(p\) open |