Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0001087

Quantum secret sharing for general access structures

Adam D. Smith

Published Jan 24, 2000• 27 citations
arXivHTMLPDF

Abstract

We explore the conversion of classical secret-sharing schemes to quantum ones, and how this can be used to give efficient QSS schemes for general adversary structures. Our first result is that quantum secret-sharing is possible for any structure for which no two disjoint sets can reconstruct the secret (this was also proved, somewhat differently, by D. Gottesman). To obtain this we show that a large class of linear classical SS schemes can be converted into quantum schemes of the same efficiency. We also give a necessary and sufficient condiion for the direct conversion of classical schemes into quantum ones, and show that all group homomorphic schemes satisfy it.

DOI
10.48550/arxiv.quant-ph/0001087

Related papers

Computational Quantum Secret Sharing

Alper Çakan, Vipul Goyal, Chen-Da Liu-Zhang +1 more

Quantum secret sharing (QSS) allows a dealer to distribute a secret quantum state among a set of parties in such a way that certain authorized subsets can reconstruct the secret, while unauthorized subsets obtain no information about it. Previous works on QSS for general access structures focused solely on the existence of perfectly secure schemes, and the share size of the known schemes is necessarily exponential even in cases where the access structure is computed by polynomial size monotone circuits. This stands in stark contrast to the classical setting, where polynomial-time computationally-secure secret sharing schemes have been long known for all access structures computed by polynomial-size monotone circuits under standard hardness assumptions, and one can even obtain shares which are much shorter than the secret (which is impossible with perfect security). While QSS was introduced over twenty years ago, previous works only considered information-theoretic privacy. In this work, we initiate the study of computationally-secure QSS and show that computational assumptions help significantly in building QSS schemes, just as in the classical case. We present a simple compiler and use it to obtain a large variety results: We construct polynomial-time computationally-secure QSS schemes under standard hardness assumptions for a rich class of access structures. This includes many access structures for which previous results in QSS necessarily required exponential share size. In fact, we can go even further: We construct QSS schemes for which the size of the quantum shares is significantly smaller than the size of the secret. As in the classical setting, this is impossible with perfect security. We also apply our compiler to obtain results beyond computational QSS. In the information-theoretic setting, we improve the share size of perfect QSS schemes for a large class of n-party access structures to 1.5^{n+o(n)}, improving upon best known schemes and matching the best known result for general access structures in the classical setting. Finally, among other things, we study the class of access structures which can be efficiently implemented when the quantum secret sharing scheme has access to a given number of copies of the secret, including all such functions in 𝖯 and NP.

Leibniz international proceedings in informatics•Jan 1, 2023•0 citations

Computational Quantum Secret Sharing

Alper Çakan, Vipul Goyal, Chen-Da Liu-Zhang +1 more

Quantum secret sharing (QSS) allows a dealer to distribute a secret quantum state among a set of parties so that certain subsets can reconstruct the secret, while unauthorized subsets obtain no information. While QSS was introduced over twenty years ago, previous works focused only on existence of perfectly secure schemes, and the share size of the known schemes is exponential even for access structures computed by polynomial size monotone circuits. This stands in contrast to the classical case, where efficient computationally-secure schemes have been long known for all access structures in $\mathsf{monotone~P}$, and one can even obtain shares which are much shorter than the secret which is impossible with perfect security. In this work, we initiate the study of computationally-secure QSS and show that computational assumptions help significantly in building QSS schemes. We present a simple compiler and use it to obtain a large variety results: We construct polynomial-time QSS schemes under standard assumptions for a rich class of access structures. This includes many access structures for which previous results in QSS required exponential share size. We also construct QSS schemes for which the size of the shares is significantly smaller than the size of the secret. As in the classical case, this is impossible with perfect security. We also use our compiler to obtain results beyond computational QSS. In the information-theoretic setting, we improve the share size of perfect QSS schemes for a large class of access structures to $1.5^{n+o(n)}$, improving upon best known schemes and matching the best known result for general access structures in the classical case. Finally, we show construct efficient schemes for all access structures in $\mathsf{P}$ and $\mathsf{NP}$ when the quantum secret sharing scheme is given multiple of copies of the secret.

