PaperlayerView exact revision on arXiv

Source-linked AI summary

Secret Sharing from Non-Extractable Randomness

Divesh Aggarwal

arXiv:2610.20173v1cs.CR

TL;DR

Whether two-out-of-two secret sharing of long secrets requires extractable randomness remained open. The paper constructs perfectly private schemes over high-entropy sources and proves a constant lower bound on deterministic one-bit extraction error.

  • Problem

    Whether two-out-of-two secret sharing of long secrets requires extractable randomness remained open [BD07, Section 5].

    Source: §1 · p. 2

  • Method

    A parity argument analyzes a key-labeling extractor against sources whose allowed keys make either a central-key choice or a left-right pair choice at each index.

    Source: §1.2 · p. 4

  • Results

    At least 1/6 statistical error: every deterministic one-bit extractor fails on some source in the constructed class.

    Source: §1.2 · p. 4

  • Takeaways & Limitations

    Perfectly private sharing of long secrets can use high-entropy sources that do not support deterministic one-bit extraction with error below 1/6.

    Source: §1.1 · p. 2, §1.2 · p. 4

    The two-out-of-n extension is stated for n ≥2 and 2b > n.

    Source: §4.1 · p. 8

Abstract

from arXiv · show

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.

1 Introduction

The paper asks whether two-out-of-two secret sharing of long secrets requires extractable randomness, as information-theoretic encryption does. It answers no with perfectly private schemes for high-entropy source classes that defeat every deterministic one-bit extractor.

1 Introduction

  • Two-out-of-two secret sharing is a weaker primitive than encryption, and whether sharing long secrets requires extraction remained open [BD07, Section 5].Prior positive results apply when schemes additionally resist one-bit local leakage or are non-malleable.Source: §1 · p. 2

1.1 Our results

  • For every b ≥2, the paper constructs a perfectly correct and private scheme for b-bit secrets using (b + 1)-bit shares, while every deterministic one-bit extractor has error at least 1/6 on some source.The sources are flat and have min-entropy at least b; the paper also extends the separation to two-out-of-n and r-out-of-r sharing.Source: §1.1 · pp. 2–3

1.2 Technical overview

  • A three-key gadget makes each source choose either a central key or a left-right pair at every index, enabling private sharing while supporting a parity-based extractor lower bound.For any labeling of keys, the two choices at each index differ by an odd signed sum, forcing one valid source to have statistical error at least 1/6.Source: §1.2 · p. 4

1.3 Related work

  • Earlier separations concern one-bit messages or small-message encryption [DS02, DPP06, BD07]; this work addresses long-secret ordinary sharing, while prior extraction results require added leakage resilience or non-malleability.The paper also distinguishes its deterministic extraction question from a weaker extraction consequence for sharing [DY15, Definition 9, Theorem 4(c), and Remark 2].Source: §1.3 · p. 5

2 Definitions

The section defines sharing from a source class and the correctness, privacy, and extraction notions used to analyze it.

2 Definitions

  • Extraction error measures the statistical distance of the extractor’s output from uniform, and a class is extractable when one extractor achieves the stated error bound across it.Projecting an ℓ-bit extractor’s output to its first bit does not increase the error, so a one-bit lower bound applies to every output length.Source: §2 · pp. 5–6
  • A source class is a fixed family of distributions on the dealer’s key, and one scheme must be private for every distribution in that class.A deterministic extractor must likewise work for every distribution in the class.Source: §2 · pp. 5–6
  • A threshold-sharing scheme maps a message and key to shares and provides reconstruction from every qualifying set of parties.The dealer samples one key from an unknown class member; the scheme uses no other randomness.Source: §2 · p. 5
  • Perfect correctness requires reconstruction of every message from every qualifying party set on every key, while privacy requires smaller coalitions’ views not to depend on the message.For two-out-of-two sharing, the individual share maps are denoted F and G.Source: §2 · pp. 5–6

3 The construction

The construction uses three key types at each index to share a message correctly and privately across a class of flat sources. A parity argument gives a one-bit extraction lower bound, and the construction extends to the full bit-string key domain.

3 The construction

  • For each index, the source contains either the central key or both side keys, and each resulting source is flat with min-entropy at least b.The scheme shares b-bit messages using keys indexed by V = F2^b.Source: §3 · p. 6

3.1 Correctness, privacy, and non-extractability

  • The tag pattern lets reconstruction identify the key branch and recover the message for every key.When neither share is tagged, the two untagged shares determine the message using α ≠ 0, 1.Source: §3.1 · p. 6
  • For every source, each party’s share distribution is independent of the message, so the scheme is perfectly private.The untagged values and tagged values have source-dependent probabilities, but their support does not depend on the message.Source: §3.1 · pp. 6–7
  • Every deterministic bit extractor has error at least 1/6 on some source in the class or its complement.The proof uses the parity of a signed sum over the three keys at each index.Source: §3.1 · p. 7

3.2 Bit strings and running time

  • The key encoding extends the construction to {0, 1}^(b+2), and the leakage example yields a nontrivial linear functional of the secret.The fourth key branch is never used by the source class; one-bit leakage from each share can nevertheless reveal a secret-dependent functional.Source: §3.2 · pp. 7–8

4 Two-out-of-n sharing

The construction extends the two-party scheme to two-out-of-n sharing. It achieves perfect correctness and privacy while retaining a lower bound on deterministic one-bit extraction.

