Abstract
Traditional $(t, n)$-threshold secret sharing schemes are insufficient for complex organizational hierarchies that require General Access Structures (GAS). Historically, GAS implementations have been plagued by "share explosion"—where participants must manage multiple shares—or high computational costs. This paper proposes two novel secret sharing schemes that realize any monotone access structure while assigning exactly one share per participant. The most significant contribution is a "perfect" scheme that achieves an ideal information rate ($\rho = 1$) by utilizing a public matrix and efficient bitwise operations, bypassing the need for expensive polynomial interpolation.
Introduction
In a standard $(t, n)$-threshold secret sharing scheme, a secret is divided among $n$ participants such that any $t$ of them can reconstruct it. However, many real-world scenarios require more granular control. For instance, a corporate vault might require the presence of "one Manager and two Clerks" or "three Clerks" to open. Such requirements constitute a General Access Structure (GAS).
While theoretical models for GAS have existed for decades, they often face practical hurdles. Early schemes required participants to hold a number of shares proportional to the number of authorized subsets they belonged to, leading to significant storage overhead. Later mathematical models based on linear programming were not universally applicable to all access structures. This paper addresses these limitations by providing a universal, single-share solution.
Proposed Schemes
1. The LCM-Based Scheme
The authors' first approach utilizes the Least Common Multiple (LCM) and coprime integers. In this model, the dealer selects a sequence of coprime integers, and each participant’s single share is derived from the product of integers associated with the authorized subsets of which they are a member.
While this scheme successfully limits each participant to one share, it has two primary drawbacks:
- Information Rate: The shares are significantly larger than the secret itself.
- Security Level: It is a "ramp" scheme, meaning that while unauthorized groups cannot fully reconstruct the secret, they may still gain partial information about it.
2. The XOR and Public Matrix Scheme
The paper’s primary contribution is a "perfect" secret sharing scheme that optimizes both storage and computation. This scheme shifts the logic of the access structure from the private shares to a publicly accessible matrix.
Mechanism: * Private Shares: The dealer assigns a single random integer $q_j$ to each participant $p_j$. * The Public Matrix ($D$): For every minimal authorized subset, the dealer constructs a XOR-sum equation that equals the secret $S$. These values are masked using the participants' private shares ($q_j$) through modular addition and then published in a matrix $D$. * Reconstruction: When an authorized group wishes to recover the secret, they use their private shares to unmask the corresponding entries in the public matrix. The resulting values are then XORed to reveal the secret.
Key Insights
Computational Efficiency
Most traditional secret sharing schemes, such as Shamir’s, rely on Lagrange interpolation. While mathematically elegant, interpolation is computationally expensive, especially as the number of participants grows. By replacing these calculations with XOR operations and modular addition, the proposed scheme is significantly faster and more suitable for hardware implementations or low-power devices.
Perfect Security and Ideal Information Rate
The second scheme is "perfect," meaning unauthorized groups gain zero information about the secret. The authors achieve this by performing XOR operations in a different mathematical field than the modular addition used for the public matrix, ensuring the system is unsolvable without the correct private keys. Furthermore, the scheme achieves an ideal information rate ($\rho = 1$), where the size of the private share is exactly equal to the size of the secret.
Results and Performance
The proposed schemes demonstrate that it is possible to realize any monotone access structure without the "share explosion" seen in previous literature.
- Universality: Unlike programming-based models, these schemes are guaranteed to work for any mathematically defined monotone access structure.
- Single Share: Both schemes maintain a strict one-share-per-person policy, simplifying key management for participants.
- Optimization: The second scheme provides a blueprint for high-speed, secure secret sharing in practical environments.
Limitations and Future Work
The primary trade-off in the second scheme is the growth of the public matrix $D$. As the number of minimal authorized subsets increases, the matrix expands. In extremely complex access structures, the storage requirements for this public data could become a bottleneck. Additionally, the scheme assumes the existence of a reliable "bulletin board" or broadcast channel where all participants can access the public matrix.
Future research may focus on optimizing the storage of the public matrix or exploring decentralized methods for distributing the matrix without a central dealer.
Conclusion
By decoupling the access logic from the private shares and utilizing efficient bitwise operations, this paper provides a robust framework for general secret sharing. The transition to a public matrix model allows for an ideal information rate and universal applicability, making it a strong candidate for modern cryptographic applications such as electronic voting and secure group communications.
Summary updated