Information-Theoretic Security as an Optimization Problem
Stefan Raß · Journal of Next Generation Information Technology · 2011
Quantum key distribution is renowned for information-theoretic security on point-to-point connections, while it is by itself not directly capable of end-to-end security. Multipath transmission is known for perfect end-to-end security, provided that perfect point-to-point security is achievable. The marriage of the two is as natural as it is difficult to achieve in real life networks: secure multipath transmission imposes stringent requirements on the network connectivity, perhaps rarely found in a real-life network infrastructure. We consider the problem of network augmentation to support perfect end-to-end security in a network in which adjacent nodes share a perfectly confidential channel. Quantum networks are one example for this. Starting with a decision-theoretic formalization of risk and confidentiality, we cast the network augmentation task into a nonlinear optimization problem, whose computational complexity is studied. With the problem turning out NP-hard in at least two of its variants, we sketch heuristics that can help to keep calculations feasible in practical applications.