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 -