Realize General Access Structure Based on Single Share

Yang Xie, Sijjad Ali, Fuyou Miao, Keju Meng

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:

  1. Information Rate: The shares are significantly larger than the secret itself.
  2. 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

Abstract

Traditional (t, n)-threshold secret sharing cannot realize all access structures of secret sharing. So, the paper introduced the concept of secret sharing scheme to realize general access structure. But this scheme has to send multiple shares to each trustee. This paper proposed two new secret sharing schemes realizing general access structures by only assigning one share to each trustee. The proposed second scheme is a perfect secret sharing scheme. Furthermore, these schemes can realize any access structures.
BibTeX
@inproceedings{xie2017realize,
  author = {Yang Xie and Sijjad Ali and Fuyou Miao and Keju Meng},
  title = {{Realize General Access Structure Based on Single Share}},
  booktitle = {2017},
  year = {2017},
  doi = {10.1109/icctec.2017.00310},
}
Figure