Complexity of Network Design for Private Communication and the P-vs-NP Question

We investigate infeasibility issues arising along network design for information-theoretically secure cryptography. In particular, we consider the problem of communication in perfect privacy and formally relate it to graph augmentation problems and the P-vs-NP-question. Based on a game-theoretic privacy measure, we consider two optimization problems related to secure infrastructure design with constraints on computational efforts and limited budget to build a transmission network. It turns out that information-theoretic security, although not drawing its strength from computational infeasibility, still can run into complexity-theoretic difficulties at the stage of physical network design. Even worse, if we measure (quantify) secrecy by the probability of information-leakage, we can prove that approximations of a network design towards maximal security are computationally equivalent to the exact solutions to the same problem, both of which are again equivalent to asserting that P = NP. In other words, the death of public-key cryptosystems upon P = NP may become the birth of feasible network design algorithms towards information-theoretically confidential communication.

@article{Rass2014,
  title     = {Complexity of Network Design for Private Communication and the P-vs-NP Question},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {5},
  number    = {2},
  year      = {2014},
  publisher = {The Science and Information Organization},
  author    = {Stefan Rass},
  doi       = {10.14569/IJACSA.2014.050222},
  url       = {https://doi.org/10.14569/IJACSA.2014.050222}
}