skip to main content


The NSF Public Access Repository (NSF-PAR) system and access will be unavailable from 11:00 PM ET on Thursday, May 23 until 2:00 AM ET on Friday, May 24 due to maintenance. We apologize for the inconvenience.

Title: Secure Multi-Function Computation with Private Remote Sources
We consider a distributed function computation problem in which parties observing noisy versions of a remote source facilitate the computation of a function of their observations at a fusion center through public communication. The distributed function computation is subject to constraints, including not only reliability and storage but also privacy and secrecy. Specifically, 1) the remote source should remain private from an eavesdropper and the fusion center, measured in terms of the information leaked about the remote source; 2) the function computed should remain secret from the eavesdropper, measured in terms of the information leaked about the arguments of the function, to ensure secrecy regardless of the exact function used. We derive the exact rate regions for lossless and lossy single-function computation and illustrate the lossy single-function computation rate region for an information bottleneck example, in which the optimal auxiliary random variables are characterized for binary input symmetric output channels. We extend the approach to lossless and lossy asynchronous multiple-function computations with joint secrecy and privacy constraints, in which case inner and outer bounds for the rate regions differing only in the Markov chain conditions imposed are characterized.  more » « less
Award ID(s):
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Proceedings of IEEE International Symposium on Information Theory
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. In this paper, the K-user interference channel with secrecy constraints is considered with delayed channel state information at transmitters (CSIT). We propose a novel secure retrospective interference alignment scheme in which the transmitters carefully mix information symbols with artificial noises to ensure confidentiality. Achieving positive secure degrees of freedom (SDoF) is challenging due to the delayed nature of CSIT, and the distributed nature of the transmitters. Our scheme works over two phases: Phase one, in which each transmitter sends information symbols mixed with artificial noises, and repeats such transmission over multiple rounds. In the next phase, each transmitter uses the delayed CSIT of the previous phase and sends a function of the net interference and artificial noises (generated in previous phase), which is simultaneously useful for all receivers. These phases are designed to ensure the decodability of the desired messages while satisfying the secrecy constraints. We present our achievable scheme for three models, namely: (1) K-user interference channel with confidential messages (IC-CM), and we show that 1 2 ( K - 6 ) SDoF is achievable; (2) K-user interference channel with an external eavesdropper (IC-EE); and 3) K-user IC with confidential messages and an external eavesdropper (IC-CM-EE). We show that for the K-user IC-EE, 1 2 ( K - 3 ) SDoF is achievable, and for the K-user IC-CM-EE, 1 2 ( K - 6 ) is achievable. To the best of our knowledge, this is the first result on the K-user interference channel with secrecy constrained models and delayed CSIT that achieves an SDoF which scales with K , square-root of number of users. 
    more » « less
  2. In this paper, a joint source-channel coding approach is taken to the problem of securely computing a function of distributed sources over a multiple-access wiretap channel that is linear with respect to a finite field. It is shown that if the joint source distribution fulfills certain conditions and the function to be computed matches the linear structure of the channel, secrecy comes for free in the sense that the fundamental limit (i.e., the secrecy computation-capacity) is achieved without the need for stochastic encoding. Furthermore, the legitimate receiver does not need any advantage over the eavesdropper, which is in stark contrast to standard physical-layer security results. 
    more » « less
  3. INTRODUCTION A brainwide, synaptic-resolution connectivity map—a connectome—is essential for understanding how the brain generates behavior. However because of technological constraints imaging entire brains with electron microscopy (EM) and reconstructing circuits from such datasets has been challenging. To date, complete connectomes have been mapped for only three organisms, each with several hundred brain neurons: the nematode C. elegans , the larva of the sea squirt Ciona intestinalis , and of the marine annelid Platynereis dumerilii . Synapse-resolution circuit diagrams of larger brains, such as insects, fish, and mammals, have been approached by considering select subregions in isolation. However, neural computations span spatially dispersed but interconnected brain regions, and understanding any one computation requires the complete brain connectome with all its inputs and outputs. RATIONALE We therefore generated a connectome of an entire brain of a small insect, the larva of the fruit fly, Drosophila melanogaster. This animal displays a rich behavioral repertoire, including learning, value computation, and action selection, and shares homologous brain structures with adult Drosophila and larger insects. Powerful genetic tools are available for selective manipulation or recording of individual neuron types. In this tractable model system, hypotheses about the functional roles of specific neurons and circuit motifs revealed by the connectome can therefore be readily tested. RESULTS The complete synaptic-resolution connectome of the Drosophila larval brain comprises 3016 neurons and 548,000 synapses. We performed a detailed analysis of the brain circuit architecture, including connection and neuron types, network hubs, and circuit motifs. Most of the brain’s in-out hubs (73%) were postsynaptic to the learning center or presynaptic to the dopaminergic neurons that drive learning. We used graph spectral embedding to hierarchically cluster neurons based on synaptic connectivity into 93 neuron types, which were internally consistent based on other features, such as morphology and function. We developed an algorithm to track brainwide signal propagation across polysynaptic pathways and analyzed feedforward (from sensory to output) and feedback pathways, multisensory integration, and cross-hemisphere interactions. We found extensive multisensory integration throughout the brain and multiple interconnected pathways of varying depths from sensory neurons to output neurons forming a distributed processing network. The brain had a highly recurrent architecture, with 41% of neurons receiving long-range recurrent input. However, recurrence was not evenly distributed and was especially high in areas implicated in learning and action selection. Dopaminergic neurons that drive learning are amongst the most recurrent neurons in the brain. Many contralateral neurons, which projected across brain hemispheres, were in-out hubs and synapsed onto each other, facilitating extensive interhemispheric communication. We also analyzed interactions between the brain and nerve cord. We found that descending neurons targeted a small fraction of premotor elements that could play important roles in switching between locomotor states. A subset of descending neurons targeted low-order post-sensory interneurons likely modulating sensory processing. CONCLUSION The complete brain connectome of the Drosophila larva will be a lasting reference study, providing a basis for a multitude of theoretical and experimental studies of brain function. The approach and computational tools generated in this study will facilitate the analysis of future connectomes. Although the details of brain organization differ across the animal kingdom, many circuit architectures are conserved. As more brain connectomes of other organisms are mapped in the future, comparisons between them will reveal both common and therefore potentially optimal circuit architectures, as well as the idiosyncratic ones that underlie behavioral differences between organisms. Some of the architectural features observed in the Drosophila larval brain, including multilayer shortcuts and prominent nested recurrent loops, are found in state-of-the-art artificial neural networks, where they can compensate for a lack of network depth and support arbitrary, task-dependent computations. Such features could therefore increase the brain’s computational capacity, overcoming physiological constraints on the number of neurons. Future analysis of similarities and differences between brains and artificial neural networks may help in understanding brain computational principles and perhaps inspire new machine learning architectures. The connectome of the Drosophila larval brain. The morphologies of all brain neurons, reconstructed from a synapse-resolution EM volume, and the synaptic connectivity matrix of an entire brain. This connectivity information was used to hierarchically cluster all brains into 93 cell types, which were internally consistent based on morphology and known function. 
    more » « less
  4. We consider the rate-limited quantum-to-classical optimal transport in terms of output-constrained rate-distortion coding for discrete quantum measurement systems with limited classical common randomness. The main coding theorem provides the achievable rate region of a lossy measurement source coding for an exact construction of the destination distribution (or the equivalent quantum state) while maintaining a threshold of distortion from the source state according to a generally defined distortion observable. The constraint on the output space fixes the output distribution to an i.i.d. predefined probability mass function. Therefore, this problem can also be viewed as information-constrained optimal transport which finds the optimal cost of transporting the source quantum state to the destination state via an entanglement-breaking channel with limited communication rate and common randomness. 
    more » « less
  5. —In this work, we address the lossy quantum-classical (QC) source coding problem, where the task is to compress the classical information about a quantum source, obtained after performing a measurement, below the Shannon entropy of the measurement outcomes, while incurring a bounded reconstruction error. We propose a new formulation, namely, "rate-channel theory", for the lossy QC source coding problem based on the notion of a backward (posterior) channel. We employ a singleletter posterior channel to capture the reconstruction error in place of the single-letter distortion observable. The formulation requires the reconstruction of the compressed quantum source to satisfy a block error constraint as opposed to the average singleletter distortion criterion in the rate-distortion setting. We also develop an analogous formulation for the classical variant with respect to a corresponding posterior channel. Furthermore, we characterize the asymptotic performance limit of the lossy QC and classical source coding problems in terms of single-letter quantum mutual information and mutual information quantities of the given posterior channel, respectively. We provide examples for the above formulations. 
    more » « less