Key Agreement from Close Secrets over Unsecured Channels

Bhavana Kanukurthi, Leonid Reyzin

We consider information-theoretic key agreement between two parties sharing somewhat different versions of a secret w that has relatively little entropy. Such key agreement, also known as information reconciliation and privacy amplification over unsecured channels, was shown to be theoretically feasible by Renner and Wolf (Eurocrypt 2004), although no protocol that runs in polynomial time was described. We propose a protocol that is not only polynomial-time, but actually practical, requiring only a few seconds on consumer-grade computers. Our protocol can be seen as an interactive version of robust fuzzy extractors (Boyen et al., Eurocrypt 2005, Dodis et al., Crypto 2006). While robust fuzzy extractors, due to their noninteractive nature, require w to have entropy at least half its length, we have no such constraint. In fact, unlike in prior solutions, in our solution the entropy loss is essentially unrelated to the length or the entropy of w, and depends only on the security parameter.

Himanshu Tyagi, Shun Watanabe

Francesco Renna, Matthieu R. Bloch, Nicola Laurenti

In this paper, we study the fundamental limits of secret-key agreement over MIMO quasi-static fading channels. We provide closed-form expressions for the secret-key capacity in both the asymptotic high-power and low-power regimes. The optimal signaling strategy for the low-power regime is shown to be independent of the eavesdropper's channel and secret-key capacity is achieved by transmitting random Gaussian symbols along the direction corresponding to the maximal eigenvalue of the legitimate channel matrix. Hence, by beamforming and waterfilling over the main channel alone, one obtains a semi-blind key-agreement strategy in which the knowledge of the eavesdropper's channel is only required for privacy amplification. We also derive the probability that a target secret-key rate is not achieved by the optimal low-power signaling when assuming only statistical CSI about the eavesdropper's channel.

Hadi Ahmadi, Reihaneh Safavi–Naini

孝也 栃窪

Reihaneh Safavi–Naini, Peng‐Wei Wang

Key agreement (KA) is a fundamental cryptographic primitive. Assuming that Alice and Bob do not have any prior shared correlation, it has been proved that key agreement with security against a computationally unbounded adversary is impossible if communication is either over a fully public channel, or the channel is fully controlled by the adversary. In this paper we consider a setting where communication is over a partially corrupted channel, and there is no prior shared correlation. We formalize security and reliability of key agreement protocols in this setting, derive bounds on the rate of secret key agreement, and give constructions that achieve the respective bounds. Our results show that secret key agreement, and hence secret message transmission, is possible, as long as a small fraction of the transmitted symbols in each round remain untouched by the adversary. Our results can be extended to key agreement between nodes in a network, when the two nodes are connected by a set of disjoint paths, and in each round a subset of paths is eavesdropped and another subset (possibly with overlap) is tampered with. We relate our results to previous works, and discuss future directions.