Secure Communication and Identification Systems - Effective Performance Evaluation on Turing Machines

Holger Boche, Rafael F. Schaefer, H. Vincent Poor

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


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.

Original languageEnglish (US)
Article number8782581
Pages (from-to)1013-1025
Number of pages13
JournalIEEE Transactions on Information Forensics and Security
StatePublished - 2020

All Science Journal Classification (ASJC) codes

  • Safety, Risk, Reliability and Quality
  • Computer Networks and Communications


  • Banach-Mazur computability
  • Borel computability
  • Secrecy capacity
  • Turing machine
  • identification capacity


Dive into the research topics of 'Secure Communication and Identification Systems - Effective Performance Evaluation on Turing Machines'. Together they form a unique fingerprint.

Cite this