Graph States for Quantum Secret Sharing

Damian Markham; Barry C. Sanders

Source-linked AI summary

Graph States for Quantum Secret Sharing

Damian Markham, Barry C. Sanders

arXiv:0808.1532v3Aug 11, 2008quant-ph

TL;DR

The paper addresses how disparate classical and quantum secret-sharing protocols can be unified, including settings with eavesdroppers and limited collaboration. It uses graph-state formalisms and embedded protocols to organize these cases, reports a (3, 5) protocol, and identifies scope limitations for some cases.

Problem
Existing secret-sharing results cover distinct classical and quantum settings, while some insecure-channel schemes require full player collaboration and some cases remain difficult.
Method
The paper uses graph states to represent classical and quantum secret-sharing protocols and embeds secret-sharing schemes within larger graph states.
Results
The formalism unifies secret sharing with eavesdroppers and presents a (3, 5) protocol, while embedded protocols provide a first step toward integrated quantum networks.
Takeaways & Limitations
Graph states offer a unified way to design secret-sharing protocols and support integration with one-way quantum information processing.
Takeaways & Limitations
The graphical properties used do not solve all cases; for example, a (3, 2) direct scheme cannot be constructed with this protocol.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper frames secret sharing across classical and quantum settings, including eavesdropping, and proposes graph states as a unifying formalism. It also targets reduced collaboration requirements and embedded protocols within one-way quantum computation.

Secret sharing has classical and quantum variants, including quantum-enhanced protection against eavesdropping and quantum-information protection through error correction.
The framework accommodates both classical and quantum channels that may be private or public.
Three subproblems show how classical secret sharing and two quantum secret-sharing versions fit into one general problem.
Graph states provide a formalism that unites these subproblems.
The approach extends classical secret sharing in insecure public channels beyond proofs requiring 100% player collaboration.
It introduces embedded secret-sharing protocols within graph states for one-way quantum computing and possible integrated measurement-based quantum computation.

II. SECRET SHARING PROBLEM AND SUBPROBLEMS

The paper defines a general secret-sharing problem for bit or qubit secrets, with threshold reconstruction and denial of access for unauthorized players and eavesdroppers. It organizes classical and quantum cases by channel type and information type.

A dealer sends a bit or qubit to n players so any k or more reconstruct it, while smaller sets and eavesdroppers receive no access.
Longer secrets can be shared by distributing one bit or qubit at a time.
The formulation incorporates classical or quantum channels that are public or private, with three major secret-sharing areas as subproblems.
The classical private-channel case is fully handled by classical information processing, although it is embedded in a graph-state description.
The public-channel classical-secret case uses quantum enhancement through random key distribution enabled by quantum purification.
Quantum state sharing addresses quantum information and has a general (k, n) solution in private channels through quantum error correction.
The graph-state formalism unifies known (n, n) CQ results and QQ for higher-dimensional stabilizer states, while adding a (3, 5) CQ result.

III. GRAPH STATES

Graph states are presented as resources for secret sharing because they are experimentally available, broadly useful in multipartite quantum processing, and graphically expose information flow.

Graph states had been experimentally built and used for information processing at sizes up to 6 qubits.
They are state resources for multipartite tasks including measurement-based quantum computation and error correction.
Their graphical representation provides an intuitive picture of information flow and permits graph-theoretic assistance with proofs and understanding.
The paper uses standard graph states plus local-unitary extensions to encode secrets as classical labels on vertices.
Entanglement allows labels to shift through the graph, exposing which player sets can access secrets and which cannot.
The paper defines labeled graph states, gives rules for information spreading and access, and describes measurement transformations.

A. Labeled graph states

Labeled graph states augment graph vertices with operation labels and vertex types that encode classical information and security structure. Encoded graph states restrict the labels to local Z operations and admit stabilizer descriptions.

