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

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.