Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Transactions on Information Forensics and Security

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

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

Published Jul 31, 2019• 20 citations
Publisher

Abstract

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.

DOI
10.1109/tifs.2019.2932226

Related papers

Performance Evaluation of Secure Communication Systems on Turing Machines

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

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. This paper presents a frame-work based on Turing machines 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 allows for effective verification of such performance requirements. In this paper, it is shown that certain scenarios such as the wire-tap channel or compound channel are Turing computable so that the corresponding communication protocols can be effectively verified. A condition is presented and proved under which a communication scenario is not Turing computable. The channel with an active jammer falls into this category when deterministic codes are used. Interestingly, random codes robustify the channel with an active jammer in the sense that it becomes Turing computable and the corresponding communication protocol effectively verifiable.

IEEE International Workshop on Information Forensics and Security•Dec 1, 2018•4 citations

Turing Meets Shannon: On the Algorithmic Computability of the Capacities of Secure Communication Systems (Invited Paper)

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

This paper presents the recent progress in studying the algorithmic computability of capacity expressions of secure communication systems. Several communication scenarios are discussed and reviewed including the classical wiretap channel, the wiretap channel with an active jammer, and the problem of secret key generation.

IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)•Jul 1, 2019•5 citations

Resource Allocation for Secure Communication Systems: Algorithmic Solvability

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

Medium access control and in particular resource allocation is one of the most important tasks when designing wireless communication systems as it determines the overall performance of a system. For the particular allocation of the available resources it is of crucial importance to know whether or not a channel supports a certain quality-of-service (QoS) requirement. This paper develops a decision framework based on Turing machines and studies the algorithmic decidability of whether or not a QoS requirement is met. Turing machines have no limitations on computational complexity, computing capacity, and storage. They can simulate any given algorithm and therewith characterize the fundamental performance limits for today’s digital computers. In this paper, secure communication and identification systems are considered both under channel uncertainty and adversarial attacks. While for perfect channel state information, the question is decidable since the corresponding capacity function is computable, it is shown that the corresponding questions become semidecidable in the case of channel uncertainty and adversarial attacks. This means there exist Turing machines that stop and output the correct answer if and only if a channel supports the given QoS requirement. Interestingly, the opposite question of whether a channel capacity is below a certain threshold is not semidecidable.

IEEE International Workshop on Information Forensics and Security•Dec 1, 2019•5 citations

Characterization of the Arithmetic Complexity of the Secrecy Capacity of Fast-Fading Gaussian Channels

Holger Boche, Andrea Grigorescu, Rafael F. Schaefer +1 more

This paper studies the computability of the secrecy capacity of fast-fading wiretap channels from an algorithmic perspective, examining whether it can be computed algorithmically or not. To address this question, the concept of Turing machines is used, which establishes fundamental performance limits of digital computers. It is shown that certain computable continuous fading probability distribution functions yield secrecy capacities that are non-computable numbers. Additionally, we assess the secrecy capacity's classification within the arithmetical hierarchy, revealing the absence of computable achievability and converse bounds.

arXiv:2501.11636•Jan 20, 2025•0 citations

Arithmetic Complexity of the Secrecy Capacity of Fast-Fading Gaussian Channels

Holger Boche, Andrea Grigorescu, Rafael F. Schaefer +1 more

This paper studies the computability of the secrecy capacity of fast-fading wiretap channels from an algorithmic perspective, examining whether it can be computed algorithmically. To address this question, the concept of Turing machines is used, providing the fundamental performance limits of digital computers. It is shown that certain computable continuous fading probability distribution functions yield secrecy capacities that are non-computable numbers. Additionally, we assess the secrecy capacity's classification within the arithmetic hierarchy, revealing absence of computable achievability and converse bounds.

IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•1 citation

Secure Identification for Gaussian Channels and Identification for Multi-Antenna Gaussian Channels

Wafa Labidi, Christian Deppe, Holger Boche

