Secret key generation with limited interaction

Jingbo Liu, Paul Cuff, Sergio Verdu

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


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.

Original languageEnglish (US)
Article number8017595
Pages (from-to)7358-7381
Number of pages24
JournalIEEE Transactions on Information Theory
Issue number11
StatePublished - Nov 2017

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


  • Communication complexity
  • Convex envelope characterization
  • Interactive communication
  • Maximal correlation
  • Random number generation
  • Strong data processing


Dive into the research topics of 'Secret key generation with limited interaction'. Together they form a unique fingerprint.

Cite this