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:0909.4479 · Electronic Proceedings in Theoretical Computer Science

Information Flow in Secret Sharing Protocols

Elham Kashefi, Damian Markham, Mehdi Mhalla, Simon Perdrix

Published Nov 14, 2009• 27 citations
arXivHTMLPDF

Abstract

The entangled graph states have emerged as an elegant and powerful quantum resource, indeed almost all multiparty protocols can be written in terms of graph states including measurement based quantum computation (MBQC), error correction and secret sharing amongst others. In addition they are at the forefront in terms of implementations. As such they represent an excellent opportunity to move towards integrated protocols involving many of these elements. In this paper we look at expressing and extending graph state secret sharing and MBQC in a common framework and graphical language related to flow. We do so with two main contributions. First we express in entirely graphical terms which set of players can access which information in graph state secret sharing protocols. These succinct graphical descriptions of access allow us to take known results from graph theory to make statements on the generalisation of the previous schemes to present new secret sharing protocols. Second, we give a set of necessary conditions as to when a graph with flow, i.e. capable of performing a class of unitary operations, can be extended to include vertices which can be ignored, pointless measurements, and hence considered as unauthorised players in terms of secret sharing, or error qubits in terms of fault tolerance. This offers a way to extend existing MBQC patterns to secret sharing protocols. Our characterisation of pointless measurements is believed also to be a useful tool for further integrated measurement based schemes, for example in constructing fault tolerant MBQC schemes.

DOI
10.4204/eptcs.9.10

Related papers

Quantum Information Processing with Graphs

Mehdi Mhalla, Mio Murao, Simon Perdrix +2 more

Graph states are an elegant and powerful quantum resource for measurement based quantum computation (MBQC). They are also used for many quantum protocols (error correction, secret sharing, etc.). The main focus of this paper is to provide a structural characterization of the graph states that can be used for quantum information processing. The existence of a gflow (generalized flow) is known to be a requirement for open graphs (graph, input set and output set) to perform uniformly and strongly deterministic computations. We weaken the gflow conditions to define two new more general types of MBQC: uniform equiprobability and constant probability. These classes can be useful from a cryptographic and information point of view because even though we can not do a deterministic computation in general we can preserve the information and transfer it perfectly from the inputs to the outputs. We derive simple graph characterizations for these classes and prove that the deterministic and uniform equiprobability classes collapse when the cardinalities of inputs and outputs are the same. We also prove the reversibility of gflow in that case. The new graphical characterizations allow us to go from open graphs to graphs in general and to consider this question: given a graph with no inputs or outputs fixed, which vertices can be chosen as input and output for quantum information processing? We present a characterization of the sets of possible inputs and ouputs for the equiprobability class, which is also valid for deterministic computations with inputs and ouputs of the same cardinality.

•Jun 14, 2010•0 citations

Quantum secret sharing with quantum graph states

Liang Jian-Wu, Cheng Zi, Shi Jin-Jing +1 more

Quantum secret sharing is an important way to achieve secure communications, which has critical applications in the field of information security for its physical properties. According to the perspective of the practical applications, improving the confidentiality and integrity of secret sharing schemes is a good method to increase the security and reliability of communications. In this paper, we propose a quantum secret sharing scheme based on generator matrix segmentation and the structural features of quantum graph states. The security of the secure secret sharing scheme is guaranteed by the pattern of transferring information by stabilizers, scalability of the information and new recovery strategy provided by the entanglement of the related graph states. It puts forward an effective solution to the problem of matrix cycle period, where some numbers without the primitive element cannot construct the generation matrix. First of all, the physical properties of quantum bits (qubits), such as uncertainty principle, no-cloning theorem and indistinguishability, not only optimize the classical schemes but also ensure the absolute safety of communication. Secondly, the application of matrix segmentation makes secret information has better scalability. It improves the coding diversity and the difficulty in deciphering. Thirdly, the favorable entanglement properties and mature experiment preparation techniques of graph states provide an approach to the practical applications. The superiority of the yielded graph states is described in graphical fashion with an elegant stabilizer. Fourthly, the shuffling operation can ensure the independence of the message among participants. Therefore, Eve can not obtain any useful information by measuring randomly. Two group-recovery protocols are proposed to show the secret recovering processing through rebuilding sub-secrets among legal cooperative participants. In the scheme design, the dealer extracts the classical secret information according to the corresponding principle between the classical and quantum information, and divides the classical secret through generated matrix which is produced with the primitive elements in finite domain satisfying the linear independence for any k column vectors. Then the dealer encodes information into graph states and distributes particles to the legal participants with unitary operations. Subsequently, the credible center obtains sub-secrets by the theory of graph states and the group recovery protocol. He can achieve the initial classical secret via the inverse algorithm of matrix segmentation. After getting the classical secret, he recovers quantum secret according to the relationship between classical information and quantum information. Theoretical analysis shows that this scheme can provide better security and scalability of the information. It is appropriate to realize the secret sharing in the quantum network communication to protect secrets from eavesdropping. Also, it can provide an approach to designing diverse and scalable quantum secure communication schemes based on quantum graph states, the algorithm of matrix segmentation, and group-recovery protocol.

