TY - JOUR

T1 - Secret key generation with limited interaction

AU - Liu, Jingbo

AU - Cuff, Paul

AU - Verdu, Sergio

N1 - Funding Information:
Manuscript received June 3, 2016; revised March 27, 2017; accepted August 7, 2017. Date of publication August 29, 2017; date of current version October 18, 2017. This work was supported in part by NSF under Grant CCF-1319304, Grant CCF-1116013, Grant CCF-1319299, and Grant CCF-1350595, and in part by the Air Force Office of Scientific Research under Grant FA9550-15-1-0180. This paper was presented at the 2016 IEEE International Symposium on Information Theory.
Publisher Copyright:
© 2017 IEEE.

PY - 2017/11

Y1 - 2017/11

N2 - A basic two-terminal secret key generation model is considered, where the interactive communication rate between the terminals may be limited, and in particular may not be enough to achieve the maximum key rate. We first prove a multi-letter characterization of the key-communication rate region (where the number of auxiliary random variables depends on the number of rounds of the communication), and then provide an equivalent but simpler characterization in terms of concave envelopes in the case of unlimited number of rounds. Two extreme cases are given special attention. First, in the regime of very low communication rates, the key bits per interaction bit (KBIB) is expressed with a new 'symmetric strong data processing constant', which has a concave envelope characterization analogous to that of the conventional strong data processing constant. The symmetric strong data processing constant can be upper bounded by the supremum of the maximal correlation coefficient over a set of distributions, which allows us to determine the KBIB for binary symmetric sources, and conclude, in particular, that the interactive scheme is not more efficient than the one-way scheme at least in the low communication-rate regime. Second, a new characterization of the minimum interaction rate needed for achieving the maximum key rate (MIMK) is given, and we resolve a conjecture by Tyagi regarding the MIMK for (possibly nonsymmetric) binary sources. We also propose a new conjecture for binary symmetric sources that the interactive scheme is not more efficient than the one-way scheme at any communication rate.

AB - A basic two-terminal secret key generation model is considered, where the interactive communication rate between the terminals may be limited, and in particular may not be enough to achieve the maximum key rate. We first prove a multi-letter characterization of the key-communication rate region (where the number of auxiliary random variables depends on the number of rounds of the communication), and then provide an equivalent but simpler characterization in terms of concave envelopes in the case of unlimited number of rounds. Two extreme cases are given special attention. First, in the regime of very low communication rates, the key bits per interaction bit (KBIB) is expressed with a new 'symmetric strong data processing constant', which has a concave envelope characterization analogous to that of the conventional strong data processing constant. The symmetric strong data processing constant can be upper bounded by the supremum of the maximal correlation coefficient over a set of distributions, which allows us to determine the KBIB for binary symmetric sources, and conclude, in particular, that the interactive scheme is not more efficient than the one-way scheme at least in the low communication-rate regime. Second, a new characterization of the minimum interaction rate needed for achieving the maximum key rate (MIMK) is given, and we resolve a conjecture by Tyagi regarding the MIMK for (possibly nonsymmetric) binary sources. We also propose a new conjecture for binary symmetric sources that the interactive scheme is not more efficient than the one-way scheme at any communication rate.

KW - Communication complexity

KW - Convex envelope characterization

KW - Interactive communication

KW - Maximal correlation

KW - Random number generation

KW - Strong data processing

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

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

U2 - 10.1109/TIT.2017.2746104

DO - 10.1109/TIT.2017.2746104

M3 - Article

AN - SCOPUS:85028733573

SN - 0018-9448

VL - 63

SP - 7358

EP - 7381

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 11

M1 - 8017595

ER -