Resource Allocation for Secure Communication Systems: Algorithmic Solvability

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication2019 IEEE International Workshop on Information Forensics and Security, WIFS 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781728132174
DOIs
StatePublished - Dec 2019
Event2019 IEEE International Workshop on Information Forensics and Security, WIFS 2019 - Delft, Netherlands
Duration: Dec 9 2019Dec 12 2019

Publication series

Name2019 IEEE International Workshop on Information Forensics and Security, WIFS 2019

Conference

Conference2019 IEEE International Workshop on Information Forensics and Security, WIFS 2019
CountryNetherlands
CityDelft
Period12/9/1912/12/19

All Science Journal Classification (ASJC) codes

  • Information Systems and Management
  • Safety, Risk, Reliability and Quality
  • Library and Information Sciences
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Resource Allocation for Secure Communication Systems: Algorithmic Solvability'. Together they form a unique fingerprint.

  • Cite this

    Boche, H., Schaefer, R. F., & Vincent Poor, H. (2019). Resource Allocation for Secure Communication Systems: Algorithmic Solvability. In 2019 IEEE International Workshop on Information Forensics and Security, WIFS 2019 [9035108] (2019 IEEE International Workshop on Information Forensics and Security, WIFS 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/WIFS47025.2019.9035108