Acta Physica Sinica•Jan 1, 2016•6 citations

Graph states for quantum secret sharing

Damian Markham, Barry C. Sanders

We consider three broad classes of quantum secret sharing with and without eavesdropping and show how a graph state formalism unifies otherwise disparate quantum secret sharing models. In addition to the elegant unification provided by graph states, our approach provides a generalization of threshold classical secret sharing via insecure quantum channels beyond the current requirement of 100% collaboration by players to just a simple majority in the case of five players. Another innovation here is the introduction of embedded protocols within a larger graph state that serves as a one-way quantum-information processing system.

arXiv:0808.1532•Physical Review A•Oct 10, 2008•450 citations

Access structure in graphs in high dimension and application to secret sharing

Anne Marin, Damian Markham, Simon Perdrix

We give graphical characterisation of the access structure to both classical and quantum information encoded onto a multigraph defined for prime dimension $q$, as well as explicit decoding operations for quantum secret sharing based on graph state protocols. We give a lower bound on $k$ for the existence of a $((k,n))_q$ scheme and prove, using probabilistic methods, that there exists $α$ such that a random multigraph has an accessing parameter $k\leq αn$ with high probability.

arXiv:1304.7105•Apr 26, 2013•6 citations

Classical versus Quantum Graph-based Secret Sharing

Jérôme Javelle, Mehdi Mhalla, Simon Perdrix

We study a simple graph-based classical secret sharing scheme: every player's share consists of a random key together with the encryption of the secret with the keys of his neighbours. A characterisation of the authorised and forbidden sets of players is given. Moreover, we show that this protocol is equivalent to the graph state quantum secret sharing (GS-QSS) schemes when the secret is classical. When the secret is an arbitrary quantum state, a set of players is authorised for a GS-QSS scheme if and only if, for the corresponding simple classical graph-based protocol, the set is authorised and its complement set is not.

arXiv:1109.4731•Sep 22, 2011•5 citations

Access Structure in Graphs in High Dimension and Application to Secret Sharing

Anne Marin, Damian Markham, Simon Perdrix

We give graphical characterisation of the access structure to both classical and quantum information encoded onto a multigraph defined for prime dimension q, as well as explicit decoding operations for quantum secret sharing based on graph state protocols. We give a lower bound on $k$ for the existence of a ((k,n))_q scheme and prove, using probabilistic methods, that there exists alpha such that a random multigraph has an accessing parameter k => alpha*n with high probability.

