The NP-Complete Face of Information-Theoretic Security  

作　　者：Stefan Rass Peter Schartner 

机构地区：[1]System Security Research Group, Institute of lnformatics, Alpen-Adria Universitgit Klagenfurt, Klagenfurt 9020, Austria

出　　处：《Computer Technology and Application》2011年第11期893-905,共13页计算机技术与应用（英文版）

摘　　要：The problem of perfectly secure communication has enjoyed considerable theoretical treatment over the last decades. Results in this area include the identification of multipath transmission as a necessary ingredient, as well as quantum key distribution （QKD）, which can perfectly protect direct lines, Combining the advantages of the quantum and multipath transmission paradigm, as well as rigorously analyzing the security of such combined techniques, is possible by virtue of game-theory. Based on a game-theoretic measure of channel vulnerability, the authors prove the problem of setting up infrastructures for QKD-based multipath transmission to be NP-complete. The authors consider the problem in two flavors, both being computationally hard. Remarkably, the authors＇ results indicate that the P-vs-NP-question is only of minor effect for confidentiality, because either nowadays public-key cryptosystems remain secure （in case that P, NP） or infrastructures facilitating perfectly confidential communication can be constructed efficiently （in case that P = NP）.

关 键 词：Risk management CRYPTOGRAPHY complexity theory NP-COMPLETENESS network security 

分 类 号：TN918[电子电信—通信与信息系统] O22[电子电信—信息与通信工程]