All existing secret key generation schemes assume that the users have access to infinite number of source observations. Motivated by applications in wireless networks, we consider the problem of generating secret keys from a finite number of correlated observations under the source model. We investigate the relationship among the achievable secret key rate, the decoding error probability, and the number of observations. Based on the connection between secret key generation and distributed source coding problems, we present two key generation schemes. In the first scheme, length of the generated key varies depending on the the realization of the source sequence, and the generated key is conditionally perfectly secure. We characterize the penalty, due to the finiteness of the number of observations, in the key rate compared to that of the scheme with infinite number of observations. In the second scheme, length of the generated key is fixed, and the key is unconditionally perfectly secure. We characterize the additional penalty associated with these additional features in the achievable key rate.
All existing secret key generation schemes assume that the users have access to infinite number of source observations. Motivated by applications in wireless networks, we consider the problem of generating secret keys from a finite number of correlated observations under the source model. We investigate the relationship among the achievable secret key rate, the decoding error probability, and the number of observations. Based on the connection between secret key generation and distributed source coding problems, we present two key generation schemes. In the first scheme, length of the generated key varies depending on the the realization of the source sequence, and the generated key is conditionally perfectly secure. We characterize the penalty, due to the finiteness of the number of observations, in the key rate compared to that of the scheme with infinite number of observations. In the second scheme, length of the generated key is fixed, and the key is unconditionally perfectly secure. We characterize the additional penalty associated with these additional features in the achievable key rate.
Secret key generation by multiple terminals is considered based on their observations of jointly distributed Gaussian signals, followed by public communication among themselves. Exploiting an inherent connection between secrecy generation and lossy data compression, two main contributions are made. The first is a characterization of strong secret key capacity, and entails a converse proof technique that is valid for real-valued (and not necessarily Gaussian) as well as finite-valued signals. The capacity formula acquires a simple form when the terminals observe “symmetrically correlated” jointly Gaussian signals. For the latter setup with two terminals, considering schemes that involve quantization at one terminal, the best rate of an achievable secret key is characterized as a function of quantization rate; secret key capacity is attained as the quantization rate tends to infinity. Structured codes are shown to attain the optimum tradeoff between secret key rate and quantization rate, constituting our second main contribution.
For secret-key generation by using a compound source, the actual statistics of the source are unknown to the participants. It is assumed that the probability distribution of the source belongs to a set which is known to the participants. The secret-key generation protocol should guarantee in this case the reliability and security of the generated secret-key simultaneously for all possible source statistics which belong to this set. At the same time, the communication rate between the legitimate users should not exceed a given communication rate parameter. In this work, this problem is studied for the case where the set of source states is arbitrary (possibly infinite) and the set of marginals (transmitter's states) is finite. The secret-key capacity is completely characterized as a function of the forward communication rate parameter between the legitimate users.
This dissertation deals with a multiterminal source model for secret key generation by multiple network terminals with prior and privileged access to a set of correlated signals complemented by public discussion among themselves. Emphasis is placed on a characterization of secret key capacity, i.e., the largest rate of an achievable secret key, and on algorithms for key construction. Various information theoretic security requirements of increasing stringency: weak, strong and perfect secrecy, as well as different types of sources: finite-valued and continuous, are studied. Specifically, three different models are investigated. First, we consider strong secrecy generation for a discrete multiterminal source model. We discover a connection between secret key capacity and a new source coding concept of "minimum information rate for signal dissemination," that is of independent interest in multiterminal data compression. Our main contribution is to show for this discrete model that structured linear codes suffice to generate a strong secret key of the best rate. Second, strong secrecy generation is considered for models with continuous observations, in particular jointly Gaussian signals. In the absence of suitable analogs of source coding notions for the previous discrete model, new techniques are required for a characterization of secret key capacity as well as for the design of algorithms for secret key generation. Our proof of the secret key capacity result, in particular the converse proof, as well as our capacity-achieving algorithms for secret key construction based on structured codes and quantization for a model with two terminals, constitute the two main contributions for this second model. Last, we turn our attention to perfect secrecy generation for fixed signal observation lengths as well as for their asymptotic limits. In contrast with the analysis of the previous two models that relies on probabilistic techniques, perfect secret key generation bears the essence of "zero-error information theory," and accordingly, we rely on mathematical techniques of a combinatorial nature. The model under consideration is the "Pairwise Independent Network" (PIN) model in which every pair of terminals share a random binary string, with the strings shared by distinct pairs of terminals being mutually independent. This model, which is motivated by practical aspects of a wireless communication network in which terminals communicate on the same frequency, results in three main contributions. First, the concept of perfect omniscience in data compression leads to a single-letter formula for the perfect secret key capacity of the PIN model; moreover, this capacity is shown to be achieved by linear noninteractive public communication, and coincides with strong secret key capacity. Second, taking advantage of a multigraph representation of the PIN model, we put forth an efficient algorithm for perfect secret key generation based on a combinatorial concept of maximal packing of Steiner trees of the multigraph. When all the terminals seek to share perfect secrecy, the algorithm is shown to achieve capacity. When only a subset of terminals wish to share perfect secrecy, the algorithm is shown to achieve at least half of it. Additionally, we obtain nonasymptotic and asymptotic bounds on the size and rate of the best perfect secret key generated by the algorithm. These bounds are of independent interest from a purely graph theoretic viewpoint as they constitute new estimates for the maximum size and rate of Steiner tree packing of a given multigraph. Third, a particular configuration of the PIN model arises when a lone "helper" terminal aids all the other "user" terminals generate perfect secrecy. This model has special features that enable us to obtain necessary and sufficient conditions for Steiner tree packing to achieve perfect secret key capacity.
In this article, we study the problem of secret key generation in the multiterminal source model, where the terminals have access to correlated Gaussian sources. We assume that the sources form a Markov chain on a tree. We give a nested lattice-based key generation scheme whose computational complexity is polynomial in the number, N, of independent and identically distributed samples observed by each source. We also compute the achievable secret key rate and give a class of examples where our scheme is optimal in the fine quantization limit. However, we also give examples that show that our scheme is not always optimal in the limit of fine quantization.
In this paper, we study the problem of secret key generation with one-way communication, where in addition to the rate limited public channel, which can be observed by both Bob and Eve, we add a secure channel, which only connects Alice and Bob. In this model, we do not pose any constraints on the sources, i.e. Bob is not degraded to or less noisy than Eve. We propose an achievability scheme, and we also suggest a converse, which meets the achievability. Therefore, we obtain the secret key capacity for this model.
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 paper, the secret-key generation based on a compound source is studied where the realization of the source statistic 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 for a finite compound source is derived as a function of the public communication rate constraint. A multi-letter capacity formula is further computed for a finite compound source for the case in which the public communication is unconstrained. Finally, a single-letter capacity formula is derived for a degraded compound source with an arbitrary (possibly infinite) set of source states and a finite set of marginal states.