TL;DR
This paper introduces novel secret sharing schemes designed for scenarios where the set of participants is not fixed and can grow indefinitely. They achieve this by developing efficient constructions for evolving access structures, particularly for threshold schemes, and establish tight bounds on share sizes, even connecting the 2-threshold case to prefix codes.
What Problem Does This Paper Address?
Traditional secret sharing schemes require the total number of participants to be known in advance. This is a significant limitation in dynamic environments where participants join over time, potentially an infinite number. The challenge is to design schemes where the share size for each arriving participant is minimized, and the overall system remains secure and efficient as the participant pool grows. The paper addresses this by introducing the concept of "evolving access structures" and developing schemes that adapt to this dynamic setting.
Methods
The paper's core contribution lies in its novel constructions for evolving access structures. For general evolving access structures, they propose a scheme where the t-th party receives a share of size $2^{t-1}$ bits. For the more specific evolving k-threshold access structure, they develop more efficient schemes. A key technique is "domain reduction" through generations, where parties are grouped, and a combination of standard threshold schemes and recursive composition is used to manage share sizes. For the 2-threshold case, they establish a direct equivalence with prefix codes, leveraging existing prefix code constructions (like Elias's) to achieve optimal share sizes.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- The "Infinite" Participant Problem: The paper tackles the practical problem of secret sharing in systems where the number of participants isn't fixed, a common scenario in distributed systems and cloud environments.
- Evolving Access Structures: The formalization of "evolving access structures" is crucial, allowing for a principled approach to dynamic participant sets.
- Prefix Codes and 2-Threshold Secret Sharing: The surprising and tight connection between prefix codes and the 2-threshold evolving secret sharing problem is a significant theoretical result, providing both constructive and lower-bound implications.
- Domain Reduction via Generations: The use of generations to manage share sizes in k-threshold schemes is an elegant technique that balances efficiency with the growing number of participants.
- Optimality for 2-Threshold: The paper demonstrates that for the 2-threshold case, their scheme is essentially optimal, matching theoretical lower bounds.
Key Results
- General Evolving Access Structures: A scheme for any evolving access structure where the t-th party's share size is $2^{t-1}$ bits.
- Evolving k-Threshold Access Structure: A scheme for an l-bit secret where the t-th party's share size is $(k-1) \log t + \text{poly}(k, l) \cdot o(\log t)$.
- Evolving 2-Threshold Access Structure:
- An optimal scheme with share size $\log t + 2 \log \log t + O(1)$ bits.
- A tight connection to prefix codes, showing that the existence of a prefix code with codeword lengths $\sigma(t)$ is equivalent to a secret sharing scheme with share size $\sigma(t)$.
- A linear scheme with share size $\log t + (l+1) \log \log t + O(l)$ for l-bit secrets.
Limitations and Future Work
- General Access Structures: The scheme for general evolving access structures has an exponential share size ($2^{t-1}$), which is noted as being similar to the limitations of classical schemes. The paper poses the open problem of proving the necessity of exponential shares for certain evolving access structures.
- k-Threshold Scheme Dependency: While the k-threshold scheme is efficient in $t$, the dependency on $k$ is polynomial. The paper questions whether more algebraic constructions could reduce this dependency.
- Generalizations: The authors suggest exploring generalizations of prefix codes for $k > 2$, the utility of evolving secret sharing in multi-party computation, and relaxing security/correctness to probabilistic or statistical notions. They also raise the question of computationally secure evolving secret sharing.
Summary updated