The basic two-terminal common randomness (CR) and key generation models are considered, where the communication between the terminals may be limited, and in particular may not be enough to achieve the maximum CR/key rate. We introduce general notions of $XY$-absolutely continuity and $XY$-concave function, and characterize the first order CR/key-communication tradeoff in terms of the evaluation of the $XY$-concave envelope of a functional defined on a set of distributions, which is simpler than the multi-letter characterization. Two extreme cases are given special attention. First, in the regime of very small communication rates, the CR bits per interaction bit (CRBIB) and key bits per interaction bit (KBIB) are expressed with a new symmetrical strong data processing constant, defined as the minimum of a parameter such that a certain information-theoretic functional touches its $XY$-concave envelope at a given source distribution. We also provide a computationally friendly strong converse bound for CRBIB and a similar (but not necessarily strong) one for KBIB in terms of the supremum of the maximal correlation coefficient over a set of distributions. The proof uses hypercontractivity and properties of the R\'enyi divergence. A criterion the tightness of the bound is given with applications to binary symmetric sources. 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 and Narayan \cite{tyagi2013common} regarding the MIMK for binary sources. We also propose a new conjecture for binary symmetric sources.
The basic two-terminal common randomness (CR) and key generation models are considered, where the communication between the terminals may be limited, and in particular may not be enough to achieve the maximum CR/key rate. We introduce general notions of XY-absolutely continuity and XY-concave function, and characterize the first order CR/key-communication tradeoff in terms of the evaluation of the XY-concave envelope of a functional defined on a set of distributions, which is simpler than the multi-letter characterization. Two extreme cases are given special attention. First, in the regime of very small communication rates, the CR bits per interaction bit (CRBIB) and key bits per interaction bit (KBIB) are expressed with a new symmetrical strong data processing constant, defined as the minimum of a parameter such that a certain information-theoretic functional touches its XY-concave envelope at a given source distribution. We also provide a computationally friendly strong converse bound for CRBIB and a similar (but not necessarily strong) one for KBIB in terms of the supremum of the maximal correlation coefficient over a set of distributions. The proof uses hypercontractivity and properties of the R'enyi divergence. A criterion the tightness of the bound is given with applications to binary symmetric sources. 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 and Narayan \cite{tyagi2013common} regarding the MIMK for binary sources. We also propose a new conjecture for binary symmetric sources.
The basic two-terminal key generation model is considered, where the communication between the terminals is limited. We introduce a preorder relation on the set of joint distributions called XY-absolute continuity, and we reduce the multi-letter characterization of the key-communication tradeoff to the evaluation of the XY-concave envelope of a functional. For small communication rates, the key bits per interaction bit is expressed with a “symmetrical strong data processing constant”. Using hypercontractivity and Rényi divergence, we also prove a computationally friendly strong converse bound for the common randomness bits per interaction bit in terms of the supremum of the maximal correlation coefficient over a set of distributions, which is tight for binary symmetric sources. Regarding the other extreme case, a new characterization of the minimum interaction for achieving the maximum key rate (MIMK) is given, and is used to resolve a conjecture by Tyagi [1] about the MIMK for binary sources.
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.
We study the generation of a secret key of maximum rate by a pair of terminals observing correlated sources and with the means to communicate over a noiseless public communication channel. Our main result establishes a structural equivalence between the generation of a maximum rate secret key and the generation of a common randomness that renders the observations of the two terminals conditionally independent. The minimum rate of such common randomness, termed interactive common information, is related to Wyner's notion of common information, and serves to characterize the minimum rate of interactive public communication required to generate an optimum rate secret key. This characterization yields a single-letter expression for the aforementioned communication rate when the number of rounds of interaction are bounded. An application of our results shows that interaction does not reduce this rate for binary symmetric sources. Further, we provide an example for which interaction does reduce the minimum rate of communication. Also, certain invariance properties of common information quantities are established that may be of independent interest.
Common Randomness (CR) as a resource is gaining increasing use cases for addressing futuristic communication demands such as scalability, technological sovereignty, and trustworthiness. For instance, CR can be applied to enhance data encryption. It also enables scalable identification (ID) codes and can support up to double-exponential ID capacity. Moreover, CR strengthens wireless communication systems by providing robustness against jamming attacks. However, from the viewpoint of a communication system, two distinct terminals or devices that wish to generate CR must first observe a correlated random source. In a wireless communication system, this source can be the channel’s stochastic nature, as reflected in the received signal. Traditionally, such an attempt has already been made for physical-layer secret key generation. However, the primary objective of PLSK is to provide information-theoretic security, which does not require generating CR at a very high rate. In novel communication methods such as ID-codes, for a discrete memoryless channel, the ID capacity is lower-bounded by CR capacity. In other words, to realize the benefits of CR assisted ID codes, it is required to generate a vast number of CR bits from very few channel observations. Therefore, there is a need to re-examine the PLSK methodology and modify it so that the resulting generated CR can be adopted into novel communication concepts, such as ID codes. This thesis aims to redesign PLSK so that the resulting information-theoretic CR rate more closely approaches the CR capacity than traditional PLSK schemes. The thesis introduces an initial PLSK implementation on Software-Defined Radios (SDRs) and discusses the trade-offs of attempting to improve the rate of CR generation in the PLSK system. Subsequently, the PLSK method is redesigned to enhance the CR rate. This is achieved through a two-step process: modifying CR generation methods and improving the storage of their components. In the methods section, I combine filters with low cutoff frequencies, multi-bit quantization, and gray-code encoding with a novel functional block called randomization. In the storage section, I propose introducing a 16-bit RSSI instead of an 8-bit RSSI to enhance CR rate through a novel paradigm called engineering entropy. I demonstrate and discuss the resulting improvement in the CR rate achieved with SDRs, compared to the corresponding state-of-the-art PLSK strategy.:1 Introduction 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 Physical Layer Secret Key Generation for Post-Quantum Cryptography 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Implementation of Physical Layer Secret Key (PLSK) . . . . . . . 9 2.3 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.6 Further Development . . . . . . . . . . . . . . . . . . . . . . . . 15 3 Overview of Common Randomness Generation 17 3.1 Theoretical Foundation . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 Illustrative Example for Common Randomness Generation . . . 19 4 ImprovingCommonRandomness Rate Through Functional Blocks 23 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2 Improving Common Randomness (CR) Rate . . . . . . . . . . . 26 4.3 Review of CR Generation Capacity . . . . . . . . . . . . . . . . 27 4.4 Individual Stages . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.5 Evaluation Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.6 The CFO-CR Testbed: The Experimental Setup . . . . . . . . . . 40 4.7 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.8 Conclusion and Future Directions . . . . . . . . . . . . . . . . . 54 5 Improving Common Randomness Rate Through RSSI Storage 59 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.3 General System Model . . . . . . . . . . . . . . . . . . . . . . . 61 5.4 Extraction Stages . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.5 Testbed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.6 Evaluation Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.7 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 5.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 Conclusions 91 Bibliography 93
We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with connections to communication under uncertainty and locality sensitive hashing. We take the approach of treating correlated sources as a critical resource, and ask whether common randomness can be generated resource-efficiently. We consider two notable sources in this setup arising from correlated bits and correlated Gaussians. We design the first explicit schemes that use only a polynomial number of samples (in the key length) so that the players can generate shared keys that agree with constant probability using optimal communication. The best previously known schemes were both non-constructive and used an exponential number of samples. In the amortized setting, we characterize the largest achievable ratio of key length to communication in terms of the external and internal information costs, two well-studied quantities in theoretical computer science. In the relaxed setting where the two parties merely wish to improve the correlation between the generated keys of length k, we show that there are no interactive protocols using o(k) bits of communication having agreement probability even as small as 2–o(k). For the related communication problem where the players wish to compute a joint function f of their inputs using i.i.d samples from a known source, we give a simultaneous message passing protocol using 2O(c) bits where c is the interactive randomized public-coin communication complexity of f. This matches the lower bound shown previously while the best previously known upper bound was doubly exponential in c. Our schemes reveal a new connection between common randomness and unbiased error-correcting codes, e.g., dual-BCH codes and their analogues in Euclidean space.
This dissertation is primarily concerned with the communication required to achieve secret key (SK) capacity in a multiterminal source model. The multiterminal source model introduced by Csiszar and Narayan consists of a group of remotely located terminals with access to correlated sources and a noiseless public channel. The terminals wish to secure their communication by agreeing upon a group secret key. The key agreement protocol involves communicating over the public channel, and agreeing upon an SK secured from eavesdroppers listening to the public communication. The SK capacity, i.e., the maximum rate of an SK that can be agreed upon by the terminals, has been characterized by Csiszar and Narayan. Their capacity-achieving key generation protocol involved terminals communicating to attain omniscience, i.e., every terminal gets to recover the sources of the other terminals. While this is a very general protocol, it often requires larger rates of public communication than is necessary to achieve SK capacity.
The primary focus of this dissertation is to characterize the communication complexity, i.e., the minimum rate of public discussion needed to achieve SK capacity. A lower bound to communication complexity is derived for a general multiterminal source, although it turns out to be loose in general. While the minimum rate of communication for omniscience is always an upper bound to the communication complexity, we derive tighter upper bounds to communication complexity for a special class of multiterminal sources, namely, the hypergraphical sources. This upper bound yield a complete characterization of hypergraphical sources where communication for omniscience is a rate-optimal protocol for SK generation, i.e., the communication complexity equals the minimum rate of communication for omniscience.
Another aspect of the public communication touched upon by this dissertation is the necessity of omnivocality, i.e., all terminals communicating, to achieve the SK capacity. It is well known that in two-terminal sources, only one terminal communicating success to generate a maximum rate secret key. However, we are able to show that for three or more terminals, omnivocality is indeed required to achieve SK capacity if a certain condition is met. For the specific case of three terminals, we show that this condition is also necessary to ensure omnivocality is essential in generating a SK of maximal rate. However, this condition is no longer necessary when there are four or more terminals.
A certain notion of common information, namely, the Wyner common information, plays a central role in the communication complexity problem. This dissertation thus includes a study of multiparty versions of the two widely used notions of common information, namely, Wyner common information and Gacs-Korner (GK) common information. While evaluating these quantities is difficult in general, we are able to derive explicit expressions for both types of common information in the case of hypergraphical sources.
We also study fault-tolerant SK…