Abstract. Common Randomness Generation (CRG) and Secret Key Establishment (SKE) are fundamental primitives that are used in information-theoretic coding and cryptography. We study these two problems over the two-way channel model of communication, introduced by Shannon. In this model, the common randomness (CK) capacity is defined as the maximum number of random bits per channel use that the two parties can generate. The secret key (SK) capacity is defined similarly when the random bits are also required to be secure against a passive adversary. We provide lower bounds on the two capacities. These lower bounds are tighter than those one might derive based on the previously known results. We prove our lower bounds by proposing a two-round, two-level coding construction over the two-way channel. We show that the lower bound on the common randomness capacity can also be achieved using a simple interactive channel coding (ICC) method. We furthermore provide upper bounds on these capacities and show that the lower and the upper bounds coincide when the two-way channel consists of two independent (physically degraded) one-way channels. We apply the results to the case where the channels are binary symmetric.
Abstract. Common Randomness Generation (CRG) and Secret Key Establishment (SKE) are fundamental primitives that are used in information-theoretic coding and cryptography. We study these two problems over the two-way channel model of communication, introduced by Shannon. In this model, the common randomness (CK) capacity is defined as the maximum number of random bits per channel use that the two parties can generate. The secret key (SK) capacity is defined similarly when the random bits are also required to be secure against a passive adversary. We provide lower bounds on the two capacities. These lower bounds are tighter than those one might derive based on the previously known results. We prove our lower bounds by proposing a two-round, two-level coding construction over the two-way channel. We show that the lower bound on the common randomness capacity can also be achieved using a simple interactive channel coding (ICC) method. We furthermore provide upper bounds on these capacities and show that the lower and the upper bounds coincide when the two-way channel consists of two independent (physically degraded) one-way channels. We apply the results to the case where the channels are binary symmetric.
Abstract. We study the problem of unconditionally secure Secret Key Establishment (SKE) when Alice and Bob are connected by two noisy channels in opposite directions, and the channels are eavesdropped by Eve. We consider the case that Alice and Bob do not have any sources of initial randomness at their disposal. We start by discussing special cases of interest where SKE is impossible, and then provide a simple SKE construction over a binary symmetric channel that achieves some rates of secret key. We next focus on the Secret Key (SK) capacity, i.e., the highest rate of secure and reliable key establishment (in bits per channel use) that the parties can achieve. Relying on the existence of capacity-achieving coding schemes, we propose a multi-round SKE protocol, called the main protocol, that proves a lower bound on the SK capacity. The main protocol consists of an initialization round, followed by repeated use of a two-round SKE protocol, called the basic protocol. We also provide an upper bound on the SK capacity and show that the two bounds coincide when channels do not leak information to the adversary. We apply the results to the case that communicants are connected by binary symmetric channels. 1
In this work we study the problems of common randomness generation (CRG) and secret key generation (SKG). In the CRG problem, two parties, Alice and Bob, receive samples X and Y, respectively, from some joint source distribution μ. The two parties wish to agree on a key consisting of many bits of randomness, by exchanging messages that depend on each party’s respective input and the previous messages. The SKG problem is the same as CRG, except that an eavesdropper who observes the messages must not be able to determine much information about the key. We study the tradeoff between the minimum total length of all messages for a protocol generating a given number of bits of randomness and the minimum possible number of rounds in such a protocol. We construct a source distribution parametrized by positive integers r, n, and l, achieving such a tradeoff in a strong sense: when Alice and Bob can use r + 2 rounds of communication and l ≥ n, they can agree on l bits of entropy by communicating only O(log n) bits, but when they are restricted to r rounds of communication, they require communication of Ω(n^(1/2) / poly log(n)) bits to agree on l bits of entropy. We also prove an analogous result for the setting in which Alice and Bob can amortize, meaning that they receive N i.i.d. samples of (X, Y) from μ, and the communication and key length, respectively, are measured by the ratio of the actual number of bits communicated and the actual key length, respectively, to N.
Secret Key Establishment (SKE) over a pair of independent Discrete Memoryless Broadcast Channels (DMBCs) was studied in where lower and upper bounds on the secret-key capacity were provided. In this paper, we study the above setup for two cases: (1) the DMBCs have “secrecy potential”, and (2) the DMBCs are stochastically degraded with independent channels. For (1), we propose a simple SKE protocol using the novel Interactive Channel Coding (ICC) method and prove that it achieves the lower bound. For (2), we give a simplified expression for the lower bound and prove that, when one of the legitimate parties sends only i.i.d. variables, the lower bound is tight and the capacity is achieved by a two-round protocol.
We study the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively get samples X1, X2, … and Y1, Y2, … with the pairs (X1, Y1), (X2, Y2), … being drawn independently from some known probability distribution µ. They wish to communicate so as to agree on L bits of randomness. The SKG problem is the restriction of the CRG problem to the case where the key is required to be close to random even to an eavesdropper who can listen to their communication (but does not have access to the inputs of Alice and Bob). In this work, we study the relationship between the amount of communication and the number of rounds of interaction in both the CRG and the SKG problems. Specifically, we construct a family of distributions µ = µr,n,L, parametrized by integers r, n and L, such that for every r there exists a constant b = b(r) for which CRG (respectively SKG) is feasible when (Xi, Yi) ∼ µr,n,L with r + 1 rounds of communication, each consisting of O(log n) bits, but when restricted to r/2 – 2 rounds of interaction, the total communication must exceed Ω(n/ logb(n)) bits. Prior to our work no separations were known for r ≥ 2.
We study the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively get samples X1,X2,… and Y1,Y2,… with the pairs (X1,Y1), (X2,Y2), … being drawn independently from some known probability distribution μ. They wish to communicate so as to agree on L bits of randomness. The SKG problem is the restriction of the CRG problem to the case where the key is required to be close to random even to an eavesdropper who can listen to their communication (but does not have access to the inputs of Alice and Bob). In this work, we study the relationship between the amount of communication and the number of rounds of interaction in both the CRG and the SKG problems. Specifically, we construct a family of distributions μ=μr,n,L, parametrized by integers r, n and L, such that for every r there exists a constant b=b(r) for which CRG (respectively SKG) is feasible when (Xi,Yi)∼μr,n,L with r+1 rounds of communication, each consisting of O(logn) bits, but when restricted to r/2−3 rounds of interaction, the total communication must exceed Ω(n/logb(n)) bits. Prior to our work no separations were known for r≥2.
Abstract—We study the secret-key capacity in a joint source-channel coding setup—the terminals are connected over a discrete memoryless channel and have access to side information, modelled as a pair of discrete memoryless source sequences. As our main result, we establish the upper and lower bounds on the secret-key capacity. In the lower bound expression, the equivocation terms of the source and channel components are functionally additive even though the coding scheme generates a single secret-key by jointly taking into account the source and channel equivocations. Our bounds coincide, thus establishing the capacity, when the underlying wiretap channel can be decomposed into a set of independent, parallel, and reversely degraded channels. For the case of parallel Gaussian channels and jointly Gaussian sources we show that Gaussian codebooks achieve the secret-key capacity. In addition, when the eavesdropper also observes a correlated side information sequence, we establish the secret-key capacity when both the source and channel of the eavesdropper are a degraded version of the legitimate receiver. We finally also treat the case when a public discussion channel is available, propose a separation based coding scheme, and establish its optimality when the channel output symbols of the legitimate receiver and eavesdropper are conditionally independent given the input. Index Terms—Information theoretic security, joint sourcechannel coding, public discussion, secret-key agreement, wiretap channel. I.