Abstract: 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.

Stefan Rass, “Complexity of Network Design for Private Communication and the P-vs-NP Question” International Journal of Advanced Computer Science and Applications(IJACSA), 5(2), 2014. http://dx.doi.org/10.14569/IJACSA.2014.050222

@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},
doi = {10.14569/IJACSA.2014.050222},
url = {http://dx.doi.org/10.14569/IJACSA.2014.050222},
year = {2014},
publisher = {The Science and Information Organization},
volume = {5},
number = {2},
author = {Stefan Rass}
}