Secret Sharing with Additive Access Structures from Correlated Random Variables
David Miller, Rémi A. Chou · 2026
Read Secret Sharing with Additive Access Structures from Correlated Random Variables by David Miller, Rémi A. Chou (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-09640.txt.
Introduction
David Miller and Rémi A. Chou extend secret sharing to groups that grow over time. Their 2026 arXiv paper builds schemes on correlated randomness and public communication. Secret sharing splits a secret so that only approved sets of participants can rebuild it.
Earlier correlated-randomness models assumed a fixed access structure. The new additive version lets any subset of participants join the approved set at each time step. The dealer learns of each change only when it happens. Such flexible schemes fit real teams, where who is trusted changes as projects evolve.
Catalog record
| CREATOR | David Miller, Rémi A. Chou |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 43 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-09640
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Secret Sharing with Additive Access Structures from Correlated Random Variables Thanks: This work was supported in part by NSF grant CCF-2047913 and CCF-2401373. David Miller, Rémi A. Chou Abstract We generalize secret-sharing models that rely on correlated randomness and public communication, originally designed for a fixed access structure, to support a sequence of dynamic access structures, which we term an Additive Access Structure. Specifically, the access structure is allowed to monotonically grow by having any subset of participants added to it at a given time step, and the dealer only learns of these changes to the access structure on the time step that they occur. For this model, we prove the existence of a secret sharing strategy that achieves the same secret rate at each time step as the best known strategy for the fixed access structure version of this model. We also prove that there exists a strategy that is capacity-achieving at any time step where the access structure is a threshold access structure. I Introduction Secret Sharing is the problem of distributing private pieces of information called shares to a set of participants such that the combined shares of an authorized subset of participants gives enough information to recover a secret, but the combined shares of an unauthorized subset of participants reveals no information about this secret. Since secret sharing was introduced in [ 18 ] , it has seen a wide variety of applications such as secure multiparty computation [ 3 ] , Byzantine agreement [ 16 ] , threshold cryptography [ 9 ] , and generalized oblivious transfer [ 19 ] . Most of the work on secret sharing has focused on models where shares are distributed using private channels, e.g., [ 1 ] . In these models, efficiency is measured by minimizing the share size relative to the secret size. There is also existing work on secret sharing that replaces private channels with correlated randomness combined with a public channel [ 26 , 5 , 7 , 17 ] . In this line of work, efficiency is quantified by the secret rate, defined as the size of the shared secret normalized by the number of source observations. However, in both of these models, the strategies assume the access structure remains fixed. If the access structure were to change, all of the shares would have to be recreated, potentially leading to inefficiency. Instead, if shares were able to be reused as the access structure changed, this inefficiency could be mitigated. For instance, this idea is pursued by [ 12 ] which introduced the Evolving Access Structure (EAS): a model where shares are distributed to participants as they join the system and the access structure can grow monotonically by adding authorized groups formed with the participant that most recently joined. Further work on the EAS includes [ 13 , 11 , 10 ] . In this paper, instead of considering a model where participants join one by one over time, and have shares communicated to them over a private channel, we consider a model where all the participants are part of the model initially, shares are produced by a correlated source of randomness, and the dealer communicates to the participants using a public channel. We call our model an Additive Access Structure (AAS) to distinguish it from the EAS since it differs in two major ways. First, there is no notion of participants joining, and as a result, there is no restriction on which subsets of participants can be added to the access structure at a given time step. Second, since all the shares are created simultaneously from a correlated source of randomness, such as channel gain measurements obtained in a wireless communication network [ 24 , 23 , 25 , 14 ] , public messages are the mechanism used to allow newly authorized groups to gain enough information to recover the shared secret. More specifically, our model for secret sharing can be described as follows. Initially, the dealer and each participant observe independent and identically distributed realizations of a correlated source of randomness and the access structure will begin with no authorized groups. Whenever one or more authorized groups are added to the access structure at a given time step, the dealer will learn the new access structure, determine a secret to be shared, and send message to every participant over a public, noiseless, authenticated channel. Since this is an iterative process, we will define an AAS as the sequence of access structures produced by adding authorized groups, and have each access structure in the AAS indexed by the time step it is produced. For example, consider the case where there are four participants \mathcal{L}=\{1,2,3,4\} . At the first time step, it might be decided that the group \{1,2,4\} should become authorized. This will make the access structure at t=1 the pair (\mathbb{A}_{1},\mathbb{U}_{1}) where \mathbb{A}_{1}=\{\{1,2,4\},\{1,2,3,4\}\} and \mathbb{U}_{1}=2^{\mathcal{L}}\backslash\mathbb{A}_{1} . The dealer, with the knowledge of (\mathbb{A}_{1},\mathbb{U}_{1}) , will then determine the secret S_{1} to be shared, and the message M_{1} to be sent. Then, at t=2 , it might be decided the group \{2,3\} should become authorized giving \mathbb{A}_{2}=\mathbb{A}_{1}\cup\{\{2,3\},\{1,2,3\},\{2,3,4\},\{1,2,3,4\}\} and \mathbb{U}_{2}=2^{\mathcal{L}}\backslash\mathbb{A}_{2} . Now, the dealer having learned about (\mathbb{A}_{2},\mathbb{U}_{2}) and knowing the message M_{1} that was previously sent, will determine a new secret S_{2} to be shared, and a new message M_{2} to be sent. This process could continue for as long as there are groups which are not yet authorized, but importantly cannot go on forever since 2^{\mathcal{L}} is finite. If no more groups were added to the access structure after t=2 , the AAS would be the sequence ((\mathbb{A}_{1},\mathbb{U}_{1}),(\mathbb{A}_{2},\mathbb{U}_{2})) . A secret rate tuple for the dealer’s strategy will be considered achievable if at each time step every authorized group, using their observations and all public messages, can determine the secret for that time step with near certainty and if every unauthorized group, using their observations and all public messages, learns a negligible amount of information about the secret. We then prove the surprising result that there exists a secret sharing strategy for an AAS where the secret rate achievable at a given time step is independent of the access structures at all other time steps, and that this secret rate matches the best known achievable secret rate for a fixed access structure [ 5 ] . Additionally, we prove that at any time step where the access structure forms a threshold access structure, the secret rate at that time step is equal to the secret sharing capacity of that threshold access structure. For the threshold AAS case, i.e., when at each time step one has a threshold access structure, it means that a dealer who is omniscient and knows the full AAS before sending any public messages has no advantage over a dealer who has to commit to a message at the current time step before learning which subsets of participants will be added to the access structure in the next time step. In our achievability proof, we introduce a novel adaptation of random binning in which the number of binnings is quantized. This modification enables us to establish the existence of a single secret sharing strategy that is fully specified a priori and