arXiv:2305.00356•Apr 29, 2023•1 citation

Matroids and quantum-secret-sharing schemes

Pradeep Kiran Sarvepalli, Robert Raussendorf

A secret-sharing scheme is a cryptographic protocol to distribute a secret state in an encoded form among a group of players such that only authorized subsets of the players can reconstruct the secret. Classically, efficient secret-sharing schemes have been shown to be induced by matroids. Furthermore, access structures of such schemes can be characterized by an excluded minor relation. No such relations are known for quantum secret-sharing schemes. In this paper we take the first steps toward a matroidal characterization of quantum-secret-sharing schemes. In addition to providing a new perspective on quantum-secret-sharing schemes, this characterization has important benefits. While previous work has shown how to construct quantum-secret-sharing schemes for general access structures, these schemes are not claimed to be efficient. In this context the present results prove to be useful; they enable us to construct efficient quantum-secret-sharing schemes for many general access structures. More precisely, we show that an identically self-dual matroid that is representable over a finite field induces a pure-state quantum-secret-sharing scheme with information rate $1$.

arXiv:0909.0549•Physical Review A•May 24, 2010•33 citations

Sharing classical secrets with Calderbank-Shor-Steane codes

Pradeep Kiran Sarvepalli, Andreas Klappenecker

In this paper we investigate the use of quantum information to share classical secrets. While every quantum secret sharing scheme is a quantum error-correcting code, the converse is not true. Motivated by this we sought to find quantum codes which can be converted to secret sharing schemes. If we are interested in sharing classical secrets using quantum information, then we show that a class of pure ${[[n,1,d]]}_{q}$ Calderbank-Shor-Steane (CSS) codes can be converted to perfect secret sharing schemes. These secret sharing schemes are perfect in the sense that the unauthorized parties do not learn anything about the secret. Gottesman had given conditions to test whether a given subset is an authorized or unauthorized set; they enable us to determine the access structure of quantum secret sharing schemes. For the secret sharing schemes proposed in this paper the access structure can be characterized in terms of minimal codewords of the classical code underlying the CSS code. This characterization of the access structure for quantum secret sharing schemes is thought to be notable.

arXiv:0905.1661•Physical Review A•Aug 18, 2009•43 citations

Nonthreshold quantum secret-sharing schemes in the graph-state formalism

Pradeep Kiran Sarvepalli

In a recent work, Markham and Sanders proposed a framework to study quantum secret-sharing (QSS) schemes using graph states. This framework unified three classes of QSS protocols, namely, sharing classical secrets over private and public channels, and sharing quantum secrets. However, previous work on graph-state secret sharing mostly focused on threshold schemes. In this paper, we focus on general access structures. We show how to realize a large class of arbitrary access structures using the graph-state formalism. We show an equivalence between $[[n,1]]$ binary quantum codes and graph-state secret-sharing schemes sharing one bit. We also establish a similar (but restricted) equivalence between a class of $[[n,1]]$ Calderbank-Shor-Steane codes and graph-state QSS schemes sharing one qubit. With these results we are able to construct a large class of graph-state quantum secret-sharing schemes with arbitrary access structures.

arXiv:1202.3433•Physical Review A•Oct 1, 2012•49 citations

Some directions beyond traditional quantum secret sharing

Sudhir Kumar Singh, R Srikanth

