Sorry, you need to enable JavaScript to visit this website.

facebooktwittermailshare

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

up
0 users have voted:

Paper Details

Authors:
Holger Boche, Rafael F. Schaefer, and H. Vincent Poor
Submitted On:
16 May 2019 - 4:42am
Short Link:
Type:
Presentation Slides
Event:
Presenter's Name:
Holger Boche
Paper Code:
IFS-L1.1
Document Year:
2019
Cite

Document Files

icassp19_skg_talk.pdf

(20)

Subscribe

[1] Holger Boche, Rafael F. Schaefer, and H. Vincent Poor, "On the Computability of the Secret Key Capacity Under Rate Constraints", IEEE SigPort, 2019. [Online]. Available: http://sigport.org/4537. Accessed: Jul. 19, 2019.
@article{4537-19,
url = {http://sigport.org/4537},
author = {Holger Boche; Rafael F. Schaefer; and H. Vincent Poor },
publisher = {IEEE SigPort},
title = {On the Computability of the Secret Key Capacity Under Rate Constraints},
year = {2019} }
TY - EJOUR
T1 - On the Computability of the Secret Key Capacity Under Rate Constraints
AU - Holger Boche; Rafael F. Schaefer; and H. Vincent Poor
PY - 2019
PB - IEEE SigPort
UR - http://sigport.org/4537
ER -
Holger Boche, Rafael F. Schaefer, and H. Vincent Poor. (2019). On the Computability of the Secret Key Capacity Under Rate Constraints. IEEE SigPort. http://sigport.org/4537
Holger Boche, Rafael F. Schaefer, and H. Vincent Poor, 2019. On the Computability of the Secret Key Capacity Under Rate Constraints. Available at: http://sigport.org/4537.
Holger Boche, Rafael F. Schaefer, and H. Vincent Poor. (2019). "On the Computability of the Secret Key Capacity Under Rate Constraints." Web.
1. Holger Boche, Rafael F. Schaefer, and H. Vincent Poor. On the Computability of the Secret Key Capacity Under Rate Constraints [Internet]. IEEE SigPort; 2019. Available from : http://sigport.org/4537