ABSTRACT Title of dissertation: Common Randomness Principles of Secrecy Himanshu Tyagi, Doctor of Philosophy, 2013 Dissertation supervisor: Professor Prakash Narayan Department of Electrical and Computer Engineering Institute for Systems Research This dissertation concerns the secure processing of distributed data by multi- ple terminals, using interactive public communication among themselves, in order to accomplish a given computational task. In the setting of a probabilistic multitermi- nal source model in which several terminals observe correlated random signals, we analyze secure distributed data processing protocols that harness the correlation in the data. The speci c tasks considered are: computing functions of the data under secrecy requirements; generating secretly shared bits with minimal rate of public communication; and securely sharing bits in presence of a querying eavesdropper. In studying these various secure distributed processing tasks, we adopt a uni ed approach that entails examining the form of underlying common randomness (CR) that is generated at the terminals during distributed processing. We make the case that the exact form of established CR is linked inherently to the data processing task at hand, and its characterization can lead to a structural understanding of the associated algorithms. An identi cation of the underlying CR and its decomposi- tion into independent components, each with a di erent operational signi cance, is a recurring fundamental theme at the heart of all the proofs in this dissertation. In addition to leading to new theoretical insights, it brings out equivalences between seemingly unrelated problems. Another distinguishing feature of this work is that it considers interactive communication protocols. In fact, understanding the structure of such interactive communication is a key step in proving our results. We make the following contributions. First, we propose a new information theoretic formulation to study secure distributed computing using public communi- cation. The parties observing distributed data are trusted but an eavesdropper has access to the public communication network. We examine distributed communica- tion protocols that allow the trusted parties to accomplish their required computa- tion tasks while giving away negligible information about a speci ed portion of the data to an eavesdropper with access to the communication. Our theoretical results provide necessary and su cient conditions that characterize the feasibility of vari- ous secure computing tasks; in many cases of practical importance, these conditions take a simple form and can be veri ed easily. When secure computing is feasible, we propose new algorithms in special cases. Next, we revisit the problem of generating shared secret keys (SKs). We investigate minimum communication requirements for generating information theo- retically secure SKs of maximum rates from correlated observations using interactive public communication. In particular, our approach allows us to examine the role of interaction in such communication. On the one hand, we nd that interaction is not needed when the observed correlated bits are symmetrically correlated and therefore, in this case, simple noninteractive protocols are the most e cient means of generating optimum rate SKs. On the other hand, we illustrate that interactive pro- tocols can require a strictly lower rate of overall communication than noninteractive protocols. Finally, we consider the task of ensuring security against an eavesdropper who makes queries about a portion of the distributed data that the terminals share by communicating over a public network. We introduce an alternative notion of secrecy which requires rendering the task of a querying eavesdropper as onerous as possible. Our main contribution in this part is the development of a new technique for proving converse results for secrecy problems involving CR with interactive communication, which is employed then to obtain an upper bound for the maximum number of queries that can be in icted on the eavesdropper for any CR and corresponding communication. Surprisingly, there is an equivalence between this notion of secrecy and that of information theoretic security, which leads to new theoretical results for SK generation; for instance, we prove a strong converse for the SK capacity. We conclude by hypothesizing the basic principles of secrecy generation that emerge from the results developed in this dissertation. Common Randomness Principles of Secrecy by Himanshu Tyagi Dissertation submitted to the Faculty of the Graduate School of the University of Maryland, College Park in partial ful llment of the requirements for the degree of Doctor of Philosophy 2013 Dissertation Committee: Professor Prakash Narayan, Advisor Professor Alexander Barg Professor P. S. Krishnaprasad Professor Sennur Ulukus Professor Armand Makowski Professor Jonathan Katz c Copyright by Himanshu Tyagi, 2013. All rights reserved. PREFACE It is di erent, they say, from knowledge; It is di erent, they say, from ignorance. - Isha Upanishad This dissertation started over a co ee conversation with my advisor Professor Prakash Narayan about his results with Professor Imr e Csisz ar on secret key gen- eration. He verbally described the main result: Multiple terminals can generate an optimum rate secret key by sharing the combined observations of all the terminals. The prior art, for a two terminal setup, involved generating optimum rate secret keys by sharing the observations of one of the terminals. However, an extension of this asymmetric scheme to the multiterminal case was not available. The alternative scheme of Csisz ar and Narayan rst recovered the entire data at all the terminals, using the least rate of public communication, and then extracted an optimum rate secret key from the recovered data. This scheme has an intriguing interpretation. In co ee shop parlance, if the observation of each terminal is represented by a slice of the \randomness cake," the overall cake can be cut into two (almost) independent parts: one corresponding to the secret key and the other to the interactive public communication used to share it. It is clear that such decompositions of common ran- domness must always underlie secure data processing protocols requiring (almost) independence of the observations of the eavesdropper and the secure portion of the data. The question is what constitutes the hypothetical randomness cake { what is the total common randomness available for decomposition? This question is the starting point of our research. For various secure data processing tasks, we characterize the form of common randomness allowed and make the case that it is connected inherently to the structure of the underlying protocols. Our presentation is reverse chronological { starting with the technical results, we conclude by hypothesizing our basic common randomness principles of secrecy that led to them. ii This dissertation could not have been completed without the help of so many of my friends and well-wishers, and the support of U. S. National Science Foun- dation under grants CCF0635271, CCF0830697, and CCF1117546. I express my deepest gratitude to my guru and advisor Professor Prakash Narayan for teaching me how to read, write, critique, discover, and invent. He patiently heard my hyper- bolic assertions and pointed out aws in my ambitious proofs. Also, my graduate learning experience was enriched by long discussions with the faculty at UMD. I am especially grateful to Professor Alexander Barg, Professor P. S. Krishnaprasad, Professor Steve Marcus, and Professor Patrick Fitzpatrick for their mentorship. It is my honor to thank Professor Imr e Csisz ar for hosting me at the R enyi Institute of Mathematics, Budapest for a semester and sharing with me his wealth of knowledge and experience. I am indebted to Dr. Piyush Gupta for serving as my mentor during my summer internship at Bell Labs, Murray Hill, where a part this dissertation was completed. My intellectual experience at UMD would have been incomplete with- out my fellow graduate students. In particular, I would like to thank Ersen Ekrem for exploring with me the nuances of the physical and the metaphysical. Thanks are due also to Shalabh Jain, Osman Ya gan, and all my other friends at UMD who made Maryland my home away from home. I am grateful to my partners in crime Arvind, Mukesh, Achint, Shalabh, Sameen, and my sister Jeevika for paying no heed to my incessant blathering about my research and always amusing me with their antics. I thank my parents for their unconditional love and unreasonable support. Their reassuring presence facilitated every di cult decision of my graduate life. Last and the most, I thank my loving wife Pooja for sharing this journey with me. Her love for the absurd and clarity of thought have inspired every aspect of my research. Himanshu Tyagi College Park, Maryland. iii To maaji, the woman who de ed time Table of Contents List of Abbreviations and Notations vii 1 Introduction 1 1.1 Main contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.1 Secure computation . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.2 Communication for optimum rate secret keys . . . . . . . . . . 11 1.1.3 Querying common randomness . . . . . . . . . . . . . . . . . . 14 1.2 Organization of the dissertation . . . . . . . . . . . . . . . . . . . . . 16 2 Classical Concepts and New Tools 18 2.1 Synopsis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2 Multiterminal source model and interactive communication . . . . . . 19 2.3 Common randomness . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4 Secret keys and secret key capacity . . . . . . . . . . . . . . . . . . . 21 2.5 Common information quantities . . . . . . . . . . . . . . . . . . . . . 27 2.6 Invariance of common information . . . . . . . . . . . . . . . . . . . . 29 2.7 Two basic tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.7.1 Balanced coloring lemma . . . . . . . . . . . . . . . . . . . . . 31 2.7.2 R enyi entropy and sets with large probability . . . . . . . . . 35 3 Secure Computation 39 3.1 Synopsis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.2 Formulation: Secure function computation by public communication . 40 3.3 When is a function securely computable? . . . . . . . . . . . . . . . . 41 3.3.1 Secret key aided by side information . . . . . . . . . . . . . . 46 3.3.2 Characterization of secure computability . . . . . . . . . . . . 49 3.3.3 A decomposition result . . . . . . . . . . . . . . . . . . . . . . 53 3.4 Proofs of main results . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4 Secure Computation: Multiple Functions 64 4.1 Synopsis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.2 Formulation: Secure computation of multiple functions . . . . . . . . 65 4.3 Characterization of securely computable functions . . . . . . . . . . . 70 4.4 Proof of su ciency . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 v 4.5 Proof of necessity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 4.6 Discussion: Alternative necessary conditions for secure computability 91 5 Common Randomness and Minimal Communication for Optimum Rate Se- cret Keys 94 5.1 Synopsis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 5.2 Interactive common information . . . . . . . . . . . . . . . . . . . . . 95 5.3 Formulation and main results . . . . . . . . . . . . . . . . . . . . . . 97 5.4 Can interaction reduce the communication rate? . . . . . . . . . . . . 111 5.4.1 Binary symmetric sources . . . . . . . . . . . . . . . . . . . . 115 5.4.2 An example where interaction does help . . . . . . . . . . . . 120 5.5 Interactive common information and su cient statistics . . . . . . . . 122 5.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 5.6.1 Local randomization . . . . . . . . . . . . . . . . . . . . . . . 126 5.6.2 Less-than-optimum rate secret keys . . . . . . . . . . . . . . . 128 6 Querying Common Randomness 130 6.1 Synopsis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 6.2 Main result: How many queries will resolve common randomness? . . 131 6.3 Technical tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 6.4 Proof of achievability . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 6.5 Proof of converse for A =M . . . . . . . . . . . . . . . . . . . . . . 138 6.6 Proof of converse for arbitrary A M . . . . . . . . . . . . . . . . . 146 6.7 Strong converse for secret key capacity . . . . . . . . . . . . . . . . . 152 6.8 General alphabet converse for A =M . . . . . . . . . . . . . . . . . 155 6.9 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 7 Conclusion: Principles of Secrecy Generation 166 A Maximum Common Function 169 B Aided Secret Key Capacity 172 C Balanced Coloring Lemma 176 D Su ciency Proof of Theorem 4.1 181 E Proof of (5.28) and (5.31) 184 F Properties of Interactive Communication 188 Bibliography 194 vi List of Abbreviations and Notations ASK aided secret key BSS binary symmetric sources CI common information CR common randomness i.i.d. independent and identically distributed mcf maximum common function pmf probability mass function rv random variable SK secret key WSK wiretap secret key Notation. Let X1; : : : ; Xm, m 2, be rvs with nite alphabets X1; : : : ;Xm, respec- tively, and a known joint pmf. For any nonempty set A M = f1; : : : ;mg, we denote XA = (Xi; i 2 A). Similarly, for real numbers R1; : : : ; Rm and A M, we denote RA = (Ri; i 2 A). Let Ac be the set MnA. We denote n i.i.d. repetitions of XM = (X1; : : : ; Xm) with values in XM = X1 : : : Xm by XnM = (Xn1 ; : : : ; Xnm) with values in X nM = X n1 : : : X nm. Given > 0, for rvs U; V; we say that U is -recoverable from V if P (U 6= f(V )) for some function f(V ) of V . Denote by kUk the size of the range space of the rv U . All logarithms and exponentials are with respect to the base 2. vii CHAPTER 1 Introduction This dissertation concerns the secure processing of distributed data by multiple terminals, using interactive public communication among themselves, in order to accomplish a given task. In many applications, data is collected and stored at physically or temporally separated locations. Examples of the former include data grids and sensor networks. The distributed data is assumed to be correlated, where the correlation can arise from shared copies of the same data, as in data grids [72]; or from the nature of the data itself, as in distributed video coding [30, 55] and in sensor networks [14, 25]. Instances of temporally separated locations with correlated data arise in biometric authentication [56] and hardware authentication [28], where the distributed data consists of the original and the noisy versions of signatures recorded at the registration and the authentication stages, respectively. In all such settings, the entities at these locations are provided with a communication infrastructure to exchange information in order to facilitate various tasks such as sharing distributed data or computing functions of their collective data. For instance, sensor nodes can communicate over a wireless network to compute average or extreme values of their measurements, or \helper" data in a biometric security system can be stored 1 publicly to correct any errors in subsequent recordings of a biometric signature. We study the following general question: If the shared communication is public, how can we guarantee security? In the setting of a probabilistic multiterminal source model in which di erent termi- nals observe correlated random signals [58, 20], we analyze secure distributed data processing protocols that harness the correlation in the data. The speci c tasks con- sidered are: computing functions of the data under secrecy requirements (Chapters 3, 4); generation of secretly shared bits with minimal rate of public communica- tion (Chapter 5); and securely sharing bits in presence of a querying eavesdropper (Chapter 6). For the rst task, we propose a new information theoretic formulation to study secure distributed computing using public communication. The parties observing distributed data are trusted but an eavesdropper can access the public communi- cation network. We examine distributed communication algorithms that allow the trusted parties to accomplish their required computation tasks while giving away negligible information about the computed value to an eavesdropper with access to the communication. This proposed setup is general and provides a uni ed frame- work for studying problems of secure computing over sensor networks, secure dis- tributed storage and secure computing over a data grid. Our theoretical results provide necessary and su cient conditions characterizing the feasibility of various secure computing tasks; in many cases of practical importance, these conditions take a simple form and can be veri ed easily. This characterization of secure comput- 2 ing provides a basic test that must be undertaken before attempting to construct algorithms. Furthermore, in special cases, we propose new algorithms for secure computing when it is feasible. The second task concerns the problem of generating shared secret keys (SKs), a common objective in many security applications. Most of the current cryptosystems rely on the availability of such shared SKs. In the context of biometric and hardware security, biometric signatures [37] and physically unclonable functions[54], respec- tively, constitute such shared SKs that have been generated from noisy recordings. We investigate minimum communication requirements for generating information theoretically secure SKs of maximum rates from correlated observations using in- teractive public communication. In particular, our approach allows us to examine the role of interaction in such communication. For instance, we nd that interac- tion is not needed when the observed correlated bits are symmetrically correlated and therefore, in this case, simple noninteractive protocols are the most e cient for generating optimum rate SKs. The last task considered entails ensuring security against an eavesdropper who makes queries about a portion of the distributed data that the terminals share by communicating over a public network. We introduce a new notion of secrecy which requires rendering the task of a querying eavesdropper as onerous as possible. Ap- plications include systems secured using biometric authentication where a portion of the recorded biometric information is stored as (public) helper data to correct any errors that occur in subsequent recordings of a biometric signature. How many attempts must a malicious party, with access to this helper data, make in order 3 to enter the system? We present a general formulation to answer such questions. Furthermore, as a surprise, we nd that this new notion of secrecy is in essence equivalent to the notion of information theoretic security. We leverage this connec- tion to obtain new theoretical results for SK generation; for instance, we prove a new strong converse for the SK capacity. In studying these various secure distributed processing tasks, we follow a uni- ed approach that entails examining the form of underlying common randomness (CR) (i.e., shared bits [2]) that is generated at the terminals during distributed pro- cessing. In this dissertation, we make the case that the exact form of established CR is linked inherently to the data processing task at hand, and its characterization can lead to a structural understanding of the associated algorithms. An identi cation of the underlying CR and its decomposition into independent components, each with a di erent operational signi cance, is a recurring fundamental theme underlying all the proofs in this dissertation. In addition to leading to new theoretical results, it brings out equivalences between seemingly unrelated problems with a common feature that the same CR is established at the terminals. Previously, Csisz ar and Narayan had observed such an equivalence between multiterminal SK generation and multiterminal data compression [20]. Speci cally, a duality was shown between the generation of an SK of maximum rate and the problem of attaining \omni- science", i.e., recovering the entire data at the SK-seeking terminals. This duality, led to a characterization of multiterminal SK capacity, which is the largest rate of nearly uniformly distributed CR that meets the security requirement of being nearly independent of the communication used to generate it. Furthermore, it enabled new 4 algorithms for SK generation [81, 83]. In the same spirit, here, too, equivalences of tasks are uncovered, leading to new structural results and new algorithms for secure function computation and e cient SK generation. Another distinguishing feature of this work is that it considers interactive com- munication protocols. The communication from a terminal can be any (randomized) function of its own observed signal and of all previous communication. Through- out this dissertation we assume that the communication is authenticated, i.e., the \honest but curious" eavesdropper can only observe passively the communication but cannot tamper with it. Furthermore, it is assumed that the communication is in a broadcast mode { each terminal observes the communication from every other terminal. Understanding the structure of such interactive communication is a key step in proving our results. For instance, the results of Chapter 6 rely on show- ing that if the observations of two terminals are independent to begin with, then they remain independent when conditioned upon the value of an interactive com- munication. Also, we show that for many tasks complex interactive protocols are not needed and simple noninteractive communication protocols su ce (see the next section for speci c examples). In the concluding chapter of this dissertation, we hypothesize basic principles of secrecy generation that have emerged from the precise results as well as heuristics developed in our work. These principles have important engineering implications and can serve as guidelines for the design of secure protocols. The theoretical results presented in this dissertation support these principles, and we conjecture that even in much broader settings, the proposed principles must hold for appropriately 5 chosen notions of security. For instance, in recent work we examine the validity of these principles in nonasymptotic regime by considering general descriptions of the observed data with xed length [70]. 1.1 Main contributions This dissertation makes three main technical contributions, which are summarized below. 1.1.1 Secure computation Suppose that the terminals inM = f1; : : : ;mg observe correlated signals, and that a subset A of them are required to compute \securely" a (single-letter) function g of all the signals. To this end, the terminals inM are allowed to communicate interac- tively over a public noiseless channel of unlimited capacity, with the communication being observed by all the terminals. The terminals in A seek to compute g in such a manner as to keep its value information theoretically secret from an eavesdropper that observes the public interterminal communication. A typical application arises in a wireless network of colocated sensors which seek to compute a given function of their correlated measurements using public communication that does not give away the value of the function. In contrast to the classic notion of secure computing in cryptography [80], we assume that the terminals are trustworthy but their public communication network can be accessed by an eavesdropper. We formulate a new Shannon theoretic multiterminal source model that ad- 6 dresses the elemental question: When can a function g be computed so that its value is independent of the public communication used in its computation? The study of problems of function computation, with and without secrecy requirements, has a long and varied history in multiple disciplines, to which we can make only a skimpy allusion here. Examples include: algorithms for exact function computation by multiple parties (cf. e.g., [40, 79, 27, 29]); algorithms for asymptotically accurate (in observation length) function computation (cf. e.g., [53, 43]); and problems of oblivious transfer [50, 3]. In contrast, our requirement of secure computation1 is to protect the value of a given function; an instance is [52] where exact function computation with secrecy was sought. We establish that the answer to the question posed above is connected innately to a problem of SK generation for terminals in M, when, in addition to the public communication, side information is provided to the decoders at the terminals in Ac in the form of the value of g, and can be used only for recovering the key. Such a key, termed an aided secret key (ASK), constitutes a modi cation of the original notion of an SK in [48, 1, 20, 21]. The largest rate of such an ASK for M is the ASK capacity C. Clearly, a function g that is securely computable for A can be recovered se- curely by all the terminals in M when its value is provided as side information for decoding to the terminals outside2 A, and so, it will yield an ASK for M of rate 1Unlike in [79] and allied literature, no key is available apriori for secure computation but can be devised as a part of the computation procedure. 2We do not assume that this value is provided to the terminals in Ac in the actual secure computing protocol. This is an arti ce that is used to derive a necessary condition for secure 7 equal to the entropy H of g. Therefore, g necessarily must satisfy H C. In Theo- rem 3.4, we show that surprisingly, H < C is a su cient condition for the existence of a protocol for the secure computation of g by A. When all the terminals in M seek to compute g securely, the corresponding ASK capacity reduces to the stan- dard SK capacity for M [20, 21]. Furthermore, under this su cient condition, our proof exhibits a secure computing protocol that uses noninteractive communication. Therefore, although interaction was allowed, it is not needed to accomplish secure computing. As a side result of independent interest, we show that a function that is securely computed by A can be augmented by residual secret CR to yield an SK for A of optimum rate. In proving the su cient condition above, our main technical tool is a new version of the \balanced coloring lemma" [2, 20]. The latter is an important basic result that is used to show the existence of (nontrivial) mappings h of a given rv U such that h(U) is (almost) independent of another rv3 V , where U and V are correlated. In Section 2.7.1, we present a new balanced coloring lemma, which builds on and extends the version given in [20]. We also present the capacity for a general ASK model involving arbitrary side information at the secrecy-seeking set of terminals; such side information is not available for communication and can be used for key recovery alone. Its capac- computability of g by A. 3 In spirit, the same purpose is served by the \generalized privacy ampli cation" result of Bennett, Brassard, Cr epeau and Maurer [7]. Indeed, an alternative proof of some of our results based on generalized privacy ampli cation was presented in [11]. 8 ity is characterized in terms of the classic concept of maximum common function (mcf) [26]. Although this result is not needed in full dose for characterizing secure computability, it remains of independent interest. Next, we consider a generalization where di erent terminals seek to compute di erent functions, without giving away the value of a private function of the data4. Speci cally, the terminals f1; :::;mg wish to compute functions g1; :::; gm, respec- tively, of their collective data using communication that must not reveal the value of a speci ed private function g0 of the data. If such a communication protocol exists, the functions g0; g1; :::; gm are said to be securely computable. A characterization of securely computable functions for this general setup re- mains open. The simplest case of interest when the terminals in a subset A of M compute only the private function g0 and those not in A perform no computation is settled in Chapter 3 and was discussed above. For this simple case, our results can be reinterpreted as follows: If g0 is securely computable (by the terminals in A), then H (XMjG0) = H (XM) H (G0) R ; (1.1) and g0 is securely computable if H (XMjG0) > R ; (1.2) where R has the operational signi cance of being the minimum overall rate of 4For instance, in a variant of Yao?s millionaire problem [80], two millionaires communicate to determine the richer between them and they want an eavesdropper not to learn their combined wealth. 9 communication needed for a speci c multiterminal source-coding task that involves the recovery of entire data at all the terminals in M when the terminals in Ac are provided the value of g0 as side information; this task does not involve any security constraint. Loosely speaking, denoting the collective data of the terminals by the random variable (rv) XM and the random value of the function g0 by the rv G0, the maximum rate of randomness (in the data) that is independent of G0 is H (XMjG0). The conditions above imply, in e ect, that g0 is securely computable if and only if this residual randomness of rate H (XMjG0) contains an interactive communication, of rate R , for the mentioned source-coding task. In Theorem 4.1, for a broad class of settings involving the secure computation of multiple functions, we establish necessary and su cient conditions for secure computation of the same form as (1.1) and (1.2), respectively. The rate R now corresponds to, roughly, the minimum overall rate of communication that allows each terminal to: (i) accomplish its required computation task, and, (ii) recover the entire data ( i.e., attain omniscience) when its decoder alone is also given the value of the private function. Using the su cient condition (1.2), we present a speci c secure computing protocol with communication of rate R . For the simple case of a single function g = g0 discussed above, under (1.2), the secure computing scheme recovers the entire data, i.e., the collective observations of all the terminals, at the (function-seeking) terminals in A using communication that is independent of G0. In fact, we observe 10 that this is a special case of the following more general principle: A terminal that computes the private function g0, can recover the entire data without a ecting the conditions for secure computability. This exhibits a structural equivalence between securely computing g0 at a terminal and recovering the entire data at that termi- nal without giving away the value of g0 to an eavesdropper observing the public communication used. In general, a single-letter formula for R is not known. Nevertheless, conditions (1.1) and (1.2) provide a structural characterization of securely computable func- tions in a broader setting. Also, a general recipe for single-letter characterization is presented, and for the cases in which a single-letter characterization is available, the aforementioned heuristic interpretation of R is precise. 1.1.2 Communication for optimum rate secret keys Consider SK generation by a pair of terminals that observe i.i.d. repetitions of two nite-valued rvs of known joint pmf. The terminals communicate over a noiseless public channel of unlimited capacity, interactively in multiple rounds, in order to agree upon the value of an SK which is required to be (almost) independent of the public communication. The maximum rate of such an SK, termed the SK capacity, was characterized in [48, 1]. In the works of Maurer and Ahlswede-Csisz ar [48, 1], SK generation of maxi- mum rate entailed both the terminals recovering the observations of any one of the terminals, using the least rate of communication required to do so. Later, it was 11 shown by Csisz ar-Narayan [20] that a maximum rate SK can be generated also by the terminals recovering the observations of both the terminals. Clearly, the latter scheme requires more communication than the former. We address the following question, which was raised in [20, Section VI]: What is the minimum overall rate of interactive communication RSK required to establish a maximum rate SK? Curtailing the rate of communication used in SK generation to a minimum is an important design objective, especially when engineering lightweight cryptography systems such as secure sensor networks with limited transmission power available at sensor nodes [23]. The basic question above is a rst step towards understanding the tradeo between the rate of communication used and the rate of SK generated. We answer this question by characterizing the form of CR that the terminals must establish in order to generate a maximum rate SK; two examples of such CR are the observations of any one terminal [48, 1] and of both terminals [20]. While our main result does not yield a single-letter characterization of the minimum rate of commu- nication above, it nonetheless reveals a central link between secrecy generation and Wyner?s notion of common information (CI) between two dependent rvs X1 and X2 [77]. Wyner de ned CI as the minimum rate of a function of i.i.d. repetitions of two correlated rvs X1 and X2 that enabled a certain distributed source coding task. Alternatively, it can be de ned as the minimum rate of a function of i.i.d. repeti- tions of X1 and X2 such that, conditioned on this function, the i.i.d. sequences are (almost) independent; this de nition, though not stated explicitly in [77], follows from the analysis therein. We introduce a variant of this notion of CI called the 12 interactive CI where we seek the minimum rate of CR, established using interactive communication, that renders the mentioned sequences conditionally independent. Clearly, interactive CI cannot be smaller than Wyner?s CI, and can exceed it. Our main contribution in this section is to show a one-to-one correspondence between the CR corresponding to interactive CI and the CR established for generating an optimum rate SK. This correspondence is used to characterize the minimum rate of communication RSK required for generating a maximum rate SK in Theorem 5.1. It is shown that, in fact, RSK is simply interactive CI minus the SK capacity. Finding a single-letter expression for interactive CI remains an open problem. However, when the number of rounds of interaction are bounded, we do obtain a single-letter formula for interactive CI, which in turn yields a single-letter expression for RSK in Theorem 5.3. Using this expression for RSK , we show that for generating an SK of maximum rate, an interactive communication scheme can have lower rate than a noninteractive one, in general. However, interaction o ers no advantage for binary symmetric sources. The expression for RSK in Theorem 5.3 also illustrates the role of su cient statistics in SK generation. We further explore this issue and show that many CI quantities of interest remain unchanged if the rvs are replaced by their corresponding su cient statistics (with respect to each other)5. 5 Interestingly, the e ect of substitution by su cient statistics has been studied in the context of a rate-distortion problem for a remote source in [24, Lemma 2], and recently, for the lossy and lossless distributed source coding problems in [78]. 13 1.1.3 Querying common randomness A set of terminals observing correlated signals agree on CR, by communicating in- teractively among themselves. What is the maximum number of queries of the form \Is CR = l?" with yes-no answers, that an observer of (only) the communication must ask in order to resolve the value of the CR?6 As an illustration, suppose that two terminals observe, respectively, n i.i.d. repetitions of the nite-valued rvs X1 and X2. The terminals agree on CR Xn1 with terminal 1 communicating to terminal 2 a Slepian-Wolf codeword of rate H (X1 j X2) obtained by random binning. An observer of the bin index can ascertain the value of CR with large probability in approximately exp [nI (X1 ^X2)] queries (corresponding to bin size). Our results show that more queries cannot be incurred by any other form of CR and associated interactive communication. In a general setting, terminals 1; :::;m observe, respectively, n i.i.d. repetitions of the rvs X1; :::; Xm, and communicate interactively to create CR, say L, for the terminals in a given subset A f1; :::;mg. For appropriate CR L and interactive communication, the number of queries of the form \Is L = l?" that an observer of the communication must ask to resolve L is exponential in n. In Theorem 6.1, we nd a single-letter formula for the largest exponent E . Remarkably, this formula coincides 6This general setup includes the aforementioned biometric application mentioned earlier. When a user is authenticated, the two versions of the biometric signatures at registration and authenti- cation match, and they constitute a CR. Here the helper data is a proxy for the communication. This view is adapted to construct e cient biometric authentication schemes in, for instance, [22]. 14 with the SK capacity for a multitermial source model with underlying rvs X1; :::; Xm [20, 21]. While it is to be expected that E is no smaller than SK capacity, the less- restricted E may seem a priori to be larger. But it is not so. The coincidence brings out, in e ect, an equivalence between in icting a maximum number of queries on an observer of communication on the one hand, and imposing the explicit secrecy constraint requiring (almost) independence of the SK and the communication on the other hand. In fact, as in the achievability proof of SK capacity in [20], the exponent E is achieved by the terminals in A attaining omniscience, i.e., by generating CR L = (Xn1 ; :::; Xnm) for A, using a communication of minimum rate. Alternatively, E can be interpreted as the smallest rate of a list of CR values produced by an observer of the communication which contains the CR value with large probability. Our main contribution in this section is a new technique for proving converse results for security problems involving CR with interactive communication, which is employed here to obtain an upper bound on E . It relies on query strategies for the CR given the communication that do not depend explicitly on the form of the CR or the communication, and do not require the rvs (X1t; :::; Xmt)nt=1 to be nite-valued or i.i.d. In fact, our converse results hold even when the underlying alphabets are arbitrary, but under mild technical assumptions. Jointly Gaussian rvs are treated as a special case. Furthermore, our converses are strong in that the characterization of E does not depend on the probability of recovery of the CR. This, in turn, leads to a new strong converse result for the SK capacity of the multiterminal source model [20], [21], showing the maximum rate of SK that can be generated does not 15 depend on the probability of recovery of the SK (at the terminals). A byproduct of our technique is a simple lossless block coding result for general nite sources, in terms of R enyi entropies. A particularization recovers the classic lossless block coding result for i.i.d. sources [58] without recourse to the asymptotic equipartition property. The technique7 is recorded separately in Section 2.7.2. The number of queries above can be interpreted as a measure of the correla- tion among the random signals observed by the terminals: A stronger correlation necessitates more queries for resolving the CR that can be generated by them. Such a measure of correlation is in the spirit of the body of work on \guessing" the value of an rv based on a correlated observation [47, 4, 5, 34]. 1.2 Organization of the dissertation The basic multiterminal source model and the notions of CR and SK, along with pertinent known results are given in Chapter 2. In the same chapter, we include a discussion on various measures of CI and point out an interesting invariance property satis ed by these CI quantities. The last section of Chapter 2 contains two important technical tools that have been introduced in this dissertation, namely a new version of the balanced coloring lemma and an estimate of the size of large probability sets in terms of R enyi entropy. These are of independent interest, too. The secure computing problem is presented in two parts, with Chapter 3 con- taining the case of a single computed function and Chapter 4 the general case of 7Recently, it was brought to our attention [75] that alternative forms of this result exist in prior literature; for instance [59, 13]. 16 multiple functions. Chapter 5 addresses the problem of minimum communication requirements for generating an optimum rate SK. This is followed in Chapter 6 by the problem of querying the value of CR. We conclude in Chapter 7 by hypothesizing the basic principles of secrecy generation that emerge from the results developed in this dissertation. 17 CHAPTER 2 Classical Concepts and New Tools 2.1 Synopsis We formulate basic concepts that will be of relevance throughout this dissertation. For a multiterminal source model, the notions of common randomness, omniscience, and secret key capacity are de ned. Also, measures of common information of two rvs due to G acs-K orner and Wyner are described, and a new invariance property is established for these measures. In particular, it is shown that for a two-terminal setup, these common information quantities remain unchanged if the two rvs are replaced by their respective su cient statistics (with respect to each other). Finally, new technical tools are described, which emerge in this dissertation and underlie our proofs. A key tool used in Chapter 6, estimating the size of a large probability set in terms of R enyi entropy, is interpreted separately, too, as a lossless block coding result for general sources. As a speci c instance, it yields the classic result for a discrete memoryless source. Section 2.2 gives the basic set-up of the multiterminal source model and inter- active communication that will be used throughout the dissertation. This is followed by Sections 2.3 and 2.4 on de nitions and preliminary results for common random- 18 ness and secrecy generation. In Section 2.5, we de ne various common information quantities and establish a new invariance property for them in Section 2.6. The nal Section 2.7 formulates technical tools that will be used in this dissertation. Speci cally, a new version of the \balanced coloring lemma" is established, which is an important tool to extract almost independent rvs, and a new connection between R enyi entropy and lossless source coding rate is provided. The results in Sections 2.6, 2.7.1 and 2.7.2 are contained, respectively, in [63], [68] and [65]. 2.2 Multiterminal source model and interactive communi- cation Consider a set of terminals M = f1; :::;mg that observe, respectively, the se- quences Xn1 ; :::; Xnm of length n. Unless stated otherwise, we assume that the rvs (X1t; :::; Xmt), t = 1; :::; n, are i.i.d. with known distribution PXM . This basic mul- titerminal source model was introduced in [20] in the context of SK generation with public transaction. The terminals have access to a noiseless public communication network of unlimited capacity over which they can communicate interactively. The communi- cation is authenticated and it is assumed that each terminal observes the commu- nication from every other terminal. Randomization at the terminals is permitted; we assume that terminal i generates a rv Ui; i 2M, such that U1; : : : ; Um and XnM are mutually independent. While the cardinalities of range spaces of Ui; i 2M; are unrestricted, we assume that H (UM) <1. 19 De nition 2.1. (Interactice Communication) Assume without any loss of general- ity that the communication of the terminals in M occurs in consecutive time slots in r rounds; such communication is described in terms of the mappings f11; : : : ; f1m; f21; : : : ; f2m; : : : ; fr1; : : : ; frm; with fji corresponding to a message in time slot j from terminal i, 1 j r, 1 i m; in general, fji is allowed to yield any function of (Ui; Xni ) and of previous communication ji = ffkl : k < j; l 2M or k = j; l < ig: The corresponding rvs representing the communication will be depicted col- lectively as F = fF11; : : : ; F1m; F21; : : : ; F2m; : : : ; Fr1; : : : ; Frmg; where F = F(n)(UM; XnM); the rv corresponding to ji is denoted by ji. A spe- cial form of such communication will be termed noninteractive communication if F = (F1; :::; Fm), where Fi = fi (Ui; Xni ), i 2 M. The overall rate of all such communication is given by 1 n log kFk: 2.3 Common randomness It is known from the pioneering work of G acs-K orner [26] (also, see [74]) that cor- relation does not result in shared bits, in general. Nevertheless, as the terminals 20 communicate with each other they are able to share bits. In fact, if the observa- tions of the terminals are correlated, the rate of the shared bits is greater than the rate of the communication. The concept of CR introduced by Csisz ar-Ahlswede [2] formalizes this idea. De nition 2.2. (Common Randomness [2]) Given interactive communication F as in De nition 2.1, an rv L = L(n) (XnM) is -common randomness ( -CR) for A from1 F if there exist rvs Li = L(n)i (Xni ;F), i 2 A, satisfying P (Li = L; i 2 A) 1 : (2.1) The rv Li will be called an estimate of L at terminal i 2 A. 2.4 Secret keys and secret key capacity Shared SKs lie at the heart of all cryptographic applications. Maurer [48] proposed a framework for studying the generation of (information theoretically secure) SKs as secret CR from correlated observations at two terminals. As mentioned above, if the observations of the terminals are correlated, the rate of the overall CR generated by the communication is greater than the rate of the communication. Heuristically, this gain in the rate is the root of the generated SK rate. The largest rate of such an SK that can be generated, the SK capacity, was characterized in [48, 1]. 1The rv L is -recoverable from (Xni ;F) for every i 2 A (see the \List of Abbreviations and Notations" before Chapter 1) but not necessarily from F alone. The deliberate misuse of the terminology \recoverable from F" economizes our presentation. 21 This standard concepts of SK and SK capacity were extended to multiple terminals in [20, 21]; we will present these general concepts below. De nition 2.3. (SK capacity [20, 21]) For n > 0; n 1, a function K of XnM is an n-secret key ( n-SK) for (the terminals in) a given set2 A0 M with jA0j 2, achievable from observations of length n, randomization UM and public communi- cation F = F(n)(UM; XnM) as above if (i) K is n-recoverable from (Ui; Xni ;F) for every i 2 A0; (ii) K satis es the \strong secrecy" condition [20, 21] sin(K;F ) , log jKj H(K j F) = log jKj H(K) + I(K ^ F) n; (2.2) where K = K(n) denotes the set of possible values of K; The terminology perfect SK will be used for a 0-SK. The SK capacity C(A0) for A0 is the largest rate lim sup n (1=n) logH(K) of n-SKs for A0 as above,3 such that limn n = 0. Remark. The secrecy condition (2.2) is tantamount jointly to a nearly uniform dis- tribution for K (i.e., log jKj H(K) is small) and to the near independence of K and F (i.e., I(K ^ F) is small). A single-letter characterization of the SK capacity C(A0) is provided in [20, 21]. 2For reasons of notation that will be apparent later, we distinguish between the secrecy seeking set A0 M and the set A M pursuing secure computation. 3In [20, 21], a secret key was de ned, in general, as K = K (UM; XnM) and SK capacity was shown to be achieved by a function of XnM. Also, in view of (2.2), SK rate can be de ned as lim sup n 1 n log jK (n)j. 22 Theorem 2.1. (Characterization of SK Capacity [20, 21]) The SK capacity C(A0) equals C(A0) = H(XM) RCO(A0); (2.3) where RCO(A0) = min RM2R(A0) mX i=1 Ri (2.4) with R(A0) = RM : X i2B Ri H(XB j XBc); B M;A0 * B : (2.5) Furthermore, the SK capacity can be achieved with noninteractive communication and without recourse to randomization at the terminals in M. Remarks. (i) We recall from [20] that RCO(A0) has the operational signi cance of being the smallest rate of \communication for omniscience" for A0, namely the smallest rate lim n (1=n) log kF(n)k of suitable communication for the terminals in M whereby XnM is n-recoverable from (Ui; Xni ;Fn) at each terminal i 2 A0, with lim n n = 0; here kF(n)k denotes the cardinality of the set of values of F(n). Thus, RCO(A0) is the smallest rate of communication among the terminals in M that enables every terminal in A0 to reconstruct with high probability all the sequences observed by all the other terminals in M, with the cooperation of the terminals in M=A0. The resulting omniscience for A0 corresponds to total CR of rate H(XM). (ii) For the trivial case jA0j = 1, say with A0 = f1g, we have that C (f1g) = H (X1). Clearly, K = Xn1 attains C (f1g). On the other hand, if K = K (XnM) is an SK for 23 terminal 1, it is also an SK for a relaxed model where terminal 1 remains the same while terminals 2; :::;m coalesce and have additional access to Xn1 . The SK capacity for the latter model with two terminals, which is no smaller than C(f1g), equals I (X1 ^XM) = H (X1) [48, 1]. Hence, C (f1g) = H (X1). (iii) The SK capacity C(A0) is not increased if the secrecy condition (2.2) is replaced by the following weaker requirement [48, 20]: 1 nI(K ^ F) n: (2.6) In fact, the \weak secrecy" criterion above was rst introduced in [48, 1]. Subse- quently, it was noted in [49, 16] that a capacity achieving SK can be generated that satis es the following stronger secrecy criterion: I(K ^ F) n: (iv) An alternative security criterion is based on the variational distance: svar(K;F) , kPK;F UK PFk1 ; (2.7) where UK denotes a uniform distribution on the set K. Note that the security index sin in (2.2) can be expressed as sin(K;F) = D (PK;FkUK PF ) ; and so by Pinsker?s inequality [18] svar(K;F) r 1 2 sin(K;F): 24 A weaker secrecy criterion than (2.2), which is also widely used in the literature (c.f. [36] and the follow-up work based on \leftover hash lemma"), is the following: svar(K;F) n: (2.8) Also, it was observed in [20, Lemma 1] that sin(K;F) svar(K;F) log jKj svar(K;F) : Therefore, if nsvar(K;F)! 0 as n! 0; (2.9) then sin(K;F)! 0. In fact, the achievability scheme in [20] ensures (2.9) by driving svar(K;F) to 0 exponentially rapidly in n. In Chapter 6, we shall establish a new \strong converse" for SK capacity under (2.9)4. (v) The weak secrecy criterion in (2.6) does not imply the security criterion in (2.8). Also, the former is not implied by (2.9). The expression for the SK capacity C(A0) in 2.3 can be expressed alternatively using a (linear programming) dual expression for RCO(A0). Let B = fB (M : B 6= ;;A * Bg : (2.10) Let (A) be the set of all collections = f B : B 2 Bg of weights 0 B 1, satisfying X B2B:B3i B = 1; i 2M: (2.11) 4The proofs in Chapter 6 can be modi ed to show a strong converse under (2.8) [73]. 25 Every 2 (A) is called a fractional partition of M (see [21, 44, 45, 46]). An equivalent expression for C(A0) is C(A0) = H (XM) max 2 (A) X B2B BH (XB j XBc) ; 0 < < 1: (2.12) Denoting sum = X B2B B; (2.13) the expression (2.12) can be written also as C(A0) = min 2 (A) "X B2B BH (XBc) ( sum 1)H (XM) # ; (2.14) For the case A =M, the expression above simpli es further to C(M) = min 1 j j 1D PXMk j jY i=1 PX i ; (2.15) where the minimum is over all (nontrivial) partitions = ( 1; :::; k) of M with j j = k parts, 2 k m [12] (see also [20, Example 4]). Depending on the task at hand, we shall use these expressions for C(A0) inter- changeably in this dissertation. Finally, for m = 2, the expression for C(M) reduces to the omnipresent mutual information. Theorem 2.2. [48, 1] The SK capacity for A0 =M = f0; 1g is C(f1; 2g) = I(X1 ^X2): For further discussion on SKs, see Section 6.7. 26 2.5 Common information quantities The rst notion of CI for two rvs was given by G acs and K orner in their seminal work [26]. One interpretation of the G acs-K orner CI is as the maximum rate of a CR that can be established by two terminals observing i.i.d. repetitions of two correlated rvs X1 and X2, without any communication. Formally, De nition 2.4. A number R 0 is an achievable G acs-K orner CI rate if for every 0 < < 1 there exists an n 1 and a ( nite-valued) rv L = L (Xn1 ; Xn2 ) of rate (1=n)H(L) R such that L is -recoverable from Xn1 and -recoverable from Xn2 . The supremum over all achievable G acs-K orner CI rates is called the G acs- K orner CI of X1 and X2, denoted CIGK(X1 ^X2). For characterizing their CI, G acs and K orner speci ed the maximal common function of X1 and X2, denoted here as mcf(X1; X2), as separate functions of X1 and X2 that agree with probability 1, such that any other common function of X1 and X2 is a function of mcf(X1; X2). Theorem 2.3. [26] The G acs-K orner CI of the rvs X1; X2 is CIGK(X1 ^X2) = H(mcf(X1; X2)): In Chapter 3, we introduce a new multiterminal version of mcf in De nition 3.4. Subsequently, Wyner de ned CI as the minimum rate of a function of i.i.d. repetitions of two correlated rvs X1 and X2 that facilitated a speci c distributed 27 source coding task [77]. Alternatively, it can be de ned as the minimum rate of a function of i.i.d. repetitions of X1 and X2 such that, conditioned on this function, the i.i.d. sequences are (almost) independent; this de nition, though not stated explicitly in [77], follows from the analysis therein. Formally, De nition 2.5. A number R 0 is an achievable Wyner CI rate if for every 0 < < 1 there exists an n 1 and a ( nite-valued) rv L = L (Xn1 ; Xn2 ) of rate (1=n)H(L) R that satis es the property: 1 nI (X n 1 ^Xn2 j L) : (2.16) Obvious examples of such an rv L are L = (Xn1 ; Xn2 ) or Xn1 or Xn2 . The in mum of all achievable CI rates, denoted CIW (X1 ^X2), is called the Wyner CI of X1 and X2. The following theorem characterizes CIW (X1 ^X2). Theorem 2.4. [77] The Wyner CI of the rvs X1; X2 is CIW (X1 ^X2) = minU I(X1; X2 ^ U); (2.17) where the rv U takes values in a ( nite) set U with jUj jX1jjX2j and satis es the Markov condition X1 U X2. The direct part follows from [77, equation (5.12)]. The proof of the converse is straightforward. The following inequality ensues [26, 77]: CIGK(X1 ^X2) I(X1 ^X2) CIW (X1 ^X2): 28 2.6 Invariance of common information The concepts and the results reviewed above, which are standard in multiterminal information theory, will be used throughout this dissertation. In this section, we present a new invariance property of CI quantities. Since any good notion of CI between rvs X1 and X2 measures the correlation between X1 and X2, it is reasonable to expect the CI to remain unchanged if X1 and X2 are replaced by their respective su cient statistics. The following theorem establishes this for the quantities H(mcf(X1; X2)); I(X1 ^X2) and CIW (X1 ^X2). Theorem 2.5. For rvs X1 and X2, let functions g1 of X1 and g2 of X2 be such that X1 g1(X1) X2 and X1 g2(X2) X2. Then the following relations hold: H(mcf(X1; X2)) = H (mcf (g1(X1); g2(X2))) ; I(X1 ^X2) = I (g1(X1) ^ g2(X2)) ; CIW (X1 ^X2) = CI (g1(X1) ^ g2(X2)) ; Remark. A new notion of CI, termed interactive CI, is introduced in Chapter 5 and a similar invariance property is established for it in Theorem 5.8 Proof. First note that I(X1 ^X2) = I (g1(X1) ^X2) = I (g1(X1) ^ g2(X2)) : Next, we consider the G acs-K orner CI. Note that any common function of g1(X1) and g2(X2) is also a common function of X1 and X2. Consequently, H(mcf(X1; X2)) H(mcf(g1(X1); g2(X2))): (2.18) 29 For the reverse inequality, observe that for an rv U such thatH(U jX2) = H(U jX1) = 0 we have U X1 g1(X1) X2: Thus, H (U jg1(X1)) H(U jX2) = 0; and similarly, H (U jg2(X2)) = 0: In particular, it holds that H (mcf(X1; X2)jg1(X1)) = H (mcf(X1; X2)jg2(X2)) = 0; and so, H(mcf(X1; X2)) H(mcf(g1(X1); g2(X2))); which along with (2.18) yields H(mcf(X1; X2)) = H(mcf(g1(X1); g2(X2))): Finally, we consider Wyner?s CI and claim that this, too, remains unchanged upon replacing the rvs with their respective su cient statistics (for the other rv). It su ces to show that CIW (X1 ^X2) = CIW (g(X1) ^X2); for a function g such that X1 g(X1) X2. Consider an rv U for which X1 U X2 is satis ed. We have 0 = I(X1 ^X2 j U) I (g(X1) ^X2 j U) : It follows from (2.17) that CIW (X1 ^X2) CIW (g(X1) ^X2) : (2.19) 30 On the other hand, for an rv L = L (gn (Xn1 ) ; Xn2 ) we have 1 nI (X n 1 ^Xn2 j L) = 1 nI (g n (Xn1 ) ^Xn2 j L) ; since I (Xn1 ^Xn2 j L; gn (Xn1 )) I (Xn1 ^Xn2 ; L j gn (Xn1 )) = I (Xn1 ^Xn2 j gn (Xn1 )) = 0: Thus, from the de nition of CIW (g(X1) ^X2) we get CIW (X1 ^X2) CIW (g(X1) ^X2); so that, by (2.19), CIW (X1 ^X2) = CIW (g(X1) ^X2): 2.7 Two basic tools In this section, we present two technical tools that have been developed in this dissertation and may be of independent interest. 2.7.1 Balanced coloring lemma Since our security criterion involves almost independence, all our achievability schemes rely on the existence of a mapping of an rv U that is almost independent of an- other rv V correlated with U . For instance, in the SK generation problem, with the established CR in the role of U and the eavesdropper?s observations (including the 31 public communication) in the role of V , is used to extract an SK. In the secure computing problem, with the local observations at a terminal in the role of U and the private function value in the role of V , constitutes a communication from the terminal which is almost independent of the private function value. One basic tool for showing the existence of such a mapping is the \balanced coloring lemma" of Ahlswede and Csisz ar [2] stated below5. Lemma 2.6. [2, Lemma 3.1] Let P be any family of N pmfs on a nite set U , and let d > 0 be such that P 2 P satis es P u : P (u) > 1d ; (2.20) for some 0 < < (1=9). Then the probability that a randomly selected mapping : U ! f1; :::; rg fails to satisfy rX i=1 X u: (u)=i P (u) 1r < 3 ; (2.21) simultaneously for each P 2 P, is less than 2Nr exp 2d3r . Note that for P = PU jV=v; v 2 V , the left side of (2.21) is svar( (U); V ), where svar is de ned in (2.7). Therefore, we can nd a mapping such that svar( (U); V ) < 3 if 2Nr exp 2d3r < 1. This gives an estimate of the size r of the range of to ensure almost independence of (U) and V . In fact, the bound in (2.20) need not be satis ed for every PU jV=v, and it su ces to require (2.20) for v 2 V0 with PV (V0) close to 1. As an illustration, consider rvs Un and V n, the n 5An alternative tool for the same purpose is the \generalized privacy ampli cation" result of Bennett, Brassard, Cr epeau and Maurer [7]. 32 i.i.d. repetitions of U; V . Then, the foregoing approach guarantees the existence of a mapping of Un of rate (approximately) H(U j V ) such that svar( (Un); V n)! 0 as n goes to 1. A typical application of the lemma above is to the case where V includes the value of a mapping h : U ! f1; : : : ; r0g. In [20, Lemma B.2], Csisz ar and Narayan proved a version of the \balanced coloring lemma" that was tailored to handle this case. When applied to the i.i.d. illustration above, it implied that for a mapping h(Un) of rate R, there exists a mapping (Un) of rate (approximately) H(U j V ) R such that for Zn = (V n; h(Un)), svar( (Un); Zn)! 0 as n!1: In other words, there is a loss equal to R in the rate of the constructed mapping if the eavesdropper additionally knows h(Un) of rate R. As an application, consider the problem of generating an SK for M. If a CR XnM is established using a com- munication of rate R, then an SK of rate H(XM) R can be generated. Therefore H(XM) RCO(M) is an achievable SK rate for M, which is optimal by Theorem 2.1. In this dissertation we need a further generalization of [20, Lemma B.2] when the bound in (2.20) holds not for U but for another rv U 0 that di ers from U with probability close to 0, i.e., we call for a balanced coloring of U while we have the bound (2.20) holding for U 0. Speci cally, consider rvs U;U 0; V with values in nite sets U ;U 0;V , respectively, where U 0 is a function of U , and a mapping h : U ! f1; : : : ; r0g. For > 0, let U0 33 be a subset of U such that (i) P (U 2 U0) > 1 2; (ii) given the event fU 2 U0; h(U) = j; U 0 = u0; V = vg, there exists u = u(u0) 2 U0 satisfying P (U 0 = u0 j h(U) = j; V = v; U 2 U0) = P (U = u j h(U) = j; V = v; U 2 U0) ; (2.22) for 1 j r0 and v 2 V : Then the following holds. Lemma 2.7. Let the rvs U;U 0; V and the set U0 be as above. Further, assume that PUV (u; v) : P (U = u j V = v) > 1d 2: (2.23) Then, a randomly selected mapping : U 0 ! f1; : : : ; rg fails to satisfy r0X j=1 X v2V P (h(U) = j; V = v) rX i=1 X u02U 0: (u0)=i P (U 0 = u0 j h(U) = j; V = v) 1r < 14 ; (2.24) with probability less than 2rr0jVj exp c 3drr0 for a constant c > 0. Remark. Note that the quantity on the left side of (2.24) is svar = svar( (U); (h(U); V )). By [20, Lemma 1] it holds that sin( (U); (h(U); V )) svar log r svar ; where sin is as in (2.2). Since the function f(x) = x log(r=x) is increasing for 0 < x < r=e, it follows from (2.24) that sin( (U); (h(U); V )) 14 log jUj 14 : (2.25) 34 Therefore, the \balanced coloring lemma" su ces to show security in the sense of (2.2), too. The proof of Lemma 2.7 is a variation of the proof of [20, Lemma B.2] and is given in Appendix C. 2.7.2 R enyi entropy and sets with large probability The next result relates the cardinalities of large probability sets to R enyi entropy. The rst part is used in the converse proofs in Chapter 6. The mentioned result is of independent interest and is shown below to yield an elementary alternative proof of the source coding theorem for an i.i.d. ( nite-valued) source. De nition 2.6. [57] Let be a nonnegative measure on U . For 0 6= 1, the R enyi entropy of order of is de ned as H ( ) = 1 1 log X u2U (u) : Lemma 2.8. (i) For every 0 < < (U), there exists a set U U such that (U ) (U) ; (2.26) and jU j =(1 ) exp (H ( )) ; 0 < 1: (2.27) (ii) Conversely, for ; 0 > 0, + 0 < (U), any set U U with (U ) as in (2.26) must satisfy jU j ( 0)1=( 1) ( (U) 0) exp (H ( )) ; > 1: (2.28) 35 Proof. (i) For 0 < 1, de ning U = n u 2 U : (u) > 11 exp [ H ( )] o , we get (U) = (U ) + X u: (u) 1 1 exp[ H ( )] (u): Writing the summand in the right-side above as (u) = (u) (u)1 , we obtain (U) (U ) + exp [ (1 )H ( )] X u2U (u) = (U ) + ; (2.29) which is (2.26). Furthermore, exp [(1 )H ( )] = X u2U (u) X u2U (u) jU j 1 exp [ H ( )] ; (2.30) which gives (2.27). (ii) By following the steps in the proof of (i), for > 1, it can shown that the set U0 = n u 2 U : (u) < ( 0)1=(1 ) exp[ H ( )] o (2.31) has (U0) > (U) 0; which, with (2.26), gives (U0 \ U ) > (U) 0: 36 Since by (2.31) (U0 \ U ) < jU0 \ U j ( 0)1=(1 ) exp[ H ( )]; (2.28) follows. Lemma 2.8 relating the cardinalities of large probability sets to R enyi entropy can be interpreted as a source coding result for a general source with nite alphabet U . Furthermore, it leads to the following asymptotic result. Consider a sequence of probability measures n on nite sets Un, n 1. For 0 < < 1, R is a -achievable (block) source coding rate if there exists sets Vn Un satisfying n(Vn) 1 ; for all n su ciently large, and lim sup n 1 n log jVnj R: The optimum source coding rate R ( ) is the in mum of all such -achievable rates. Proposition 2.9. For each 0 < < 1, lim #1 lim sup n 1 nH ( n) R ( ) lim "1 lim sup n 1 nH ( n): (2.32) Corollary 2.10. If n is an i.i.d. probability measure on Un = U ::: U , then R ( ) = H( 1); 0 < < 1: Proof. The Proposition is a direct consequence of Lemma 2.8 upon taking appropri- ate limits in (2.27) and (2.28) with Un in the role of U . The Corollary follows since 37 for i.i.d. n, H ( n) = nH ( 1) and lim !1H ( 1) = H( 1): Note that the Corollary above is proved without recourse to the \asymptotic equipartition property". Moreover, it contains a strong converse for the lossless coding theorem for an i.i.d. source. In general, Proposition 2.9 implies a strong converse whenever the lower and upper bounds for R ( ) in (2.32) coincide. This implication is a special case of a general source coding result in [32, Theorem 1.5.1], [33], where it was shown that a strong converse holds i for rvs Un with pmfs n, the \lim-inf" and \lim-sup" of Zn = 1n log 1 n(Un) in n-probability coincide, i.e., sup n : lim n n(Zn < ) = 0 o = inf n : lim n n(Zn > ) = 0 o : (2.33) In fact, a straightforward calculation shows that the lower and upper bounds for R ( ) in (2.32) are admissible choices of on the left- and right-sides of (2.33), respectively. 38 CHAPTER 3 Secure Computation 3.1 Synopsis A subset of a set of terminals that observe correlated signals seek to compute a given function of the signals using public communication. It is required that the value of the function be concealed from an eavesdropper with access to the communica- tion. We show that the function is securely computable if and only if its entropy is less than the capacity of a new secrecy generation model, for which a single-letter characterization is provided. The main results in Section 3.3 are organized in three parts: capacity of a (new) aided secret key model; characterization of the secure computability of a function g; and a decomposition result for the total entropy of the model, which lies at the heart of our technical approach. Proofs are provided in Section 3.4 and concluding remarks in Section 3.5. The results of this chapter were reported in [67, 69, 68]. 39 3.2 Formulation: Secure function computation by public communication Terminals 1; : : : ;m observe, respectively, the sequences Xn1 ; : : : ; Xnm, of length n. Let g : XM ! Y be a given mapping, where Y is a nite alphabet. For n 1, the mapping gn : X nM ! Yn is de ned by gn(xnM) = (g(x11; : : : ; xm1); : : : ; g(x1n; : : : ; xmn)); xnM = (xn1 ; : : : ; xnm) 2 X nM: For convenience, we shall denote the rv gn (XnM) by Gn; n 1, and, in particular, G1 = g (XM) simply by G. The terminals in a given set A M wish to \compute securely" the function gn(xnM) for xnM in X nM. To this end, the terminals are allowed to communicate over a noiseless public channel, possibly interactively in several rounds. Randomization at the terminals is permitted; we assume that terminal i generates a rv Ui; i 2M, such that U1; : : : ; Um and XnM are mutually independent. While the cardinalities of range spaces of Ui; i 2 M; are unrestricted, we assume that H (UM) <1 (see De nition 2.1). De nition 3.1. For n > 0; n 1, we say that g is n-securely computable ( n- SC) by (the terminals in) a given set A M with jAj 1 from observations of length n, randomization UM and public communication F = F(n), if (i) gn is n- recoverable from (Ui; Xni ;F) for every i 2 A, i.e., there exists bg(n)i 40 satisfying P bg(n)i (Ui; Xni ;F) 6= Gn n; i 2 A; (3.1) and (ii) gn satis es the strong secrecy condition [49, 16, 19]. I(Gn ^ F) n: (3.2) By de nition, an n-SC function g is recoverable (as gn) at the terminals in A and is e ectively concealed from an eavesdropper with access to the public communication F. De nition 3.2. We say that g is securely computable by A if g is n- SC by A from observations of length n, suitable randomization UM and public communication F, such that lim n n = 0. Figure 3.1 shows our setup for secure computing. 3.3 When is a function securely computable? We consider rst the case when all the terminals inM wish to compute securely the function g, i.e., A =M. Our result for this case will be seen to be linked inherently to the standard concept of SK capacity for a multiterminal source model described in the previous chapter (see De nition 2.3), and serves to motivate our approach to the general case when A M. A comparison of the conditions in (3.2) and (2.6) that must be met by a securely computable g and an SK K, respectively, shows for a given g to be securely 41 Public communication F , I(F ?Gn) ?= 0 Xn1 g?(n)2= =Pr { } ?= 1= gn(XnM)g?(n)a XnmXn2 Xna F1 F2 Fa Fm A =g?(n)1 Figure 3.1: Secure computation of g computable, it is necessary that H(G) C(M): (3.3) Remarkably, it transpires that H(G) < C(M) is a su cient condition for g to be securely computable, and constitutes our rst result. Theorem 3.1. A function g is securely computable by M if H(G) < C(M): (3.4) Conversely, if g is securely computable by M, then H(G) C(M). Theorem 3.1 is, in fact, a special case of our main result in Theorem 3.4 below. Example 3.1. Secure Computation of Parity. Let m = 2, and let X1 and X2 be 42 f0; 1g-valued rvs with PX1(1) = p = 1 PX1(0); 0 < p < 1; PX2jX1(1 j 0) = PX2jX1(0 j 1) = ; 0 < < 1 2; such rvs X1 and X2 give rise to binary symmetric sources (BSS). Let g(x1; x2) = x1 + x2 mod 2. From Theorem 2.1, C(f1; 2g) = h(p ) h( ), where p = (1 p) +p(1 ). Since H(G) = h( ), by Theorem 3.1 g is securely computable if 2h( ) < h(p ): (3.5) We give a simple scheme for the secure computation of g when p = 1=2, that relies on Wyner?s well-known method for Slepian-Wolf data compression [76] and a derived SK generation scheme in [82], [81]. When p = 1=2, we can write Xn1 = Xn2 +Gn mod 2 (3.6) with Gn being independent separately of Xn2 and Xn1 . We observe as in [76] that there exists a binary linear code, of rate = 1 h( ), with parity check matrix P such that Xn1 , and so Gn, is n-recoverable from (F1; Xn2 ) at terminal 2, where the Slepian-Wolf codeword F1 = PXn1 constitutes public communication from terminal 1, and where n decays to 0 exponentially rapidly in n. Let cGn be the estimate of Gn thereby formed at terminal 2. (We can take cGn to have been compressed losslessly to rate H(G).) Further, let K = K(Xn1 ) be the location of Xn1 in the coset of the standard array corresponding to P. By the previous observation, K 43 too is n-recoverable from (F1; Xn2 ) at terminal 2. From [82], [81], K constitutes a \perfect" SK for terminals 1 and 2, of rate = I(X1 ^X2) = 1 h( ), and satisfying I(K ^ F1) = 0: (3.7) Also, observe from (3.6) that K = K(Xn1 ) = K(Xn2 + Gn) and F1 = F1(Xn1 ) = F1(Xn2 + Gn). Since Gn is independent of Xn2 , it follows that conditioned on each xed value Gn = gn, the (common) argument of K and F1, namely Xn2 +Gn, has a conditional pmf that equals the pmf of Xn2 + gn which, in turn, coincides with the pmf of Xn1 + gn, i.e., a permutation of the pmf of Xn1 . Hence by (3.7), I(K ^ F1; Gn) = I(K ^ F1 j Gn) = 0; (3.8) since I(K ^Gn) I(Xn1 ^Gn) = 0. Then terminal 2 communicates cGn in encrypted form as F2 = cGn +K mod 2 (all represented in bits), with encryption feasible since H(G) = h( ) < 1 h( ) = 1nH(K); by the su cient condition (3.5). Terminal 1 then decrypts F2 using K to recover cGn. The computation of gn is secure since I(Gn ^ F1; F2) = I(Gn ^ F1) + I(Gn ^ F2 j F1) is small; speci cally, the rst term equals 0 since I(Gn ^ F1) I(Gn ^ Xn1 ) = 0, 44 while the second term is bounded according to I(Gn ^ F2 j F1) = H(cGn +K j F1) H(cGn +K j F1; Gn) H(K) H(Gn +K j F1; Gn) + n; with n ! 0 = I(K ^ F1; Gn) + n = n; where the intermediate step uses Fano?s inequality and the exponential decay of n to 0, and the last equality is by (3.8). Example 3.2. Consider the setup of Example 3.1 for the case p = 1=2, but now with terminal 1 alone seeking to compute g. Since Gn is independent of Xn2 , secure computation of g at terminal 1 is possible with terminal 2 simply communicating Xn2 , even when X1 and X2 are independent. Note that H(G) = h( ) C (f1g) = H (X1) = 1; for 0 1=2. We now turn to the general model for the secure computability of g by a given set A M. Again in the manner of (3.3), it is clear that a necessary condition is H(G) C(A): In contrast, when A M, the condition H(G) < C(A) is not su cient for g to be securely computable by A as seen by the following simple example. Example 3.3. Omniscience is Forbidden. Let m = 3, A = f1; 2g and consider rvs X1; X2; X3 with X1 = X2, where X1 is independent of X3 and H(X3) < H(X1). 45 Let g be de ned by g(x1; x2; x3) = x3, xi 2 Xi, 1 i 3. Clearly, C(f1; 2g) = H(X1). Therefore, H(G) = H(X3) < C(f1; 2g). However, for g to be computed by the terminals 1 and 2, its value must be conveyed to them necessarily by public communication from terminal 3. Thus, g is not securely computable. We observe in Example 3.2 that if the value of Gn is given to terminal 2 after it has communicated Xn2 to terminal 1, then both terminals attain omniscience, with terminal 1 doing so from communication that is independent of Gn. Terminal 1 then computes Gn from its omniscience. Interestingly, the secure computability of g can be examined in terms of a new SK generation problem that contains these features and is formulated next. 3.3.1 Secret key aided by side information We consider an extension of the SK generation problem in De nition 2.3, which involves additional side information ZnA0 that is correlated with XnM and is provided to the terminals in A0 for use in only the recovery stage of SK generation; however, the public communication F remains as in De nition 2.1. Formally, the extension is described in terms of generic rvs (X1; : : : ; Xm; fZi; i 2 A0g), where the rvs Zi too take values in nite sets Zi, i 2 A0. The full force of this extension will not be needed to characterize the secure computability of g; an appropriate particularization will su ce. Nevertheless, this concept is of independent interest. De nition 3.3. A function K of (XnM; ZnA0) is an n- secret key aided by side infor- mation ZnA0 ( n-ASK) for the terminals A0 M, jA0j 2, achievable from observa- 46 tions of length n, randomization UM and public communication F = F(UM; XnM) if it satis es the conditions in De nition 2.3 with (Ui; Xni ; Zni ;F) in the role of (Ui; Xni ;F) in condition (i). The corresponding ASK capacity C(A0; ZA0) is de ned analogously as in De nition 2.3. In contrast with the omniscience rate of H(XM) that appears in the passage following Theorem 2.1, now an underlying analogous notion of omniscience will involve total CR of rate exceeding H(XM). Speci cally, the enhanced CR rate will equal the entropy of the mcf of the rvs (XM; Zi)i2A, introduced for a pair of rvs in [26] (see also [17, Problem 3.4.27] and Chapter 2 above). De nition 3.4. [26] For two rvs Q;R with values in nite setsQ;R, the equivalence relation q q0 in Q holds if there exist N 1 and sequences (q0; q1; : : : ; qN) in Q with q0 = q, qN = q0 and (r1; : : : ; rN) in R satisfying P (Q = ql 1; R = rl) > 0 and P (Q = ql; R = rl) > 0, l = 1; : : : ; N . Denote the corresponding equivalence classes in Q by Q1; : : : ;Qk. Similarly, let R1; : : : ;Rk0 denote the equivalence classes in R. As argued in [26], k = k0 and for 1 i; j k, P (Q 2 Qi j R 2 Rj) = P (R 2 Rj j Q 2 Qi) = 8 >>>< >>>: 1; i = j; 0; i 6= j: The mcf of the rvs Q;R is a rv mcf(Q;R) with values in f1; : : : ; kg, de ned by mcf(Q;R) = i i Q 2 Qi; R 2 Ri; i = 1; : : : ; k: For rvs Q1; :::; Qm taking values in nite alphabets, we de ne the mcf(Q1; :::; Qm) 47 recursively by mcf(Q1; :::; Qm) = mcf mcf(Q1; :::; Qm 1); Qm (3.9) with mcf(Q1; Q2) as above. De nition 3.5. With Qn denoting n i.i.d. repetitions of the rv Q, we de ne mcfn(Q1; :::; Qm) = fmcf (Q1t; :::; Qmt)gnt=1 : (3.10) Note that mcfn(Q1; :::; Qm) is a function of each individual Qni ; i = 1; :::;m. Remark. As justi cation for the De nition (3.9), consider a rv that satis es H( j Qi) = 0; i = 1; :::;m (3.11) and suppose for any other rv 0 satisfying (3.11) that H( ) H( 0). Then Lemma 3.2 below shows that must satisfy H( ) = H(mcf(Q1; :::; Qm)). The following result for the mcf of m 2 rvs is a simple extension of the classic result for m = 2 [26, Theorem 1]. Lemma 3.2. Given 0 < < 1, if (n) is -recoverable from Qni for each i = 1; :::;m, then lim sup n 1 nH (n) H(mcf(Q1; :::; Qm)): (3.12) Proof: The proof involves a recursive application of [26, Lemma, Section 4] to mcf(Q1; :::; Qm) in (3.9), and is provided in Appendix A. We are now in a position to characterize ASK capacity. In a manner analogous to Theorem 2.1, this is done in terms of H(mcf(XM; Zi)i2A0) and the smallest rate 48 of communication RCO(A0; ZA0) for each terminal in A0 to attain omniscience that corresponds to n i.i.d. repetitions of mcf ((XM; Zi)i2A0). Theorem 3.3. The ASK capacity C(A0;ZA0) is given by C(A0;ZA0) = H(mcf((XM; Zi)i2A0)) RCO(A0;ZA0); where RCO(A0;ZA0) = min RM2R(A0;ZA0 ) X i2M Ri; with R(A0;ZA0) = RM : X i2B Ri maxj2Bc\A0H(XB j XBc ; Zj); B M;A 0 * B : (3.13) The proof of Theorem 3.3 is along the same lines as that of Theorem 2.1 [20] and is provided in Appendix B. The remark following Theorem 2.1 also applies to the ASK capacity C(A0;ZA0), as will be seen from the proof of Theorem 3.3. 3.3.2 Characterization of secure computability If g is securely computable by the terminals in A, then Gn constitutes an ASK for M under the constraint (2.6), of rate H(G), with side information in the form of Gn provided only to the terminals in Ac in the recovery stage of SK generation. Thus, a necessary condition for g to be securely computable by A, in the manner of (3.3), is H(G) C(M;ZM); (3.14) 49 where ZM = ZM(A) = fZigi2M with Zi = 8 >>>< >>>: 0; i 2 A G; i 2 Ac: (3.15) By particularizing Theorem 3.3 to the choice of ZM as above, the right side of (3.14) reduces to C(M;ZM) = H(XM) RCO(M;ZM); where (3.16) RCO(M;ZM) = min RM2R(M;ZM) X i2M Ri; with R(M;ZM) = ( RM : X i2B Ri H(XB j XBc); B M;A * B H(XB j XBc ; G); B M;A B ) : Our main result says that the necessary condition (3.14) is tight. Consider a protocol that enables the terminals in M to attain omniscience using communication that is independent of Gn, when Gn is provided only as \decoder side information" to the terminals in Ac but cannot be used for communication. Our proof shows that condition (3.17) below is su cient for such a protocol to exist. Clearly, this protocol also serves for the secure computation of g by the terminals in A upon disregarding the decoding tasks in Ac (so that the protocol does not depend on a knowledge of Gn). Theorem 3.4. A function g is securely computable by A M if H(G) < C(M;ZM): (3.17) Furthermore, under the condition above, g is securely computable with noninteractive communication and without recourse to randomization at the terminals in M. 50 Conversely, if g is securely computable by A M, then H(G) C(M;ZM). Remarks. (i) As in the proof of achievability of SK capacity in [20], our proof of the su ciency of (3.17) for the secure computability of g holds with n in (3.1), (3.2) decaying to zero exponentially rapidly in n. (ii) It is easy to see that C(M) C (M;ZM) C(A), where ZM is as in (3.15). In particular, the second inequality holds by noting that an SK for M is also an SK for A, and that the side information for recovery ZM in (3.15) is not provided to the terminals in A. (iii) Observe in Example 3 that C (M;ZM) = C(M) = 0 and so, by Theorem 3.4, g is not securely computable as noted earlier. Example 3.4. Secure Computing Using an SK. In certain practical applications, di erent terminals observe mutually independent data and each seeks to securely compute a function g of the totality of all the observations. To enable this, they share a perfect SK, say K, of rate R. Then, since the SK capacity for this model is equal to R, by Theorem 3.1 a protocol for securely computing g exists if H(G) < R, and only if H(G) R. Therefore, the terminals must share an SK of rate larger than H(G) to accomplish secure computing. Concretely, consider the case m = 2 with terminals 1 and 2 observing, re- spectively, random independent bits B1 and B2. Each terminal wishes to compute securely B1 B2. Furthermore, assume that the terminals share a one-bit SK K, which is independent of (B1; B2); thus, X1 = (B1; K) and X2 = (B2; K). Then, the following simple protocol ensures secure computing: F1 = B1, F2 = K B1 B2. 51 In fact, this same protocol can be repeated n times to securely compute the parity for n i.i.d. pairs of independent random bits observed by the two terminals. But is this optimal or can we make do with less than n bits of SK? Heuristically, se- cure computing is feasible owing to the advantage that the legitimate parties have over the eavesdropper due to the correlation in their observations. In this simple example, this correlation corresponds to a shared SK. Therefore, the question raised above is, in e ect, an \inverse" problem where we wish to quantify the minimum correlation needed to ensure secure computing. Speci cally, since the SK capacity in this model is equal to the rate R of the SK, secure computing is feasible only if R H(B1 B2) = 1 and so, the number of bits of SK cannot be (asymptotically) less than n for secure computing. Hence, the simple protocol above is asymptotically optimal. Example 3.5. Secure Auction. In an online auction, m 1 bidders acting inde- pendently of each other, randomly place one of k bids on a secure server. After a period of independent daily bidding, the server posts a cryptic message on a public website. We shall see that such a message exists from which each bidder can deduce securely the highest daily bids, but for m > k + 1 no message exists to allow any of them to identify securely the daily winners. Indeed, here A = f1; :::;m 1g and X1; :::; Xm 1 are i.i.d. rvs distributed uniformly on f1; :::; kg, while Xm = (X1; :::; Xm 1). Let g1(x1; :::; xm) = max 1 i m 1 xi and g2(x1; :::; xm) = arg max 1 i m 1 xi. Then, straightforward computation yields that H(G1) < log k; and for both g1; g2 that C (M;ZM) = C(M); where, by Theorem 52 2.1, C(M) = H(XM) RCO(M) = (m 1) log k (m 2) log k = log k: (3.18) Hence, by Theorem 3.4, g1 is securely computable. Since H(G2) = log(m 1); g2 is securely computable if k > m 1. However, for k < m 1, g2 is not securely computable by any terminal i 2 f1; :::;m 1g. This, too, is implied by Theorem 3.4 upon noting that for each i 2 f1; :::;m 1g and a restricted choice A = fig and ZM as in (3.15), C (M;ZM) = H(Xi) = log k < log(m 1) = H(G2); where the rst equality is a consequence of remark (ii) following Theorem 3.4, (3.18) and remark (i) following Theorem 2.1. 3.3.3 A decomposition result The su ciency condition (3.17) prompts the following two natural questions: Does the di erence C (M;ZM) H(G) possess an operational signi cance? If g is securely computable by the terminals in A, clearly Gn forms an SK for A. Can Gn be augmented suitably to form an SK for A of maximum achievable rate? The answers to both these questions are in the a rmative. In particular, our approach to the second question involves a characterization of the minimum rate of communication for omniscience for A, under the additional requirement that this communication be independent of Gn. Speci cally, we show below that for a securely computable function g, this minimum rate remains RCO(A) (see (2.4), (2.5)). 53 Addressing the rst question, we introduce a rv Kg = K(n)g such that K = (Kg; Gn) constitutes an n-ASK for M with side information ZM as in (3.15) and satisfying the additional requirement I (Kg ^Gn) n: (3.19) Let the largest rate limn(1=n)H (Kg) of such an ASK be Cg (M;ZM). Observe that since K is required to be nearly independent of F, where F is the public communication involved in its formation, it follows by (3.19) that Kg is nearly independent of (Gn;F). Turning to the second question, in the same vein let K 0g be a rv such that K 0 = K 0g; Gn constitutes an n-SK for A M and satisfying (3.19). Let Cg(A) denote the largest rate of K 0g. As noted above, K 0g will be nearly independent of (Gn;F0), where F0 is the public communication involved in the formation of K 0. Proposition 3.5. If g satis es (3.17), for A M it holds that (i) Cg (M;ZM(A)) = C (M;ZM(A)) H(G); (ii) Cg(A) = C(A) H(G): Remarks. (i) For the case A = M, both (i) and (ii) above reduce to Cg(M) = C(M) H(G). (ii) Theorem 2.1 and Proposition 3.5 (ii) lead to the observation H(XM) = RCO(A) +H(G) + Cg(A); which admits the following heuristic interpretation. The \total randomness" XnM that corresponds to omniscience decomposes into three \nearly mutually indepen- 54 dent" components: a minimum-sized communication for omniscience for A and the independent parts of an optimum-rate SK for A composed of Gn and K 0g. 3.4 Proofs of main results Proof of Theorem 3.4. The necessity of (3.14) follows by the comments preceding Theorem 3.4. The su ciency of (3.17) will be established by showing the existence of non- interactive public communication comprising source codes that enable omniscience corresponding to XnM at the terminals in A, and thereby the computation of g. Furthermore, the corresponding codewords are selected so as to be simultaneously independent of Gn, thus assuring security. First, from (3.17) and (3.16), there exists > 0 such that RCO(M;ZM) + < H(XMjG), using G = g(XM). For each i and Ri 0, consider a (map- valued) rv Ji that is uniformly distributed on the family Ji of all mappings X ni ! f1; : : : ; dexp(nRi)eg; i 2M. The rvs J1; :::; Jm; XnM are taken to be mutually inde- pendent. Fix ; 0, with 0 > m and + 0 < 1. It follows from the proof of the general source network coding theorem [17, Lemma 3.1.13 and Theorem 3.1.14] that for all su ciently large n, P jM 2 JM : XnM is n-recoverable from Xni ; jMnfig XnMnfig ; Zni ; i 2M 1 ; (3.20) provided RM = (R1; :::; Rm) 2 R(M;ZM), where n vanishes exponentially rapidly 55 in n. This assertion follows exactly as in the proof of [20, Proposition 1, with A =M] but with ~Xi there equal to (Xi; Zi) rather than Xi, i 2 M. In particular, we shall choose RM 2 R(M;ZM) such that mX i=1 Ri RCO(M;ZM) + 2 : (3.21) Below we shall establish that P (fjM 2 JM : I (jM(XnM) ^Gn) ng) 0; (3.22) for all n su ciently large, to which end it su ces to show that P n jM 2 JM : I ji(Xni ) ^Gn; jMnfig XnMnfig nm o 0 m; i 2M; (3.23) since I (jM (XnM) ^Gn) = mX i=1 I ji (Xni ) ^Gn j j1 (Xn1 ) ; : : : ; ji 1 Xni 1 mX i=1 I ji (Xni ) ^Gn; jMnfig XnMnfig : Then it would follow from (3.20), (3.22) and de nition of ZM in (3.15) that P jM 2 JM : Gn is n-recoverable from Xni ; jMnfig XnMnfig ; i 2 A; and I(jM(XnM) ^Gn) < n 1 0: This shows the existence of a particular realization jM of JM such that Gn is n-SC from Xni ; jMnfig XnMnfig for each i 2 A. 56 It now remains to prove (3.23). Fix i 2 M and note that for each ji 2 Ji, with kjik denoting the cardinality of the (image) set ji(X ni ), I ji (Xni ) ^Gn; jMnfig XnMnfig I ji (Xni ) ^Gn; jMnfig XnMnfig + log kjik H (ji (Xni )) = D ji(Xni ); Gn; jMnfig XnMnfig Uji(Xni ) Gn; jMnfig XnMnfig ; (3.24) where the right side above denotes the (Kullback-Leibler) divergence between the joint pmf of ji(Xni ), Gn; jMnfig XnMnfig and the product of the uniform pmf on ji(X ni ) and the pmf of Gn; jMnfig XnMnfig . Using [20, Lemma 1], the right side of (3.24) is bounded above further by svar log kjik svar ; (3.25) where svar = svar ji(Xni );Gn; jMnfig XnMnfig is the variational distance between the pmfs in the divergence above. Therefore, to prove (3.23), it su ces to show that P n jM 2 JM : svar ji(Xni );Gn; jMnfig XnMnfig nm o 0 m; i 2M; (3.26) on account of the fact that log kji(Xni )k = O(n), and the exponential decay to 0 of n. De ning ~Ji = jMnfig 2 JMnfig : XnM is n-recoverable from Xni ; jMnfig XnMnfig ; Zni ; we have by (3.20) that P JMnfig 2 ~Ji 1 . It follows that P n jM 2 JM : svar ji (Xni ) ;Gn; jMnfig XnMnfig nm o + X jMnfig2 ~Ji P JMnfig = jMnfig P n ji 2 Ji : svar ji(Xni );Gn; jMnfig XnMnfig nm o ; 57 since Ji is independent of JMnfig. Thus, (3.26), and hence (3.23), will follow upon showing that P n ji 2 Ji : svar ji(Xni );Gn; jMnfig XnMnfig nm o 0 m ; jMnfig 2 ~Ji; (3.27) for all n su ciently large. Fix jMnfig 2 ~Ji. We take recourse to Lemma 2.7 and set U = XnM; U 0 = Xni ; V = Gn; h = jMnfig, and U0 = xnM 2 X nM : xnM = i xni ; jMnfig xnMnfig ; gn (xnM) 1 (i 2 Ac) for some mapping i. By the de nition of ~Ji, P (U 2 U0) 1 n; so that condition (2.22)(i) preceding Lemma 2.7 is met. Condition (2.22)(ii), too, is met since conditioned on the events in (2.22)(ii), only those xnM 2 U0 can occur that are determined uniquely by their ith components xni . Upon choosing d = exp n H(XMjG) 6 ; in (2.23), the hypotheses of Lemma 2.7 are satis ed with = p n for an appropriate exponentially vanishing n. Then, by Lemma 2.7, with r = dexp[nRi]e ; r0 = 2 666 exp 2 4n 0 @ X l2Mnfig Rl + 6 1 A 3 5 3 777 ; and with Ji in the role of , we get from (2.24) and (3.21) that P ji 2 Ji : svar ji(Xni );Gn; jMnfig XnMnfig 14p n 58 decays to 0 doubly exponentially in n, which proves (3.27). This completes the proof of Theorem 3.4. Proof of Proposition 3.5. (i) Since the rv (K(n)g ; Gn), with nearly independent components, constitutes an ASK forM with side information ZM as in (3.15), it is clear that H(G) + Cg (M;ZM) C (M;ZM) : (3.28) In order to prove the reverse of (3.28), we show that C (M;ZM) H(G) is an achievable ASK rate for Kg that additionally satis es (3.19). First, note that in the proof of Theorem 3.4, the assertions (3.20) and (3.23) mean that for all su ciently large n, there exists a public communication FM, say, such that I(FM ^ Gn) < n and XnM is n-recoverable from (Xni ; FM; Zni ) for every i 2M, with limn n = 0. Fix 0 < < , where is as in the proof of Theorem 3.4. Apply Lemma 2.7, choosing U = U 0 = XnM; U0 = X nM; V = Gn; h = FM; d = exp h n H (XMjG) 6 i ; (3.29) whereby the hypothesis (2.23) of Lemma 2.7 is satis ed for all n su ciently large. Fixing r0 = l exp h n RCO (M;ZM) + 2 im ; by Lemma 2.7 a randomly chosen of rate 1 n log r = H(XMjG) RCO (M;ZM) = C (M;ZM) H(G) 59 will yield an ASK Kg = K(n)g = (XnM) which is nearly independent of (FM; Gn) (and, in particular, satis es (3.19)) with positive probability, for all n su ciently large. (ii) The proof can be completed as that of part (i) upon showing that for a se- curely computable g, for all > 0 and n su ciently large, there exists a public communication F 0M that meets the following requirements: its rate does not exceed RCO(A) + ; I(F 0M ^Gn) < n; and XnM is n-recoverable from (Xni ; F 0M) for every i 2 A. To that end, for RM = (R1; :::; Rm) 2 R(M;ZM) as in the proof of Theorem 3.4, consider R0M = (R01; :::; R0m) 2 R(A) that satis es R0i Ri for all i 2M and mX i=1 R0i RCO(A) + ; noting that R (M;ZM) R(A). Further, for JM and JM as in that proof, de ne a (map-valued) rv J 0i that is uniformly distributed on the family J 0i of all map- pings from f1; : : : ; dexp(nRi)eg to f1; : : : ; dexp(nR0i)eg, i 2 M. The rvs J1; :::; Jm; J 01; :::; J 0m; XnM are taken to be mutually independent. De ne J 0M as the set of map- pings jM 2 JM for which there exists a j0M 2 J 0M such that XnM is n-recoverable from (Xni ; j0M (jM (XnM))) for every i 2 A. By the general source network coding theorem [17, Lemma 3.1.13 and Theorem 3.1.14], applied to the random mapping J 0M (JM), it follows that for all su ciently large n, P JM 2 J0M 1 : This, together with (3.20) and (3.23) in the proof of Theorem 3.4, imply that for a securely computable g there exist jM 2 JM and j0M 2 J 0M for which the public 60 communication F 0M , j0M(jM) satis es the aforementioned requirements. Finally, apply Lemma 2.7 with U;U 0;U0; V and d as in (3.29) but with h = F 0M and r0 = l exp h n RCO (A) + 2 im : As in the proof above of part (i), an SK K 0g = K 0(n) g of rate 1 n log r = H(XMjG) RCO (A) = C (A) H(G) which is nearly independent of (F 0M; Gn) (and, hence, satis es (3.19)) exists for all n su ciently large. 3.5 Discussion We obtain simple necessary and su cient conditions for secure computability ex- pressed in terms of function entropy and ASK capacity. The latter is the largest rate of an SK for a new model in which side information is provided for use in only the recovery stage of SK generation. This model could be of independent interest. In particular, a function is securely computable if its entropy is less than the ASK capacity of an associated secrecy model. The di erence is shown to correspond to the maximum achievable rate of an ASK which is independent of the securely computed function and, together with it, forms an ASK of optimum rate. Also, a function that is securely computed by A can be augmented to form an SK for A of maximum rate. Our results extend trivially to functions de ned on a block of symbols of xed length in an obvious manner by considering larger alphabets composed of 61 supersymbols of such length. However, they do not cover sequences of functions of symbols of increasing length (in n), e.g., a running average (in n). In our proof of Theorem 3.4, g was securely computed from omniscience at all the terminals in A M that was attained using noninteractive public communica- tion. However, omniscience is not necessary for the secure computation of g, and it is possible to make do with communication of rate less than RCO(A) using an interactive protocol. A related unresolved question is: What is the minimum rate of public communication for secure computation? A natural generalization of the conditions for secure computability of g by A M given here entails a characterization of conditions for the secure computability of multiple functions g1; :::; gk by subsets A1; :::;Ak of M, respectively. This unsolved problem, in general, will not permit omniscience for any Ai; i = 1; :::; k. For instance with m = 2, A1 = f1g, A2 = f2g, and X1 and X2 being independent, the functions gi(xi) = xi, i = 1; 2, are securely computable trivially, but not through omniscience since, in this example, public communication is forbidden for the secure computation of g1; g2. The next chapter addresses a version of the mentioned generalization. Yet another direction involves a model in which the terminals in M securely compute G = g (XM), and the eavesdropper has additional access to correlated side information that may not be available to the terminals in M. Speci cally, the eavesdropper observes n i.i.d. repetitions Zn of a Z-valued rv Z that has a given joint pmf with XM, in addition to the public communication F of the terminals in 62 M. The secrecy condition (2.2) is replaced by I (Gn ^ F j Zn) n; (3.30) noting that G need not be independent of Z. Having computed g securely, the terminals in M can extract a rv K = K (Gn), of rate H(G j Z), that is (nearly) independent of Zn. Together with (3.30), this means that K is similarly independent of (F; Zn). Since K constitutes a wiretap secret key (WSK), its rate H(G j Z) necessarily cannot exceed the corresponding WSK capacity [48, 1, 20]. A single- letter characterization of WSK capacity remains unresolved in general (cf. [31]). The su ciency of the previous necessary condition is unclear even when WSK capacity is known. In the special circumstance in which the terminals inM, too, have access to Zn, a single-letter characterization of WSK capacity is known [20]. In this case, our proof technique shows that the aforementioned necessary condition is also su cient. 63 CHAPTER 4 Secure Computation: Multiple Functions 4.1 Synopsis This chapter generalizes and extends the results of the previous chapter to the com- putation of multiple given functions of the observations at the terminals while main- taining the privacy of a speci ed function. Speci cally, multiple terminals observe correlated data and seek to compute functions of the data using interactive public communication. At the same time, it is required that the value of a private function of the data remain concealed from an eavesdropper observing this communication. In general, the private function and the functions computed by the terminals can be all di erent. We show that a class of functions are securely computable if and only if the conditional entropy of data given the value of private function is greater than the least rate of interactive communication required for a related multiterminal source-coding task. A single-letter formula is provided for this rate in special cases. The problem of secure computing for multiple functions is formulated in the next section, followed by our results in Section 4.3. The proofs are given in Sections 4.4 and 4.5. The nal section discusses alternative forms of the necessary conditions. The results of this chapter were reported in [62, 64]. 64 4.2 Formulation: Secure computation of multiple functions We consider a multiterminal source model for function computation using public communication, with a con dentiality requirement. Terminals 1; : : : ;m observe, respectively, the sequences Xn1 ; : : : ; Xnm of length n. For 0 i m, let gi : XM ! Yi be given mappings, where the sets Yi are nite. Further, for 0 i m and n 1, the (single-letter) mapping gni : X nM ! Yni is de ned by gni (xnM) = (gi(x11; : : : ; xm1); : : : ; gi(x1n; : : : ; xmn)); xnM = (xn1 ; : : : ; xnm) 2 X nM: For convenience, we shall denote the rv gni (XnM) by Gni ; n 1, and, in particular, G1i = gi (XM) simply by Gi. Each terminal i 2M wishes to compute the function gni (xnM), without reveal- ing gn0 (xnM), xnM 2 X nM. To this end, the terminals are allowed to communicate over a noiseless public channel, possibly interactively in several rounds. An interactive communication protocol is as in De nition 2.1 but, for simplicity, in this chapter we do not allow local randomization, i.e., UM = ;. The rate of the interactive communication F is 1n log kFk. De nition 4.1. For n > 0, n 1, we say that functions1 gM = (g0; g1; :::; gm), with private function g0, are n-securely computable ( n- SC) from observations of length n, and public communication F = F(n), if (i) Gni is n- recoverable from (Xni ;F) for every i 2M, and 1 The abuse of notation gM = (g0; g1; :::; gm) simpli es our presentation. 65 (ii) F satis es the secrecy condition 1 nI (G n 0 ^ F) n: Remark. The de nition of secrecy here corresponds to the notion of weak secrecy. When our results have a single-letter form, our achievability schemes for secure computing attain strong secrecy (see De nition 2.3 and remarks (ii), (iii) following Theorem 2.1). By de nition, for n-SC functions gM, the private function G0 is e ectively concealed from an eavesdropper with access to the public communication F. De nition 4.2. For private function g0, we say that functions gM are securely com- putable if gM are n- SC from observationsXnM of length n and public communication F = F(n), such that lim n n = 0. Figure 4.1 shows the setup for secure computing. In this dissertation, we give necessary and su cient conditions for the secure computability of certain classes of functions gM = (g0; g1; :::; gm). The formulation in Chapter 3, in which the terminals in a given subset A of M are required to compute (only) g0 securely, is a special case with gi = 8 >>>< >>>: g0; i 2 A; constant; otherwise. (4.1) Upon rearranging the terms in Theorem 3.4, we see that conditions H (XM j G0) R (4.2) 66 Fm Xn1 Xn2 Xnm G?(n)1 G? (n) 2 G? (n) m Interactive Communication F, 1nI (F ?Gn0) ? 0 F1 F2 Figure 4.1: Secure computation of g1; :::; gm with private function g0 and H (XM j G0) > R (4.3) constitute, respectively, necessary and su cient conditions for the functions above to be securely computable, with R being the minimum rate of interactive com- munication F that enables all the terminals in M to attain omniscience, using F and with decoder side information Gn0 given to the terminals in M n A. In fact, it was shown that when condition (4.3) holds, it is possible to recover XnM using communication that is independent of Gn0 . The guiding heuristic in this chapter is the following general principle, which is also consistent with the results of the previous chapter: Conditions (4.2) and (4.3) constitute, respectively, the necessary and su cient conditions for functions gM = (g0; g1; :::; gm) to be securely computable, where R is the in mum of the rates of interactive communication F0 such that, for each 67 1 i m, the following hold simultaneously: (P1) Gni is n-recoverable from (Xni ;F0), and (P2) XnM is n-recoverable from (Xni ; Gn0 ;F0), i.e., terminals attain omniscience, with Gn0 as side information that is used only for decoding (but is not used for the communication F0), where n ! 0 as n!1. Thus, (P1) and (P2) require any terminal computing g0 to become omniscient, an observation that was also made for the special case in Chapter 3. The rst con- dition (P1) above is straightforward and ensures the computability of the functions g1; :::; gm, by the terminals 1; :::;m, respectively. The omniscience condition (P2) fa- cilitates the decomposition of total entropy into mutually independent components that include the random values of the private function Gn0 and the communication F0. For the speci c case in (4.1), R above has a single-letter formula. In general, a single-letter expression for R is not known. Our results, described in section 4.3, are obtained by simple adaptations of this principle. However, unlike in the previous chapter, our conditions, in general, are not of a single-letter form. Nevertheless, they provide a structural characterization of secure computability. As an application, our results provide simple conditions for secure computability in the following illustrative example. Example 4.1. Secure Computing for Binary Symmetric Sources. We consider the case of m = 2 terminals that observe BSS (see Example 3.1) with underlying 68 rvs X1; X2 with joint pmf given by P (X1 = 0; X2 = 0) = P (X1 = 1; X2 = 1) = 1 2 ; P (X1 = 0; X2 = 1) = P (X1 = 1; X2 = 0) = 2 ; where 0 < < 1=2 (cf. Example 3.1). The results of this dissertation will allow us to provide conditions for the secure computability of the four choices of g0; g1; g2 below; it will follow by Theorem 4.1 that functions g0; g1; g2 are securely computable if h( ) < ; and conversely, if the functions above are securely computable, then h( ) ; where h( ) = log (1 ) log(1 ), and the constant = ( ) depends on the choice of the function. These characterizations are summarized in the next table. Denote the AND and the OR of two random bits X1 and X2 by X1:X2 and X1 X2, respectively. g0 g1 g2 X1 X2 X1 X2 X1 X2 1=2 X1 X2 X1 X2 1 X1 X2; X1:X2 X1 X2; X1:X2 X1:X2 2 =3 X1 X2 X1 X2 X1:X2 2=3 The results for the rst two settings follow from Examples 3.1, 3.2. The third and fourth results are new. In these settings, terminal 1 is required to recover 69 the private function; our results below show that the conditions for the secure com- putability in these cases remain unchanged even if this terminal is required to attain omniscience. Note that since h( ) < 1 for all 0 < < 1=2, there exists a commu- nication protocol for securely computing the functions in the second setting. By contrast, a secure computing protocol for the functions in the third setting does not exist for any 0 < < 1=2, since h( ) > 2 =3. 4.3 Characterization of securely computable functions In this section, we characterize securely computable functions for three settings. Our necessary and su cient conditions entail the comparison of H (XMjG0) with a rate R ; the speci c choice of R depends on the functions gM. Below we consider three di erent classes of functions gM. Although the rst class is a special case of the second, the two are handled separately as the more restrictive case is amenable to simpler analysis. Furthermore, for m = 2, the obtained necessary and su cient conditions for secure computability take a single-letter form in the rst case (see Corollary 4.4). (1) In the rst class we consider, values of all the functions g1; :::; gm must be kept secret. In addition, at least one of the terminals must compute all the functions g1; :::; gm. This case arises in distributed function computation over a network where all the computed values are collated at a single sink node, and we are interested in securing the collated function values. Alternatively, denoting the function computed at the sink node by the private function g0, the computed functions g1; :::; gm can 70 be restricted to be functions of g0. Speci cally, for 0 < m0 < m, and for private function g0, let gi = 8 >>>< >>>: g0; i 2 [1;m0] ; gi (g0) ; i 2 [m0 + 1;m] : (4.4) (2) The next case is a relaxation of the previous model in that the restriction gi = gi (g0) for i 2 [m0 + 1;m] is dropped. For this general case, our analysis below implies roughly that requiring the terminals [1;m0] that compute the private function g0 to recover the entire data XnM does not change the conditions for secure computability, which is a key observation of this dissertation. (3) The last class of problems we study is an instance of secure multiterminal source coding , which arises in the data download problems in sensor networks where each node is interested in downloading the data observed by a subset of nodes. Speci - cally, we consider the situation where each terminal wishes to recover some subset XnMi of the sources where Mi Mn fig, i.e., gi (XM) = XMi ; i 2M: (4.5) This last case appears at rst blush to be disconnected from the previous two cases. However, our characterizations of secure computability below have the same form for all cases above. Moreover, the same heuristic principle, highlighted in (P1) and (P2), leads to a characterization of secure computability in all three cases. The necessary and su cient conditions for secure computability are stated in terms of quantities R i (gM), i = 1; 2; 3, which are de ned next. The subscript 71 i corresponds to case (i) above. In particular, the quantity R corresponds to the minimum rate of communication needed for an appropriate modi cation of the source-coding task in (P1), (P2). Below we give speci c expressions for R i , i = 1; 2; 3, along with their operational roles (for a complete description of this role see the su ciency proof in Section 4.4). Denote by R 1 (gM) the closure of the (nonempty) set of pairs2 R(1)F ; 1 nI (G n 0 ^ F) ; for all n 1 and interactive communication F, where R(1)F = 1 nH(F) + 1 n mX i=m0+1 H (Gni jXni ;F) + inf RM; (4.6) with the in mum taken over the rates R1; :::; Rm satisfying the following constraints: (1a) 8L (M, [1;m0] * L, RL 1 nH XnLjXnMnL;F ; (1b) 8L (M, [1;m0] L, RL 1 nH XnLjXnMnL; Gn0 ;F : The quantity infn;FR(1)F corresponds to the solution of a multiterminal source coding problem. Speci cally, it is the in mum of the rates of interactive communication that satisfy (P1) and (P2) above (see [18, Theorem 13.15], [20]). 2The rst term accounts for the rate of the communication and the second term tracks the information about Gn0 leaked by F (see (4.11)) below 72 Next, let R 2 (gM) denote the closure of the set of pairs R(2)F ; 1 nI (G n 0 ^ F) ; for all n 1 and interactive communication F, where R(2)F = 1 nH(F) + inf R0[m0+1;m] +RM ; (4.7) with the in mum taken over the rates R1; :::; Rm and R0m0+1; :::; R0m satisfying the following constraints: (2a) 8L (M, [1;m0] * L, RL 1 nH XnLjXnMnL;F ; (2b) for m0 < j m, R0j 1 nH Gnj jXnj ;F ; (2c) 8L M; [1;m0] L, and L0 [m0 + 1;m] with either L 6= M or L0 6= [m0 + 1;m], R0L0 +RL 1 nH GnL0 ; XnLjGn[m0+1;m]nL0 ; XnMnL; Gn0 ;F : The quantity infn;FR(2)F corresponds to the solution of a multiterminal source coding problem, and is the in mum of the rates of interactive communication F0 that satisfy (P1) and (P2) above, and additionally satis es: (P3) XnM is n-recoverable from Gnj ; Gn0 ;F0 , m0 < j m. 73 This modi cation corresponds to the introduction of m m0 dummy terminals, with the jth dummy terminal observing Gnj , m0 < j m (see section 4.6); the dummy terminals can be realized by a terminal i in [1; :::;m0] that recovers XnM from (Xni ;F). The conditions (P2) and (P3) above correspond to the omniscience at the terminals in the extended model, with Gn0 provided as side information only for decoding. Finally, denote by R 3 (gM) the closure of the set of pairs R(3)F ; 1 nI (G n 0 ^ F) ; for all interactive communication F, where R(3)F = 1 nH(F) + inf RM; (4.8) with rates R1; :::; Rm satisfying the following constraints: (3a) For 1 i m, 8L Mi Mn fig, RL 1 nH XnLjXnMinL; Xni ;F ; (3b) 8L (M, RL 1 nH XnLjXnMnL; Gn0 ;F : As before, the quantity infn;FR(3)F corresponds to the in mum of the rates of inter- active communication that satisfy (P1) and (P2) above. Our main result below characterizes securely computable functions for the three settings above. 74 Theorem 4.1. For i = 1; 2; 3, with functions g0; g1; :::; gm as in the case (i) above, the functions gM are securely computable if the following condition holds: H (XMjG0) > R i (gM) : (4.9) Conversely, if the functions above are securely computable, then H (XMjG0) R i (gM) ; (4.10) where R i (gM) = inf (x;0)2R i (gM) x; i = 1; 2; 3: (4.11) Remark. Although the rst setting above is a special case of the second, it is unclear if for gM in (4.4) the quantities R 1(gM) and R 2(gM) are identical (also, see Section 4.6). In general, the multi-letter characterizations of secure computability of gM above can have di erent forms. For case (1) with m = 2, Corollary 4:4 below provides a single-letter formula for R 1(gM). However, a similar single-letter formula for R 2(gM) is not known. Theorem 4.1 a ords the following heuristic interpretation. The quantityH (XMjG0) represents the maximum rate of randomness in XnM that is (nearly) independent of Gn0 . On the other hand, R i (gM) is an appropriate rate of communication for the computation of gM; we show that latter being less than H (XMjG0) guarantees the secure computability of gM. Although the characterization in Theorem 4.1 is not of a single-letter form, the following result provides a su cient condition for obtaining such forms. Denote by R(i)constant, i = 1; 2; 3, the quantity R(i)F for F = constant. 75 Lemma 4.2. For case (i), i = 1; 2; 3, if for all n 1 and interactive communication F R(i)F R (i) constant; (4.12) then R i (gM) = R (i) constant = infn;FR(i)F . The proof is a simple consequence of the de nition of R i (gM) in (4.11). Note that R(i)constant has a single-letter form. Remark. As mentioned before, the quantity infn;FR(i)F is the in mum of the rates of interactive communication that satis es (P1), (P2) for i = 1; 3, and satis es (P1)-(P3) for i = 2. Thus, when the conditions of Lemma 4.2 hold, we have from Theorem 4.1 that gM are securely computable if H (XMjG0) > R(i)constant; and if gM are securely computable then H (XMjG0) R(i)constant; where R(i)constant is the minimum rate of communication that satis es (P1), (P2) for i = 1; 3, and satis es (P1)-(P3) for i = 2. As a consequence of Lemma 4.2, we obtain below a single-letter characteriza- tion of securely computable functions, with m = 2, in a special case; the following lemma is instrumental to our proof. Lemma 4.3. Let m = 2. For an interactive communication F, we have H(F) H (FjXn1 ) +H (FjXn2 ) : 76 Proof. Lemma 4.3 is a special case of [21, Lemma B.1] (also, see [46]). We provide a proof here for completion. H(F) = H(F1) +H(F j F1) H(F1 j Y n) +H(F j F1) H(F1 j Y n) +H(F2 j F1) +H(F j F1; F2) H(F1 j Y n) +H(F2 j F1; Xn) +H(F j F1; F2) = H(F1; F2 j Y n) +H(F1; F2 j Xn) +H(F j F1; F2); where the last step uses H(F1 j Xn) = H(F2 j F1; Y n) = 0. The proof is completed by an iterative application of these steps. We next consider case (1) for two terminals. Corollary 4.4. For m = 2, for functions g0; g1; g2 with g1 = g0 and g2 = g2 (g0), we have R 1 (gM) = H (X2jX1) +H (G2jX2) +H (X1jX2; G0) : (4.13) Proof: The constraints (1a) and (1b) satis ed by rates R1; R2 in the de nition of R(1)F are R2 1 nH (X n 2 jXn1 ;F) ; R1 1 nH (X n 1 jXn2 ; Gn0 ;F) ; which further yields R(1)F = 1 n [H (F) +H (G n 2 jXn2 ;F) +H (Xn2 jXn1 ;F) +H (Xn1 jXn2 ; Gn0 ;F)] : (4.14) 77 Thus, R(1)constant equals the term on the right side of (4.13). Upon manipulating the expression for R(1)F above, we get R(1)F = 1 n [H(F) H (FjX n 1 ) H (FjXn2 ; Gn0 ) I (Gn2 ^ FjXn2 )] +R(1)constant: (4.15) Further, since H (G2jG0) = 0, it holds that I (Gn2 ^ FjXn2 ) I (Gn0 ^ FjXn2 ) ; which along with (4.15) yields R(1)F 1 n H(F) H (FjXn1 ) H (FjXn2 ) +R(1)constant R(1)constant; where the last inequality follows from Lemma 4.3. The result then follows from Lemma 4.2. We next derive simple conditions for secure computability for the BSS in Ex- ample 4.1 Example 4.2. Consider the setup of Example 4.1, with g0 = g1 = X1 X2; X1:X2 and g2 = X1:X2. By Corollary 4.4 and the observation H (G2jX2) = h( )=2, we get R 1 (gM) = 3h( )=2. SinceH (X1; X2 j G0) = H (X1; X2 j X1 X2) H (X1:X2 j X1 X2) = , the characterization of secure computability claimed in Example 4.1 follows from Theorem 4.1. Example 4.3. In the setup of Example 4.1, consider g0 = g1 = X1 X2 and g2 = X1:X2. This choice of g0; g1; g2 is an instance of case (2) above. For an interactive communication F, the constraints (2a), (2b), (2c) in the de nition of R(2)F , upon 78 simpli cation, reduce to R1 1 nH (X n 1 jXn2 ; Gn0 ; Gn2 ;F) ; R2 1 nH (X n 2 jXn1 ;F) ; R1 +R2 1 nH (X n 1 ; Xn2 jGn0 ; Gn2 ;F) ; R02 1 nH (G n 2 jXn2 ;F) : Therefore, inf [R1 +R2 +R02] with R1; R2; R02 satisfying (2a), (2b), (2c), is given by 1 n H (Xn1 jXn2 ; Gn0 ; Gn2 ;F) + max fH (Xn2 jGn0 ; Gn2 ;F) ; H (Xn2 jXn1 ;F)g +H (Gn2 jXn2 ;F) ; which further gives R(2)F = 1 n H(F) +H (Xn1 jXn2 ; Gn0 ; Gn2 ;F) + max fH (Xn2 jGn0 ; Gn2 ;F) ; H (Xn2 jXn1 ;F)g +H (Gn2 jXn2 ;F) : (4.16) It follows from H (Xn1 jXn2 ; Gn0 ; Gn2 ;F) = 0 that R(2)constant = H (G2jX2) + max fH (X2jG0; G2) ; H (X2jX1)g = h( )2 + max f ; h( )g = 3 2h( ); (4.17) as h( ) > for 0 < < 1=2. 79 Next, note from (4.16) that for any interactive communication F R(2)F 1 n [H(F) +H (X n 2 jXn1 ;F) +H (Gn2 jXn2 ;F)] = 1n [H(F) +H (X n 2 jXn1 ) H (FjXn1 ) +H (Gn2 ;FjXn2 ) H (FjXn2 )] 1n [H(F) H (FjX n 1 ) H (FjXn2 )] +H (G2jX2) +H (X2jX1) H (G2jX2) +H (X2jX1) = 3 2h( ); (4.18) where the last inequality above follows from Lemma 4.3. The characterization in Example 4.1 follows from (4.17), (4.18), and H (X1; X2jG0) = 1, using Lemma 4.2 and Theorem 4.1. 4.4 Proof of su ciency Su ciency of (4.9) for i = 1: We propose a two step protocol for securely computing g0; g1; :::; gm. In the rst step, for su cient large N , the terminals [1;m0] (g0-seeking terminals) attain omniscience, using an interactive communication F00 = F00 XNM that satis es 1 N I GN0 ^ F00 ; (4.19) where > 0 is su ciently small. Next, upon attaining omniscience, one of the terminals in [1;m0] computes the following for m0 < j m: (i) Slepian-Wolf codewords F^j = F^j GNj of appropriate rates R0j for a recovery of GNj by a decoder with the knowledge of XNj and previous communication F00, and 80 (ii) the rvs Kj = Kj XNj of rates R0j that satisfy: 1 NH (Kj) R 0 j ; (4.20) 1 N I Kj ^GN0 ;F00; n Kl F^l o m0 R0j+1: Thus, a randomly chosen mapping Kj+1 = Kj+1 XNj+1 of rate R0j+1 is almost jointly-independent of GN0 ;Fk;F0(j) (see [16]). This argument is made rigorous using a version of the balanced coloring lemma. Speci cally, in Lemma 2.7, set U = XNM, U 0 = XNj+1, V = GN0 ;Fk, h = F0(j), and U0 = xNM 2 XNM : xNM = j+1 xNj+1; f 0 xNM ;Fk; gn0 xNM ; for some mapping j+1, where f 0 XNM = F0 is as in (4.26). By the de nition of F0, P (U 2 U0) 1 ; so that condition (2.22)(i) preceding Lemma 2.7 is met. Condition (2.22)(ii), too, is met from the de nition of U0; h and V . Upon choosing d = exp k H (XnMjGn0 ;F) n 2m ; in (2.23), the hypotheses of Lemma 2.7 are satis ed for appropriately chosen , and for su ciently large k. Then, by Lemma 2.7, with r = exp NR0j+1 ; r0 = exp NR(j) ; 84 and with Kj+1 in the role of , it follows from (2.25) that there exists rv Kj+1 = Kj+1 XNj+1 that satis es (4.20) and (4.21), for k su ciently large. The proof is completed upon repeating this argument for m0 < j < m. Su ciency of (4.9) for i = 2: The secure computing protocol for this case also consists of two stages. In the rst stage, as before, the terminals [1;m0] (g0- seeking terminals) attain omniscience, using an interactive communication F00 = F00 XNM . The second stage, too, is similar to the previous case and involves one of the omniscience-attaining terminals in [1;m0] transmitting communication F^j = F^j GNj to the terminals j, for m0 < j m. However, the encryption-based scheme of the previous case is not applicable here; in particular, (4.22) no longer holds. Instead, the communication F^j now consists of the Slepian-Wolf codewords for GNj given XNj , and previous communication F00. We show below that if (4.9) holds, then there exist communication F00 and F^j, m0 < j m, of appropriate rate such that the following holds: 1 N I GN0 ^ F00; F^m0+1; :::; F^m < ; for su ciently large N . Speci cally, when (4.9) holds for i = 2, using similar manipulations as in the previous case we get that for all 0 < < 0, there exist interactive communication F = F (XnM), and rates R1; :::; Rm; R0m0+1; :::; R0m satisfying (2a)-(2c) (for F) such that 1 nI (G n 0 ^ F) < 2 ; 85 and RM +R0[m0+1;m] + < 1 nH (X n M j Gn0 ;F) ; (4.31) with < H (XM j G0) R 2 (gM) 0; (4.31) replaces (4.25) in the previous case. Next, for N = nk consider 2m m0 correlated sources XNj , 1 j m, and GNj , m0 < j m. Since R1; :::; Rm; R0m0+1; :::; R0m satisfy (2a)-(2c), random mappings F 0j = F 0j XNj of rates Rj, 1 j m, and F 0j+m m0 = F 0j+m m0 GNj of rates R0j, m0 < j m satisfy the following with high probability, for k su ciently large (see [18, Lemma 13.13 and Theorem 13.14]): (i) for 1 i m, XnkM is -recoverable from F 01; :::; F 0m;Fk; Xnki ; (ii) for m0 < j m, Gnkj is -recoverable from F 0j+m m0 ;Fk; Xnkj ; (iii) for m0 < j m, XnkM is -recoverable from F0;Fk; Xnkj ; Gnk0 and from F0;Fk; Gnkj ; Gnk0 , where Fk = (F1; :::;Fk) are i.i.d. rvs Fi = F XM;n(i 1)+1; :::; XM;ni , 1 i k. It follows from (4.31) in a manner similar to the proof in Appendix D that there exist communication F 0j , 1 j 2m m0 as above such that 1 nkI Gnk0 ^ F0;Fk < ; for su ciently large k. The rst stage of the protocol entails transmission of Fk, followed by the trans- mission of F 01; :::; F 0m, i.e., F00 = Fk; F 01; :::; F 0m . The second stage of communication 86 F^j is given by F 0j+m m0 , for m0 < j m. Su ciency of (4.9) for i = 3: Using the de nition of R 3 (gM) and the manip- ulations above, the su ciency condition (4.9) implies that for all 0 < < 0, there exist interactive communication F = F (XnM), and rates R1; :::; Rm satisfying (3a), (3b) (for F) such that 1 nI (G n 0 ^ F) < 2 ; and RM + < 1 nH (X n M j Gn0 ;F) ; (4.32) for < H (XM j G0) R 3 (gM) 0. Denoting by Fk = (F1; :::;Fk) the i.i.d. rvs Fi = F Xnin(i 1)+1 , 1 i k, it follows from (3a) and (3b) that for N = nk the random mappings F 0i = F 0i Xnki of rates Ri, 1 i m, satisfy the following with high probability, for k su ciently large (see [18, Lemma 13.13 and Theorem 13.14]): (i) for i 2M, XnkMi is -recoverable from F0;Fk; Xnki ; (ii) for i 2M, XnkM is -recoverable from F0;Fk; Xnki ; Gnk0 . From (4.32), proceeding along the lines of the arguments in Appendix D, it follows that there exist F 0i , i 2M, as above such that 1 nkI Gnk0 ^ F0;Fk < ; for su ciently large k. The interactive communication F0;Fk constitutes the protocol for securely computing gM, where gi (XM) = XMi ; i 2M. 87 4.5 Proof of necessity Necessity of (4.10) for i = 1: If functions gM are securely computable then there exists an interactive communication F such that Gni is n-recoverable from (Xni ;F), i 2M, and 1 nI (G n 0 ^ F) < n; (4.33) where n ! 0 as n!1. It follows from the Fano?s inequality that3 1 nH (G n i j Xni ;F) < c1 n; i 2M: (4.34) Using an approach similar to that in [20], we have from (4.33): 1 nH (X n M) = 1 nH (G n 0 ;F) + 1 nH (X n M j Gn0 ;F) 1nH (G n 0 ) + 1 nH (F) + 1 nH (X n M j Gn0 ;F) n; (4.35) = 1nH (G n 0 ) + 1 nH (F) + 1 n mX i=1 H Xni j Xn[1;i 1]; Gn0 ;F n: (4.36) Next, for L (M, with [1;m0] * L, we have 1 nH XnL j XnMnL;F = 1nH XnL j XnMnL; Gn0 ;F + 1nH Gn0 j XnMnL;F 1nH XnL j XnMnL; Gn0 ;F + c1 n; where the last step follows from (4.34) and the assumption that gi = g0 for i 2 3The constants c1; c2; c3; c4 depend only on log kXMk, m, m0 (and not on n). 88 [1;m0]. Continuing with the inequality above, we get 1 nH XnL j XnMnL;F 1n X i2L H Xni j Xn[1;i 1]; Gn0 ;F + c1 n ; (4.37) Letting Ri = 1 nH Xni j Xn[1;i 1]; Gn0 ;F + c1 n; i 2M; by (4.37) R1; :::; Rm satisfy (1a) and (1b) for F, whereby it follows from (4.34) and (4.36) that H (XM j G0) 1nH(F) + 1 n mX i=m0+1 H (Gni j Xni ;F) +RM c2 n R(1)F c2 n; where F satis es (4.33). Taking the limit n ! 1, and using the de nition of R 1 (gM) we get H (XM j G0) R 1 (gM) : Necessity of (4.10) for i = 2: If gM are securely computable, the approach above implies that there exists an interactive communication F satisfying (4.33) and (4.34) such that, with Ri = 8 >>>< >>>: 1 nH Xni j Xn[1;i 1]; Gn0 ;F + c1 n; 1 i m0; 1 nH Xni j Xn[1;i 1]; Gn[m0+1;i 1]; Gn0 ;F + c1 n; m0 < i m; R0j = c1 n; m0 < j m; 89 we have by (4.35), H (XM j G0) 1 nH(F) + 1 nH (X n M j Gn0 ;F) n 1nH(F) + 1 n m0X i=1 H Xni j Xn[1;i 1]; Gn0 ;F + 1n mX i=m0+1 H Xni j Xn[1;i 1]; Gn[m0+1;i 1]; Gn0 ;F n 1nH(F) +RM +R 0 [m0+1;m] c3 n: (4.38) Furthermore, (4.34) and the assumption gi = g0, 1 i m0, yield for [1;m0] * L (M that 1 nH XnL j XnMnL;F 1nH XnL j XnMnL; Gn0 ;F + c1 n X i2L; i m0 1 nH Xni j Xn[1;i 1]; Gn0 ;F + c1 n + X i2L; i>m0 1 nH Xni j Xn[1;i 1]; Gn[m0+1;i 1]; Gn0 ;F + c1 n = RL; (4.39) and similarly, for [1;m0] L M, L0 [m0 + 1;m], with either L 6= M or L0 6= [m0 + 1;m] that 1 nH GnL0 ; XnLjGn[m0+1;m]nL0 ; XnMnL; Gn0 ;F = 1nH XnLjGn[m0+1;m]nL0 ; XnMnL; Gn0 ;F 1nH XnL j XnMnL; Gn0 ;F RL +R0L0 ; (4.40) Therefore, (4.39), (4.34) and (4.40) imply that R1; :::; Rm, R0m0 ; :::; R0m satisfy (2a)- (2c) for F, which along with (4.38) yields H (XM j G0) R(2)F c3 n; 90 where R(2)F is as in (4.7), and F satis es (4.33), which completes the proof of necessity (4.10) for i = 2 upon taking the limit n!1. Necessity of (4.10) for i = 3: If the functions gM in (4.5) are securely com- putable then, as above, there exists an interactive communication F that satis es (4.33) and (4.34). De ning Ri = 1 nH Xni j Xn[1;i 1]; Gn0 ;F + c1 n; i 2M; similar manipulations as above yield H (XM j G0) 1 nH(F) +RM c4 n: (4.41) Further, from (4.34) we get that R1; :::; Rm satisfy (3a) and (3b) for F. It follows from (4.41) that H (XM j G0) R(3)F c4 n; where R(2)F is as in (4.8), and F satis es (4.33), which completes the proof of necessity (4.10) for i = 3 as above. 4.6 Discussion: Alternative necessary conditions for secure computability The necessary condition (4.10) for secure computing given in section 4.3 is in terms of quantities R(i)F , i = 1; 2; 3, de ned in (4.6), (4.7), (4.8), respectively. As remarked before, for i = 1; 3, the quantity infFR(i)F is the in mum over the rates of interactive communication that satisfy conditions (P1) and (P2). However, this is not true for 91 i = 2. Furthermore, although i = 1 is special case of i = 2, it is not clear if the necessary condition (4.10) for i = 2 reduces to that for i = 1 upon imposing the restriction in (4.4). In this section, we shed some light on this ba ing observation. First, consider the functions gM in (4.1). For this choice of functions, denot- ing by R 0 the minimum rate of interactive communication that satis es (P1) and (P2), the results in [68] imply that (4.2) constitutes a necessary condition for secure computability, with R = R 0. Next, consider an augmented model obtained by introducing a new terminal m+1 that observes rv Xm+1 = ~g (XM) and seeks to compute gm+1 = ;. Further, the terminal does not communicate, i.e., observation Xnm+1 is available only for decoding. Clearly, secure computability in the original model implies secure computability in the new model. It follows from the approach of [68] that for the new model also, (4.2) constitutes a necessary condition for secure computability, with R now being the minimum rate of interactive communication that satis es (P1) and (P2) when terminal m+ 1 does not communicate; this R is given by maxfH (XM j ~g(XM); G0) ; R 0g: Note that the new necessary condition (4.2) is H (XM j G0) R 0 = maxfH (XM j ~g(XM); G0) ; R 0g; which is, surprisingly, same as the original condition H (XM j G0) R 0: Our necessary condition (4.10) for i = 2 is based on a similar augmentation 92 that entails introduction ofm m0 new terminals observing gm0+1 (XM) ; :::; gm (XM) (to be used only for decoding). Now, however, this modi cation may result in a dif- ferent necessary condition. 93 CHAPTER 5 Common Randomness and Minimal Communication for Optimum Rate Secret Keys 5.1 Synopsis We focus on the generation of a secret key of maximum rate by a pair of terminals observing correlated data and with the means to communicate over a noiseless public communication channel. Our main result establishes a structural equivalence be- tween the generation of a maximum rate secret key and the generation of a common randomness that renders the observations of the two terminals conditionally inde- pendent. The minimum rate of such common randomness, termed interactive com- mon 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 ex- pression 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. 94 The de nition of interactive common information and the heuristics underlying our approach are given in Section 5.2. Our main results are provided in Section 5.3, followed by illustrative examples in the subsequent section. Section 5.5 shows an invariance property of interactive common information. A discussion of our results and possible extensions is given in the nal section. The results of this chapter were reported in [61, 63]. 5.2 Interactive common information The results of this chapter are for the case of two terminals; for convenience, we simplify our notations for the interactive communication F. Terminals 1 and 2 com- municate interactively, with, say, terminal 1 transmitting rst. Each terminal then communicates alternately for r rounds. Speci cally, an r-interactive communication f = (f1; f2; :::; fr) is a sequence of nite-valued mappings with f2i+1 : X n1 F2i ! F2i+1; 0 i b(r 1)=2c; f2i : X n2 F2i 1 ! F2i; 1 i br=2c; where fFigri=1 are nite sets and F0 = ;. As in Chapter 2, this set-up subsumes protocols where terminal 2 initiates the communication upon choosing f1 = con- stant. Let F = f (Xn1 ; Xn2 ) describe collectively the corresponding rv. The rate of this communication is given by 1 n log kFk: We assume that the communication from each terminal is a (deterministic) function of its knowledge. In particular, randomization is not allowed. This is not a limiting 95 assumption; see Section 5.6.1. We de ne a new notion of CI, termed interactive CI, which will be a key concept for this chapter. Recall from Chapter 2 that Wyner?s CI is de ned as the minimum rate of rvs L = L(n)(Xn1 ; Xn2 ) such that for all > 0, the following holds for n su ciently large: 1 nI (X n 1 ^Xn2 j L) : (5.1) Interactive CI is de ned by restricting the rvs L to be CR. De nition 5.1. An achievable r-interactive CI rate is de ned in a manner analogous to the achievable CI rate, but with the restriction that the rvs L in (5.1) be -CR, i.e., L = (J;F), where F is an r-interactive communication and J is -recoverable from F. The in mum of all achievable r-interactive CI rates, denoted CIri (X1;X2), is called the r-interactive CI of the rvs X1 and X2. By de nition, the nonnegative sequence fCIri (X1;X2)g1r=1 is nonincreasing in r and is bounded below by CIW (X1 ^ X2). De ne CIi(X1 ^X2) = limr!1CI r i (X1;X2): Then CIi(X1 ^ X2) CIW (X1 ^ X2) 0. Note that CIri (X1;X2) may not be symmetric in X1 and X2 since the communication is initiated at terminal 1. However, since CIr+1i (X1;X2) CIri (X2;X1) CIr 1i (X1;X2); 96 clearly, CIi(X1 ^X2) = limr!1CI r i (X1;X2) = limr!1CI r i (X2;X1) = CIi(X2 ^X1): (5.2) Further, for all 0 < < 1, J = Xn1 is -recoverable from Xn2 and a communication (of a Slepian-Wolf codeword) F = F (Xn1 ), and L = (J; F ) satis es (5.1). Hence, CIi(X1 ^X2) H(X1); similarly, CIi(X1 ^X2) H(X2). To summarize, we have 0 CIW (X1 ^X2) CIi(X1 ^X2) minfH(X1);H(X2)g; (5.3) where the rst and the last inequalities can be strict. In Section 5.4.1 we show that the second inequality is strict for BSS X1; X2. The r-interactive CI plays a pivotal role in optimum rate SK generation. Loosely speaking, our main result asserts the following. A CR that satis es (5.1) can be used to generate an optimum rate SK and conversely, an optimum rate SK yields a CR satisfying (5.1). In fact, such a CR of rate R can be recovered from an interactive communication of rate R C, where C is the SK capacity for X1 and X2. Therefore, to nd the minimum rate of interactive communication needed to generate an optimum rate SK, it is su cient to characterize CIi(X1 ^X2). 5.3 Formulation and main results De nition 5.2. A number R0 0 is an achievable r-interactive communication rate for CIri if, for all 0 < < 1, there exists, for some n 1, an r-interactive communication F of rate (1=n) log kFk R0 + , and an -CR J recoverable from F, with L = (J;F) satisfying (5.1). Let RrCI denote the in mum of all achievable 97 r-interactive communication rates for CIri . Similarly, R00 0 is an achievable r- interactive communication rate for SK capacity if, for all 0 < < 1, there exists, for some n 1, an r-interactive communication F of rate (1=n) log kFk R00 + , and an -SK K, recoverable from F, of rate (1=n)H(K) I(X1 ^X2) ; RrSK denotes the in mum of all achievable r-interactive communication rates for SK capacity. Note that by their de nitions, both RrCI and RrSK are nonincreasing with increasing r, and are bounded below by zero. De ne RCI = limr!1R r CI ; RSK = limr!1R r SK : Although RrCI(X1;X2) and RrSK(X1;X2) are not equal to RrCI(X2;X1) and RrSK(X2;X1), respectively, the quantities RCI and RSK are symmetric in X1 and X2 using an argument similar to the one leading to (5.2). Theorem 5.1. For every r 1, RrSK = RrCI = CIri (X1;X2) I(X1 ^X2): (5.4) Corollary 5.2. It holds that RSK = RCI = CIi(X1 ^X2) I(X1 ^X2): (5.5) Remark. The relation (5.5) can be interpreted as follows. Any CR J recoverable from (interactive communication) F, with L = (J;F) satisfying (5.1), can be decomposed into two mutually independent parts: An SK K of maximum rate and the interactive communication F. It follows upon rewriting (5.5) as CIi(X1^X2) = I(X1^X2)+RCI that the communication F is (approximately) of rate RCI . Furthermore, RCI is the same as RSK . 98 A computable characterization of the operational term CIi(X1 ^ X2) is not known. However, the next result gives a single-letter characterization of CIri (X1;X2). Theorem 5.3. Given rvs X1; X2 and r 1, we have CIri (X1;X2) = minU1;:::;Ur I(X1; X2 ^ U1; :::; Ur); (5.6) where the minimum is taken over rvs U1; :::; Ur taking values in nite sets U1; :::;Ur, respectively, that satisfy the following conditions (P1) U2i+1 X1; U2i X2; 0 i b(r 1)=2c; U2i X2; U2i 1 X1; 1 i br=2c; (P2) X1 U r X2; (P3) jU2i+1j jX1j 2iY j=1 jUjj+ 1; 0 i b(r 1)=2c; jU2ij jX2j 2i 1Y j=1 jUjj+ 1; 1 i br=2c; with U0 = ; and U0 = constant. Remark. Note that (5.6) has the same form as the expression for CIW (X1 ^X2) in (2.17) with W replaced by (U1; :::; Ur) satisfying the conditions above. Before presenting the proof of our main Theorems 5.1 and 5.3, we give perti- nent technical results that will constitute central tools for the proofs. Lemma 5.4. For an r-interactive communication F, de ne Fi = F Xni1(n(i 1)+1); Xni(2n(i 1)+1) ; 1 i k: 99 Then, for all k k0(n; ; jX1j; jX2j) there exists an r-interactive communication F0 = F0 Xnk1 ; Xnk2 of rate 1 nk log kF 0k 1n [H (FjX n 1 ) +H (FjXn2 )] + ; (5.7) such that Fk is an -CR recoverable from F0. Proof. From the Slepian-Wolf theorem [60], there exist mappings f1; :::; fr of F k1 ; :::; F kr , respectively, of rates 1 k log kf2i+1k H(F2i+1 j X n 2 ; F1; :::; F2i) + n 2r ; 0 i b(r 1)=2c; 1 k log kf2ik H(F2i j X n 1 ; F1; :::; F2i 1) + n 2r ; 1 i br=2c; such that F k2i+1 is 2r -recoverable from f2i+1(F k2i+1); XN2 ; F k1 ; :::; F k2i ; 0 i b(r 1)=2c; F k2i is 2r -recoverable from f2i(F k2i); XN1 ; F k1 ; :::; F k2i 1 ; 1 i br=2c; for all k su ciently large. Thus, the communication F0 given by F 0i = fi F ki , 1 i r constitutes the required communication of rate 1 nk log kF 0k 1n [H (FjX n 1 ) +H (FjXn2 )] + : Remark. Lemma 5.4 says that, in essence, for an optimum rate communication F, 1 n log kFk 1 n [H (FjX n 1 ) +H (FjXn2 )] : 100 Lemma 5.5. (A General Decomposition) For a CR J recoverable from an interactive communication F we have nI(X1 ^X2) = I (Xn1 ^Xn2 j J;F) +H(J;F) H (F j Xn1 ) H (F j Xn2 ) H (J j Xn1 ;F) H (J j Xn2 ;F) : (5.8) Proof. For T = T (Xn1 ; Xn2 ) we have, nI(X1 ^X2) = H (Xn1 ; Xn2 ) H (Xn1 j Xn2 ) H (Xn2 j Xn1 ) = H (Xn1 ; Xn2 j T ) H (Xn1 j Xn2 ; T ) H (Xn2 j Xn1 ; T ) +H(T ) H (T j Xn1 ) H (T j Xn2 ) = I (Xn1 ^Xn2 j T ) +H(T ) H (T j Xn1 ) H (T j Xn2 ) : Lemma 5.5 follows upon choosing T = J;F. Note that a simpli cation of (5.8) gives I(X1 ^X2) 1 n I (Xn1 ^Xn2 j J;F) +H(J;F) H (F j Xn1 ) H (F j Xn2 ) : (5.9) If J is an -CR recoverable from F, Fano?s inequality implies 1 n H(J j Xn1 ;F) +H(J j Xn2 ;F) 2 log jX1jjX2j+ 2h( ) = ( ); say, (5.10) where ( )! 0 as ! 0. Combining (5.8) and (5.10) we get I(X1 ^X2) 1 n I (Xn1 ^Xn2 j J;F) +H(J;F) H (F j Xn1 ) H (F j Xn2 ) ( ); (5.11) 101 and further, by Lemma 4.3, I(X1 ^X2) 1 n [I (X n 1 ^Xn2 j J;F) +H(J;F) H(F)] ( ): (5.12) Proof of Theorem 5.1. In this section we give a proof for (5.4). The proof of (5.5) then follows upon taking limit r ! 1 on both sides of (5.4). The proof of (5.4) follows from claims 1-3 below. In particular, the proofs of claims 1-3 establish a structural equivalence between a maximum rate SK and an SK of rate 1nH(J j F) extracted from a CR J recoverable from F such that L = (J;F) satis es (5.1). Claim 1: RrCI CIri (X1;X2) I(X1 ^X2). Proof. By the de nition of RrCI , for every 0 < < 1 there exists, for some n 1, an r-interactive communication F of rate 1 n log kFk R r CI + ; (5.13) and J , an -CR recoverable from F, such that L = (J;F) satis es (5.1). It follows upon rearranging the terms in (5.12) that 1 nH(J;F) I(X1 ^X2) + 1 nH(F) + ( ); which with (5.13) gives 1 nH(J;F) I(X1 ^X2) +R r CI + + ( ): (5.14) Since (J;F) satis es 1 nI (X n 1 ^Xn2 j J;F) + ( ); 102 the inequality (5.14), along with the fact that ( + ( )) ! 0 as ! 0, implies that I(X1 ^X2) +RrCI is an achievable r-interactive CI rate; hence, CIri (X1;X2) I(X1 ^X2) +RrCI . Claim 2: RrSK RrCI . Proof. Using the de nition of RrSK , for 0 < < 1 there exists, for some n 1, an r-interactive communication F of rate 1n log kFk RrSK + , and an -SK K recoverable from F of rate 1 nH(K) I(X1 ^X2) : (5.15) By choosing J = K in (5.12) and rearranging the terms we get, 1 nI (X n 1 ^Xn2 j K;F) I(X1 ^X2) 1 nH(K j F) + ( ): Next, from (1=n)I(K ^ F) < , we have 1 nI (X n 1 ^Xn2 j K;F) I(X1 ^X2) 1 nH(K) + + ( ) 2 + ( ); where the last inequality follows from (5.15). Since (2 + ( )) ! 0 as ! 0, RrSK is an achievable r-interactive communication rate for CIri , and thus, RrSK RrCI . Claim 3: RrSK CIri (X1;X2) I(X1 ^X2). Proof. For 0 < < 1, let J be an -CR recoverable from an r-interactive communication F, with 1 nH(J;F) CI r i (X1;X2) + ; (5.16) 103 such that L = (J;F) satis es (5.1), and so, by (5.9), 1 n [H(F j X n 1 ) +H(F j Xn2 )] 1 nH(J;F) I(X1 ^X2) + CIri (X1;X2) I(X1 ^X2) + 2 : (5.17) To prove the assertion in claim 3, we show that for some N 1 there exists ( )-SK K = K(XN1 ; XN2 ) of rate 1 n log kKk I(X1 ^X2) ( ) recoverable from an r-interactive communication F00 = F00(XN1 ; XN2 ) of rate 1 N log kF 00k 1n [H(F j X n 1 ) +H(F j Xn2 )] + ( ) 2 ; (5.18) where ( )! 0 as ! 0. Then (5.18), along with (5.17), would yield 1 N log kF 00k CIri (X1;X2) I(X1 ^X2) + ( ); (5.19) so that CIri (X1;X2) I(X1^X2) is an achievable r-interactive communication rate for SK capacity, thereby establishing the claim. It remains to nd K and F00 as above. To that end, let J be recovered as J1 = J1(Xn1 ;F) and J2 = J2(Xn2 ;F) by terminals 1 and 2, respectively, i.e., P (J = J1 = J2) 1 : Further, for k 1, let J1i = J1 Xni1(n(i 1)+1);Fi ; J2i = J2 Xni(2n(i 1)+1);Fi ; 1 i k; where Fi = F Xni1(n(i 1)+1); Xni(2n(i 1)+1) . For odd r, we nd an r-interactive com- munication F00 such that Jk1 ;Fk is a -CR recoverable from F00, for all k su ciently 104 large; the the SK K will be chosen to be a function of Jk1 ;Fk of appropriate rate. The proof for even r is similar and is obtained by interchanging the roles of J1 and J2. In particular, by Lemma 5.4, for all k su ciently large there exists an r-interactive communication F0 such that Fk is -CR recoverable from F0 of rate given by (5.7). Next, from Fano?s inequality 1 n maxfH(J j J1);H(J1 j J2)g log jX1jjX2j+ h( ): (5.20) By the Slepian-Wolf theorem [60] there exists a mapping f of Jk1 of rate 1 k log kfk H(J1 j J2) + n ; (5.21) such that Jk1 is -recoverable from f Jk1 ; Jk2 ; (5.22) for all k su ciently large. It follows from (5.20), (5.21) that 1 nk log kfk + log jX1jjX2j+ h( ): (5.23) For N = nk, we de ne the r-interactive communication F00 = F00 XN1 ; XN2 as F 00i = F 0i ; 1 i r 1; F 00k = F 0r; f(Jk1 ); i = r; Thus, Jk1 ;Fk is 2 -CR recoverable from F00, where, by (5.7) and (5.23), the rate of communication F00 is bounded by 1 nk log kF 00k 1n [H (FjX n 1 ) +H (FjXn2 )] + 2 + log jX1jjX2j+ h( ): (5.24) 105 Finally, to construct the SK K = K Jk1 ;Fk , using the corollary of Balanced Coloring Lemma in [20, Lemma B.3], with U = (J1;F); V = ; n = k; g = F0; we get from (5.24) that there exists a function K of Jk1 ;Fk such that 1 k log kKk H(U) 1 k log kF 00k H(J1;F) H(F j Xn1 ) H(F j Xn2 ) n(2 + log jX1jjX2j+ h( )); (5.25) and I(K ^ F0) exp( ck); where c > 0, for all su ciently large k. We get from (5.25) and (5.9) that the rate of K is bounded below as follows: 1 nk log kKk I(X1 ^X2) 1 nI (X n 1 ^Xn2 j J1;F) 2 log jX1jjX2j h( ): (5.26) Observe that I(Xn1 ^Xn2 j J;F) = I(J1; Xn1 ^Xn2 j J;F) I(Xn1 ^Xn2 j J; J1;F) I(Xn1 ^Xn2 j J1;F) H(J j J1); which along with (5.20), and the fact that L = (J;F) satis es (5.1), yields 1 nI(X n 1 ^Xn2 j J1;F) + log jX1jjX2j+ h( ): (5.27) 106 Upon combining (5.26) and (5.27) we get, 1 nk log kKk I(X1 ^X2) 3 2 log jX1jjX2j 2h( ): Thus, for ( ) = 4 +2 log jX1jjX2j+2h( ), K is a ( )-SK of rate (1=nk) log kKk I(X1 ^ X2) ( ), recoverable from r-interactive communication F00, which with (5.24), completes the proof. Proof of Theorem 5.3. Achievability. Consider rvs U1; :::; Ur satisfying conditions (P1)-(P3) in the statement of Theorem 5.3. It su ces to show for every 0 < < 1, for some n 1, there exists an r-interactive communication F, and -CR J recoverable from F, such that I(X1; X2 ^ U r) 1 nH(J;F) I(X1; X2 ^ U r) + ; (5.28) and 1 nH(F) I(X1; X2 ^ U r) I(X1 ^X2) + ; (5.29) since from (5.12), (5.28) and (5.29), we have 1 nI (X n 1 ^Xn2 j J;F) 1 nH(F) 1 nH(J;F) + I(X1 ^X2) + ( ) 2 + ( ): We show below that I(X1; X2 ^ U r) I(X1 ^X2) = b(r 1)=2cX i=0 I(X1 ^ U2i+1 j X2; U2i) + br=2cX i=1 I(X2 ^ U2i j X1; U2i 1): (5.30) 107 Thus, the proof will be completed upon showing that there exists an -CR J , recov- erable from F of rate 1 nH(F) b(r 1)=2cX i=0 I(X1 ^ U2i+1 j X2; U2i) + br=2cX i=1 I(X2 ^ U2i j X1; U2i 1) + ; (5.31) such that (J;F) satis es (5.28). For r = 2, such a construction was given by Ahlswede-Csisz ar [2, Theorem 4.4]. (In their construction, F was additionally a function of J .) The extension of their construction to a general r is straightforward, and is relegated to Appendix E. It remains to prove (5.30). Note that I(X1; X2 ^ U r) b(r 1)=2cX i=0 I(X1 ^ U2i+1 j X2; U2i) br=2cX i=1 I(X2 ^ U2i j X1; U2i 1) = b(r 1)=2cX i=0 I(X2 ^ U2i+1 j U2i) + br=2cX i=1 I(X1 ^ U2i j U2i 1): (5.32) Further, from conditions (P1)-(P3) it follows that b(r 1)=2cX i=0 I(X2 ^ U2i+1 j U2i) + br=2cX i=1 I(X1 ^ U2i j U2i 1) I(X2 ^X1) = b(r 1)=2cX i=1 I(X2 ^ U2i+1 j U2i) + br=2cX i=2 I(X1 ^ U2i j U2i 1) + I(X1 ^ U2 j U1) + I(X2 ^ U1) I(X2 ^X1) = b(r 1)=2cX i=1 I(X2 ^ U2i+1 j U2i) + br=2cX i=2 I(X1 ^ U2i j U2i 1) + I(X1 ^ U2 j U1) I(X1 ^X2 j U1) = b(r 1)=2cX i=1 I(X2 ^ U2i+1 j U2i) + br=2cX i=2 I(X1 ^ U2i j U2i 1) I(X1 ^X2 j U1; U2) = ::: = I(X1 ^X2 j U r) = 0: (5.33) 108 Combining (5.32) and (5.33) we get (5.30). Converse. Let R 0 be an achievable r-interactive CI rate. Then, for all 0 < < 1, for some n 1, there exists an r-interactive communication F, and -CR J recoverable from F, such that (1=n)H(J;F) R+ and L = (J;F) satis es (5.1). Let J be recovered as J1 = J1(Xn1 ;F) and J2 = J2(Xn2 ;F) by terminals 1 and 2, respectively, i.e., P (J = J1 = J2) 1 : Further, let rv T be distributed uniformly over the set f1; :::; ng. De ne rvs U r as follows: U1 = F1; XT 11 ; Xn2(T+1); T; Ui = Fi; 2 i < r; Ur = 8 >>>< >>>: (Fr; J1); r odd, (Fr; J2); r even. We complete the proof for odd r; the proof for even r can be completed similarly. It was shown by Kaspi [39, equations (3.10)-(3.13)] that U2i+1 X1T ; U2i X2T ; 0 i b(r 1)=2c; U2i X2T ; U2i 1 X1T ; 1 i br=2c: Next, note from (5.27) that + log jX1jjX2j+ h( ) 1 nI(X n 1 ^Xn2 j J1;F) 1n nX i=1 I(X1i ^Xn2 j X i 11 ; J1;F) 1n nX i=1 I(X1i ^X2i j X i 11 ; Xn2(i+1); J1;F) = I(X1T ^X2T j U r): (5.34) 109 Similarly, it holds that + log jX1jjX2j+ h( ) I(X1T ^Xn2(T+1) j XT 11 ; J1;F; T ): (5.35) The entropy rate of (J;F) is now bounded as 1 nH(J;F) 1nH(J1;F) 1 nH(J1 j J) 1nH(J1;F) log jX1jjX2j h( ) = 1nI(X n 1 ; Xn2 ^ J1;F) log jX1jjX2j h( ) = H(X1T ; X2T ) 1 nH(X n 1 j J1;F) 1 nH(X n 2 j Xn1 ; J1;F) log jX1jjX2j h( ) = H(X1T ; X2T ) H(X1T j XT 11 ; J1;F; T ) H(X2T j XT 11 ; Xn2(T+1); X1T ; Xn1(T+1); J1;F; T ) log jX1jjX2j h( ) I(X1T ; X2T ^ U r) 2 log jX1jjX2j 2h( ); where the second inequality follows from Fano?s inequality, and the last inequality follows from (5.35). Consequently, R 1nH(J;F) I(X1T ; X2T ^ U r) 2( + log jX1jjX2j+ h( )): (5.36) We now replace the rvs U1; :::; Ur with those taking values in nites sets U1; :::;Ur, re- spectively, with U1; :::;Ur satisfying the cardinality bounds in condition (iii). Similar bounds were derived in the context of interactive function computation in [42]. For 1 l r, assume that rvs U1; :::;Ul 1 satisfy the cardinality bounds. We consider odd l; the steps for even l are similar. If the rv Ul does not satisfy the cardinality bound, from the Support Lemma [18, Lemma 15.4], we can replace it with another 110 rv ~Ul that takes less than or equal to jX1j Ql 1 i=1 jUij + 1 values, while keeping the following quantities unchanged: PX1TU l 1 ; I(X1T ^X2T j U r); and I(X1T ; X2T ^ U r): Note that we have only altered PUl in the joint pmf PX1TX2TUr = PUlPX1TU l 1jUlPX2T jX1TU l 1 . Hence, the Markov relations in (P1) remain unaltered. Furthermore, PX1TX2T = PX1X2 . Finally, since the set of pmfs on a nite alphabet is compact, and the choice of above was arbitrary, it follows upon taking ! 0 in (5.34) and (5.36) that there exists U r1 satisfying (P1)-(P3) such that R I(X1; X2 ^ U r); which completes the proof. 5.4 Can interaction reduce the communication rate? It is well known that the SK capacity can be attained by using a simple one-way communication from terminal 1 to terminal 2 (or from X2 to X1). Here we derive the minimum rate RNI of such noninteractive communication using the expression for CIri (X1;X2) in (5.6). Since this expression has a double Markov structure, it can be simpli ed by the following observation (see [18, Problem 16.25]): If rvs U;X1; X2 satisfy U X1 X2; X1 U X2; (5.37) then there exist functions f = f(U) and g = g(X1) such that 111 (i) P (f(U) = g(X1)) = 1; (ii) X1 g(X1) X2. In particular, for rvs U;X1; X2 that satisfy (5.37), it follows from (i) above that I(X1; X2 ^ U) = I(X1 ^ U) I(g(X1) ^ f(U)) = H(g(X1)): Turning to (5.6), for rvs U r with r odd, the observations above applied to the rvs X1 and X2 conditioned on each realization U r 1 = ur 1 implies that there exists a function g = g (X1; U r 1) such that X1 g X1; U r 1 ; U r 1 X2; (5.38) and I (X1; X2 ^ U r) I X1; X2 ^ U r 1 +H g X1; U r 1 j U r 1 ; where rv U r 1 satis es (P1), (P3). Similar observations hold for even r. Thus, for the minimization in (5.6), conditioned on arbitrarily chosen rvs U r 1 satisfying (P1), (P3), the rv Ur is selected as a su cient statistic for X2 given the observation X1 (su cient statistic for X1 given the observation X2) when r is odd (r is even). Speci cally, for r = 1, we have CI1i (X1;X2) = minX1 g1(X1) X2 H (g1(X1)) ; (5.39) and CI1i (X2;X1) = minX2 g2(X2) X1 H (g2(X2)) : (5.40) 112 The answer to the optimization problems in (5.39) and (5.40) can be given explicitly. In fact, we specify next a minimal su cient statistic forX2 on the basis ofX1. De ne an equivalence relation on X1 as follows: x x0 , PX2jX1 (y j x) = PX2jX1 (y j x0) ; y 2 X2: (5.41) Let g 1 be the function corresponding to the equivalence classes of . We claim that g 1 is a minimal su cient statistic for X2 on the basis of X1. This expression for the minimal su cient statistic was also given in [38, Lemma 3.5(4)]. Speci cally, X1 g 1(X1) X2 since with g 1(X1) = c, say, we have PX2jg 1(X1) (y j c) = X x2X1 PX2;X1jg 1(X1) (y; x j c) = X x:g 1(x)=c PX1jg 1(X1) (x j c) PX2jX1;g 1(X1) (y j x; c) = PX2jX1;g 1(X1) (y j x; c) ; 8x with g 1(x) = c: Also, if g1(X1) satis es X1 g1(X1) X2 then g 1 is a function of g1. To see this, let g1(x) = g1(x0) = c for some x; x0 2 X1. Then, PX2jg1(X1) (y j c) = PX2jX1 (y j x) = PX2jX1 (y j x0) ; y 2 X2; so that g 1(x) = g 1(x0). Since g 1 is a minimal su cient statistic for X2 on the basis of X1, it follows from (5.39) that CI1i (X1;X2) = H (g 1(X1)) ; and similarly, with g 2(X2) de ned analogously, CI1i (X2;X1) = H (g 2(X2)) : 113 Therefore, from (5.4), the minimum rate RNI of a noninteractive communication for generating a maximum rate SK is given by RNI = min fH (g 1(X1)) ;H (g 1(X1))g I(X1 ^X2): (5.42) From the expression for RNI , it is clear that the rate of noninteractive com- munication can be reduced by replacing X1 and X2 with their respective minimal su cient statistics g 1(X1) and g 2(X2). Can the rate of communication required for generating an optimum rate SK be reduced by resorting to complex interactive communication protocols? To answer this question we must compare the expression for RNI with RSK . Speci cally, from Theorem 5.1 and the Corollary following it, interaction reduces the rate of communication i , for some r > 1, CIri (X1;X2) < min fH (g 1(X1)) ;H (g 1(X1))g ; (5.43) where g 1 and g 2 are as in (5.42); interaction does not help i CIi(X1 ^X2) = min fH (g 1(X1)) ;H (g 1(X1))g : Note that instead of comparing with CIri (X1;X2) in (5.43), we can also compare with CIri (X2;X1). We shall explore this question here, and give an example where the answer is in the a rmative. In fact, we rst show that interaction does not help in the case of BSS. Then we give an example where interaction does help. 114 5.4.1 Binary symmetric sources For BSS X1 and X2, we note a property of rvs U r that satisfy the conditions (P1)- (P3) in Theorem 5.3. Lemma 5.6. Let X1 and X2 be f0; 1g valued rvs with I(X1^X2) 6= 0. Then, for rvs U1; :::; Ur that satisfy the conditions (P1)-(P3) in Theorem 5.3, for every realization u1; :::; ur of U1; :::; Ur, one of the following holds: H(X1 j U r = ur) = 0; or H(X2 j U r = ur) = 0: (5.44) Proof. Given a sequence ur, assume that H(X1 j U r = ur) > 0 and H(X2 j U r = ur) > 0; which is equivalent to PX1jUr (1 j ur) PX1jUr (0 j ur) > 0 and PX2jUr (1 j ur) PX2jUr (0 j ur) > 0: (5.45) We consider the case when r is even; the case of odd r is handled similarly. From the Markov conditions X1 U r X2 and X1 X2; U r 1 Ur, we have PX1;X2jUr (x; y j ur) = PX1jUr (x j ur) PX2jUr (y j ur) = PX1jX2;Ur 1 x j y; ur 1 PX2jUr (y j ur) ; x; y 2 f0; 1g: Since PX2jUr (y j ur) > 0 from (5.45), we have PX1jUr (x j ur) = PX1jX2;Ur 1 x j y; ur 1 ; x; y 2 f0; 1g; 115 which further implies PX1jX2;Ur 1 x j 1; ur 1 = PX1jX2;Ur 1 x j 0; ur 1 ; x 2 f0; 1g: Hence, I(X1 ^X2 j U r 1 = ur 1) = 0. Noting from (5.45) that PX1jUr 1 1 j ur 1 PX1jUr 1 0 j ur 1 > 0; we can do the same analysis as above, again for r 1. Upon repeating this process r times we get I(X1 ^X2) = 0, which is a contradiction. Therefore, either H(X1 j U r = ur) = 0 or H(X2 j U r = ur) = 0 holds. Note that CIri (X1;X2) = H(X1; X2) maxUr H(X1; X2 j U r); where the max is taken over rvs U r as in Theorem 5.3. If H(X1 j U i = ui) = 0, it follows that I X1 ^X2 j U i = ui = 0; and H(X1; X2 j U i = ui; U ri+1) = H(X2 j U i = ui; U ri+1) H(X2 j U i = ui): (5.46) Similarly, H(X2 j U i = ui) = 0 implies I X1 ^X2 j U i = ui = 0; and H(X1; X2 j U i = ui; U ri+1) H(X1 j U i = ui): (5.47) 116 For a sequence ur with PUr (ur) > 0, let (ur) be the minimum value of i such that H(X1 j U i = ui) = 0 or H(X2 j U i = ui) = 0; if X1 and X2 are independent, (ur) = 0. Note that is a stopping-time adapted to U1; :::; Ur. Then, from (5.46), (5.47), CIri (X1;X2) remains unchanged if we restrict the support of U r to sequences ur with ui = for all i > (ur). Furthermore, the Markov condition (P1) implies that if for a sequence ur, = (ur) is odd then PX2jX1;U (y j x; u ) = PX2jX1;U 1 y j x; u 1 ; and so if PX1jU (1 j u ) PX1jU (0 j u ) > 0; it holds from the de nition of that PX2jU (1 j u ) PX2jU (0 j u ) > 0; which is a contradiction. Therefore, we have H(X1 j U = u ) = 0. Similarly, H(X2 j U = u ) = 0 holds for even . To summarize, CIri (X1;X2) = minU I (X1; X2 ^ U ) ; (5.48) where U r are rvs satisfying (P1)-(P3), and is the stopping-time de ned above. We show next that for BSS, interaction can never reduce the rate of commu- nication for optimum rate SK generation. In fact, we conjecture that for any BSS X1; X2, RNI = RSK. 117 Theorem 5.7. Let X1 and X2 be f0; 1g-valued rvs, with P (X1 = 0; X2 = 0) = P (X1 = 1; X2 = 1) = 1 2(1 ); P (X1 = 0; X2 = 1) = P (X1 = 1; X2 = 0) = 1 2 ; 0 < < 1 2 : (5.49) Then, CIi(X1 ^X2) = minfH(X1);H(X2)g; i.e., interaction does not help to reduce the communication required for optimum rate SK generation. Remark. As a consequence of Theorem 5.7, for sources with joint distribution as in (5.49), the second inequality in (5.3) can be strict. Speci cally, it was noted by Wyner (see the discussion following equation (1.19) in [77]) that for BSS, CIW (X1^ X2) < 1. From Theorem 5.7, we have CIi(X1 ^X2) = minfH(X1);H(X2)g = 1: Thus, for BSS X1 and X2, CIW (X1 ^X2) < CIi(X1 ^X2). Proof. Denote by U r0 the following set of stopped sequences in U r: For i r, for a sequence ur 2 U r the stopped sequence ui 2 U r0 if: H X1 j U j = uj > 0; H X2 j U j = uj > 0; 8 j < i; and H X1 j U i = ui = 0 or H X2 j U i = ui = 0: For i 2 f0; 1g, de ne the following subsets of U r0 : U1i = u 2 U r0 : is odd;PX1jU (i j u ) = 1 ; U2i = u 2 U r0 : is even;PX2jU (i j u ) = 1 : 118 By their de nition the sets U10 ;U11 ;U20 ; and U21 are disjoint, whereby we have PU (U r0 ) = PUr U10 [ U11 [ U20 [ U21 = 1X i=0 PUr U1i + PUr U2i = 1: (5.50) For u 2 U r0 , denote by p(u ) the probability PU (u ). Further, for u 2 U10 SU11 , denote by W u : X1 ! X2 the stochastic matrix corresponding to PX2jX1;U ( j ; u ), and for u 2 U20 SU21 , denote by T u : X2 ! X1 the stochastic matrix corresponding to PX1jX2;U ( j ; u ). With this notation, the following holds: 1 2(1 ) = PX1;X2 (i; i) = X u 2U1i p(u )W u (i j i) + X u 2U2i p(u )T u (i j i); i 2 f0; 1g; (5.51) since the sets U10 ;U11 ;U20 ;U21 are disjoint. Upon adding (5.51) for i = 0; 1, we get 1X i=0 2 4 X u 2U1i p(u )W u (i j i) + X u 2U2i p(u )T u (i j i) 3 5 = (1 ): Furthermore, from (5.50) we get 1 = 1X i=0 X u 2U1i p(u ) + X u 2U2i p(u ): Therefore, since the function g(z) = z log z is concave for 0 < z < 1, the Jensen?s inequality yields g(1 ) 1X i=0 X u 2U1i p(u )g W u (i j i) + X u 2U2i p(u )g T u (i j i) (5.52) Similarly, using for i 6= j; i; j 2 f0; 1g, 1 2 = PX1;X2 (i; j) = X u 2U1i p(u ) 1 W u (i j i) + X u 2U2j p(u ) 1 T u (j j j) ; 119 we get g( ) 1X i=0 X u 2U1i p(u )g 1 W u (i j i) + X u 2U2i p(u )g 1 T u (i j i) (5.53) On adding (5.52) and (5.53) we get h( ) = g( ) + g(1 ) 1X i=0 X u 2U1i p(u )h W u (i j i) + X u 2U2i p(u )h T u (i j i) : Note that the right-side above equals H(X1; X2 j U ), which yields h( ) = maxfH(X1 j X2);H(X2 j X1)g H(X1; X2 j U ): Since rvs U r above were arbitrary, we have from (5.48), CIri (X1;X2) H(X1; X2) maxfH(X1 j X2);H(X2 j X1)g = minfH(X1);H(X2)g: Combining this with (5.3), we obtain CIri (X1;X2) = minfH(X1);H(X2)g: 5.4.2 An example where interaction does help Consider rvs X1 and X2 with X1 = X2 = f0; 1; 2g, and with joint pmf: 2 6666664 a a a b a a a c a 3 7777775 ; 120 where a; b; c are nonnegative, 7a+ b+ c = 1, and c 6= a, which holds i b 6= 1 8a. Assume that 2a > b > a: (5.54) From (5.43), to show that interaction helps, it su ces to nd rvs U1; :::; Ur satisfying (P1)-(P3) such that I (X1; X2 ^ U1; :::; Ur) < min fH (g 1(X1)) ;H (g 2(X2))g ; (5.55) where g 1 and g 2 are as in (5.42). From (5.41), g 1(x) = g 1(x0) i PX2;X1 (y; x) PX2;X1 (y; x0) = PX1 (x)PX1 (x0) ; y 2 X2; (5.56) i.e., the ratio PX2;X1 (y;x)PX2;X1 (y;x0) does not depend on y. Therefore, for the pmf above, g 1(X1) and g 2(X2) are equivalent to X1 and X2, respectively. Thus, min fH (g 1(X1)) ;H (g 2(X2))g = minfH(X1);H(X2)g; where H(X1) = H(X2) for the given pmf. Next, let U1 = f1(X1), U2 = f2(X2; f1(X1)), where f1 and f2 are given below: f1(x) = 8 >>>< >>>: 1; x = 2; 2; x = 0; 1; f2(y; 1) = 0;8 y 2 f0; 1; 2g; and f2(y; 2) = 8 >>>< >>>: 1; y = 0; 2; y = 1; 2: Clearly, U1 and U2 satisfy (P1) and (P2). For (P3), note that if (U1; U2) = (1; 0), then X1 = 2, and if (U1; U2) = (2; 1), then X2 = 0. Finally, if (U1; U2) = (2; 2), then 121 X1 2 f0; 1g and X2 2 f1; 2g, implying PX1;X2jU1;U2 (x; y j 2; 2) = PX1;X2 (x; y) 4a = 14 ; 8 (x; y) 2 f0; 1g f1; 2g: Therefore, I(X1 ^X2 j U1; U2) = 0, and so U1; U2 satisfy (P3). We show that (5.55) holds for this choice of U1; U2. Speci cally, I (X1; X2 ^ U1; U2) = H (U1; U2), and the following holds: H(X2) H (U1; U2) = H(X1) H (U1; U2) = H (X1jU1) H (U2jU1) = P (f1(X1) = 2) H (X1jf1(X1) = 2) H (f2(2; X2)jf1(X1) = 2) = (5a+ b) h PX1jf1(X1) (0j2) h PX2jf1(X1) (0j2) = (5a+ b) h 3a 5a+ b h a+ b 5a+ b : Then, from (5.54), a+ b 5a+ b < 3a 5a+ b < 1 2 ; which implies (5.55) for U1; U2. 5.5 Interactive common information and su cient statistics In Chapter 2, we saw that several CI quantities remain unchanged if X1 and X2 are replaced, respectively, with their su cient statistics (for the other). This is true even for the interactive CI. 122 Theorem 5.8. For rvs X1 and X2, let functions g1 of X1 and g2 of X2 be such that X1 g1(X1) X2 and X1 g2(X2) X2. Then the following relations hold: CIri (X1;X2) = CIri (g1(X1); g2(X2)) ; r 1; CIi(X1 ^X2) = CIi (g1(X1) ^ g2(X2)) : Remark. (i) Theorem 5.8 implies that the minimum rate of communication for gen- erating a maximum rate SK remains unchanged if X1 and X2 are replaced by g1(X1) and g2(X2) as above, respectively. (ii) Note that g1(X1) and g2(X2) above are, respectively, functions of g 1(X1) and g 2(X2) de ned through (5.41). Proof. First note that I(X1 ^X2) = I (g1(X1) ^X2) = I (g1(X1) ^ g2(X2)) : (5.57) Proof. . From (5.57), any protocol that generates an optimum rate SK for the sources g1(X1) and g2(X2) also generates an optimum rate SK for the sources X1 and X2. Thus, the minimum communication rate for prior protocols is bounded below by the minimum communication rate for the latter protocols, so that by Theorem 5.1, CIri (g1(X1); g2(X2)) I (g1(X1) ^ g2(X2)) CIri (X1;X2) I (X1 ^X2) ; which, by (5.57), is CIri (g1(X1); g2(X2)) CIri (X1;X2) : (5.58) 123 In fact, (5.58) holds with equality: We claim that any choice of rvs U r that satisfy (P1)-(P3) also satisfy the following Markov relations: U2i+1 g1(X1); U2i g2(X2); 0 i b(r 1)=2c; U2i g2(X2); U2i 1 g1(X1); 1 i br=2c; g1(X1) U r g2(X2): (5.59) It follows that CIri (g1(X1); g2(X2)) I (g1(X1); g2(X2) ^ U r) I (X1; X2 ^ U r) ; (5.60) and consequently, CIri (g1(X1); g2(X2)) CIri (X1;X2) : Thus, by (5.58), CIri (g1(X1); g2(X2)) = CIri (X1;X2) : (5.61) Taking the limit r !1 we get CIi (g1(X1) ^ g2(X2)) = CIi (X1 ^X2) : It remains to establish (5.59); instead, using induction we establish the following stronger Markov relations: For 1 i r, Ui g1(X1); U i 1 X2; i odd; Ui g2(X2); U i 1 X1; i even; X1 g1(X1); U i X2 and X1 g2(X2); U i X2: (5.62) 124 Clearly, (5.62) implies the rst two Markov relations in (5.59). The last Markov chain in (5.59) follows upon observing 0 = I (X1 ^X2 j U r) I (g1(X1) ^ g2(X2) j U r) : To see that (5.62) holds for i = 1 note that I (X1 ^X2 j g1(X1); U1) I (X1 ^X2 j g1(X1)) + I (U1 ^X2 j g1(X1); X1) = 0; and I (X1 ^X2 j g2(X2); U1) I (X1 ^X2 j g2(X2)) + I (U1 ^X2; g2(X2) j X1) = 0: Next, assume that (5.62) holds for an even i. Then, from (P1) we get: I X2 ^ Ui+1 j X1; U i = 0 ,I X2 ^ Ui+1 j X1; g1(X1); U i = 0 ,I X2 ^X1; Ui+1 j g1(X1); U i = I X2 ^X1 j g1(X1); U i = 0; where the last equality follows from (5.62). From the last inequality above we have Ui+1 g1(X1); U i X2 and X1 g1(X1); U i+1 X2: Furthermore, it also follows from (5.62) that I X1 ^X2 j g2(X2); U i+1 I X1; Ui+1 ^X2 j g2(X2); U i = I Ui+1 ^X2 j g2(X2); X1; U i I Ui+1 ^X2 j X1; U i = 0; where the last equality follows from (P1). Thus, we have X1 g2(X2); U i+1 X2; 125 establishing the validity of (5.62) for i+ 1. The proof of (5.59) can be completed by induction by using a similar argument for odd i. 5.6 Discussion 5.6.1 Local randomization Although independent local randomization was not allowed in our formulation, our main result characterizing RSK holds even when such randomization is available. Consider a model where terminals 1 and 2, in additional to their respective obser- vations Xn1 and Xn2 , have access to nite-valued1 rvs T1 and T2, respectively. The rvs T1, T2, and (Xn1 ; Xn2 ) are mutually independent. The SK capacity is de ned as before, with Xn1 and Xn2 now replaced by (Xn1 ; T1) and (Xn2 ; T2), respectively. It is known [48, 2] that even with randomization the SK capacity equals I(X1 ^X2). For this model, denote the minimum rate of r-interactive communication required to generate an SK of rate I(X1 ^X2) by ~RrSK . Lemma 5.9. For r 1, ~RrSK = RrSK : To see this, we de ne quantities ~RrCI and ~CI r i analogously to RrSK and CIri , with Xn1 and Xn2 replaced by (Xn1 ; T1) and (Xn2 ; T2), respectively. Note that this substitution is made even in condition (5.1), i.e., the CR J and the communication 1The cardinalities of the range spaces of T1 and T2 are allowed to be at most exponential in n. 126 F now are required to satisfy: 1 nI (X n 1 ; T1 ^Xn2 ; T2 j J;F) : (5.63) We observe that (5.8) still holds, with (Xn1 ; T1) and (Xn2 ; T2) replacing, respectively, Xn1 and Xn2 on the right-side. Therefore, the proof of Theorem 5.1 is valid, and we get: ~RrCI = ~RrSK = ~CI r i I(X1 ^X2): (5.64) By its de nition ~RrCI RrCI , since L = (J;F) = L(Xn1 ; Xn2 ) satisfying (5.1) will meet (5.63) as well. We claim that ~RrCI RrCI , which by (5.64) and Theorem 5.1 implies Lemma 5.9. Indeed, consider CR J recoverable from F such that (J;F) attain ~RrCI . Then, the condition (5.63) gives 1 nI (X n 1 ^Xn2 j J;F; T1; T2) 0: So, there exist t1; t2 such that conditioned on T1 = t1; T2 = t2 the CR J is still recoverable from F, and 1 nI (X n 1 ^Xn2 j J;F; T1 = t1; T2 = t2) 0: Thus, with T1 = t1; T2 = t2 xed, (J;F) constitutes a feasible choice in the de nition of RrCI . Since the number of values taken by F can only decrease upon xing T1 = t1; T2 = t2, we get ~RrCI RrCI . Therefore, the availability of local randomization does not decrease the rate of communication required for generating an optimum rate SK. 127 5.6.2 Less-than-optimum rate secret keys SK generation is linked intrinsically to the e cient generation of CR. For 0, a rate R 0 is an achievable CR rate for if for every 0 < < 1 there exists, for some n 1, an -CR L with 1 nH(L) R ; recoverable from an r-interactive communication F, for arbitrary r, of rate 1 nH(F) + ; the maximum achievable CR rate for is denoted by CR( ). Similarly, denote by C( ) the maximum rate of an SK that can be generated using a communication as above. It can be shown in a straightforward manner that C( ) = CR( ) : (5.65) The graph of CR as a function of is plotted in Fig. 5.1. CR( ) is an increasing and a concave function of , as seen from a simple time-sharing argument. Since RSK is the minimum rate of communication required to generate a maximum rate SK, CR( ) = I(X1 ^X2) for RSK . Thus, our results characterize the graph of CR( ) for all RSK . The quantity RSK is the minimum value of for which the slope of CR( ) is 1; CR (RSK) is equal to the interactive CI CIi(X1 ^ X2). Furthermore, from the proof of Theorem 5.1, a CR L that satis es (5.1) must yield an optimum rate SK. Thus, any CR recoverable from a communication of rate less than RSK cannot satisfy (5.1). A characterization of CR( ) for < RSK is central 128 I(X ? Y ) I(X ? Y ) RSK H(X|Y ) +H(Y |X) H(X,Y ) CR(?) ?min{H(X|Y ), H(Y |X)} min{H(X), H(Y )} CIi(X ? Y ) Figure 5.1: Minimum rate of communication RSK for optimum rate SK generation to the characterization of C( ), and this, along with a single-letter characterization of RSK , is an open problem. We close this chapter by remarking that an extension of the results of this chapter to the case of multiple terminals is not known. In particular, an appropriate notion of interactive CI for multiple terminals, with connections to the minimal communication for optimum rate SK generation, is unavailable. The identi cation of such a notion of multiterminal interactive CI will lead to a characterization of the CR underlying optimum rate SK generation for multiple terminals and shed light on the structure of such SKs; it remains an interesting open problem. 129 CHAPTER 6 Querying Common Randomness 6.1 Synopsis A set of m terminals, observing correlated signals, communicate interactively to generate common randomness for a given subset of them. Knowing only the com- munication, how many direct queries of the value of the common randomness will resolve it? A general upper bound, valid for arbitrary signal alphabets, is developed for the number of such queries by using a query strategy that applies to all com- mon randomness and associated communication. When the underlying signals are i.i.d. repetitions of m correlated random variables, the number of queries can be exponential in signal length. For this case, the mentioned upper bound is tight and leads to a single-letter formula for the largest query exponent, which coincides with the secret key capacity of a corresponding multiterminal source model. In fact, the upper bound constitutes a strong converse for the optimum query exponent, and implies also a new strong converse for secret key capacity. The problem formulation and our main result characterizing the optimum query exponent are given in the next section. Simple and essential technical tools are presented in Section 6.3. Achievability is proved in Section 6.4. The less com- 130 plex converse proof for the case A = f1; :::;mg is given in Section 6.5. However, this proof does not extend to an arbitrary A f1; :::;mg, for which a di erent converse is provided in Section 6.6. Section 6.7 contains the strong converse result for SK capacity. A converse for the optimum query exponent for rvs with arbitrary alphabets is proved in Section 6.8, with jointly Gaussian rvs as a special case. The results of this chapter were reported in [66, 65]. 6.2 Main result: How many queries will resolve common randomness? Consider the multiterminal source model of Section 2.2. The terminals communicate interactively with each other over a public communication network, as described in De nition 2.1, in order to generation a CR (see De nition 2.2). For simplicity, we do not allow independent local randomization UM. However, our results do not change if such randomization is allowed; see Section 6.9. A querier observing the communication F wants to resolve the value of this CR L by asking questions of the form \Is L = l?" with yes-no answers. While queries of this form have been termed \guessing" [47, 4, 5, 34], we use the terminology \query" since our approach covers a broader class of query strategies; see Section 6.9. De nition 6.1. For rvs U; V with values in the sets U ;V , a query strategy q for U given V = v is a bijection q( jv) : U ! f1; :::; jUjg, where the querier, upon observing V = v, asks the question \Is U = u?" in the q(ujv)th query. Thus, a query strategy q for resolving a CR L on the basis of an observed 131 communication F = i is an ordering of the possible values of L. The terminals seek to generate a CR L for A using communication F so as to make the task of the querier observing F as onerous as possible. For instance, if L were to be independent of F, then the querier necessarily must search exhaustively over the set of possible values of L, which can be exponentially large (in n). De nition 6.2. Given 0 < < 1, a query exponent E > 0 is -achievable if for every 0 < 0 < 1, there exists an -CR L = L(n) (XnM) for A M from communication F = F (XnM) such that for every query strategy q for L given F, P q(L j F) exp(nE) > 1 0; (6.1) for all n N( ; 0). The -optimum query exponent, denoted E ( ), is the supremum of all -achievable query exponents; E ( ) is nondecreasing in . The optimum query exponent E is the in mum of E ( ) for 0 < < 1, i.e., E = lim !0 E ( ): Remark. Clearly, 0 E log jXMj. Condition (6.1) forces any query strategy adopted by the querier to have an ex- ponential complexity (in n) with large probability; E is the largest value of the exponent that can be in icted on the querier. Our main result is a single-letter characterization of the optimum query expo- nent E . Theorem 6.1. The optimum query exponent E equals E = E ( ) = H (XM) max 2 (A) X B2B BH (XB j XBc) ; 0 < < 1: (6.2) 132 Remarkably, the value of E coincides with the SK capacity of a multiterminal source model; see (2.12). In fact, the achievability proof of Theorem 6.1 is straight- forward and employs, in e ect, an SK in forming an appropriate CR L. We show that for such a CR L, any query strategy is tantamount to an exhaustive search over the set of values of the SK, a feature that is apparent for a \perfect" SK with I(K ^ F) = 0. The di cult step in the proof of Theorem 6.1 is the converse part which involves an appropriate query strategy, for arbitrary L and F, that limits the incurred query exponents. Our strong converse yields a uniform upper bound for E ( ), 0 < < 1. We shall see that while the expression for E in (6.2) lends itself to the achiev- ability proof of Theorem 6.1 in Section 6.4, alternative forms are suited better for the converse proof. Using the alternative form in (2.14), the expression (6.2) can be written also as E = min 2 (A) "X B2B BH (XBc) ( sum 1)H (XM) # ; (6.3) which is used in the converse proof for an arbitrary A M in Section 6.6. The converse proof for the case A =M is facilitated by the further simpli cation pointed out in (2.15). 6.3 Technical tools The following simple observation relates the number of queries in a query strategy q to the cardinality of an associated set. 133 Proposition 6.2. Let q be a query strategy for U given V = v, v 2 V. Then, jfu 2 U : q(ujv) gj : Proof. The claim is straightforward since q( jv) is a bijection. For rvs U; V , nding a lower bound for q(U jV ) involves nding a suitable upper bound for the conditional probabilities PU jV ( j ). This idea is formalized by the following lemma. Lemma 6.3. Given > 0 and 0 < < 1=2, let the rvs U; V , satisfy P (u; v) : PU jV (ujv) 1 : (6.4) Then for every query strategy q for U given V , P (q(U jV ) ) 1 0; (6.5) for all 0 2 . Conversely, if (6.5) holds for every query strategy q for U given V , with 0 < 0 (1 p )2, then P (u; v) : PU jV (ujv) 1 : (6.6) Proof. Suppose (6.4) holds but not (6.5). Then there exists q with P (q(U jV ) < ) > 0: (6.7) From (6.4) and (6.7) P (u; v) : PU jV (ujv) ; q(ujv) < > 1 + 0 1 = 0 : (6.8) 134 On the other hand, the left side of (6.8) equals X v PV (v) X u:q(ujv)< ; PUjV (ujv) PU jV (ujv) : ; by Proposition 6.2 = ; which contradicts (6.8) since 0 2 . For the converse, suppose that (6.6) does not hold; then, we show that a query strategy q0 exists which violates (6.5) when 0 < 0 (1 p )2. The negation of (6.6) is P (u; v) : PU jV (ujv) > 1 > 1 ; which, by a reverse Markov inequality1 [41, p. 157] (see also [26, p. 153]), gives a set V0 V with PV (V0) > 1 p ; (6.9) and PU jV (u : PU jV (ujv) > 1 v > 1 p ; v 2 V0: (6.10) Denoting by Uv the set f g in (6.10), we have 1 PU jV (Uv j v) > jUvj ; 1The reverse Markov inequality states that for rvs U; V with P ((U; V ) 2 S) 1 for some S U V, there exists V0 V such that P ((U; V ) 2 S j V = v) 1 p , v 2 V0, and P (V 2 V0) 1 p . 135 so that jUvj < ; v 2 V0: (6.11) For each v 2 V0, order the elements of U arbitrarily but with the rst jUvj elements being from Uv. This ordering de nes a query strategy q0( jv), v 2 V0; for v =2 V0, let q0( jv) be de ned arbitrarily. Then for v 2 V0, u 2 Uv, q0(ujv) < by (6.11), so that P (q0(U jV ) < ) X v2V0 X u2Uv PU;V (u; v) > (1 p )2; (6.12) by (6.9) and (6.10). So, q = q0 violates (6.5) when 0 (1 p )2. Finally, the following simple observation will be useful. Proposition 6.4. For pmfs Q1; Q2, on V, Q1 (fv : Q1(v) Q2(v)g) 1 ; 0 < < 1: Proof. The claim follows from X v2V:Q1(v)< Q2(v) Q1(v) < X v2V:Q1(v)< Q2(v) Q2(v) : 136 6.4 Proof of achievability Denoting the right-side of (6.2) by C, we claim, for 0 < < 1, 0 < < 1=2, > 0, the existence of an -CR L = XnM for A from F with P (xnM; i) : PLjF (xnM j i) exp [ n(C )] 1 ; (6.13) for all n su ciently large. Then the assertion of the theorem follows by applying the rst part of Lemma 6.3 with U = L, V = F; = exp[n(C )], to conclude from (6.5) that E ( ) C; since > 0 was chosen arbitrarily. Turning to the mentioned claim, it is shown in [20, Proposition 1], [21, Theo- rem 3.1] that there exists communication F such that L = XnM is -CR for A from F with 1 n log kFk max 2 (A) X B2B BH (XB j XBc) + 3 ; (6.14) for all n su ciently large. Using Proposition 6.4 with Q1 = PF and Q2 being the uniform pmf over the range of F, we get PF i : PF (i) 2kFk 1 2 : (6.15) Also, for xnM in the set Tn of PXM-typical sequences with constant [18, De nition 2.8], we have PXnM (x n M) exp n H (XM) 3 (6.16) 137 and PXnM (Tn) 1 2 ; for all n su ciently large. Denoting by I0 the set on the left-side of (6.15), it follows that P (XnM 2 Tn;F 2 I0) 1 : (6.17) The claim results from (6.15)-(6.17) upon observing that for (xnM; i) 2 T n I0, PXnMjF (x n M j i) = PXnM ((xnM)) 1 (F (xnM) = i) PF (i) 2 exp n H (XM) 3 kFk exp[ n(C )]; for all n large enough, where the last inequality is by (6.14). Remark. The achievability proof brings out a connection between a large probability uniform upper bound for PL, the size kFk of the communication F, and the associated number of queries needed. Loosely speaking, the number of queries is approximately 1kFk , which reduces to kLk kFk if L is nearly uniformly distributed. 6.5 Proof of converse for A =M Recalling the expression for E in (2.15), given a partition of M with j j = k, 2 k m, we observe that for a consolidated source model with k sources and underlying rvs Y1; :::; Yk where2 Yi = X i , the -optimum query exponent E ( ) can be no smaller than E ( ) (since the terminals in each i coalesce, in e ect). 2 For speci city, the elements in each i are arranged in increasing order. 138 Theorem 6.5. For every partition of M with j j = k, E ( ) 1 k 1D PY1;:::;Ykk kY i=1 PYi ; 0 < < 1; and so E ( ) min E ( ) min 1 j j 1D PXMk j jY i=1 PX i : Theorem 6.5 establishes, in view of (2.15), the converse part of Theorem 6.1 when A =M. The proof of Theorem 6.5 relies on the following general result, which holds for queries of CR generated in a multiterminal source model with underlying rvs Y1; :::; Yk for n = 1. Theorem 6.6. Let L = L (Y1; :::; Yk) be -CR for f1; :::; kg from interactive com- munication F = F (Y1; :::; Yk), 0 < < 1. Given > 0 such that + p + < 1, let be such that P ( (y1; :::; yk) : PY1;:::;Yk (y1; :::; yk)Qk i=1 PYi (yi) )! 1 : (6.18) Then, there exists a query strategy q0 for L given F such that P q0(L j F) 2 1 k 1 ! (1 p + )2: (6.19) Proof of Theorem 6.5. We apply Theorem 6.6 to n i.i.d. repetitions of the rvs Y1; :::; Yk. Denoting by T 0n the set of PY1;:::;Yk-typical sequences with constant , we have PY n1 ;:::;Y nk (T 0 n) 1 ; 139 and for (yn1 ; :::; ynk ) 2 T 0n, PY n1 ;:::;Y nk (y n 1 ; :::; ynk )Qk i=1 PY ni (yni ) exp n kX i=1 H (Yi) H (Y1; :::; Yk) + = exp n D PY1;:::;Ykk kY i=1 PYi + ; for all n large enough. Thus, the hypothesis of Theorem 6.6 holds with = n = exp n D PY1;:::;Ykk kY i=1 PYi + : If E is an -achievable query exponent (see De nition 6.2), then there exists an -CR L = L (Y n1 ; :::; Y nk ) from communication F = F (Y n1 ; :::; Y nk ) such that (6.1) holds for the query strategy q0 of Theorem 6.6 for this choice of L and F. In particular for 0 < (1 p + )2, we get from (6.19) and (6.1) that P exp(nE) q0(L j F) 2=(k 1) exp " n 1 k 1D PY1;:::;Ykk kY i=1 PYi + k 1 !#! (1 p + )2 0 > 0; (6.20) for all n su ciently large. It follows that E 1k 1D PY1;:::;Ykk kY i=1 PYi + 2 k 1 : Since E was any -achievable query exponent and > 0 was chosen arbitrarily, the assertion of Theorem 6.5 is established. Proof of Theorem 6.6. Denote by L the set of values of the CR L. Using the hypothesis (6.18) of the Theorem, we shall show below the existence of a set Io of 140 values of F and associated sets L(i) L, i 2 I0, such that for every i 2 I0 PLjF (L(i) j i) 1 p + ; (6.21) jL(i)j 2 1 k 1 ; (6.22) and PF (I0) 1 p + : (6.23) Then, we consider a query strategy q0 for L given F as in the proof of converse part of Lemma 6.3, with L; F; I0; L(i) in the roles of U; V; V0; Uv, respectively. Thus, for all i 2 I0, l 2 L(i), q0(l j i) jL(i)j 2 1 k 1 ; and so, as in (6.12), we get by (6.21)-(6.23), P q0(L j F) 2 1 k 1 ! (1 p + )2; thereby establishing the assertion (6.19). The existence of the sets I0 and fL(i); i 2 I0g satisfying (6.21)-(6.23) is argued in three steps below. Step 1. First, we note the following simple property of interactive communication: if rvs Y1; :::; Yk are mutually independent, they remain mutually independent when conditioned on an interactive communication F. Lemma 6.7. Let the pmf ~PY1;:::;Yk be such that ~PY1;:::;Yk = kY j=1 ~PYj : (6.24) Then, for i = F (y1; :::; yk), we have ~PY1;:::;YkjF (y1; :::; yk j i) = kY j=1 ~PYj jF (yj j i) : (6.25) 141 Proof. The proof follows upon observing that I~P (Yj ^ Y1; :::; Yj 1; Yj+1; :::; Yk j F) I~P (Yj ^ Y1; :::; Yj 1; Yj+1; :::; Yk) = 0; j = 1; :::; k; (6.26) where the rst inequality is by [1, Lemma 2.2] upon choosing U = Yj, V = (Y1; :::; Yj 1; Yj+1; :::; Yk), to be the communication from terminal j, and to be the communication from the remaining terminals. Hereafter in this proof, we shall select ~PYj = PYj ; j = 1; :::; k: (6.27) Step 2. In this step, we select the aforementioned set of communication values I0. Let Lj = Lj (Yj;F) denote an estimate of CR L at terminal j, j = 1; :::; k (see De nition 2.2). Denote by T0 the set f g on the left side of (6.18). For each realization (l; i) of (L;F), denote by Al;i Y1 ::: Yk the set Al;i = T0 \ f(y1; :::; yk) : F (y1; :::; yk) = i; Lj (yj; i) = L (y1; :::; yk) = l; j = 1; :::; kg : (6.28) Since L is -CR from F, we have from (2.1) and (6.18) that P ((Y1; :::; Yk) 2 AL;F) 1 : By a reverse Markov inequality, there exists a set I1 of values of F with PF (I1) 1 p + ; (6.29) and P ((Y1; :::; Yk) 2 AL;F j F = i) 1 p + ; i 2 I1: (6.30) 142 Next, denote by I2 the set of values of F such that ~PF (i) PF (i) ; i 2 I2; (6.31) where ~PF is, as usual, the distribution of F under ~P. From Proposition 6.4 with Q1 = PF, Q2 = ~PF, we have PF (I2) 1 : (6.32) Thus, by (6.29) and (6.32), I0 , I1 \ I2 satis es (6.23). Step 3. In this step, we identify sets L(i) that satisfy (6.21) and (6.22). For each i 2 I0, the sets Al;i corresponding to di erent values l are disjoint. Upon de ning the nonnegative measure3 on L for each i 2 I0 by (l) , PY1;:::;YkjF (Al;i j i) ; l 2 L; (6.33) we get (L) = X l2L PY1;:::;YkjF (Al;i j i) = P ((Y1; :::; Yk) 2 AL;i j F = i) 1 p + ; by (6.30). Applying Lemma 2.8 (i) with L in the role of U , we set L(i) = U , and so (L(i)) (L) 1 p + (6.34) 3Although depends on i, our notation will suppress this dependence. 143 and jL(i)j =(1 ) exp (H ( )) ; 0 < 1: (6.35) It follows from (6.34) that PLjF (L(i) j i) X l2L(i) PY1;:::;YkjF (Al;i j i) = (L(i)) 1 p + ; (6.36) which establishes (6.21). Finally, we obtain an upper bound on exp (H ( )) for = 1k , which will lead to (6.22). Denote by Ajl;i Yj the projection of the set Al;i Y1 ::: Yk along the jth coordinate, j = 1; :::; k. The sets Ajl;i are disjoint for di erent values of l, by de nition (see (6.28)). Thus, for the pmf ~PY1;::;Yk in (6.24), (6.27), we have 1 kY j=1 "X l2L ~PYj jF Ajl;i j i # "X l2L kY j=1 ~PYj jF Ajl;i j i 1 k !#k ; (6.37) where the last step follows from H older?s inequality4 [35, Section 2.7]. Using (6.25), the right-side of (6.37) is the same as "X l2L ~PY1;:::;YkjF A1l;i ::: Akl;i j i 1 k #k ; which is bounded below by "X l2L ~PY1;:::;YkjF (Al;i j i) 1 k #k ; (6.38) 4See [71, equation (33)] for an early use of H older?s inequality in a CR converse proof. 144 since Al;i A1l;i ::: Akl;i: (6.39) Upon noting that Al;i T0, for all (y1; :::; yk) 2 Al;i, it follows that ~PY1;:::;YkjF (y1; :::; yk j i) = ~PY1;:::;Yk (y1; :::; yk) ~PF (i) = Qk j=1 ~PYj (yj) ~PF (i) = Qk j=1 PYj (yj) ~PF (i) PY1;:::;Yk (y1; :::; yk) ~PF (i) PY1;:::;YkjF (y1; :::; yk j i) 1 ; where the third equality and the subsequent inequalities are by (6.27), (6.18) and (6.31), respectively. Combining the observations above with (6.37) and (6.38), we get 1 "X l2L PY1;:::;YkjF (Al;i j i) 1 1 k #k ; = "X l2L (l) 1k #k ; which, recalling De nition 2.6, further yields exp H 1 k ( ) = "X l2L (l) 1k # k k 1 1 k 1 : The previous bound, along with (6.35), gives (6.22). 145 6.6 Proof of converse for arbitrary A M The converse technique of the previous section for A = M can be extended to an arbitrary A M, yielding an analogous upper bound for E ( ) in terms of divergences. However, the resulting upper bound is inadequate as it is known to exceed the expression in the right-side of (6.3) (see [10]). In this section, we develop a new converse technique that targets directly the latter. The main steps of the general converse proof for the caseA M are analogous to those in the previous section. The central step is the counterpart of Theorem 6.6, which is given next. Given a fractional partition as in (2.11), its dual partition is = ( ) = Bc ; B 2 B with Bc = B sum 1 ; B 2 B; (6.40) where B is de ned in (2.10) and sum is given by (2.13). It is known from [46], and can be seen also from (2.11) and (2.13), that X B2B:Bc3i Bc = 1 sum 1 X B2B:Bc3i B = 1 sum 1 "X B2B B X B2B:B3i B # = 1 sum 1 [ sum 1] = 1; i 2M; (6.41) so that , too, is a fractional partition of M. Theorem 6.8. Let L = L (Y1; :::; Ym) be -CR for A from interactive communication F = F (Y1; :::; Ym), 0 < < 1. Given > 0 such that + p + < 1 and a fractional 146 partition 2 (A), let Bc ; B 2 B, and 0 be such that P yM : PYM (yM) 1 0 ; PYBc (yBc) 1 Bc ; B 2 B 1 : (6.42) Then, with = Y B2B BcBc 0 ; (6.43) there exists a query strategy q0 for L given F such that P q0(L j F) ( ) sum 1! (1 p + )2; (6.44) where ( ) = (m2m) m m+1. Proof. As in the proof of Theorem 6.6, the assertion (6.44) will follow upon showing the existence of sets I0 and L(i) L, i 2 I0, such that (6.21) and (6.23) are satis ed, along with the following replacement for (6.22): jL(i)j ( ) sum 1 ; i 2 I0: (6.45) To this end, we provide here appropriate replacements for the three steps in the proof of Theorem 6.6. Step 1. For each B (M, consider the pmf ~PBYM de ned by ~PBYM (yM) = PYB (yB) PYBc (yBc) (6.46) Note that ~PB ~PBc . The collection of pmfs n ~PBc ; B 2 B o serve as a replacement for the pmf ~P in (6.24). For the pmf ~PB in (6.46), we note that I~PB (YB ^ Fkj j kj) = 0; j 2 Bc; (6.47) 147 since Fkj = fkj (Yj; kj) and YBc is independent of YB conditioned on kj. The following Lemma serves the role of Lemma 6.7. Lemma 6.9. For B (M and i = F (yM), we have ~PBYB jF (yB j i) = PYB (yB)Qr k=1 Q j2B ~PBFkj j kj ikj j i kj ; (6.48) where i kj denotes the past values of communication in i for round k and terminal j. Proof. Note that ~PBYB jF (yB j i) = ~PBFjYB (i j yB) ~PBYB (yB) ~PBF (i) = ~PBFjYB (i j yB) PYB (yB) ~PBF (i) ; (6.49) where the previous step is by (6.46). Furthermore, ~PBFjYB (i j yB) = rY k=1 mY j=1 ~PBFkj jYB ; kj ikj j yB; i kj = rY k=1 Y j2Bc ~PBFkj jYB ; kj ikj j yB; i kj = rY k=1 Y j2Bc ~PBFkj j kj ikj j i kj ; (6.50) where the last step uses (6.47). Next, ~PBF (i) = rY k=1 mY j=1 ~PBFkj j kj ikj j i kj = rY k=1 Y j2B ~PBFkj j kj ikj j i kj Y j2Bc ~PBFkj j kj ikj j i kj ! : (6.51) Then (6.49), along with (6.50) and (6.51), gives (6.48). Step 2. Denoting by T0 the set f g on the left-side of (6.42), for each L = l;F = i, de ne Al;i = T0 \ fyM : F (yM) = i; Lj (yj; i) = L (yM) = l; j 2 Ag : (6.52) 148 Analogous to the proof of Theorem 6.6, the set I1 of values of F with P (YM 2 AL;F j F = i) 1 p + ; i 2 I1; satis es PF (I1) 1 p + : For j 2M and B (M, denote by Ij;B the set of i such that (m2m) 1 rY k=1 ~PBFkj j kj ikj j i kj rY k=1 PFkj j kj ikj j i kj : (6.53) The following simple extension of Proposition 6.4 holds: PF Icj;B = X i2Icj;B PF (i) = X i2Icj;B mY l=1 rY k=1 PFklj kl ikl j i kl = X i2Icj;B Y l 6=j rY k=1 PFklj kl ikl j i kl ! rY k=1 PFkj j kj ikj j i kj < (m2m) 1 X i2Icj;B Y l 6=j rY k=1 PFklj kl ikl j i kl ! rY k=1 ~PBFkj j kj ikj j i kj (m2m) 1 X i Y l 6=j rY k=1 PFklj kl ikl j i kl ! rY k=1 ~PBFkj j kj ikj j i kj = (m2m) 1 ; (6.54) where the rst inequality is by (6.53), and (6.54) holds since the summand is a pmf for F, as can be seen by directly computing the sum. De ning I2 = m\ j=1 \ B(M Ij;B, we get PF (I2) 1 : 149 The set I0 is de ned as I1 \ I2, and satis es (6.23). Step 3. Finally, we de ne sets L(i) L, i 2 I0 that satisfy (6.21) and (6.45). For each i 2 I0, let (l) = PYMjF (Al;i j i) ; l 2 L: (6.55) Then, the sets L(i) satisfying (6.21) are obtained by an application of Lemma 2.8 (i) as in (6.34) and (6.35) above. The condition (6.45) will be obtained upon showing that for = sum 1 sum ; (6.56) it holds that =(1 ) exp (H ( )) ( ) sum 1 : (6.57) To do so, rst note that for each B 2 B, the set Bc \ A is nonempty. Thus, by (6.52), the projections ABcl;i of Al;i along the coordinates in Bc ( M are disjoint across l 2 L. Thus, 1 Y B2B X l2L ~PBcYMjF ABcl;i j i ! B : Using H older?s inequality [35, Section 2.7], and recalling (6.40) and (2.13) we get 1 "X l2L Y B2B ~PBcYMjF ABcl;i j i Bc ! # 11 : (6.58) Next, note from Lemma 6.9 that ~PBcYMjF ABcl;i j i = X yBc2ABcl;i PYBc (yBc) rY k=1 Y j2Bc ~PBcFkj j kj ikj j i kj ; 150 which, since the order of products can be interchanged, and upon using (6.53), is bounded below by X yBc2ABcl;i PYBc (yBc) Y j2Bc (m2m) 1 rY k=1 PFkj j kj ikj j i kj : It follows that Y B2B ~PBcYMjF ABcl;i j i Bc Y B2B 2 4 X yBc2ABcl;i PYBc (yBc) 3 5 Bc Y B2B Y j2Bc " (m2m) 1 rY k=1 PFkj j kj ikj j i kj # Bc : (6.59) The right-side of (6.59) can be simpli ed by noting that Y B2B Y j2Bc " (m2m) 1 rY k=1 PFkj j kj ikj j i kj # Bc = mY j=1 " (m2m) 1 rY k=1 PFkj j kj ikj j i kj #P B2B:Bc3j Bc = m2m m PF (i) ; (6.60) where the previous step uses (6.41). The de nition of T0, along with (6.59) and (6.60), gives Y B2B ~PBcYMjF ABcl;i j i Bc m (m2m)m PF (i) Y B2B ABcl;i Bc ! Bc : (6.61) Also, since Al;i T0, we have PYM (Al;i) Al;i 0 ; which, with (6.43) and (6.61), gives Y B2B ~PBcYMjF ABcl;i j i Bc m (m2m)m 0 @ Q B2B ABcl;i Bc Al;i 1 APYMjF (Al;i j i) : (6.62) 151 Since is a fractional partition, [45, Corollary 3.4] implies 0 @ Q B2B ABcl;i Bc Al;i 1 A 1; (6.63) which combined with (6.58)-(6.63) yields 1 m (m2m)m 1 "X l2L (l) # 1 1 : The previous inequality implies (6.57) since 1 = sum 1: 6.7 Strong converse for secret key capacity A byproduct of Theorem 6.1 is a new result that establishes a strong converse for the SK capacity of a multiterminal source model, for the terminals in A M. In this context, we shall consider the security requirement (2.9), i.e., lim n nsvar(K; F) = 0: De nition 6.3. Given 0 < < 1, R 0 is an -achievable SK rate for A M if for every > 0, there is an N = N( ; ) such that for every n N , there exists an -CR K = K (XnM) for A from F satisfying 1 n log kKk R ; (6.64) and svar(K; F) n: (6.65) 152 The supremum of -achievable SK rates is the -SK capacity, denoted C( ). The SK capacity is the in mum of C( ) for 0 < < 1. We recall the following. Theorem 6.10. [20] The secret key capacity for A M is C = E = H (XM) max 2 (A) X B2B BH (XB j XBc) ; 0 < < 1: Remark. The (new) secrecy requirement (2.9) is not unduly restrictive. Indeed, the achievability proof of Theorem 6.10 [20] holds with sin(K; F) vanishing to zero exponentially rapidly in n, which, by Pinsker?s inequality (cf. [18]), implies (2.9). The converse proof in [20] was shown under the weak secrecy condition lim n 1 nI(K ^ F) = 0; (6.66) which, in turn, is implied by (2.9) by a simple application of [20, Lemma 1]. The strong converse for SK capacity, valid under (2.9), is given next. Theorem 6.11. For every 0 < < 1, it holds that C( ) = C: (6.67) Remark. It is not known if the strong converse in Theorem 6.11 holds under (6.66). Proof. Theorem 6.10 [20] already provides the proof of achievability, i.e., C( ) C. The converse proof below shows that if R is an -achievable SK rate, then R is an -achievable query exponent. Therefore, R E ( ) = C; 0 < < 1; (6.68) where the equality is by (6.2). Speci cally, for every > 0, suppose that there exists K = K (XnM) and communication F satisfying (6.64) and (6.65) for all n su ciently 153 large. We claim that the hypothesis (6.4) of Lemma 6.3 holds with U = K, V = F and = exp[n(R 2 )] for every 0 < < 1=2, when is su ciently small. Therefore, by (6.5), R 2 is an -achievable query exponent which leads to (6.68) since can be chosen arbitrarily small. Turning to the claim, observe that P (k; i) : PKjF (k j i) > 2 exp[n(R )] P (k; i) : PKjF (k j i) > 2 kKk P (k; i) : log kKkPKjF (k j i) > 1 E log kKkPKjF (K j F) ; where the rst and the last inequality above follow from (6.64) and the Markov inequality, respectively. Next, we show that E log kKkPKjF (K j F) svar(K; F) log kKk2 svar(K; F) : (6.69) Then, the right-side can be bounded above by n log n + 2 log XM ; (6.70) for all n su ciently large; the claim follows upon taking n ! 1 and ! 0. To see (6.69), note that for t1; t2; jt1 t2j < 1, f(t) , t log t satis es (cf. [18, Lemma 2.7]) f(t1) f(t2) t1 t2 log 1 t1 t2 : (6.71) 154 Then, for F = i, X k PKjF (k j i) log kKkPKjF (k j i) = X k PKjF (k j i) log PKjF (k j i) + PKjF (k j i) log kKk+ 1 kKk log kKk 1 kKk log kKk X k PKjF (k j i) log PKjF (k j i) 1 kKk log 1 kKk + PKjF (k j i) 1 kKk log kKk X k PKjF (k j i) 1 kKk log kKk PKjF (k j i) 1kKk ; (6.72) where the previous inequality uses (6.71) with t1 = PKjF (k j i) and t2 = kKk 1 for every value k of K. Finally, (6.69) follows upon multiplying both sides by PF (i), summing over i and using the log-sum inequality [18]. Observe that the proof of Theorem 6.11 does not rely on the form of the rvs K;F, and is, in e ect, a statement relating the size of any achievable SK rate under the svar-secrecy requirement (2.9) to the query exponent. As a consequence, also the SK capacity for more complex models in which the eavesdropper has additional access to side information can be bounded above by the optimum query exponent when the querier, too, is given access to the same side information. 6.8 General alphabet converse for A =M In this section, we present a converse technique for the optimum query exponent for rvs with general alphabets, with jointly Gaussian rvs as a special case. No corresponding general claim is made regarding achievability of the exponent. Our technique also leads to a new strong converse for Gaussian SK capacity [51]. Let Yi be a complete separable metric space, with associated Borel - eld i, 155 1 i k; a special case of interest is Yi = Rni . Denote by Yk the set Y1 ::: Yk and by k the product - eld5 1 ::: k on Yk. Let P = PY1;:::;Yk be a probability measure on Yk; k . The interactive communication fFji : 1 j r; 1 i kg is speci ed as in De nition 2.1, with the rv Fji taking values in, say, (Zji;Fji), and being i-measurable for each xed value of the preceding communication ji = (Fst : 1 s < j; 1 t k or s = j; 1 t < i) : Then, there exists a unique regular conditional probability measure on Yk; k conditioned on (F), denoted PY1;:::;YkjF (cf. [6, Chapter 6]). The notation Qi will be used interchangeably for the probability measure PY1;:::;YkjF ( j i). We make the following basic assumption of absolute continuity: Qi << PY1;:::;Yk ; PF a.s. in i; (6.73) i.e., (6.73) holds over a set of i with PF-probability 1. Assumption (6.73) is satis ed by a large class of interactive communication protocols including F taking countably many values. Moreover, we can assume the following without loss of generality: Qi F 1(i)c = 0; PF a.s. in i; (6.74) dQi dP (y k) = 0; for yk 2 F 1(i)c; PF a.s. in i: (6.75) Next, we de ne -CR L from F and its local estimates Li, respectively, as rvs taking countably many values, measurable with respect to k and i (F), 5Hereafter, the term \product - eld" of - elds 1; :::; k, will mean the smallest - eld containing sets from 1 ::: k, and will be denoted, with an abuse of notation, simply as k = 1 ::: k. 156 1 i k, and satisfying P (L = Li; 1 i k) 1 : The main result of this section, given below, extends Theorem 6.6 to general mea- sures as above. Theorem 6.12. For 0 < < 1, let L be -CR from interactive communication F. Let ~P = ~PY1;:::;Yk be a probability measure on Yk; k with ~P (A1 ::: Ak) = kY i=1 PYi (Ai) Ai 2 i; 1 i k: (6.76) Assuming that P << ~P, and given > 0 such that + p + < 1, let be such that P yk : dP d ~P (yk) 1 : (6.77) Then, there exists a query strategy q0 for L given F such that P q0(L j F) 2 1 k 1 ! (1 p + )2: (6.78) The proof of Theorem 6.12 is deferred to the end of this section. At this point, we present its implications for a Gaussian setup. Let X(n)i be an Rn-valued rv, i = 1; :::;m, and let X(n)M = X(n)1 ; :::; X (n) m be jointly Gaussian N (0; (n)), where (n) is a positive de nite matrix. We remark that X(n)M need not be independent or identically distributed across n. The notion of an -optimum query exponent E ( ), 0 < < 1, is exactly as in De nition 6.2, even though the underlying CR now can take countably many values. Also, given a partition of M with j j = k, 2 k m, the quantity E ( ) is de ned as in Section 6.5. 157 Proposition 6.13. For X(n)M N (0; (n)) with (n) being positive de nite, it holds that E ( ) min E ( ) min 1 2(j j 1) lim supn 1 n log Qj j i=1 (n) i j (n)j ; 0 < < 1; where (n) i is the covariance matrix of X(n) i , i = 1; :::; j j, and j j denotes determi- nant. Corollary 6.14. When X(n)M is i.i.d. in n with XM N (0; ), E ( ) min 1 2(j j 1) log Qj j i=1 i j j ; 0 < < 1: Proof. Proceeding as in the proof of Theorem 6.5, we apply Theorem 6.12 to the rvs Yi = X(n) i , 1 i j j. Speci cally, we show that the hypothesis (6.77) is satis ed with = n = Qj j i=1 n i j (n)j !1=2 exp(n ); (6.79) where 0 < < 1=2 is arbitrary. Then, the Proposition follows from the de nition of E ( ) and (6.79) as in the proof of Theorem 6.5. The Corollary results by a straightforward calculation. It remains to verify that (6.77) holds for in (6.79). For B (M; B 6= ;, let gB denote the density of the Gaussian rv X(n)B . From the AEP for Gaussian rvs [15, equation (47)] (see also [8]), P 1 n log gB X(n)B 1nh X(n)B > ; for some ; 6= B M < 2m exp( c( )n); > 0; (6.80) where h denotes di erential entropy and c( ) > 0 is a positive constant that does 158 not depend on n. Since dP d ~P = gMQj j i=1 g i ; P a.s. and h X(n)M = 12 log(2 e) mnj (n)j; h X(n) i = 12 log(2 e) j ijn (n) i ; 1 i j j; using the upper and lower bounds from (6.80) that hold with signi cant probability for all n su ciently large, we get that (6.77) holds with as in (6.79), for 0 < < 1=2. As an application of the Corollary above, we establish a new strong converse for SK capacity when the underlying rvs X(n)M are i.i.d. Gaussian in n; for this model, the SK capacity was established in [51]. The notions of -achievable SK rate, -SK capacity C( ) and SK capacity C are as in De nition 6.3, with condition (6.64) replaced by range(K) = f1; :::; bexp(nR)cg; (6.81) which rules out such rvs K as take in nitely many values. Proposition 6.15. When X(n)M is i.i.d. in n with XM N (0; ), C( ) = min 1 2(j j 1) log Qj j i=1 i j j ; 0 < < 1: (6.82) Proof. That C( ) is no smaller than the right-side of (6.82) follows from the achievability proof in [51]. The proof of the reverse inequality is along the lines of the proof of Theorem 159 6.11 and is obtained upon replacing the upper bound (6.70) by n log n + 2 R; and noting that Lemma 6.3 can be extended straightforwardly to an arbitrary rv V (with the explicit summations in the proof of that Lemma written as expectations), provided that the rv U is nite-valued. Proof of Theorem 6.12. In the manner of the proof of Theorem 6.6, it su ces to identify measurable sets I0 and L(i) L, i 2 I0, such that (6.21)-(6.23) are satis ed. Below we generalize appropriately the steps 1-3 in the proof of Theorem 6.6. Step 1. The following claim is an extension of Lemma 6.7. Lemma 6.16. Given measurable sets Ai 2 i, 1 i k, for ~P in (6.76), ~PY1;:::;YkjF (A1 ::: Ak j i) = kY j=1 ~PYj jF (Aj j i) ; PF a.s. in i; (6.83) where ~PY1;:::;YkjF is the regular conditional probability on (Yk; k) conditioned on (F). The proof uses the interactive property of the communication and is relegated to the Appendix F. Step 2. Next, we identify the set I0. The following technical observation will be used. Lemma 6.17. For every A0 2 k such that dP d ~P (yk) > 0; yk 2 A0; (6.84) 160 it holds that ~PY1;:::;YkjF (A0 j i) = dPF d ~PF (i) Z A0 dQi dP d ~P; ~PF a.s. in i (6.85) The proof is given in the Appendix F. Denoting by T0 the set n yk 2 Yk : 0 < dPd ~P(y k) o , let Al = T0 \ yk : Lj yj;F(yk) = L(yk) = l; 1 j k ; l 2 L: Then, for Al;i , Al \ F 1(i), (6.74), (6.75) and Lemma 6.17 imply ~PY1;:::;YkjF (Al;i j i) = dPF d ~PF (i) Z Al;i dQi dP d ~P; ~PF a.s. in i: (6.86) Below we restrict attention to the set of values of F for which (6.86) holds for every l 2 L; this set has ~PF measure 1 by (6.85) since the set L is countable. Proceeding along the lines of the proof of Theorem 6.6, we de ne I1 as the set of those i for which PY1;:::;YkjF (Al;i j i) 1 p + : (6.87) Since L is an -CR from F, it follows from (6.77), the fact that P yk : dP d ~P (yk) = 0 = 0; and by a reverse Markov inequality, that PF (I1) 1 p + : (6.88) Furthermore, for the set I2 of values i of F satisfying dPF d ~PF (i) ; (6.89) 161 it holds that PF (I2) 1 ; (6.90) since Z Ic2 dPF = Z Ic2 dPF d ~PF d ~PF < : De ne I0 = I1 \ I2; (6.23) follows from (6.88) and (6.90). Step 3. Since Lemma 2.8 (i) applies to a countable set U = L, de ning the non- negative measure on L as in (6.33) for each i 2 I0 and using (6.87), the sets L(i) obtained in (6.34)-(6.36) satisfy (6.21). Also, condition (6.22) will follow from (6.35) upon showing that exp (H ( )) 1 k 1 : (6.91) To do so, denote by Ajl;i the projection of Al;i along the jth coordinate, 1 j k. As before, the sets Ajl;i are disjoint across l 2 L. Then, H older?s inequality [35] implies that 1 kY j=1 "X l2L ~PYj jF Ajl;i j i # "X l2L kY j=1 ~PYj jF Ajl;i j i 1 k !#k = "X l2L ~PY1;:::;YkjF A1l;i ::: Akl;i j i 1 k #k ; (6.92) where the previous step uses Lemma 6.16. The right-side of (6.92) is bounded below 162 by "X l2L ~PY1;:::;YkjF (Al;i j i) 1 k #k ; since Al;i A1l;i ::: Akl;i, which by (6.86) equals 2 4X l2L dPF d ~PF (i) Z Al;i dQi dP d ~P ! 1 k 3 5 k : From the de nition of the set I2 in (6.89), the expression above exceeds 2 4X l2L Z Al;i dQi dP d ~P ! 1 k 3 5 k ; which is the same as 2 4X l2L Z Al;i dQi dP dP=d ~P dP=d ~P d ~P ! 1 k 3 5 k : (6.93) Since Al;i T0, the sum in (6.93) is bounded below further by 2 4X l2L Z Al;i dQi dP dP d ~P d ~P ! 1 k 3 5 k = 2 4X l2L Z Al;i dQi ! 1 k 3 5 k = "X l2L PY1;:::;YkjF (Al;i j i) 1 k #k : Combining the observations above from (6.92) onward, we have "X l2L PY1;:::;YkjF (Al;i j i) 1 k #k ; which is the same as (6.91) with = 1=k. 163 6.9 Discussion The description of the optimum query exponent in De nition 6.2 can be re ned to display an explicit dependence on 0. Let E ( ; 0) denote the optimum query exponent for xed 0 < ; 0 < 1. Our proofs establish E ( ; 0) equals the right side of (6.2) for 0 < (1 p )2 (see (6.20)). For 0 > 1 , the following construction of L renders E ( ; 0) unbounded: Choose L = 0 with probability (1 ) and uniformly distributed on a su ciently large set with probability . For the remaining values of ; 0, E ( ; 0) is not known. A less restrictive model for querying than that in Section 6.2 can be consid- ered, allowing general queries with binary answers. Such a query strategy can be represented as a search on a binary tree whose leaves correspond to the values of the CR L. The query strategies considered in this dissertation correspond to the case where the search tree is a path with leaves attached to each node. For a general tree model, our results can be adapted to show that the maximum number of queries that can be in icted on a querier grows only linearly in n at a rate that is equal to the expression for E in (6.2). We remark also that allowing randomness at the terminals inM for interactive communication and CR recovery, does not improve the optimum query exponent. Such randomization is described by mutually independent rvs W1; :::;Wm, where each Wi is distributed uniformly on the ( nite) set f1; :::; wig, and the rvs W1; :::;Wm are independent of XnM. The claim of the remark is seen from the converse result in Theorem 6.8. Indeed, the assertion (6.44) of Theorem 6.8 remains unchanged upon 164 replacing Yi by (Yi;Wi), i 2 M, 0 by 0 Q i2Mwi , and Bc by Bc Q i2Bc wi , B 2 B; and observing that in (6.43), the wi- terms cancel in the numerator and the denominator. Finally, Lemma 6.3, which considered rvs U; V , can be used to characterize the optimum query exponent for a family of nite-valued rvs fUn; Vng1n=1 with asso- ciated probability measures fPng1n=1 (which are not necessarily consistent). Here, is described analogously as E in De nition 6.2. An application of Lemma 6.3 yields that Pn- lim infn log PUnjVn (Un j Vn) n Pn- lim sup n log PUnjVn (Un j Vn) n where the left and right limits equal, respectively, the left- and right-sides of (2.33) with n = Pn and Zn = log PUnjVn (Un j Vn) n : 165 CHAPTER 7 Conclusion: Principles of Secrecy Generation Would I not have to be a barrel of memory if I wanted to carry my reasons around with me? - Nietzsche?s Zarathustra We conclude this dissertation by hypothesizing three principles of multitermi- nal secrecy generation that have emerged from our research. The results reported in the previous chapters provide important instances that a rmatively support these principles. We conjecture that these basic principles go beyond the models studied here and will apply in a broader setting for appropriately de ned notions of security. The rst principle we state applies to secure computing with public commu- nication when the privacy of a given function g0 must be maintained. Principle 1. If the value of a function g0 of the data can be recovered se- curely at a terminal, then the entire data can be recovered at the terminal using a communication that does not give away the value of g0. If the entire data can be recovered at a terminal using communication that does not give away the value of g0 then clearly the function g0 can be securely computed at that terminal. The principle above claims that the converse is also true. Indeed, once the value of g0 is recovered at the terminal, the terminals can communicate further to 166 attain omniscience at that terminal using communication that is independent jointly of the previous communication and the function g0. Speci cally, for the cases when we have a single-letter characterization for secure computability, the quantity R in Theorem 4.1 remains unchanged if the terminal computing the function g0 is required to recover the entire data; this includes the special case studied in Chapter 3. In fact, R remains roughly the same with such a replacement for all the cases studied in Chapter 4, thus providing credence to the conjecture that computing the private function securely at a terminal is as hard as recovering the entire data at that terminal without giving away the value of the private function to the eavesdropper. The next principle captures the structure of all protocols that can generate an optimum rate SKs for two terminals by characterizing the CR that is established when such a protocol is executed. Principle 2. A CR corresponds to an optimum rate SK if and only if it renders the observations of the two terminals (almost) conditionally independent. Clearly, a CR resulting from an optimum rate SK must render the observations almost conditionally independent as otherwise we can exploit the residual correlation to enhance further the SK rate. In Chapter 5 we have established the converse statement for i.i.d. observations1. We conjecture that in fact, such a structural equivalence between optimum rate SKs and a CR that renders the observations conditionally independent holds for more general distributions. 1 Although our actual proof entailed going to multiple blocks, an alternative single-shot proof can also be provided using a very interesting construction suggested by Braverman and Rao in [9, Theorem 4.1] in place of Lemma 5.4. 167 Finally, our last principle conjectures that the almost independence secrecy criterion imposed on an SK is equivalent to an alternative criterion requiring a large number of queries with probability close to 1 for resolving the value of the SK based on the public communication (see 6.1). Principle 3. Imposing an almost independence secrecy criterion is equivalent to imposing a lower bound on the complexity of a querier of the secret. Thus, a largest size SK makes the task of a querier the most onerous. It is clear that almost independence between a CR and the associated public communication will ensure that a querier has no option but to retort to exhaustive search of the CR space. It is the converse that we assert here, i.e, forming a CR that necessitates a certain number of queries is tantamount to generating an SK of size equal to the number of queries. In Chapter 6, we proved this principle for i.i.d. observations in an asymptotic sense as the number of observations tends to in nity. We conjecture that a direct correspondence can be obtained between almost independence and lower bounds on the complexity of a querier by connecting both these notions to the bounds on conditional probability in Lemma 6.3; this is work in progress. 168 Appendix A Maximum Common Function We prove Lemma 3.2 based on [26, Lemma, Section 4], which is paraphrased rst. Let the rvs Q and R take values in the nite set Q and R, respectively. For a stochastic matrix W : Q ! Q, let f ~D1; :::; ~Dlg be the ergodic decomposition (into communicating classes) of Q based on W (cf. e.g., [41, pp. 157 and 28{42]). Let ~D(n) denote a xed ergodic class of Qn (the n-fold Cartesian product of Q) on the basis of W n (the n-fold product of W ). Let D(n) andR(n) be any (nonempty) subsets of ~D(n) and Rn, respectively. Lemma GK. [26] For ~D(n);D(n);R(n) as above, assume that P Qn 2 D(n) j Rn 2 R(n) exp[ n n]; P Rn 2 R(n) j Qn 2 D(n) exp[ n n]; (A.1) where lim n n = 0. Then (as stated in [26, bottom of p. 157]), P Qn 2 D(n) P Qn 2 ~D(n) exp[ n n log2 n]; (A.2) for a (positive) constant that depends only on the pmf of (Q;R) and on W . A simple consequence of (A.2) is that for a given ergodic class ~D(n) and disjoint subsets D(n)1 ; :::;D(n)t of it, and subsets R(n)1 ; :::;R(n)t (not necessarily distinct) of Rn, 169 such that D(n)t0 ;R (n) t0 ; t0 = 1; :::; t, satisfy (A.1), it holds that t exp[n n log2 n]: (A.3) Note that the ergodic decomposition of Qn on the basis of W n for the speci c choice W (qjq0) = X r2R P (Q = q j R = r)P (R = r j Q = q0) ; q; q0 2 Q corresponds to the set of values of mcfn(Q;R) de ned by (3.10) [26]. Next, pick Q = Qm, R = (Q1; :::; Qm 1), and de ne the stochastic matrix W : Q ! Q by W (qjq0) = X P (Q = q j mcf(Q1; :::; Qm 1) = ) P (mcf(Q1; :::; Qm 1) = j Q = q0) ; q; q0 2 Q: (A.4) The ergodic decomposition of Qn on the basis of W n (with W as in (A.4)) will correspond to the set of values of mcfn(Q1; :::; Qm), recalling (3.9). Since (n) is -recoverable from Qni ; i = 1; :::;m, note that 0(n) = (n);mcfn(Q1; :::; Qm) also is -recoverable in the same sense, recalling De nition 3.5. This implies the existence of mappings 0(n)i ; i = 1; :::;m, satisfying P 0(n)1 (Qn1 ) = ::: = 0(n)m (Qnm) = 0(n) 1 : (A.5) For each xed value c = (c1; c2) of 0(n), let D(n)c = qnm 2 Qnm : 0(n)m (qnm) = c ; R(n)c = (qn1 ; :::; qnm 1) 2 Qn1 ::: Qnm 1 : 0(n)i (qni ) = c; i = 1; :::;m 1 : 170 Let C( ) denote the set of c?s such that P Qn 2 D(n)c j Rn 2 R(n)c 1 p ; P Rn 2 R(n)c j Qn 2 D(n)c 1 p : (A.6) Then, as in [26, Proposition 1], it follows from (A.5) that P 0(n) 2 C( ) 1 4p : (A.7) Next, we observe for each xed c2, that the disjoint sets D(n)c1;c2 lie in a xed ergodic class of Qn (determined by c2). Since (A.6) are compatible with the assumption (A.1) for all n su ciently large, we have from (A.3) that kfc1 : (c1; c2) 2 C( )gk exp[n n log2 n]; (A.8) where depends on the pmf of (Q1; :::; Qm) and W in (A.4), and where limn n = 0. Finally, 1 nH 0(n) = 1nH (n);mcfn(Q1; :::; Qm H (mcf(Q1; :::; Qm)) + 1 nH (n);1 0(n) 2 C( ) j mcfn(Q1; :::; Qm) H (mcf(Q1; :::; Qm)) + 1 nH (n) j mcfn(Q1; :::; Qm);1 0(n) 2 C( ) H(mcf(Q1; :::; Qm)) + n; where lim n n = 0 by (A.7) and (A.8). 171 Appendix B Aided Secret Key Capacity We prove Theorem 3.13. Considering rst the achievability part, x > 0. From the result for a general source network [17, Theorem 3.1.14] it follows, as in the proof of [20, Proposition 1], that for RM 2 R (A0; ZA0) and all n su ciently large, there exists a noninteractive communication F(n) = (F (n)1 ; :::; F (n) m ) with 1 n log kF (n)k mX i=1 Ri + ; such that X nM is n-recoverable from Xni ; Zni ;F(n) ; i 2 A0. Therefore, fmcf ((XMt; Zit)i2A0)gnt=1 is n-recoverable from Xni ; Zni ;F(n) ; i 2 A0. The last step takes recourse to Lemma 2.7. Speci cally, choose U = U 0 = fmcf ((XMt; Zit)i2A0)gnt=1 ; U0 = U ; V = constant; h = F (n); d = n [H (mcf ((XM; Zi)i2A0)) ] ; whereby the hypothesis (2.23) of Lemma 2.7 is satis ed for all n su ciently large. Fixing r0 = & exp " n mX i=1 Ri + !#? ; 172 Lemma 2.7 implies the existence of a , and thereby an ASK K(n) = (fmcf ((XMt; Zit)i2A0)gnt=1) of rate 1 n log r = H (mcf ((XM; Zi)i2A0)) mX i=1 Ri 3 : In particular, we can choose mX i=1 Ri RCO (A0;ZA0) + 2 : Since was arbitrary, this establishes the achievability part. We shall establish a stronger converse result by requiring the ASK as in De - nition 3.3 to satisfy the weaker secrecy condition (2.6), or by allowing the ASK to depend explicitly on the randomization UM but enforcing the strong secrecy condi- tion (2.2). Let K = K(n) (UM; XnM; ZnA0) be an n-ASK for A0, achievable using ob- servations of length n, randomization UM, public communication F = F (UM; XnM) and side information ZnA0 . Then, by (2.6), 1 nH(K) 1 nH(K j F) + n: (B.1) Let Ku = K (u;XnM; ZnA0) denote the random value of the ASK for a xed UM = u. Since (XnM; K) is n-recoverable from the rvs (UM; XnM; Zni ) for each i 2 A0, PUM (fu : (XnM; Ku) is p n-recoverable from (UM = u;XnM; Zni ) for each i 2 A0g) 1 p n: (B.2) Also, for each UM = u 1 nH (X n M; K j UM = u) = 1 nH (X n M; Ku) 173 by independence of UM and (XnM; ZnA0), and therefore, by Lemma 3.2, for u in the set in (B.2), 1 nH (X n M; K j UM = u) H (mcf ((XM; Zi)i2A0)) + n; (B.3) for all n su ciently large and where lim n n = 0. Then, 1 nH(UM; X n M; K) 1nH (UM) +H (mcf ((XM; Zi)i2A0)) + n + p n log (jXMjjZA0 j) ; (B.4) by (B.2) and (B.3). The proof is now completed along the lines of [20, Lemma 2 and Theorem 3]. Speci cally, denoting the set of positive integers f1; :::; lg by [1; l], 1 nH(UM; X n M; K) = 1 nH(K j F) + mX i=1 R0i + 1 nH(UM); where R0i = 1 n X : i modm H(F j F[1; 1]) + 1 nH Ui; Xni j F; K; U[1;i 1]; Xn[1;i 1] H(Ui): (B.5) Consider B *M, A0 * B. For j 2 A0 \Bc, we have 1 nH (UB) + 1 nH XB j XnBc ; Znj = 1nH UB; XnB j UBc ; XnBc ; Znj = 1nH F1; :::; Frm; K; UB; XnB j UBc ; XnBc ; Znj : Furthermore, sinceK is n-recoverable from (F; UBc ; XnBc ; Znj ) andH(F jUBc ; XnBc) = 0 for i mod m with i 2 Bc, 1 nH F1; :::; Frm; K; UB; XnB j UBc ; XnBc ; Znj 174 = 1n rmX =1 H F j F[1; 1]; UBc ; XnBc ; Znj + 1nH K j UBc ; XnBc ; Znj ;F + 1n X i2B H Ui; Xni j UBc\[i+1;m]; XnBc\[i+1;m]; Znj ;F; K; U[1;i 1]; Xn[1;i 1] 1n X i2B X : i modm H F j F[1; 1] +H Ui; Xni j F; K; U[1;i 1]; Xn[1;i 1] + n log jKj+ 1n X i2B Ri +H(UB); (B.6) where Ri , R0i + n log jKj+ 1 n ; i 2M: It follows from (B.1) and (B.4)-(B.6) that 1 nH(K) H (mcf ((XM; Zi)i2A0)) mX i=1 Ri + n + n + n log jKj+ 1n + p n log (jXMjjZA0 j) ; (B.7) where RM 2 R (A0; ZA0) from (B.6), and therefore mX i=1 Ri RCO (A0; ZA0) : (B.8) Then, (B.7), (B.8) imply 1 nH(K) C (A 0; ZA0) + n + n + n log jKj+ 1 n + p n log (jXMjjZA0j) : (B.9) If K = K (XnM; ZnA0) as in De nition 3.3, then jKj (jX jjZA0 j)n and the converse part follows from (B.9). On the other hand, for K = K (UM; XnM; ZnA0), the proof is completed using (2.2) in the manner of [20, Theorem 3]. This completes the converse part. 175 Appendix C Balanced Coloring Lemma We provide a proof of Lemma 2.7. Using the condition (i) in the de nition of U0, the left-side of (2.24) is bounded above by 2 2 + r0X j=1 X v2V P (h(U) = j; V = v; U 2 U0) rX i=1 X u02U 0: (u0)=i P (U 0 = u0 j h(U) = j; V = v; U 2 U0) 1 r : Therefore, it is su cient to prove that r0X j=1 X v2V P (h(U) = j; V = v; U 2 U0) rX i=1 X u02U 0: (u0)=i P (U 0 = u0 j h(U) = j; V = v; U 2 U0) 1 r < 12 ; (C.1) with probability greater than 1 2rr0jVj exp c 3drr0 for a constant c > 0. Let q = PV v 2 V : P (U 2 U0jV = v) < 1 2 3 : 176 Then, since 1 2 P (U 2 U0) X v2V : P(U2U0jV=v)< 1 2 3 P (U 2 U0jV = v) PV (v) + (1 q) < 1 2 3 q + (1 q); we get from the extremities above that q < 3 2 2 : (C.2) For u 2 U0 and v 2 V satisfying P (U 2 U0jV = v) 1 2 3 ; P (U = ujV = v; U 2 U0) > 3 d(1 2) ; we have that P (U = ujV = v) > 1d: Therefore, by (C.2) and (2.23), it follows that X (u;v): u2U0;P(U=ujV=v;U2U0)> 3d(1 2) P (U = u; V = v) 2 + q < 5 2 2 ; which is the same as r0X j=1 X v2V P (h(U) = j; V = v; U 2 U0) X u2U0: P(U=ujV=v;U2U0)> 3d(1 2) P (U = ujh(U) = j; V = v; U 2 U0) < 5 2 2 : (C.3) 177 The bound in (C.3) will now play the role of [20, inequality (50), p. 3059] and the remaining steps of our proof, which are parallel to those in [20, Lemma B.2], are provided here for completeness. Setting D to be the set of those (j; v) that satisfy X u2U : P(U=ujV=v;U2U0)> 3d(1 2) P (U = ujh(U) = j; V = v; U 2 U0) 5 2 ; we get that X (j;v)2Dc P (h(U) = j; V = v; U 2 U0) < : (C.4) Next, de ning E = (j; v) : P (h(U) = j; V = v; U 2 U0) r0P (V = v; U 2 U0) ; it holds for (j; v) 2 E, P (U = ujh(U) = j; V = v; U 2 U0) r0 P (U = ujV = v; U 2 U0) : (C.5) Also, X (j;v)2Ec P (h(U) = j; V = v; U 2 U0) < r0 r0X j=1 X v2V P (V = v; U 2 U0) : (C.6) Further, for (j; v) 2 E, if P (U = ujh(U) = j; V = v; U 2 U0) > 3r0 d(1 2) (C.7) then from (C.5), we have P (U = ujV = v; U 2 U0) > 3 d(1 2) : (C.8) 178 Therefore, denoting by I(j; v) the event fh(U) = j; V = v; U 2 U0g, and recalling the conditions that de ne U0 in (2.22), we have for (j; v) 2 E \D that X u02U 0: P(U 0=u0j I(j;v))> 3r0 d(1 2) P (U 0 = u0j I(j; v)) = X u02U 0: P(U=u(u0)j I(j;v))> 3r0 d(1 2) P (U = u(u0)j I(j; v)) = X u2U : P(U=uj I(j;v))> 3r0 d(1 2) P (U = uj I(j; v)) 5 2 ; (C.9) where the rst equality is by (2.22), the second equality is due to U 0 being a function of U , and the previous inequality is by (C.7), (C.8) and the de nition of the set D. Also, using (C.4), (C.6), we get X (j;v)2E\D P (h(U) = j; V = v; U 2 U0) 1 2 : (C.10) Now, the left-side of (C.1) is bounded, using (C.10), as r0X j=1 X v2V P (h(U) = j; V = v; U 2 U0) rX i=1 X u02U 0: (u0)=i P (U 0 = u0 j h(U) = j; V = v; U 2 U0) 1 r 4 + X (j;v)2E\D P (h(U) = j; V = v; U 2 U0) rX i=1 X u02U 0: (u0)=i P (U 0 = u0 j h(U) = j; V = v; U 2 U0) 1 r : (C.11) Using (C.9), the family of pmfs fP (U 0 = ( )jh(U) = j; V = v; U 2 U0) ; (j; v) 2 E \ Dg satis es the hypothesis (2.20) of Lemma 2.6 with d replaced by (1 2)d3r0 and replaced by 5 =2; assume that 0 < < 2=45 so as to meet the condition following 179 (2.20). This family consists of at most r0jVj pmfs. Therefore, using Lemma 2.6, r0X j=1 X v2V P (h(U) = j; V = v; U 2 U0) rX i=1 X u02U 0: (u0)=i P (U 0 = u0 j h(U) = j; V = v; U 2 U0) 1 r < 23 2 with probability greater than 1 2rr0jVj exp 25 3(1 2)d 36rr0 1 2rr0jVj exp c 3d rr0 ; for a constant c. This completes the proof of (C.1), and thereby the lemma. 180 Appendix D Su ciency Proof of Theorem 4.1 From (4.25), we have nRM + 2 < H (X n M j Gn0 ;F) ; where R1; :::; Rm satisfy conditions (1a) and (1b). For each i and Ri 0, consider a (map-valued) rv Ji that is uniformly distributed on the family Ji of all mappings X nki ! f1; : : : ; dexp(knRi)eg; i 2 M. The rvs J1; :::; Jm; XnkM are taken to be mutually independent. Fix ; 0, with 0 > m and + 0 < 1. It follows from the proof of the general source network coding theorem [18, Lemma 13.13 and Theorem 13.14] that for all su ciently large k, P jM 2 JM : XnkM is -recoverable from Xnki ; jMnfig XnkMnfig ; Zki ; i 2M 1 ; (D.1) where, for i 2M, Zki = 8 >>>< >>>: Fk; j 2 [1;m0] ; Fk; Gnk0 ; m0 < j m: 181 Below we shall establish that P jM 2 JM : 1 nkI jM(XnkM) ^Gnk0 ;Fk 0; (D.2) for all k su ciently large, to which end it su ces to show that P jM 2 JM : 1 nkI ji(Xnki ) ^Gnk0 ;Fk; jMnfig XnkMnfig m 0 m; i 2M; (D.3) since I jM XnkM ^Gnk0 ;Fk = mX i=1 I ji Xnki ^Gnk0 ;Fk j j1 Xnk1 ; : : : ; ji 1 Xnki 1 mX i=1 I ji Xnki ^Gnk0 ;Fk; jMnfig XnkMnfig : Then it would follow from (D.1), (D.2), and de nition of ZM that P jM 2 JM : XnkM is -recoverable from Xnki ; Zki ; jMnfig XnkMnfig ; i 2M; and 1nkI jM(XnkM) ^Gnk0 ;Fk < 1 0: This shows the existence of a particular realization F0 of JM that satis es (4.26) and (4.27). It now remains to prove (D.3). De ning ~Ji = jMnfig 2 JMnfig : XnkM is -recoverable from Xnki ; Zki ; jMnfig XnkMnfig ; ; we have by (D.1) that P JMnfig 2 ~Ji 1 . It follows that P jM 2 JM : 1 nkI ji(Xnki ) ^Gnk0 ;Fk; jMnfig XnkMnfig m + X jMnfig2 ~Ji P JMnfig = jMnfig p jMnfig ; 182 since Ji is independent of JMnfig, where p jMnfig is de ned as P ji 2 Ji : 1 nkI ji(Xnki ) ^Gnk0 ;Fk; jMnfig XnkMnfig m : Thus, (D.3) will follow upon showing that p jMnfig 0 m ; jMnfig 2 ~Ji; (D.4) for all k su ciently large. Fix jMnfig 2 ~Ji. We take recourse to Lemma 2.7 and set U = XnkM ; U 0 = Xnki ; V = Gnk0 ; Fk ; h = jMnfig; and U0 = xnkM 2 X nkM : xnkM = i xnki ; jMnfig xnkMnfig ;Fk xnkM ; gn0 (xnM) 1 (m0 < i m) for some mapping i. By the de nition of ~Ji, P (U 2 U0) 1 ; so that condition (2.22)(i) preceding Lemma 2.7 is met. Condition (2.22)(ii), too, is met from the de nition of U0; h and V . Upon choosing d = exp k H (XnMjGn0 ;F) 2 ; in (2.23), the hypotheses of Lemma 2.7 are satis ed, for appropriately chosen , and for su ciently large k. Then, by Lemma 2.7, with r = dexp (knRi)e ; r0 = exp knRMni ; and with Ji in the role of , (D.4) follows from (2.24) and (2.25). 183 Appendix E Proof of (5.28) and (5.31) It remains to prove that there exists -CR J , recoverable from F such that J;F satisfy (5.28) and (5.31). We provide a CR generation scheme with r stages. For 1 k r, denote by Ek the error event in the kth stage (de ned below recursively in terms of Ek 1), and by E0 the negligible probability event corresponding to Xn1 ; Xn2 not being PX1X2-typical. Consider 1 k r, k odd. For brevity, denote by V the rvs Uk 1 and by U the rv Uk; for k = 1, V is taken to be a constant. Suppose that conditioned on Eck 1 terminals 1 and 2 observe, respectively, sequences x1 2 X n1 and x2 2 X n2 , as well as a common sequence v 2 Vn such that (v;x1;x2) are jointly PV X1X2-typical. For > 0, generate at random exp [n(I(X1; X2 ^ U j V ) + )] sequences u 2 Un that are jointly PUV -typical with v, denoted by uij, 1 i N1, 1 j N2, where N1 = exp [n (I(X1 ^ U j X2; V ) + 3 )] ; N2 = exp [n (I(X2 ^ U j V ) 2 )] : The sequences uij are generated independently for di erent indices ij. Denote by L(k)(v;x1) a sequence uij, 1 i N1, 1 j N2, that is jointly PUV X1-typical with (v;x1) (if there exist more than one such sequences, choose any of them). The error event when no such sequence is found is denoted by Ek1; this happens 184 with probability vanishing to 0 doubly exponentially in n. The communication Fk(v;x1) is de ned to equal the rst index i of uij = L(k)(v;x1). Upon observing Fk(v;x1) = i, the terminal 2 computes L(k)2 (v;x2; i) as the unique sequence in fuij; 1 j N2g, that is jointly typical with (v;x2). If no such sequence is found or if several such sequences are found an error event Ek2 occurs. Clearly, the rate of communication Fk is bounded above by 1 n logN1 = I(X1 ^ U j X2; V ) + 3 = I(X1 ^ Uk j X2; U k 1) + 3 ; (E.1) and also, for large n, 1 nH(L (k)) 1n log(1 +N1N2) I(X1; X2 ^ U j V ) + 2 = I(X1; X2 ^ Uk j X2; Uk 1) + 2 : (E.2) Denote by Ek3 the event L(k)(v;x1);v;x1;x2 not being jointly PUV X1X2-typical. The error event Ek is de ned as Ek = Ek 1 [ Ek1 [ Ek2 [ Ek3. Then, conditioned on Eck the terminals share sequences (uij;v) that are jointly typical with (x1;x2). In the next stage k + 1, the sequence (uij;v) plays the role of the sequence v. The scheme for stages with even k is de ned analogously with roles of X1 and X2 interchanged. We claim that L(1); :::; L(r) constitutes the required CR along with the communication F = F1; :::; Fk. Then, (5.31) follows from (E.1), and the second inequality in (5.28) follows from (E.2). Moreover, for every realization u1; :::;ur of 185 L(1); :::; L(r), with E = 1Er we have, P L(1); :::; L(r) = u1; :::;ur j E = 0 P (f(x1;x2) : (u1; :::;ur;x1;x2) are jointly PUrX1X2 typicalg) exp [ n(I(X1; X2 ^ U r) )] ; for n large, which further yields 1 nH(L (1):::L(r) j E = 0) I(X1; X2 ^ U r) : Therefore, 1 nH(L (1):::L(r)) 1nH(L (1):::L(r) j E = 0) P (Er) log jX1jjX2j I(X1; X2 ^ U r) P (Er) log jX1jjX2j: Thus, the claim will follow upon showing that P (Er)! 0 as n!1. In particular, it remains to show that P (Ek2)! 0 and P (Ek3)! 0, k = 1; :::; r, as n!1. As before, we show this for odd k and the proof for even k follows mutatis mutandis. To that end, note rst that for any jointly PUV X1-typical (u;v;x1), the set of x2 2 X n2 such that (u;v;x1;x2) are jointly typical with (u;v;x1) has conditional probability close to 1 conditioned on Un = u; V n = v; Xn1 = x1, and so by the Markov relation X2 V;X1 U , also conditioned on V n = v; Xn1 = x1. Upon choosing u = L(k)(v;x1) in the argument above, we get P (Ek2)! 0. Finally, we show that P (Ek3) will be small, for large probability choices of the random codebook fuijg. Speci cally, for xed typical sequences (v;x1;x2), the probability P (Ek3 j V n = v; Xn1 = x1; Xn2 = x2) is 186 bounded above exactly as in [2, equation (4.15)]: P (Ek3 j V n = v; Xn1 = x1; Xn2 = x2) N1X i=1 N2X j=1 N2X l=1;l 6=j P (uij;v;x1) jointly PUV X1-typical; (uil;v;uil) jointly PUV X2-typical N1N22 : exp[ n(I(X1 ^ U j V ) + I(X1 ^ U j V ) + o(n))] exp[ n + o(n)]; for all n su ciently large. Note that the probability distribution in the calculation above comes from codebook generation, and in particular, the second inequality above uses the fact that uil and uij are independently selected for l 6= j. Thus, P (Ek3 j Ek2)! 0 for an appropriately chosen codebook, which completes the proof. 187 Appendix F Properties of Interactive Communication We prove two basic properties of interactive communication that were used in the general converse proof in Section 6.8. We retain the notation introduced therein. Lemma F.1. For every A0 2 k such that dP d ~P (yk) > 0; yk 2 A0; (F.1) it holds that ~PY1;:::;YkjF (A0 j i) = dPF d ~PF (i) Z A0 dQi dP d ~P; ~PF a.s. in i (F.2) Proof. It su ces to show that the right-side of (F.2) constitutes a version of E~P f1A0 j (F)g, i.e., Z F 1(B) 1A0d ~P = Z B Z A0 dPF d ~PF (z)dQzdP d ~P ~PF (d z) ; (F.3) for every set B in the range - eld of F. To show that, we note for every A 2 k that Z F 1(B) 1AdP = Z B PY jF (A j z) PF (d z) = Z B Z A dQz dP dP PF (dz) ; (F.4) 188 where the previous step uses the assumption (6.73). Using Fubini?s and Tonelli?s theorems to interchange the order of integrals in (F.4), we get Z F 1(B) 1A dP = Z A Z B dQz dP PF (dz) dP; = Z A 1F 1(B) dP; which further implies 1F 1(B) = Z B dQz dP PF (dz) ; P a.s.; (F.5) since the set A 2 k was arbitrary. Next, for every B in the range - eld of F, it follows from (F.5) and (F.1) that Z F 1(B) 1A0d ~P = Z A0 1F 1(B)d ~P = Z A0 1 dP=d ~P 1F 1(B)dP = Z A0 1 dP=d ~P Z B dQz dP PF (dz) dP = Z A0 Z B dQz dP PF (dz) d ~P: (F.6) The claim (F.3) follows upon interchanging the order of integrals in (F.6). Lemma F.2. Given measurable sets Ai 2 i, 1 i k, for ~P in (6.76), ~PY1;:::;YkjF (A1 ::: Ak j i) = kY j=1 ~PYj jF (Aj j i) ; PF a.s. in i; (F.7) where ~PY1;:::;YkjF is the regular conditional probability on (Yk; k) conditioned on (F). Proof. For 1 l r, 1 j k, denote by lj the interactive communication preceding Flj, by Flj the rv (Flj; lj), and by ilj a realization of Flj. Without loss 189 of generality, we choose a version of ~PY kjF that satis es ~PY kjFlj F 1lj (ilj)c j ilj = 0; ~PFlj a.s., (F.8) for all 1 l r; 1 j k. The following property of interactive communication is pivotal to our proof: For each i lj , 1lj (i lj) is a product set, i.e., 1lj (i lj) = A01 ::: A0k; A0j 2 j; 1 j k: We prove the claim by induction upon observing that ~PY kjFlj can be obtained by conditioning ~PY kj lj on the rv Flj. Formally, denote by k(i lj) = 1(i lj) ::: k(i lj) the - eld induced by k on A01 ::: A0k, and by Flj( ; i lj) the smallest sub- - eld of k(i lj) with respect to which Flj is measurable (for i lj xed). Using (F.8), we choose a version of ~PY kjF such that for each 1 l r and 1 j k, ~PY kjFlj ( j ilj) is the regular conditional probability on the probability space A01 ::: A0k; k(i lj); ~PY kj lj j i lj conditioned on Flj( ; i lj) . Speci cally, ~PY kjFlj (A j ilj) = E~PY kj lj( ji lj) 1A j Flj( ; i lj) (ilj); A 2 k; (F.9) where the underlying - eld for the conditional expectation is k(i lj). For this version of ~PY kjF, we show below that if (F.7) holds with lj in the role of F, then it holds with Flj in the role of F. Lemma F.2 then follows by induction since (F.7) holds with F = ;. 190 It remains to prove the assertion above. To that end, for B 2 Flj, denote by F 1lj B; i lj the set yj 2 Yj : Flj yj; i lj 2 B : With an abuse of notation, we do not distinguish between the sets F 1lj B; i lj and its cylindrical extension Y1 ::: F 1lj B; i lj ::: Yk: Then, using the notation ~Qi lj and ~Qti lj ; 1 t k, for the probability measures ~PY kj lj j i lj and ~PYtj lj j i lj , 1 t k, respectively, our induction hypothesis states ~Qi lj(A1 :::: Ak) = kY t=1 ~Qi lj(At); At 2 t; 1 t k: (F.10) It follows that Z F 1lj (B;i lj) 1A1 ::: Ak d ~Qi lj = Z F 1lj (B;i lj) 1A1\A01 ::: Ak\A0k d ~Qi lj = "Y t6=j Z 1At\A0t d ~Q t i lj #Z F 1lj (B;i lj) 1Aj\A0j d ~Q j i lj ; (F.11) where the rst equality uses (F.8) and the second uses (F.10). De ning P tlj(A) , E ~Qi lj t 1A j Flj( ; i lj) ; A 2 t(i lj); 1 t k; 191 we have from (F.11) that Z F 1lj (B;i lj) 1A1 ::: Ak d ~Qi lj = "Y t6=j Z P tlj(At \ A0t) d ~Qti lj #Z F 1lj (B;i lj) P jlj(Aj \ A0j) d ~Qji lj = Z F 1lj (B;i lj) kY t=1 P tlj(At \ A0t) d ~Qi lj ; where the second equality uses (F.10). Thus, by (F.9), ~PY kjFlj (A1 ::: Ak j ilj) = kY t=1 P tlj(At \ A0t); ~PFlj a.s. in ilj: (F.12) Since by (F.8) P tlj(A0t) = 1, 1 t k, it follows from (F.12) that P tlj(At) = P tlj(At \ A0t) = ~PY kjFlj A01 ::: A0t 1 At A0t+1 ::: A0k j ilj = ~PYtjFlj (At j ilj) : The previous observation, along with (F.12), implies that (F.7) holds with Flj in the role F. 192 Index aided secret key capacity characterization, 49 de nition, 46 balanced coloring lemma, 31 common information G acs-K orner characterization, 27 de nition, 27 multiterminal, 47 interactive characterization, 99 de nition, 96 invariance, 122 invariance, 29 Wyner characterization, 28 de nition, 28 common randomness de nition, 21 communication for omniscience, 23 fractional partition, 26, 146 H older?s inequality, 144, 162 interactice communication de nition, 20 interactive communication properties, 76, 141, 148, 160 rate, 20 lossless coding theorem, 38 maximum common function, 47 millionaire problem, 9 minimal su cient statistic, 113 multiterminal source model, 19 noninteractive communication, 20 query exponent optimum characterization, 132 de nition, 132 Gaussian, 158 query strategy, 131, 133, 134 R enyi entropy, 35 reverse Markov inequality, 135, 142, 161 secret key capacity alternative expressions, 26 characterization, 23 de nition, 22 two terminals, 26 secret keys rate limited communication, 128 secure auction, 52 secure computability characterization, 42, 49, 75, 91 de nition, 40, 41, 65, 66 secure computation of parity, 42 secure computing using SKs, 51 secure multiterminal source coding, 71 security index divergence, 22 variational distance, 24 source coding, 37 strong converse, 133 Gaussian, 159 SK capacity, 153 strong secrecy, 22 weak secrecy, 24 wiretap secret key, 63 193 Bibliography [1] R. Ahlswede and I. Csisz ar. Common randomness in information theory and cryptography{part i: Secret sharing. IEEE Trans. Inf. Theory, 39(4):1121{ 1132, July 1993. [7, 11, 12, 21, 24, 26, 63, 142] [2] R. Ahlswede and I. Csisz ar. Common randomness in information theory and cryptography{part ii: CR capacity. IEEE Trans. Inf. Theory, 44(1):225{240, January 1998. [4, 8, 21, 32, 108, 126, 187] [3] R. Ahlswede and I. Csisz ar. On the oblivious transfer capacity. IEEE Interna- tional Symposium on Information Theory, pages 2061{2064, 2007. [7] [4] E. Arikan. An inequality on guessing and its application to sequential decoding. IEEE Trans. Inf. Theory, 42(1):99{105, January 1996. [16, 131] [5] E. Arikan and N. Merhav. The Shannon cipher system with a guessing wire- tapper. IEEE Trans. Inf. Theory, 45(6):1860{1866, September 1999. [16, 131] [6] R. B. Ash. Real Analysis and Probability. Academic Press, 1972. [156] [7] C. H. Bennett, G. Brassard, C. Cr epeau, and U. M. Maurer. Generalized privacy ampli cation. IEEE Trans. Inf. Theory, 41(6):1915{1923, November 1995. [8, 32] [8] S. Bobkov and M. Madiman. Concentration of the information in data with log-concave distributions. Annals of Probability, 39(4):1528{1543, 2011. [158] [9] M. Braverman and A. Rao. Information equals amortized communication. An- nual Symposium on Foundations of Computer Science, pages 748{757, 2011. [167] [10] C. Chan. Generating secret in a network. Ph. D. Dissertation, Massachussetts Institute of Technology, 2010. [146] [11] C. Chan. Multiterminal secure source coding for a common secret source. Proc. Conference on Communication, Control, and Computing (Allerton), pages 188{ 195, Sep 2011. [8] 194 [12] C. Chan and L. Zheng. Mutual dependence for secret key agreement. Proc. Annual Conference on Information Sciences and Systems (CISS 2010). [26] [13] P.N. Chen and F. Alajaji. Csisz ar?s cuto rates for arbitrary discrete sources. IEEE Trans. Inf. Theory, 47(1):330{338, 2001. [16] [14] C. Y. Chong and S. P. Kumar. Sensor networks: Evolution, opportunities, and challenges. Proc. IEEE, 91(8):1247 { 1256, August 2003. [1] [15] T. Cover and S. Pombra. Gaussian feedback capacity. IEEE Trans. Inf. Theory, 35(1):37{43, January 1989. [158] [16] I. Csisz ar. Almost independence and secrecy capacity. Prob. Pered. Inform., 32(1):48{57, 1996. [24, 41, 84] [17] I. Csisz ar and J. K orner. Information theory: Coding theorems for discrete memoryless channels. Academic Press, 1981. [47, 55, 60, 172] [18] I. Csisz ar and J. K orner. Information theory: Coding theorems for discrete memoryless channels. 2nd edition. Cambridge University Press, 2011. [24, 72, 86, 87, 110, 111, 137, 153, 154, 155, 181] [19] I. Csisz ar and P. Narayan. Common randomness and secret key generation with a helper. IEEE Trans. Inf. Theory, 46(2):344{366, March 2000. [41] [20] I. Csisz ar and P. Narayan. Secrecy capacities for multiple terminals. IEEE Trans. Inf. Theory, 50(12):3047{3061, December 2004. [2, 4, 7, 8, 12, 15, 19, 22, 23, 24, 25, 26, 33, 34, 35, 49, 51, 56, 57, 63, 72, 88, 106, 137, 153, 172, 174, 175, 178] [21] I. Csisz ar and P. Narayan. Secrecy capacities for multiterminal channel models. IEEE Trans. Inf. Theory, 54(6):2437{2452, June 2008. [7, 8, 15, 22, 23, 26, 77, 137] [22] Y. Dodis, R. Ostrovsky, L. Reyzin, and A. Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM Journal on Computing, 38(1):97{139, 2008. [14] [23] T. Eisenbarth and S. Kumar. A survey of lightweight-cryptography implemen- tations. IEEE Design and Test of Computers, 24(6):522{533, December 2007. [12] [24] K. Eswaran and M. Gastpar. Rate loss in the ceo problem. Proc. Conference on Information Sciences and Systems, March 2005. [13] [25] N. M. Freris, H. Kowshik, and P. R. Kumar. Fundamentals of large sen- sor networks: Connectivity, capacity, clocks, and computation. Proc. IEEE, 98(11):1828 { 1846, November 2010. [1] [26] P. G acs and J. K orner. Common information is far less than mutual informa- tion. Problems of Control and Information Theory, 2(2):149{162, 1973. [9, 20, 27, 28, 47, 48, 135, 169, 170, 171] 195 [27] R. G. Gallager. Finding parity in a simple broadcast nework. IEEE Trans. Inf. Theory, 34(2):176{180, March 1988. [7] [28] B. Gassend, D. Clarke, M. van Dijk, and S. Devadas. Silicon physical random functions. Proc. ACM Conference on Computer Communications and Security, pages 148 {160, November 2002. [1] [29] A. Giridhar and P. R. Kumar. Computing and communicating functions over sensor networks. IEEE Journ. on Select. Areas in Commun., 23(4):755{764, April 2005. [7] [30] B. Girod, A. Margot, S. Rane, and D. Rebollo-Monedero. Distributed video coding. Proc. IEEE, 93(1):71{83, January 2005. [1] [31] A. A. Gohari and V. Anantharam. Information-theoretic key agreement of multiple terminalspart i. IEEE Trans. Inf. Theory, 56(8):3973 { 3996, August 2010. [63] [32] T. S. Han. Information-Spectrum Methods in Information Theory [English Translation]. Series: Stochastic Modelling and Applied Probability, Vol. 50, Springer, 2003. [38] [33] T. S. Han and S. Verd u. Approximation theory of output statistics. IEEE Trans. Inf. Theory, 39(3):752{772, May 1993. [38] [34] M. K. Hanawal and R. Sundaresan. The Shannon cipher system with a guessing wiretapper: General sources. IEEE Trans. Inf. Theory, 57(4):2503{2516, April 2011. [16, 131] [35] G. Hardy, J. E. Littlewood, and G. P olya. Inequalities. 2nd edition. Cambridge University Press, 1952. [144, 150, 162] [36] R. Impagliazzo and D. Zuckerman. How to recycle random bits. Proc. Annual Symposium on Foundations of Computer Science, pages 248{253, 1989. [25] [37] A. K. Jain, A. Ross, and S. Pankanti. Biometrics: a tool for information security. IEEE Transactions on Information Forensics and Security, 1(2):125{ 143, 2006. [3] [38] S. Kamath and V. Ananthram. A new dual to the G acs-K orner common infor- mation de ned via the Gray-Wyner system. Proc. Conference on Communica- tion, Control, and Computing (Allerton), pages 1340{1346, Oct 2010. [113] [39] A. H. Kaspi. Two-way source coding with a delity criterion. IEEE Trans. Inf. Theory, 31(6):735{740, November 1985. [109] [40] J. Korner and K. Marton. How to encode the modulo-two sum of binary sources. IEEE Trans. Inf. Theory, 25(2):219{221, March 1979. [7] 196 [41] M. Loeve. Probability theory. 2nd Edition. Van Nostrand New York, 1960. [135, 169] [42] N. Ma and P. Ishwar. Some results on distributed source coding for interactive function computation. IEEE Trans. Inf. Theory, 57(9):6180{6195, September 2011. [110] [43] N. Ma, P. Ishwar, and P. Gupta. Information-theoretic bounds for multiround function computation in collocated networks. IEEE International Symposium on Information Theory, pages 2306{2310, 2009. [7] [44] M. Madiman and A. Barron. Generalized entropy power inequalities and mono- tonicity properties of information. IEEE Trans. Inf. Theory, 53(7):2317{2329, July 2007. [26] [45] M. Madiman and A. Barron. Entropy and set cardinality inequalities for partition-determined functions. Random Structures and Algorithms, 40:399{ 424, 2012. [26, 152] [46] M. Madiman and P. Tetali. Information inequalities for joint distributions, with interpretations and applications. IEEE Trans. Inf. Theory, 56(6):2699{2713, June 2010. [26, 77, 146] [47] J. L. Massey. Guessing and entropy. Proc. IEEE International Symposium on Information Theory, 1994. [16, 131] [48] U. M. Maurer. Secret key agreement by public discussion from common infor- mation. IEEE Trans. Inf. Theory, 39(3):733{742, May 1993. [7, 11, 12, 21, 24, 26, 63, 126] [49] U. M. Maurer. Communications and Cryptography: Two sides of One Tapestry, chapter 26, pages 271{285. Norwell, MA: Kluwer, R.E. Blahut et al., Eds. edition, 1994. [24, 41] [50] A.C.A. Nascimento and A. Winter. On the oblivious transfer capacity of noisy correlations. Proc. IEEE International Symposium on Information Theory, pages 1871{1875, 2009. [7] [51] S. Nitinawarat and P. Narayan. Secret key generation for correlated Gaussian sources. IEEE Trans. Inf. Theory, 58(6):3373{3391, June 2012. [155, 159] [52] A. Orlitsky and A. El Gamal. Communication with secrecy constraints. STOC, pages 217{224, 1984. [7] [53] A. Orlitsky and J. R. Roche. Coding for computing. IEEE Trans. Inf. Theory, 47(3):903{917, March 2001. [7] [54] R. S. Pappu. Physical one-way functions. Ph. D. Dissertation, Massachussetts Institute of Technology, 2001. [3] 197 [55] R. Puri, A. Majumdar, P. Ishwar, and K. Ramchandran. Distributed video coding in wireless sensor networks. IEEE Signal Processing Magazine, pages 94{106, July 2006. [1] [56] N. K. Ratha, J. H. Connell, and R. M. Bolle. Enhancing security and privacy in biometrics-based authentication systems. IBM Syst. J., 40(3):614{634, 2001. [1] [57] A. R enyi. On measures of entropy and information. Proc. Fourth Berkeley Symposium on Mathematics Statistics and Probability, Vol. 1 (Univ. of Calif. Press), pages 547{561, 1961. [35] [58] C. E. Shannon. A mathematical theory of communication. Bell System Tech- nical Journal, 27:379{423, 1948. [2, 16] [59] H. Shimokawa. R enyi?s entropy and error exponent of source coding with count- ably in nite alphabet. Proc. IEEE International Symposium on Information Theory, 2006. [16] [60] D. Slepian and J. Wolf. Noiseless coding of correlated information source. IEEE Trans. Inf. Theory, 19(4):471{480, July 1973. [83, 100, 105] [61] H. Tyagi. Minimal public communication for maximum rate secret key gen- eration. Proc. IEEE International Symposium on Information Theory, pages 578{582, 2011. [95] [62] H. Tyagi. Distributed computing with privacy. Proc. IEEE International Sym- posium on Information Theory, pages 1157{1161, 2012. [64] [63] H. Tyagi. Common information and secret key capacity. To appear, IEEE Trans. Inf. Theory, 2013. [19, 95] [64] H. Tyagi. Distributed function computation with con dentiality. IEEE Journal on Selected Areas in Communications, 31(4):691{701, April 2013. [64] [65] H. Tyagi and P. Narayan. How many queries will resolve common randomness? Proc. IEEE International Symposium on Information Theory, 2013. [19, 131] [66] H. Tyagi and P. Narayan. How many queries will resolve common randomness? To appear, IEEE Trans. Inf. Theory, 2013. [131] [67] H. Tyagi, P. Narayan, and P. Gupta. Secure computing. Proc. IEEE Interna- tional Symposium on Information Theory, pages 2612 { 2616, 2010. [39] [68] H. Tyagi, P. Narayan, and P. Gupta. When is a function securely computable? IEEE Trans. Inf. Theory, 57(10):6337{6350, October 2011. [19, 39, 92] [69] H. Tyagi, P. Narayan, and P. Gupta. When is a function securely computable? Proc. IEEE International Symposium on Information Theory, pages 2876{2880, 2011. [39] 198 [70] H. Tyagi and S. Watanabe. Work in progress. 2013. [6] [71] S. Venkatesan and V. Anantharam. The common randomness capacity of a pair of independent discrete memoryless channels. IEEE Trans. Inf. Theory, 44(1):215{224, January 1998. [144] [72] S. Venugopal, R. Buyya, and K. Ramamohanarao. A taxonomy of data grids for distributed data sharing, management and processing. ACM Computing Surveys, 38(3), 2006. [1] [73] S. Watanabe. Personal communication. 2013. [25] [74] H. S. Witsenhausen. On sequences of pairs of dependent random variables. Siam J. Appl. Math., 28(1):100{113, January 1975. [20] [75] Y. Wu. Personal communicattion. 2013. [16] [76] A. D. Wyner. Recent results in the Shannon theory. IEEE Trans. Inf. Theory, 20(1):2{10, January 1974. [43] [77] A. D. Wyner. The common information of two dependent random variables. IEEE Trans. Inf. Theory, 21(2):163{179, March 1975. [12, 28, 118] [78] G. Xu and B. Chen. The su ciency principle for decentralized data reduction. Proc. IEEE International Symposium on Information Theory, pages 319{323, 2012. [13] [79] A. C. Yao. Some complexity questions related to distributive computing. Proc. Annual Symposium on Theory of Computing, pages 209{213, 1979. [7] [80] A. C. Yao. Protocols for secure computations. Proc. Annual Symposium on Foundations of Computer Science, pages 160{164, 1982. [6, 9] [81] C. Ye. Information theoretic generation of multiple secret keys. Ph. D. Disser- tation, University of Maryland, College Park, 2005. [5, 43, 44] [82] C. Ye and P. Narayan. Secret key and private key constructions for simple mul- titerminal source models. Proc. IEEE International Symposium on Information Theory, pages 2133{2137, 2005. [43, 44] [83] C. Ye and P. Narayan. Secret key and private key constructions for simple mul- titerminal source models. IEEE Trans. Inf. Theory, 58(2):639{651, February 2012. [5] 199