Rate Region for Interactive Key Generation and Common Randomness Generation
Rate Region for Interactive Key Generation and Common Randomness Generation
复制标题
交互式密钥生成和公共随机性生成的速率区域
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Jingbo Liu
中科院分区：
文献类型：
--
作者：
Jingbo Liu
本文的目的是提供交互式密钥生成和CR生成中速率区域的多字母表征的自包含证明，作为我们最近对相同问题[1]的某些单字母表征/界的工作的支持文档。交互式CR生成问题在几个方面类似于交互式源编码[2]。此外，两轮CR生成的多字母解决方案[3，定理4.2]或最大密钥速率所需的最小通信[4，定理4]是已知的。虽然很可能这些特殊情况的证明（基于典型化）可以扩展以获得本文中的结果，但我们使用似然编码器[5]作为技术上更简单且适用于非离散字母的替代证明技术。1 .密钥生成与CR生成的关系（假设随机编码器）•如果（R,R1, R2）对于密钥生成是可实现的，那么（R+R1 +R2, R1, R2）对于CR生成是可实现的实际上，我们可以假设每一轮的通信消息是渐近独立的，否则，带侧信息问题的源编码的可实现方案意味着这些消息可以被压缩以满足独立性约束。我们还可以假设密钥生成中的通信速率正好是R1和R2，否则我们只需添加额外的随机位来扩大通信速率。然后设CR = (key, communication)，速率为R+R1 +R2，因为key和communication是独立的。•如果（R,R1, R2）对于CR生成是可实现的，那么（R−R1−R2, R1, R2）对于密钥生成是可实现的：这是因为使用隐私放大/剩余哈希引理（参见Renner 's one-shot bound[6]），我们可以渐近地独立于通信提取H（CR|通信）位。（未来的工作：值得比较剩余哈希的一次边界与直接从似然编码器得到的一次边界）。以上观察结果表明，CR生成与密钥生成在渐近上是等价的问题，因此足以证明概念上更简单的CR生成的可实现性和逆反性。2。多字母速率区域本节描述了密钥生成和CR生成的速率区域。
The purpose of this note is to provide a self-contained proof of a multi-letter characterization of the rate regions in interactive key generation and CR generation, as a supporting document for our recent work on certain single-letter characterization/bounds for the same problem [1]. The interactive CR generation problem is in several ways similar to interactive source coding [2]. Also, the multi-letter solutions for two-round CR generation [3, Theorem 4.2] or the minimum communication needed for maximum key rates [4, Theorem 4] are known. Although it is probable that the proofs of these special cases (based on typicality) can be extended to obtain the results in this note, we use the likelihood encoder [5] as an alternative proof technique which is technically simpler and applies to non-discrete alphabets. I. RELATION BETWEEN KEY GENERATION AND CR GENERATION (ASSUMING STOCHASTIC ENCODERS) • If (R,R1, R2) is achievable for key generation, then (R+R1 +R2, R1, R2) is achievable for CR generation. Indeed, we can assume that the communication messages in each round are asymptotically independent, since otherwise the achievability scheme of the source coding with side information problem implies that these messages can be compressed to satisfy the independence constraint. We can also assume that the communication rates in key generation are exactly R1 and R2, since otherwise we simply pad extra random bits to enlarge the communication rates. Then let CR = (key, communication) which has rate R+R1 +R2 because of the independence between the key and the communication. • If (R,R1, R2) is achievable for CR generation, then (R−R1−R2, R1, R2) is achievable for key generation: this is because using privacy amplification/leftover hash lemma (cf. Renner’s one-shot bound [6]), we can extract H(CR|communication) bits independent of communication asymptotically. (Future work: worth comparing one-shot bound from leftover hash with the one-shot bound directly from the likelihood encoder). The above observations imply that, asymptotically, CR generation and key generation are equivalent problems, so it suffices to prove the achievability and converse for CR generation which is conceptually simpler. II. MULTI-LETTER RATE REGIONS The rate regions for key generation and CR generation are characterized in this section.