Graph definitions: Vertices are connected when an edge joins them, and the neighbors of vertex vi form the set Ni.
Graph-state construction: A graph state is created from |+⟩⊗n by applying controlled-phase gates exactly along graph edges.
Labeled graph states: Each vertex label is extended to (i, ℓi1, ℓi2, ℓi3), with the first two additional bits representing classical information.
Labeled graph states: An unlabeled vertex corresponds to ℓi⋆=(0,0), while the third bit is represented graphically by # or □ and concerns protocol security.
Labeled graph states: The labeled graph state is obtained from a graph state through local unitary operations, including Z and the partial phase shift S.
Security encoding: The S gate supports an X ↔ Y basis transformation for eavesdropping protection, analogous to BB84.
Encoded graph states: Encoded graph states use only local Z gates and set ℓi1=0 for every vertex, yielding an orthonormal family.
Stabilizer description: The encoded states can be specified by stabilizer eigenequations and illustrated through three- and four-qubit examples, including 4GHZM states.

B. Dependence and Access

The labeled graph-state formalism represents how player subsets depend on encoded bits and determines which information they can access through stabilizer-based measurements, LOCC, or shared quantum channels. Bit shuffling exposes equivalent labelings and the resulting access structure.

Dependence: A player subset’s dependence on encoded information is determined by the labels that remain on its vertices after equivalent graph-state relabelings.Labels absent from the subset represent local operations outside it and cannot affect its reduced state.
Four-player example: Three collaborating players can learn bits ℓ22 and ℓ32 while remaining completely denied bits ℓ12 and ℓ42.The same subset can obtain this information using shared quantum channels or LOCC.
Four-player example: Two players can learn only the parity ℓ22 ⊕ ℓ32 via LOCC.The reduced state of the two-player subset depends on this parity rather than on the two individual bits separately.
General principles: Bit ℓi2 is accessible to a player set if and only if that set contains vertex vi and all of its neighbours.This condition is the general accessibility principle P2 for encoded graph states.
General principles: With shared quantum channels, all one-bit labels are accessible when P2 holds; with classical channels, adjacent players cannot jointly learn both corresponding bits.Nonadjacent players can learn both bits under the classical-channel condition described in P4.
Graph equivalence: The bit shuffling in P1 identifies equivalent labeled graph states rather than describing an active communication process.The equivalence follows from stabilizer eigenequations and is valid up to an irrelevant global phase in the four-player example.

C. Local Z and Y measurements on encoded graph states

Local Pauli measurements transform encoded graph states through graph changes and label updates. Z measurements preserve the original graph structure while Y measurements additionally induce local complementation and vertex-type changes, producing conjugate graph states.

Local Z measurements: A Z measurement deletes the measured vertex and its edges, while updating each neighbour’s label with the measurement outcome.For outcome sZ_i, neighbouring labels change by adding sZ_i to their second label bit modulo two.
Measurement outcomes: Measurement outcomes Sα_i = 0, 1 correspond to eigenvalues −1, +1 and are incorporated into the resulting graph labels.The figure illustrates these transformations for Z and Y measurements on vertex v1.
Local Y measurements: A Y measurement performs local complementation, changes neighbouring # vertices to □ vertices, and then removes the measured vertex and its edges.Local complementation toggles the edges among the measured vertex’s neighbours.
Label propagation: Z-label operations commute with Z measurement, whereas they do not commute with Y measurement and therefore transfer label dependence to the measured graph.For Y measurement, bit ℓ12 is carried forward under the measurement rule.
Conjugate graphs: The graph obtained after a Y measurement is called the conjugate graph and is generated by local complementation, neighbour-type replacement, and vertex removal.The corresponding state is the encoded conjugate graph state used in the later formalism.
Embedded graph states: Embedded nGHZM graph states are defined as subgraphs whose vertices have no neighbours outside the embedded graph.The associated graph state is embedded when its nGHZM graph satisfies this condition.

IV. SECRET SHARING PROTOCOLS

The paper uses encoded graph states to construct classical, classical-with-insecure-quantum-channels, and quantum secret-sharing protocols with specified threshold access structures. The constructions include (n,n), (3,4), and (3,5) schemes, LOCC decoding, security extensions, and embedded graph-state transformations.