Leibniz international proceedings in informatics•Jan 1, 2013•0 citations
The entangled graph states have emerged as an elegant and powerful quantum resource, indeed almost all multiparty protocols can be written in terms of graph states including measurement based quantum computation (MBQC), error correction and secret sharing amongst others. In addition they are at the forefront in terms of implementations. As such they represent an excellent opportunity to move towards integrated protocols involving many of these elements. In this paper we look at expressing and extending graph state secret sharing and MBQC in a common framework and graphical language related to flow. We do so with two main contributions. First we express in entirely graphical terms which set of players can access which information in graph state secret sharing protocols. These succinct graphical descriptions of access allow us to take known results from graph theory to make statements on the generalisation of the previous schemes to present new secret sharing protocols. Second, we give a set of necessary conditions as to when a graph with flow, i.e. capable of performing a class of unitary operations, can be extended to include vertices which can be ignored, pointless measurements, and hence considered as unauthorised players in terms of secret sharing, or error qubits in terms of fault tolerance. This offers a way to extend existing MBQC patterns to secret sharing protocols. Our characterisation of pointless measurements is believed also to be a useful tool for further integrated measurement based schemes, for example in constructing fault tolerant MBQC schemes.
Graph states are an elegant and powerful quantum resource for measurement based quantum computation (MBQC). They are also used for many quantum protocols (error correction, secret sharing, etc.). The main focus of this paper is to provide a structural characterization of the graph states that can be used for quantum information processing. The existence of a gflow (generalized flow) is known to be a requirement for open graphs (graph, input set and output set) to perform uniformly and strongly deterministic computations. We weaken the gflow conditions to define two new more general types of MBQC: uniform equiprobability and constant probability. These classes can be useful from a cryptographic and information point of view because even though we can not do a deterministic computation in general we can preserve the information and transfer it perfectly from the inputs to the outputs. We derive simple graph characterizations for these classes and prove that the deterministic and uniform equiprobability classes collapse when the cardinalities of inputs and outputs are the same. We also prove the reversibility of gflow in that case. The new graphical characterizations allow us to go from open graphs to graphs in general and to consider this question: given a graph with no inputs or outputs fixed, which vertices can be chosen as input and output for quantum information processing? We present a characterization of the sets of possible inputs and ouputs for the equiprobability class, which is also valid for deterministic computations with inputs and ouputs of the same cardinality.
Quantum secret sharing is an important way to achieve secure communications, which has critical applications in the field of information security for its physical properties. According to the perspective of the practical applications, improving the confidentiality and integrity of secret sharing schemes is a good method to increase the security and reliability of communications. In this paper, we propose a quantum secret sharing scheme based on generator matrix segmentation and the structural features of quantum graph states. The security of the secure secret sharing scheme is guaranteed by the pattern of transferring information by stabilizers, scalability of the information and new recovery strategy provided by the entanglement of the related graph states. It puts forward an effective solution to the problem of matrix cycle period, where some numbers without the primitive element cannot construct the generation matrix. First of all, the physical properties of quantum bits (qubits), such as uncertainty principle, no-cloning theorem and indistinguishability, not only optimize the classical schemes but also ensure the absolute safety of communication. Secondly, the application of matrix segmentation makes secret information has better scalability. It improves the coding diversity and the difficulty in deciphering. Thirdly, the favorable entanglement properties and mature experiment preparation techniques of graph states provide an approach to the practical applications. The superiority of the yielded graph states is described in graphical fashion with an elegant stabilizer. Fourthly, the shuffling operation can ensure the independence of the message among participants. Therefore, Eve can not obtain any useful information by measuring randomly. Two group-recovery protocols are proposed to show the secret recovering processing through rebuilding sub-secrets among legal cooperative participants. In the scheme design, the dealer extracts the classical secret information according to the corresponding principle between the classical and quantum information, and divides the classical secret through generated matrix which is produced with the primitive elements in finite domain satisfying the linear independence for any k column vectors. Then the dealer encodes information into graph states and distributes particles to the legal participants with unitary operations. Subsequently, the credible center obtains sub-secrets by the theory of graph states and the group recovery protocol. He can achieve the initial classical secret via the inverse algorithm of matrix segmentation. After getting the classical secret, he recovers quantum secret according to the relationship between classical information and quantum information. Theoretical analysis shows that this scheme can provide better security and scalability of the information. It is appropriate to realize the secret sharing in the quantum network communication to protect secrets from eavesdropping. Also, it can provide an approach to designing diverse and scalable quantum secure communication schemes based on quantum graph states, the algorithm of matrix segmentation, and group-recovery protocol.
We consider three broad classes of quantum secret sharing with and without eavesdropping and show how a graph state formalism unifies otherwise disparate quantum secret sharing models. In addition to the elegant unification provided by graph states, our approach provides a generalization of threshold classical secret sharing via insecure quantum channels beyond the current requirement of 100% collaboration by players to just a simple majority in the case of five players. Another innovation here is the introduction of embedded protocols within a larger graph state that serves as a one-way quantum-information processing system.
We give graphical characterisation of the access structure to both classical and quantum information encoded onto a multigraph defined for prime dimension qqq, as well as explicit decoding operations for quantum secret sharing based on graph state protocols. We give a lower bound on kkk for the existence of a ((k,n))q((k,n))_q((k,n))q​ scheme and prove, using probabilistic methods, that there exists ααα such that a random multigraph has an accessing parameter k≤αnk\leq αnk≤αn with high probability.
We study a simple graph-based classical secret sharing scheme: every player's share consists of a random key together with the encryption of the secret with the keys of his neighbours. A characterisation of the authorised and forbidden sets of players is given. Moreover, we show that this protocol is equivalent to the graph state quantum secret sharing (GS-QSS) schemes when the secret is classical. When the secret is an arbitrary quantum state, a set of players is authorised for a GS-QSS scheme if and only if, for the corresponding simple classical graph-based protocol, the set is authorised and its complement set is not.
We give graphical characterisation of the access structure to both classical and quantum information encoded onto a multigraph defined for prime dimension q, as well as explicit decoding operations for quantum secret sharing based on graph state protocols. We give a lower bound on kkk for the existence of a ((k,n))_q scheme and prove, using probabilistic methods, that there exists alpha such that a random multigraph has an accessing parameter k => alpha*n with high probability.