On the Computability of the Secret Key Capacity under Rate Constraints

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

doi:10.1109/ICASSP.2019.8683122

On the Computability of the Secret Key Capacity under Rate Constraints

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

11 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	2427-2431
Number of pages	5
ISBN (Electronic)	9781479981311
DOIs	https://doi.org/10.1109/ICASSP.2019.8683122
State	Published - May 2019
Externally published	Yes
Event	44th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Brighton, United Kingdom Duration: May 12 2019 → May 17 2019

Publication series

Name	ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
Volume	2019-May
ISSN (Print)	1520-6149

Conference

Conference	44th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019
Country/Territory	United Kingdom
City	Brighton
Period	5/12/19 → 5/17/19

All Science Journal Classification (ASJC) codes

Software
Signal Processing
Electrical and Electronic Engineering

Keywords

Secret key generation
Turing computability
rate constraint
secret key capacity

Access to Document

10.1109/ICASSP.2019.8683122

Cite this

Boche, H., Schaefer, R. F., & Vincent Poor, H. (2019). On the Computability of the Secret Key Capacity under Rate Constraints. In 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings (pp. 2427-2431). Article 8683122 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 2019-May). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICASSP.2019.8683122

Boche, Holger ; Schaefer, Rafael F. ; Vincent Poor, H. / On the Computability of the Secret Key Capacity under Rate Constraints. 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 2427-2431 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).

@inproceedings{28ad9fd37d5841d6ae32767a5cb1837d,

title = "On the Computability of the Secret Key Capacity under Rate Constraints",

abstract = "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.",

keywords = "Secret key generation, Turing computability, rate constraint, secret key capacity",

author = "Holger Boche and Schaefer, {Rafael F.} and {Vincent Poor}, H.",

note = "Publisher Copyright: {\textcopyright} 2019 IEEE.; 44th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 ; Conference date: 12-05-2019 Through 17-05-2019",

year = "2019",

month = may,

doi = "10.1109/ICASSP.2019.8683122",

language = "English (US)",

series = "ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "2427--2431",

booktitle = "2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings",

address = "United States",

}

Boche, H, Schaefer, RF & Vincent Poor, H 2019, On the Computability of the Secret Key Capacity under Rate Constraints. in 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings., 8683122, ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, vol. 2019-May, Institute of Electrical and Electronics Engineers Inc., pp. 2427-2431, 44th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019, Brighton, United Kingdom, 5/12/19. https://doi.org/10.1109/ICASSP.2019.8683122

On the Computability of the Secret Key Capacity under Rate Constraints. / Boche, Holger; Schaefer, Rafael F.; Vincent Poor, H.
2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. p. 2427-2431 8683122 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 2019-May).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On the Computability of the Secret Key Capacity under Rate Constraints

AU - Boche, Holger

AU - Schaefer, Rafael F.

AU - Vincent Poor, H.

PY - 2019/5

Y1 - 2019/5

N2 - 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.

AB - 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.

KW - Secret key generation

KW - Turing computability

KW - rate constraint

KW - secret key capacity

UR - http://www.scopus.com/inward/record.url?scp=85068994234&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85068994234&partnerID=8YFLogxK

U2 - 10.1109/ICASSP.2019.8683122

DO - 10.1109/ICASSP.2019.8683122

M3 - Conference contribution

AN - SCOPUS:85068994234

T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings

SP - 2427

EP - 2431

BT - 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 44th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019

Y2 - 12 May 2019 through 17 May 2019

ER -

Boche H, Schaefer RF, Vincent Poor H. On the Computability of the Secret Key Capacity under Rate Constraints. In 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2019. p. 2427-2431. 8683122. (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). doi: 10.1109/ICASSP.2019.8683122

On the Computability of the Secret Key Capacity under Rate Constraints

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this