CC protocols: Graph-state constructions realize (n,n), (3,4), and (3,5) threshold secret-sharing schemes, with LOCC sufficient for decoding.The schemes use an encoded nGHZM state, a 4-qubit ring, and a 5-qubit ring, respectively.
CC protocols: In the (3,4) scheme, authorized triples obtain secret information while selected pairs obtain only specified bit combinations.The square encoded graph denies information to adjacent pairs, while opposite pairs and triples access particular encoded combinations.
CQ protocols: Graph states generalize the HBB protocol to (n,n) and (3,5), while conjugate-graph checks verify that an eavesdropper has not entangled the transmitted state with an ancilla.The dealer’s extra qubits purify the earlier protocols, and measurement in conjugate bases supports correlation checking.
CQ protocols: The approach cannot extend the (3,4) CC protocol to key distribution because its conjugate graph lacks the required access structure.The GHZ and five-qubit ring encoded graph states satisfy the corresponding conjugate-graph requirement, but the 4-qubit ring does not.
CQ protocols: The CQ extensions distribute secure random keys with the same secrecy access structures and allow authorized players to access keys by LOCC.The security argument uses stabilizer checks and zero mutual information between the environment and the dealer; the (3,5) extension permits any three players but not any pair to reveal the key.
CC protocols: In the (3,5) scheme, every pair is denied information, whereas any three players can access the secret through cyclic-neighbor or T-shaped configurations.The five-qubit ring supports these access patterns via Properties P1, P2, and P4, with LOCC access.

V. EMBEDDED PROTOCOLS

The paper embeds classical, key-distribution, and quantum secret-sharing protocols within larger graph states, preserving an (n,n) structure for designated player subgroups despite attached neighbours. These embedded protocols connect secret sharing to one-way quantum processing and extended quantum networks.

Integration with quantum processing: Embedded quantum secret sharing can serve as a component of larger networks, including protocols whose inputs or outputs are linked to measurement-based quantum computation.The paper presents this as a step toward integrated quantum information protocols.
Graph-state construction: An n-GHZ tree embeds an nGHZM state in a larger graph, with neighbour sets attached to vertices other than v1.Neighbour sets may overlap.
Classical secret sharing: The embedded tree supports an (n,n) direct classical secret-sharing scheme for the subgroup {v1, . . . , vn}.All n designated players are required to read the encoded secret, while neighbours can alter who may help reconstruct it.
Access structure: Without neighbour assistance, all n designated players must cooperate; with appropriate neighbour assistance, fewer designated players can reconstruct the secret.For the illustrated case, a neighbour of player 2 can replace that player in the collaborating set.
Key distribution: Attaching the dealer to v1 yields an embedded (n,n) key-distribution scheme independent of the form or overlap of the neighbour sets.The designated subgroup accesses the key through stabilizer measurements, while the environment has no information after the required checks pass.
Quantum secret sharing: The same construction yields an embedded weak (n,n) quantum secret-sharing scheme, where incomplete designated subsets cannot access the secret perfectly but individual players may obtain some information.The dealer teleports the secret qubit into the graph-state encoding, and Z-basis measurements plus parity-dependent corrections recover it.

VI. CONCLUSIONS

The paper presents graph states as a unified resource for classical and quantum secret sharing, including eavesdropper settings and embedded protocols. It reports a (3,5) quantum-secret-sharing example, while identifying unresolved generality, security, and noise limitations.

Main conclusions: Graph states unify secret sharing for classical and quantum secrets in the presence of eavesdroppers.The approach uses graphical properties to characterize which players can access which information.
Main conclusions: The work gives a graph-state approach to quantum secret sharing beyond (n,n), explicitly presenting a (3,5) protocol with an eavesdropper.This extends the settings addressed by the paper beyond earlier all-player collaboration requirements.
Integration: Embedded secret-sharing protocols are introduced as a first step toward integrating quantum networks and combining tasks without changing or swapping hardware.The authors connect this direction to secret computing and other integrated protocols.
Open problems: Not all (k,n) cases are solved directly; specifically, the graph-state protocol cannot realize a (3,2) direct secret-sharing scheme.The paper leaves extension of the graphical approach to these cases as an ongoing investigation.
Limitations and open problems: Security remains unresolved for broader attack classes, and the protocols are not resilient to noisy channels.The paper notes that approaches used elsewhere may address both issues.