Quantum Access Structure and Secret Sharing

Chen‐Ming Bai, Zhihui Li, Yongming LiarXiv 2017 · DOI · arXiv

Abstract

In this paper we define a kind of decomposition for a quantum access structure. We propose a conception of minimal maximal quantum access structure and obtain a sufficient and necessary condition for minimal maximal quantum access structure, which shows the relationship between the number of minimal authorized sets and that of the players. Moreover, we investigate the construction of efficient quantum secret schemes by using these techniques, a decomposition and minimal maximal quantum access structure. A major advantage of these techniques is that it allows us to construct a method to realize a general quantum access structure. For these quantum access structures, we present two quantum secret schemes via the idea of concatenation or a decomposition of a quantum access structure. As a consequence, the application of these techniques allow us to save more quantum shares and reduce more cost than the existing scheme.

Introduction

Quantum Secret Sharing (QSS) involves a dealer distributing a quantum secret among a group of players such that only specific authorized subsets can collaborate to recover it. The rules defining these subsets are known as the access structure.

Current QSS research faces two primary hurdles: resource efficiency and verification complexity. Quantum data is expensive to create and maintain, yet existing general schemes often use redundant "threshold cascade" approaches that require a high number of quantum shares. Furthermore, determining if a group is authorized can be computationally intensive if the access structure is bloated with too many minimal authorized sets. This paper addresses these issues by introducing a more compact way to represent and implement these structures.

Methodology and Theoretical Framework

The authors employ two primary theoretical tools: decomposition and minimal maximal access structures. Decomposition allows a complex, general access structure to be broken into smaller, manageable sub-structures. Building on Gottesman’s definition of a "maximal" structure (where authorized and unauthorized sets are perfect complements), the authors define a "minimal" version.

Dynamic adjustment of a minimal maximal quantum access structure when adding or deleting players.

A fundamental theorem proven in the paper states that a maximal access structure is minimal if and only if the number of minimal authorized sets ($r$) equals the number of players ($n$). This $r=n$ condition provides a clear target for optimizing QSS protocols. These structures are also easier to update; as shown in Figure 1, adding or removing a player has a localized effect, making the system robust for dynamic secret sharing.

Using these tools, the authors propose two schemes:

  • Scheme I: Uses an "optimal decomposition" where players hold registers of entangled particles corresponding to different sub-access structures.
  • Scheme II: A concatenation scheme that combines the minimal maximal structure with a $((l, 2l-1))$ quantum threshold scheme, allowing for the realization of general access structures with fewer total shares.

Results and Comparative Analysis

The authors evaluated their approach using comparative benchmarks against the standard Gottesman threshold cascade scheme for 5-player and 6-player scenarios. The results demonstrate a significant reduction in verification overhead.

Comparison of verification times for standard vs. minimal maximal structures.

As detailed in the table above, in a 5-player scenario, the standard maximal structure requires 10 verification sets, while the minimal maximal structure requires only 5. For 6 players, the requirement drops from 11 sets to 6. Beyond verification, the schemes optimize share distribution. For instance, the concatenation method (Scheme II) can realize an access structure using a $((2, 3))$ threshold scheme that previously required a much more cumbersome $((4, 7))$ scheme. These improvements are achieved while maintaining security requirements, ensuring unauthorized sets gain zero information about the secret.

Conclusion and Future Work

This research demonstrates that by "compacting" access structures into minimal maximal forms, QSS can become significantly more efficient. While the theoretical framework is robust, future work is needed to address the physical implementation challenges, such as the impact of quantum noise (decoherence) on these specific decompositions. Additionally, finding an "optimal decomposition" for arbitrary, highly complex access structures remains a non-trivial computational task that warrants further investigation into automated search algorithms.

Summary updated

Abstract

In this paper we define a kind of decomposition for a quantum access structure. We propose a conception of minimal maximal quantum access structure and obtain a sufficient and necessary condition for minimal maximal quantum access structure, which shows the relationship between the number of minimal authorized sets and that of the players. Moreover, we investigate the construction of efficient quantum secret schemes by using these techniques, a decomposition and minimal maximal quantum access structure. A major advantage of these techniques is that it allows us to construct a method to realize a general quantum access structure. For these quantum access structures, we present two quantum secret schemes via the idea of concatenation or a decomposition of a quantum access structure. As a consequence, the application of these techniques allow us to save more quantum shares and reduce more cost than the existing scheme.
BibTeX
@misc{bai2017quantum,
  author = {Chen‐Ming Bai and Zhihui Li and Yongming Li},
  title = {{Quantum Access Structure and Secret Sharing}},
  year = {2017},
  eprint = {1701.01951},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1701.01951},
}

Loading related content...

Figure