IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)

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

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

Published Jul 1, 2019• 5 citations

Abstract

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.

DOI: 10.1109/spawc.2019.8815442

Related papers

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

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

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.

IEEE Transactions on Information Forensics and SecurityJul 31, 201920 citations

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 SecurityDec 1, 20184 citations

On the Computability of the Secret Key Capacity under Rate Constraints

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

Secret key generation refers to the problem of generating a common secret key without revealing any information about it to an eaves-dropper. All users observe correlated components of a common source and can further use a rate-limited public channel for discussion which is open to eavesdroppers. This paper studies the Turing computability of the secret key capacity with a single rate-limited public forward transmission. Turing computability provides fundamental performance limits for today’s digital computers. It is shown that the secret key capacity under rate constraints is not Turing computable, and consequently there is no algorithm that can simulate or compute the secret key capacity, even if there are no limitations on computational complexity and computing power. On the other hand, if there are no rate constraints on the forward transmission, the secret key capacity is Turing computable. This shows that restricting the communication rate over the public channel transforms a Turing computable problem into a non-computable problem. To the best of our knowledge, this is the first time that such a phenomenon has been observed.

IEEE International Conference on Acoustics Speech and Signal ProcessingApr 17, 201915 citations

Previous messages provide the key to achieve shannon capacity in a wiretap channel

Shahid Mehraj Shah, S Parameswaran, Vinod Sharma

We consider a wiretap channel and use previously transmitted messages to generate a secret key which increases the secrecy capacity. This can be bootstrapped to increase the secrecy capacity to the Shannon capacity without using any feedback or extra channel while retaining the strong secrecy of the wiretap channel.

arXiv:1404.5945IEEE International Conference on Communications workshopsJun 1, 20132 citations

Previous messages provide the key to achieve shannon capacity in a wiretap channel

Shahid Mehraj Shah, Parameswaran S, Vinod Sharma

Aug 16, 20167 citations

On the Algorithmic Computability of the Secret Key and Authentication Capacity Under Channel, Storage, and Privacy Leakage Constraints

Holger Boche, Rafael F. Schaefer, Sebastian Baur +1 more

Secret key generation refers to the problem of generating a common secret key without revealing any information about it to an eavesdropper. All users observe correlated components of a common source and can further use a noisy public channel for discussion, which is open to eavesdroppers. A related problem is that of secure authentication, which has structural similarities and connections to the first problem. For authentication, users need to be enrolled and securely authenticated while minimizing the privacy leakage rate. This paper studies the algorithmic computability of the forward secret key capacity and the secure authentication capacity. For the algorithmic computability, the concept of a Turing machine is used as it provides fundamental performance limits for today's digital computers. In this paper, it is shown that the forward secret key capacity with a noisy public channel is not computable and consequently, there is no algorithm that can simulate or compute the secret key capacity; even if there are no limitations on computational complexity and computing power. On the other hand, if the public channel is noiseless so that there are no rate constraints on the public communication, the secret key capacity is a computable continuous function, which is the strongest form of computability. A similar behavior is subsequently observed for the authentication problem: The secure authentication capacity under storage rate and privacy leakage rate constraints is not computable, while the case without privacy leakage rate constraints is computable.

IEEE Transactions on Signal ProcessingJul 24, 201932 citations