Secret key establishment from common randomness has been traditionally investigated under cartain limiting assumptions, of which the most ubiquitous appears to be that the information available to all parties comes in the form of independent and identically distributed (i.i.d.) samples of some correlated random variables. Unfortunately, models employing the i.i.d assumption are often not accurate representations of real scenarios. A more capable model would represent the available information as correlated hidden Markov models (HMMs), based on the same underlying Markov chain. Such a model accurately reflects the scenario where all parties have access to imperfect observations of the same source random process, exhibiting a certain time dependency. In this paper, we derive a computationally-efficient asymptotic converse bound for the secret key capacity of the correlated-HMM scenario. The main obstacle, not only for our model, but also for other non-i.i.d cases, is the computational complexity. We address this by converting the initial bound to a product of Markov random matrices, and using recent results regarding its convergence to a Lyapunov exponent. The methods developed in the paper are easily extensible to derive a secret-key capacity lower bound.
Secret key establishment from common randomness has been traditionally investigated under cartain limiting assumptions, of which the most ubiquitous appears to be that the information available to all parties comes in the form of independent and identically distributed (i.i.d.) samples of some correlated random variables. Unfortunately, models employing the i.i.d assumption are often not accurate representations of real scenarios. A more capable model would represent the available information as correlated hidden Markov models (HMMs), based on the same underlying Markov chain. Such a model accurately reflects the scenario where all parties have access to imperfect observations of the same source random process, exhibiting a certain time dependency. In this paper, we derive a computationally-efficient asymptotic converse bound for the secret key capacity of the correlated-HMM scenario. The main obstacle, not only for our model, but also for other non-i.i.d cases, is the computational complexity. We address this by converting the initial bound to a product of Markov random matrices, and using recent results regarding its convergence to a Lyapunov exponent. The methods developed in the paper are easily extensible to derive a secret-key capacity lower bound.
Establishing secret common randomness between two or multiple devices in a network resides at the root of communication security. In its most frequent form of key establishment, the problem is traditionally decomposed into a randomness generation stage (randomness purity is subject to employing often costly true random number generators) and an information-exchange agreement stage, which relies either on public-key infrastructure or on symmetric encryption (key wrapping).\nThis dissertation has been divided into two main parts. In the first part, an algorithm called KERMAN is proposed to establish secret-common-randomness for ad-hoc networks, which works by harvesting randomness directly from the network routing metadata, thus achieving both pure randomness generation and (implicitly) secret-key agreement. This algorithm relies on the route discovery phase of an ad-hoc network employing the Dynamic Source Routing protocol, is lightweight, and requires relatively little communication overhead. The algorithm is evaluated for various network parameters, and different levels of complexity, in OPNET network simulator. The results show that, in just ten minutes, thousands of secret random bits can be generated network-wide, between different pairs in a network of fifty users.\nThe proposed algorithm described in this first part of this research study has inspired study of the problem of generating a secret key\nbased on a more practical model to be explored in the second part of this dissertation. Indeed, secret key establishment from common randomness has been traditionally investigated under certain limiting assumptions, of which the most ubiquitous appears to be that the information available to all parties comes in the form of independent and identically distributed (i.i.d.) samples of some correlated andom variables. Unfortunately, models employing the i.i.d assumption are often not accurate representations of real scenarios. A more capable model would represent the available information as correlated hidden Markov models (HMMs), based on the same underlying Markov chain. Such a model accurately reflects the scenario where all parties have access to imperfect observations of the same source random process, exhibiting a certain time dependency. In the second part of the dissertation , a computationally-efficient asymptotic bounds for the secret key capacity of the correlated-HMM scenario has been derived. The main obstacle, not only for this model, but also for other non-i.i.d cases, is the computational complexity. This problem has been addressed by converting the initial bound to a product of Markov random matrices, and using recent results regarding its convergence to a Lyapunov exponent.
Traditional approaches to secret key establishment based on common randomness have been based on certain restrictive assumptions, such as considering the available common randomness to consist of independent and identically distributed (i.i.d) repetitions of correlated random variables. Unfortunately, the i.i.d assumption does not generally reflect the conditions of real-life scenarios. For this reason, the current paper investigates the key-establishment potential of a more pragmatic model, in which all parties have access to imperfect information about a common source modeled as a Markov chain. Each party's information thus comes in the form of a hidden Markov model and, since the different parties share the same underlying Markov chain, we call the overall model a sibling hidden Markov model (SHMM). This paper studies upper and lower bounds on the secret key capacity for various types of SHMM. The difficulty of the problem emerges from its prohibitive computational cost. To address this obstacle, we represent the joint probability of the observations as the L1norm of a Markov random matrix, and use its convergence to a Lyapunov exponent.
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.
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.
In the classical Secret-Key generation model, Common Randomness is generated by two terminals based on the observation of correlated components of a common source, while keeping it secret from a non-legitimate observer. It is assumed that the statistics of the source are known to all participants. In this work, the Secret-Key generation model based on a compound source is studied where the source realization is unknown. The protocol should guarantee the security and reliability of the generated Secret-Key, simultaneously for all possible realizations of the compound source. A single-letter lower-bound of the Secret-Key capacity is derived for the case where the public communication rate is limited. Furthermore, a multi-letter capacity formula is computed for the case where the public communication is unconstrained.
We study the problem of information-theoretically secure secret key agreement under the well-known source model and channel model. In both of these models the parties wish to create a shared secret key that is secure from an eavesdropper with unlimited computational resources. In the channel model, the first party can choose a sequence of inputs to a discrete memoryless channel, which has outputs at the other parties and at the eavesdropper. After each channel use, the parties can engage in arbitrarily many rounds of interactive authenticated communication over a public channel. At the end, each party should be able to generate the key. In the source model, the parties wishing to generate a secret key (as well as the eavesdropper) receive a certain number of independent identically distributed copies of jointly distributed random variables after which the parties are allowed interactive authenticated public communication, at the end of which each party should be able to generate the key. We derive new lower and upper bounds on the secret key rate under the source model and the channel model, and introduce a technique for proving that a given expression bounds the secrecy rate from above in the channel model. Our lower bounds strictly improve what is essentially the best known lower bound in both the source model and the channel model. Our upper bound in the channel model strictly improves the current state of art upper bound. We do not know whether our new upper bound in the source model represents an strict improvement but it includes the current best known bound as a special case.