On weak odd domination and graph-based quantum secret sharing

DOI10.1016/J.TCS.2015.05.038MaRDI QIDQ496043zbMATH OpenOpenAlexFDO

Authors Sylvain Gravier, Jérôme Javelle, Mehdi Mhalla, Simon Perdrix

Publication date 16 September 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.2495

zbMATH Keywords

graph theorycomplexityNP-completenessquantum information

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Quantum algorithms and complexity in the theory of computing (68Q12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Authentication, digital signatures and secret sharing (94A62)

Abstract: A weak odd dominated (WOD) set in a graph is a subset B of vertices for which there exists a distinct set of vertices C such that every vertex in B has an odd number of neighbors in C. We point out the connections of weak odd domination with odd domination, [sigma,rho]-domination, and perfect codes. We introduce bounds on kappa(G), the maximum size of WOD sets of a graph G, and on kappa'(G), the minimum size of non WOD sets of G. Moreover, we prove that the corresponding decision problems are NP-complete. The study of weak odd domination is mainly motivated by the design of graph-based quantum secret sharing protocols: a graph G of order n corresponds to a secret sharing protocol which threshold is kappa_Q(G) = max(kappa(G), n-kappa'(G)). These graph-based protocols are very promising in terms of physical implementation, however all such graph-based protocols studied in the literature have quasi-unanimity thresholds (i.e. kappa_Q(G)=n-o(n) where n is the order of the graph G underlying the protocol). In this paper, we show using probabilistic methods, the existence of graphs with smaller kappa_Q (i.e. kappa_Q(G)< 0.811n where n is the order of G). We also prove that deciding for a given graph G whether kappa_Q(G)< k is NP-complete, which means that one cannot efficiently double check that a graph randomly generated has actually a kappa_Q smaller than 0.811n.

Recommendations

• New protocols and lower bounds for quantum secret sharing with graph states
• Quantum secret sharing for a class of special hypergraph access structures
• Graph state-based quantum secret sharing with the Chinese remainder theorem
• Graph states for quantum secret sharing
• Quantum secret sharing with continuous variable graph state
• A NOTE ON SOME QUANTUM SECRET SHARING SCHEMES
• Secret sharing schemes on graphs
• Cryptanalysis and improvement of verifiable quantum (k,n) secret sharing
• Verifiable quantum \((k,n)\)-threshold secret key sharing

Cites work

• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 1934394 (Why is no real title available?)
• scientific article; zbMATH DE number 921905 (Why is no real title available?)
• 1-perfect codes in Sierpiński graphs
• A Finite Gilbert–Varshamov Bound for Pure Stabilizer Quantum Codes
• A constructive proof of the general Lovász local lemma
• A single quantum cannot be cloned
• Finding Optimal Flows Efficiently
• Graph concatenation for quantum codes
• Graph states for quantum secret sharing
• Information flow in secret sharing protocols
• Linear cellular automata and the garden-of-eden
• Mod-2 independence and domination in graphs
• New protocols and lower bounds for quantum secret sharing with graph states
• Parity dimension for graphs
• The One Way to Quantum Computation
• The σ-Game and Cellular Automata
• Which Graph States are Useful for Quantum Information Processing?

Cited in

(3)

• Implementation of quantum secret sharing and quantum binary voting protocol in the IBM quantum computer
• Parameterized complexity of weak odd domination problems
• On the complexity of finding large odd induced subgraphs and odd colorings

This page was built for publication: On weak odd domination and graph-based quantum secret sharing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q496043)