We investigate two directions beyond the traditional quantum secret sharing (QSS). First, a restriction on QSS that comes from the no-cloning theorem is that any pair of authorized sets in an access structure should overlap. From the viewpoint of application, this places an unnatural constraint on secret sharing. We present a generalization, called assisted QSS (AQSS), where access structures without pairwise overlap of authorized sets is permissible, provided some shares are withheld by the share dealer. We show that no more than $λ-1$ withheld shares are required, where $λ$ is the minimum number of {\em partially linked classes} among the authorized sets for the QSS. Our result means that such applications of QSS need not be thwarted by the no-cloning theorem. Secondly, we point out a way of combining the features of QSS and quantum key distribution (QKD) for applications where a classical information is shared by quantum means. We observe that in such case, it is often possible to reduce the security proof of QSS to that of QKD.

arXiv:0805.1076•Physica Scripta•May 21, 2008•3 citations
We explore the conversion of classical secret-sharing schemes to quantum ones, and how this can be used to give efficient QSS schemes for general adversary structures. Our first result is that quantum secret-sharing is possible for any structure for which no two disjoint sets can reconstruct the secret (this was also proved, somewhat differently, by D. Gottesman). To obtain this we show that a large class of linear classical SS schemes can be converted into quantum schemes of the same efficiency. We also give a necessary and sufficient condiion for the direct conversion of classical schemes into quantum ones, and show that all group homomorphic schemes satisfy it.
Quantum secret sharing (QSS) allows a dealer to distribute a secret quantum state among a set of parties in such a way that certain authorized subsets can reconstruct the secret, while unauthorized subsets obtain no information about it. Previous works on QSS for general access structures focused solely on the existence of perfectly secure schemes, and the share size of the known schemes is necessarily exponential even in cases where the access structure is computed by polynomial size monotone circuits. This stands in stark contrast to the classical setting, where polynomial-time computationally-secure secret sharing schemes have been long known for all access structures computed by polynomial-size monotone circuits under standard hardness assumptions, and one can even obtain shares which are much shorter than the secret (which is impossible with perfect security). While QSS was introduced over twenty years ago, previous works only considered information-theoretic privacy. In this work, we initiate the study of computationally-secure QSS and show that computational assumptions help significantly in building QSS schemes, just as in the classical case. We present a simple compiler and use it to obtain a large variety results: We construct polynomial-time computationally-secure QSS schemes under standard hardness assumptions for a rich class of access structures. This includes many access structures for which previous results in QSS necessarily required exponential share size. In fact, we can go even further: We construct QSS schemes for which the size of the quantum shares is significantly smaller than the size of the secret. As in the classical setting, this is impossible with perfect security. We also apply our compiler to obtain results beyond computational QSS. In the information-theoretic setting, we improve the share size of perfect QSS schemes for a large class of n-party access structures to 1.5^{n+o(n)}, improving upon best known schemes and matching the best known result for general access structures in the classical setting. Finally, among other things, we study the class of access structures which can be efficiently implemented when the quantum secret sharing scheme has access to a given number of copies of the secret, including all such functions in 𝖯 and NP.
Quantum secret sharing (QSS) allows a dealer to distribute a secret quantum state among a set of parties so that certain subsets can reconstruct the secret, while unauthorized subsets obtain no information. While QSS was introduced over twenty years ago, previous works focused only on existence of perfectly secure schemes, and the share size of the known schemes is exponential even for access structures computed by polynomial size monotone circuits. This stands in contrast to the classical case, where efficient computationally-secure schemes have been long known for all access structures in monotone P\mathsf{monotone~P}monotone P, and one can even obtain shares which are much shorter than the secret which is impossible with perfect security. In this work, we initiate the study of computationally-secure QSS and show that computational assumptions help significantly in building QSS schemes. We present a simple compiler and use it to obtain a large variety results: We construct polynomial-time QSS schemes under standard assumptions for a rich class of access structures. This includes many access structures for which previous results in QSS required exponential share size. We also construct QSS schemes for which the size of the shares is significantly smaller than the size of the secret. As in the classical case, this is impossible with perfect security. We also use our compiler to obtain results beyond computational QSS. In the information-theoretic setting, we improve the share size of perfect QSS schemes for a large class of access structures to 1.5n+o(n)1.5^{n+o(n)}1.5n+o(n), improving upon best known schemes and matching the best known result for general access structures in the classical case. Finally, we show construct efficient schemes for all access structures in P\mathsf{P}P and NP\mathsf{NP}NP when the quantum secret sharing scheme is given multiple of copies of the secret.
A secret-sharing scheme is a cryptographic protocol to distribute a secret state in an encoded form among a group of players such that only authorized subsets of the players can reconstruct the secret. Classically, efficient secret-sharing schemes have been shown to be induced by matroids. Furthermore, access structures of such schemes can be characterized by an excluded minor relation. No such relations are known for quantum secret-sharing schemes. In this paper we take the first steps toward a matroidal characterization of quantum-secret-sharing schemes. In addition to providing a new perspective on quantum-secret-sharing schemes, this characterization has important benefits. While previous work has shown how to construct quantum-secret-sharing schemes for general access structures, these schemes are not claimed to be efficient. In this context the present results prove to be useful; they enable us to construct efficient quantum-secret-sharing schemes for many general access structures. More precisely, we show that an identically self-dual matroid that is representable over a finite field induces a pure-state quantum-secret-sharing scheme with information rate 111.
In this paper we investigate the use of quantum information to share classical secrets. While every quantum secret sharing scheme is a quantum error-correcting code, the converse is not true. Motivated by this we sought to find quantum codes which can be converted to secret sharing schemes. If we are interested in sharing classical secrets using quantum information, then we show that a class of pure [[n,1,d]]q{[[n,1,d]]}_{q}[[n,1,d]]q​ Calderbank-Shor-Steane (CSS) codes can be converted to perfect secret sharing schemes. These secret sharing schemes are perfect in the sense that the unauthorized parties do not learn anything about the secret. Gottesman had given conditions to test whether a given subset is an authorized or unauthorized set; they enable us to determine the access structure of quantum secret sharing schemes. For the secret sharing schemes proposed in this paper the access structure can be characterized in terms of minimal codewords of the classical code underlying the CSS code. This characterization of the access structure for quantum secret sharing schemes is thought to be notable.
In a recent work, Markham and Sanders proposed a framework to study quantum secret-sharing (QSS) schemes using graph states. This framework unified three classes of QSS protocols, namely, sharing classical secrets over private and public channels, and sharing quantum secrets. However, previous work on graph-state secret sharing mostly focused on threshold schemes. In this paper, we focus on general access structures. We show how to realize a large class of arbitrary access structures using the graph-state formalism. We show an equivalence between [[n,1]][[n,1]][[n,1]] binary quantum codes and graph-state secret-sharing schemes sharing one bit. We also establish a similar (but restricted) equivalence between a class of [[n,1]][[n,1]][[n,1]] Calderbank-Shor-Steane codes and graph-state QSS schemes sharing one qubit. With these results we are able to construct a large class of graph-state quantum secret-sharing schemes with arbitrary access structures.
We investigate two directions beyond the traditional quantum secret sharing (QSS). First, a restriction on QSS that comes from the no-cloning theorem is that any pair of authorized sets in an access structure should overlap. From the viewpoint of application, this places an unnatural constraint on secret sharing. We present a generalization, called assisted QSS (AQSS), where access structures without pairwise overlap of authorized sets is permissible, provided some shares are withheld by the share dealer. We show that no more than λ−1λ-1λ−1 withheld shares are required, where λλλ is the minimum number of {\em partially linked classes} among the authorized sets for the QSS. Our result means that such applications of QSS need not be thwarted by the no-cloning theorem. Secondly, we point out a way of combining the features of QSS and quantum key distribution (QKD) for applications where a classical information is shared by quantum means. We observe that in such case, it is often possible to reduce the security proof of QSS to that of QKD.