TY - JOUR
T1 - Secure Communication and Identification Systems - Effective Performance Evaluation on Turing Machines
AU - Boche, Holger
AU - Schaefer, Rafael F.
AU - Poor, H. Vincent
N1 - Funding Information:
Manuscript received August 13, 2018; revised June 24, 2019; accepted July 9, 2019. Date of publication July 31, 2019; date of current version October 8, 2019. The work of H. Boche was supported in part by the German Research Foundation (DFG) under Gottfried Wilhelm Leibniz Prize Grant BO 1734/20-1, Grant BO 1734/24-3, and Grant BO 1734/25-1. The work of R. F. Schaefer was supported by the German Federal Ministry of Education and Research (BMBF) under the national initiative for “Post Shannon Communication (NewCom)” under Grant 16KIS1004. The work of H. V. Poor was supported in part by the U.S. National Science Foundation under Grant CCF-0939370 and Grant CCF-1513915. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Loukas Lazos. (Corresponding author: Rafael F. Schaefer.) H. Boche is with the Institute of Theoretical Information Technology, Technische Universität München, 80290 Munich, Germany, and also with the Munich Center for Quantum Science and Technology (MCQST), 80799 Munich, Germany (e-mail: boche@tum.de).
Publisher Copyright:
© 2005-2012 IEEE.
PY - 2020
Y1 - 2020
N2 - Modern communication systems need to satisfy pre-specified requirements on spectral efficiency and security. Physical layer security is a concept that unifies both and connects them with entropic quantities. In this paper, a framework based on Turing machines is developed to address the question of deciding whether or not a communication system meets these requirements. It is known that the class of Turing solvable problems coincides with the class of algorithmically solvable problems so that this framework provides the theoretical basis for effective verification of such performance requirements. A key issue here is to decide whether or not the performance functions, i.e., capacities, of relevant communication scenarios, particularly those with secrecy requirements and active adversaries, are Turing computable. This is a necessary condition for the corresponding communication protocols to be effectively verifiable. Within this framework, it is then shown that for certain scenarios including the wiretap channel the corresponding capacities are Turing computable. Next, a general necessary condition on the performance function for Turing computability is established. With this, it is shown that for certain scenarios, including the wiretap channel with an active jammer, the performance functions are not computable when deterministic codes are used. As a consequence, such performance functions are also not computable on all other computer architectures such as the von Neumann-architecture or the register machines.
AB - Modern communication systems need to satisfy pre-specified requirements on spectral efficiency and security. Physical layer security is a concept that unifies both and connects them with entropic quantities. In this paper, a framework based on Turing machines is developed to address the question of deciding whether or not a communication system meets these requirements. It is known that the class of Turing solvable problems coincides with the class of algorithmically solvable problems so that this framework provides the theoretical basis for effective verification of such performance requirements. A key issue here is to decide whether or not the performance functions, i.e., capacities, of relevant communication scenarios, particularly those with secrecy requirements and active adversaries, are Turing computable. This is a necessary condition for the corresponding communication protocols to be effectively verifiable. Within this framework, it is then shown that for certain scenarios including the wiretap channel the corresponding capacities are Turing computable. Next, a general necessary condition on the performance function for Turing computability is established. With this, it is shown that for certain scenarios, including the wiretap channel with an active jammer, the performance functions are not computable when deterministic codes are used. As a consequence, such performance functions are also not computable on all other computer architectures such as the von Neumann-architecture or the register machines.
KW - Banach-Mazur computability
KW - Borel computability
KW - Secrecy capacity
KW - Turing machine
KW - identification capacity
UR - http://www.scopus.com/inward/record.url?scp=85070399355&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85070399355&partnerID=8YFLogxK
U2 - 10.1109/TIFS.2019.2932226
DO - 10.1109/TIFS.2019.2932226
M3 - Article
AN - SCOPUS:85070399355
SN - 1556-6013
VL - 15
SP - 1013
EP - 1025
JO - IEEE Transactions on Information Forensics and Security
JF - IEEE Transactions on Information Forensics and Security
M1 - 8782581
ER -