4.1 The construction

  • At each index, the source selects either all n − 1 central keys or all n side keys, and the scheme assigns tagged dummy shares or untagged message-dependent shares.The central keys differ only as keys and give every party its true share.Source: §4.1 · p. 8
  • For n ≥ 2 and 2b > n, the scheme is perfectly correct and private for a class of flat sources with min-entropy at least b + log(n − 1).Each share has b + 1 bits, and the one-bit extraction bound is 1/(4n − 2).Source: §4.1 · pp. 8–9, §4.2 · p. 9

4.2 Correctness, privacy, and non-extractability

  • Any two distinct parties can reconstruct the message from their shares for every key.The tag pattern identifies whether one share is a dummy; when neither is tagged, the two untagged values determine the message.Source: §4.2 · p. 9
  • Every party’s share distribution is independent of the message, although it is uniform for n = 2 and need not be uniform for n ≥ 3.The stated probabilities are (n − 1)/Z_T for each untagged value and 1/Z_T for each tagged value indexed outside T.Source: §4.2 · p. 9
  • For every extractor, some source or its complement gives error at least 1/(4n − 2), and an index-only extractor attains this bound on some source.A set of more than two parties can reconstruct from any two of its members.Source: §4.2 · pp. 9–10

5 r-out-of-r secret sharing

The paper extends the construction to r-out-of-r sharing using keys that activate nonempty subsets of parties. The resulting schemes are perfectly correct and private, yet their source classes do not permit accurate deterministic one-bit extraction.

5 r-out-of-r secret sharing

  • The construction uses keys (u, S), where S is a nonempty subset of activated parties; active parties receive their pad plus a secret-dependent term, while inactive parties receive tagged dummy shares.The pads sum to zero, and every r − 1 parties’ pad values uniquely determine the index u.Source: §5 · p. 10
  • For r ≥ 2 and b ≥ r, the scheme is perfectly correct and private, with b + 1-bit shares and source min-entropy at least (r − 1)b + log(2^(r−1) − 1).Every extractor has error at least 1/(2(2r − 1)) on some source or its complement.Source: §5 · p. 11
  • For r = 2 the extraction bound is 1/6, and for r = 3 it is 1/14; an index-only extractor achieves the bound for some source.The bound is tight for the source class.Source: §5 · pp. 11–12
  • The tags identify the activated set, and the sum of the shares then determines the message because the coefficient of the message is nonzero.Any coalition of fewer than r − 1 parties sees a projection of an r − 1 party view that is independent of the message.Source: §5 · p. 11
  • Every coalition of r − 1 parties has a view whose distribution does not depend on the message, giving perfect privacy.For each nonempty observed tag pattern, exactly one key per index produces it; the empty pattern occurs only at indices in T.Source: §5 · p. 11
  • The r-out-of-r and two-out-of-n constructions are not derivable from the two-out-of-two result through the described distribution-design reductions.Those reductions do not go in the direction needed to obtain these higher-threshold results.Source: §5 · p. 12

Conclusion and Acknowledgments

The authors recount the long-standing conjecture that sources supporting ordinary two-out-of-two secret sharing are extractable, despite repeated failures to prove it or find a counterexample. They also acknowledge assistance from language models in developing the counterexample.

  • DA pursued the question for more than ten years and discussed it with numerous researchers.The acknowledgment names, among others, Yevgeniy Dodis, Maciej Obremski, Eldon Chung, and Siyao Guo.Source: Conclusion and Acknowledgments · p. 12
  • The authors report that attempts to prove the extractability conjecture or find a counterexample both failed.The conjecture was that every source supporting two-out-of-two secret sharing is extractable.Source: Conclusion and Acknowledgments · p. 12
  • In, a straightforward argument showed extractability for sources supporting leakage-resilient or non-malleable schemes.The section describes these as relaxations of ordinary secret sharing.Source: Conclusion and Acknowledgments · p. 12
  • The authors credit ChatGPT 6.0 with finding a counterexample and Claude Fable 5.1 with assisting the paper's writing.DA states that he verified the text to the best of his ability and takes full responsibility for it.Source: Conclusion and Acknowledgments · p. 12

A Comparison with a statement of Yao and Li

The appendix argues that a claimed implication for ordinary secret sharing in is incompatible with Theorem 1.1. It identifies a mismatch with the encryption argument: perfect reconstruction makes full share-tuple distributions for different messages disjoint.

A Comparison with a statement of Yao and Li

  • Theorem 1.1 is incompatible with an implication for ordinary secret sharing in, according to the appendix.The appendix checks its comparison against the published journal version and identifies where the argument departs from the encryption case.Source: A Comparison with a statement of Yao… · p. 14
  • For [YL25], the appendix says perfect reconstruction implies their perfect-binding condition, defined by injectivity of the full share tuple in the message for fixed key.Their construction sets ψ(m, k) to the entire tuple of shares.Source: A Comparison with a statement of Yao… · p. 14
  • The encryption lemma in [BD07] requires full outputs on a fixed message and a uniform message to be close, but perfect reconstruction gives disjoint supports across messages for sharing.Thus, the appendix says substituting the sharing map ψ for encryption in that lemma does not meet its needed condition.Source: A Comparison with a statement of Yao… · p. 14
  • The appendix's reconstruction-based f makes Z (1, 0)-extractable, while [YL25, Proposition 2] would then imply that S_b is (1, δ)-extractable for every δ > 0, contradicting Theorem 1.1 for δ < 1/6.The appendix says the error is in the statement, not only in its proof, and that the same issue affects [YL25, Theorems 5 and 8] for threshold sharing.Source: A Comparison with a statement of Yao… · p. 14
Loading 2610.20173v1…