New applications in modern communications are demanding robust and ultra-reliable low latency information exchange such as machine-to-machine and human-to-machine communications. For many of these applications, the identification approach of Ahlswede and Dueck is much more efficient than the classical message transmission scheme proposed by Shannon. Previous studies concentrate mainly on identification over discrete channels. For discrete channels, it was proved that identification is robust under channels uncertainty. Furthermore, optimal identification schemes that are secure and robust against jamming attacks have been considered. However, no results for continuous channels have yet been established. That is why we focus on the continuous case: the Gaussian channel for its known practical relevance. We deal with secure identification over Gaussian channels. Provable secure communication is of a high interest for future communication systems. A key technique for implementing secure communication is the physical layer security based on information theoretic security. We model this with the wiretap channel. In particular, we provide a suitable coding scheme for the Gaussian wiretap channel (GWC) and determine the corresponding secure identification capacity. We also consider Multiple-Input Multiple-Output (MIMO) Gaussian channels and provide an efficient signal-processing scheme. This scheme allows a separation of signal-processing and Gaussian coding.

arXiv:2011.06443•Nov 12, 2020•3 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.
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. This paper presents a frame-work based on Turing machines 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 allows for effective verification of such performance requirements. In this paper, it is shown that certain scenarios such as the wire-tap channel or compound channel are Turing computable so that the corresponding communication protocols can be effectively verified. A condition is presented and proved under which a communication scenario is not Turing computable. The channel with an active jammer falls into this category when deterministic codes are used. Interestingly, random codes robustify the channel with an active jammer in the sense that it becomes Turing computable and the corresponding communication protocol effectively verifiable.
Medium access control and in particular resource allocation is one of the most important tasks when designing wireless communication systems as it determines the overall performance of a system. For the particular allocation of the available resources it is of crucial importance to know whether or not a channel supports a certain quality-of-service (QoS) requirement. This paper develops a decision framework based on Turing machines and studies the algorithmic decidability of whether or not a QoS requirement is met. Turing machines have no limitations on computational complexity, computing capacity, and storage. They can simulate any given algorithm and therewith characterize the fundamental performance limits for today’s digital computers. In this paper, secure communication and identification systems are considered both under channel uncertainty and adversarial attacks. While for perfect channel state information, the question is decidable since the corresponding capacity function is computable, it is shown that the corresponding questions become semidecidable in the case of channel uncertainty and adversarial attacks. This means there exist Turing machines that stop and output the correct answer if and only if a channel supports the given QoS requirement. Interestingly, the opposite question of whether a channel capacity is below a certain threshold is not semidecidable.
This paper studies the computability of the secrecy capacity of fast-fading wiretap channels from an algorithmic perspective, examining whether it can be computed algorithmically or not. To address this question, the concept of Turing machines is used, which establishes fundamental performance limits of digital computers. It is shown that certain computable continuous fading probability distribution functions yield secrecy capacities that are non-computable numbers. Additionally, we assess the secrecy capacity's classification within the arithmetical hierarchy, revealing the absence of computable achievability and converse bounds.
This paper studies the computability of the secrecy capacity of fast-fading wiretap channels from an algorithmic perspective, examining whether it can be computed algorithmically. To address this question, the concept of Turing machines is used, providing the fundamental performance limits of digital computers. It is shown that certain computable continuous fading probability distribution functions yield secrecy capacities that are non-computable numbers. Additionally, we assess the secrecy capacity's classification within the arithmetic hierarchy, revealing absence of computable achievability and converse bounds.
New applications in modern communications are demanding robust and ultra-reliable low latency information exchange such as machine-to-machine and human-to-machine communications. For many of these applications, the identification approach of Ahlswede and Dueck is much more efficient than the classical message transmission scheme proposed by Shannon. Previous studies concentrate mainly on identification over discrete channels. For discrete channels, it was proved that identification is robust under channels uncertainty. Furthermore, optimal identification schemes that are secure and robust against jamming attacks have been considered. However, no results for continuous channels have yet been established. That is why we focus on the continuous case: the Gaussian channel for its known practical relevance. We deal with secure identification over Gaussian channels. Provable secure communication is of a high interest for future communication systems. A key technique for implementing secure communication is the physical layer security based on information theoretic security. We model this with the wiretap channel. In particular, we provide a suitable coding scheme for the Gaussian wiretap channel (GWC) and determine the corresponding secure identification capacity. We also consider Multiple-Input Multiple-Output (MIMO) Gaussian channels and provide an efficient signal-processing scheme. This scheme allows a separation of signal-processing and Gaussian coding.