Function Computation, Secrecy Generation and Common Randomness

Rudolf Ahlswede

Eyal Kushilevitz Z, Adi Rosén

Himanshu Tyagi

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 multiterminal 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 specific 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 unified 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 identification of the underlying CR and its decomposition into independent components, each with a different operational significance, is

Sirin Nitinawarat, Chunxuan Ye, Alexander Barg +2 more

Inherent connections are known to exist between common randomness generated by multiterminal source coding and channel coding on the one hand, and information theoretic secrecy generation by means of public communication on the other hand. Based on these connections, points of contact have been found recently also between secrecy generation for a special model for the latter and the combinatorial problem of tree packing in a multigraph. This paper provides a brief (and partial) survey of these links, especially those between secrecy generation and combinatorial tree packing. Our objective is to highlight specific connections between common randomness, secrecy and tree packing.

Divya Gupta, Yuval Ishai, Hemanta K. Maji +1 more

Fan Li, Jinyuan Chen

In many communication networks, secrecy constraints usually incur an extra limit in capacity (or generalized degrees-of-freedom, GDoF), in the sense that a penalty in capacity (or GDoF) is incurred due to the secrecy constraints. Over the past decades a significant amount of effort has been made by the researchers to understand the limits of secrecy constraints in communication networks. In this work, we focus on how to break the limits of secrecy constraints in communication networks, i.e., how to remove the penalty in GDoF due to the secrecy constraints. We begin with three basic settings: a two-user symmetric Gaussian interference channel with confidential messages, a symmetric Gaussian wiretap channel with a helper, and a two-user symmetric Gaussian multiple access wiretap channel. Interestingly, in this work we show that adding common randomness at the transmitters can totally remove the penalty in sum GDoF or GDoF region of the three settings considered here. The results reveal that adding common randomness at the transmitters is a powerful way to break the limits of secrecy constraints in communication networks. Common randomness can be generated offline. The role of the common randomness is to jam the information signal at the eavesdroppers, without causing too much interference at the legitimate receivers. To accomplish this role, a new method of Markov chain-based interference neutralization is proposed in the achievability schemes utilizing common randomness. From the practical point of view, we hope to use less common randomness to break the limits of secrecy constraints. With this motivation, for most of the cases we characterize the minimal GDoF of common randomness to break the limits of secrecy constraints, based on our derived converses.