Near-Optimal Placement of Secrets in Graphs

Werner  Poguntke

doi:10.4236/ojdm.2016.64020

Werner Poguntke

Abstract: We consider the reconstruction of shared secrets in communication networks, which are modelled by graphs whose components are subject to possible failure. The reconstruction probability can be approximated using minimal cuts, if the failure probabilities of vertices and edges are close to zero. As the main contribution of this paper, node separators are used to design a heuristic for the near-optimal placement of secrets sets on the vertices of the graph.

Keywords: Graph Algorithm, Cut, Secret Sharing, Approximation, Network Design

Cite this paper: Poguntke, W. (2016) Near-Optimal Placement of Secrets in Graphs. Open Journal of Discrete Mathematics, 6, 238-247. doi: 10.4236/ojdm.2016.64020.

References

[1] Blakley, R. (1979) Safeguarding Cryptographic Keys. Proceedings of the AFIPS 1979 National Computer Conference, 48, 313-317.

[2] Shamir, A. (1979) How to Share a Secret. Communications of the ACM, 22, 612-613.
http://dx.doi.org/10.1145/359168.359176

[3] Simmons, G.J. (1991) An Introduction to Shared Secret and/or Shared Control Schemes and Their Application. Contemporary Cryptology, IEEE Press, New York, 441-497.

[4] Stinson, D.R. (1992) An Explication of Secret Sharing Schemes. Designs, Codes, and Cryptography, 2, 357-390.
http://dx.doi.org/10.1007/BF00125203

[5] Blundo, C., de Santis, A., Stinson, D.R. and Vaccaro, U. (1995) Graph Decomposition and Secret Sharing Schemes. Journal of Cryptology, 8, 39-64.
http://dx.doi.org/10.1007/BF00204801

[6] Lee, C.-Y., et al. (1999) A Probability Model for Reconstructing Secret Sharing under the Internet Environment. Information Sciences, 116, 109-127.
http://dx.doi.org/10.1016/S0020-0255(98)10104-4

[7] PÖnitz, A. and Sans, O. (2001) Computing the Reconstruction Probability of Distributed Secret Sharing Schemes Using the Composition Method. (Unpublished Manuscript)

[8] Colbourn, J. (1987) Combinatorics of Network Reliability. Oxford University Press, Oxford.

[9] Shier, D.R. (1991) Network Reliability and Algebraic Structures. Clarendon Press, Oxford.

[10] Bienstock, D. (1988) Some Lattice-Theoretic Tools for Network Reliability Analysis. Mathematics of Operations Research, 13, 467-478.
http://dx.doi.org/10.1287/moor.13.3.467

[11] Tittmann, P. and Blechschmidt, A. (1991) Reliability Bounds Based on Network Splitting. Elektronische Informationsverarbeitung und Kybernetik, 27, 317-326.

[12] Poguntke, W. and Simonet, G. (2004) Secrets and Separators. ALGCO—Algorithmes, Graphes et Combinatoire, LIRMM—Laboratoired’Informatique de Robotique et de Microélectronique de Montpellier, Report 04001.

[13] Kloks, T. and Kratsch, D. (2006) Listing All Minimal Separators of a Graph. Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science, Springer, LNCS 775, 759-768.
http://dx.doi.org/10.1137/s009753979427087x

[14] Poguntke, W. (2003) Using Mincuts to Design Secret Sharing Schemes in Graphs. Extended Abstract. Electronic Notes in Discrete Mathematics, 13, 97-102.
http://dx.doi.org/10.1016/S1571-0653(04)00447-0