Search

We propose a data-driven framework for optimizing privacy-preserving data release mechanisms to attain the information-theoretically optimal tradeoff between minimizing distortion of useful data and concealing specific sensitive information. Our approach employs adversarially-trained neural networks to implement randomized mechanisms and to perform a variational approximation of mutual information privacy. We validate our Privacy-Preserving Adversarial Networks (PPAN) framework via proof-of-concept experiments on discrete and continuous synthetic data, as well as the MNIST handwritten digits dataset. For synthetic data, our model-agnostic PPAN approach achieves tradeoff points very close to the optimal tradeoffs that are analytically-derived from model knowledge. In experiments with the MNIST data, we visually demonstrate a learned tradeoff between minimizing the pixel-level distortion versus concealing the written digit., Comment: 16 pages

Privacy-preserving data release mechanisms aim to simultaneously minimize information-leakage with respect to sensitive data and distortion with respect to useful data. Dependencies between sensitive and useful data results in a privacy-utility tradeoff that has strong connections to generalized rate-distortion problems. In this work, we study how the optimal privacy-utility tradeoff region is affected by constraints on the data that is directly available as input to the release mechanism. In particular, we consider the availability of only sensitive data, only useful data, and both (full data). We show that a general hierarchy holds: the tradeoff region given only the sensitive data is no larger than the region given only the useful data, which in turn is clearly no larger than the region given both sensitive and useful data. In addition, we determine conditions under which the tradeoff region given only the useful data coincides with that given full data. These are based on the common information between the sensitive and useful data. We establish these results for general families of privacy and utility measures that satisfy certain natural properties required of any reasonable measure of privacy or utility. We also uncover a new, subtler aspect of the data processing inequality for general non-symmetric privacy measures and discuss its operational relevance and implications. Finally, we derive exact closed-analytic-form expressions for the privacy-utility tradeoffs for symmetrically dependent sensitive and useful data under mutual information and Hamming distortion as the respective privacy and utility measures., Comment: 20 pages, 3 figures, under submission

For a number of lossy source coding problems it is shown that even if the usual single-letter sum-rate-distortion expressions may become invalid for non-infinite distortion functions, they can be approached, to any desired accuracy, via the usual valid expressions for appropriately truncated finite versions of the distortion functions., Comment: 4 pages

In the secure two-party computation problem, two parties wish to compute a (possibly randomized) function of their inputs via an interactive protocol, while ensuring that neither party learns more than what can be inferred from only their own input and output. For semi-honest parties and information-theoretic security guarantees, it is well-known that, if only noiseless communication is available, only a limited set of functions can be securely computed; however, if interaction is also allowed over general communication primitives (multi-input/output channels), there are "complete" primitives that enable any function to be securely computed. The general set of complete primitives was characterized recently by Maji, Prabhakaran, and Rosulek leveraging an earlier specialized characterization by Kilian. Our contribution in this paper is a simple, self-contained, alternative derivation using elementary information-theoretic tools., Comment: 6 pages, extended version of ITW 2014 paper

In game theory, a trusted mediator acting on behalf of the players can enable the attainment of correlated equilibria, which may provide better payoffs than those available from the Nash equilibria alone. We explore the approach of replacing the trusted mediator with an unconditionally secure sampling protocol that jointly generates the players' actions. We characterize the joint distributions that can be securely sampled by malicious players via protocols using error-free communication. This class of distributions depends on whether players may speak simultaneously ("cheap talk") or must speak in turn ("polite talk"). In applying sampling protocols toward attaining correlated equilibria with rational players, we observe that security against malicious parties may be much stronger than necessary. We propose the concept of secure sampling by rational players, and show that many more distributions are feasible given certain utility functions. However, the payoffs attainable via secure sampling by malicious players are a dominant subset of the rationally attainable payoffs., Comment: 4 pages, to appear at GlobalSIP 2013

BIOMETRICS are an important and widely used class of methods for identity verification and access control. Biometrics are attractive because they are inherent properties of an individual. They need not be remembered like passwords, and are not easily lost or forged like identifying documents. At the same time, bio- metrics are fundamentally noisy and irreplaceable. There are always slight variations among the measurements of a given biometric, and, unlike passwords or identification numbers, biometrics are derived from physical characteristics that cannot easily be changed. The proliferation of biometric usage raises critical privacy and security concerns that, due to the noisy nature of biometrics, cannot be addressed using standard cryptographic methods. In this article we present an overview of "secure biometrics", also referred to as "biometric template protection", an emerging class of methods that address these concerns., Comment: 16 pages, 11 figures, 1 table

The problem in which one of three pairwise interacting parties is required to securely compute a function of the inputs held by the other two, when one party may arbitrarily deviate from the computation protocol (active behavioral model), is studied. An information-theoretic characterization of unconditionally secure computation protocols under the active behavioral model is provided. A protocol for Hamming distance computation is provided and shown to be unconditionally secure under both active and passive behavioral models using the information-theoretic characterization. The difference between the notions of security under the active and passive behavioral models is illustrated through the BGW protocol for computing quadratic and Hamming distances; this protocol is secure under the passive model, but is shown to be not secure under the active model., Comment: 7 pages, 1 figure, submitted to ISIT 2013

We present a theoretical framework for the analysis of privacy and security tradeoffs in secure biometric authentication systems. We use this framework to conduct a comparative information-theoretic analysis of two biometric systems that are based on linear error correction codes, namely fuzzy commitment and secure sketches. We derive upper bounds for the probability of false rejection ($P_{FR}$) and false acceptance ($P_{FA}$) for these systems. We use mutual information to quantify the information leaked about a user's biometric identity, in the scenario where one or multiple biometric enrollments of the user are fully or partially compromised. We also quantify the probability of successful attack ($P_{SA}$) based on the compromised information. Our analysis reveals that fuzzy commitment and secure sketch systems have identical $P_{FR}, P_{FA}, P_{SA}$ and information leakage, but secure sketch systems have lower storage requirements. We analyze both single-factor (keyless) and two-factor (key-based) variants of secure biometrics, and consider the most general scenarios in which a single user may provide noisy biometric enrollments at several access control devices, some of which may be subsequently compromised by an attacker. Our analysis highlights the revocability and reusability properties of key-based systems and exposes a subtle design tradeoff between reducing information leakage from compromised systems and preventing successful attacks on systems whose data have not been compromised., Comment: 15 pages

Consider a network of k parties, each holding a long sequence of n entries (a database), with minimum vertex-cut greater than t. We show that any empirical statistic across the network of databases can be computed by each party with perfect privacy, against any set of t < k/2 passively colluding parties, such that the worst-case distortion and communication cost (in bits per database entry) both go to zero as n, the number of entries in the databases, goes to infinity. This is based on combining a striking dimensionality reduction result for random sampling with unconditionally secure multi-party computation protocols., Comment: 12 pages, 6 figures

In 1985 Kaspi provided a single-letter characterization of the sum-rate-distortion function for a two-way lossy source coding problem in which two terminals send multiple messages back and forth with the goal of reproducing each other's sources. Yet, the question remained whether more messages can strictly improve the sum-rate-distortion function. Viewing the sum-rate as a functional of the distortions and the joint source distribution and leveraging its convex-geometric properties, we construct an example which shows that two messages can strictly improve the one-message (Wyner-Ziv) rate-distortion function. The example also shows that the ratio of the one-message rate to the two-message sum-rate can be arbitrarily large and simultaneously the ratio of the backward rate to the forward rate in the two-message sum-rate can be arbitrarily small., Comment: 5 pages, submitted to IEEE International Symposium on Information Theory (ISIT) 2010

An interactive function computation problem in a collocated network is studied in a distributed block source coding framework. With the goal of computing a desired function at the sink, the source nodes exchange messages through a sequence of error-free broadcasts. The infinite-message minimum sum-rate is viewed as a functional of the joint source pmf and is characterized as the least element in a partially ordered family of functionals having certain convex-geometric properties. This characterization leads to a family of lower bounds for the infinite-message minimum sum-rate and a simple optimality test for any achievable infinite-message sum-rate. An iterative algorithm for evaluating the infinite-message minimum sum-rate functional is proposed and is demonstrated through an example of computing the minimum function of three sources., Comment: 5 pages. 2 figures. This draft has been submitted to IEEE International Symposium on Information Theory (ISIT) 2010

A two-terminal interactive function computation problem with alternating messages is studied within the framework of distributed block source coding theory. For any finite number of messages, a single-letter characterization of the sum-rate-distortion function was established in previous works using standard information-theoretic techniques. This, however, does not provide a satisfactory characterization of the infinite-message limit, which is a new, unexplored dimension for asymptotic-analysis in distributed block source coding involving potentially an infinite number of infinitesimal-rate messages. In this paper, the infinite-message sum-rate-distortion function, viewed as a functional of the joint source pmf and the distortion levels, is characterized as the least element of a partially ordered family of functionals having certain convex-geometric properties. The new characterization does not involve evaluating the infinite-message limit of a finite-message sum-rate-distortion expression. This characterization leads to a family of lower bounds for the infinite-message sum-rate-distortion expression and a simple criterion to test the optimality of any achievable infinite-message sum-rate-distortion expression. For computing the amplewise Boolean AND function, the infinite-message minimum sum-rates are characterized in closed analytic form. These sum-rates are shown to be achievable using infinitely many infinitesimal-rate messages. The new convex-geometric characterization is used to develop an iterative algorithm for evaluating any finite-message sumrate-distortion function. It is also used to construct the first examples which demonstrate that for lossy source reproduction, two messages can strictly improve the one-message Wyner-Ziv rate-distortion function settling an unresolved question from a 1985 paper., Comment: 40 pages, 5 figures. Submitted to IEEE Transactions on Information Theory in Sep 2010 and revised in Mar 2012. This version (version 3) is the latest revised version. Version 1 was published in Allerton Conference 2009. Version 2 contains extensions to the rate-distortion theory and an achievable proof of the sum-rate R* in the second example

We propose an information theoretic framework for the secure two-party function computation (SFC) problem and introduce the notion of SFC capacity. We study and extend string oblivious transfer (OT) to sample-wise OT. We propose an efficient, perfectly private OT protocol utilizing the binary erasure channel or source. We also propose the bootstrap string OT protocol which provides disjoint (weakened) privacy while achieving a multiplicative increase in rate, thus trading off security for rate. Finally, leveraging our OT protocol, we construct a protocol for SFC and establish a general lower bound on SFC capacity of the binary erasure channel and source., Comment: 5 pages, 2 figures. Submitted to 2009 IEEE International Symposium on Information Theory, Seoul, South Korea

We study the limits of communication efficiency for function computation in collocated networks within the framework of multi-terminal block source coding theory. With the goal of computing a desired function of sources at a sink, nodes interact with each other through a sequence of error-free, network-wide broadcasts of finite-rate messages. For any function of independent sources, we derive a computable characterization of the set of all feasible message coding rates - the rate region - in terms of single-letter information measures. We show that when computing symmetric functions of binary sources, the sink will inevitably learn certain additional information which is not demanded in computing the function. This conceptual understanding leads to new improved bounds for the minimum sum-rate. The new bounds are shown to be orderwise better than those based on cut-sets as the network scales. The scaling law of the minimum sum-rate is explored for different classes of symmetric functions and source parameters., Comment: 9 pages. A 5-page version without appendices was submitted to IEEE International Symposium on Information Theory (ISIT), 2009. This version contains complete proofs as appendices

A two-terminal interactive distributed source coding problem with alternating messages for function computation at both locations is studied. For any number of messages, a computable characterization of the rate region is provided in terms of single-letter information measures. While interaction is useless in terms of the minimum sum-rate for lossless source reproduction at one or both locations, the gains can be arbitrarily large for function computation even when the sources are independent. For a class of sources and functions, interaction is shown to be useless, even with infinite messages, when a function has to be computed at only one location, but is shown to be useful, if functions have to be computed at both locations. For computing the Boolean AND function of two independent Bernoulli sources at both locations, an achievable infinite-message sum-rate with infinitesimal-rate messages is derived in terms of a two-dimensional definite integral and a rate-allocation curve. A general framework for multiterminal interactive function computation based on an information exchange protocol which successively switches among different distributed source coding configurations is developed. For networks with a star topology, multiple rounds of interactive coding is shown to decrease the scaling law of the total network rate by an order of magnitude as the network grows., Comment: 30 pages, 6 figures. This work has been submitted to the IEEE for possible publication. Parts of this work were presented at 2008 IEEE International Symposium on Information Theory (ISIT'08)

This paper re-examines the well-known fundamental tradeoffs between rate and reliability for the multi-antenna, block Rayleigh fading channel in the high signal to noise ratio (SNR) regime when (i) the transmitter has access to (noiseless) one bit per coherence-interval of causal channel state information (CSI) and (ii) soft decoding delays together with worst-case delay guarantees are acceptable. A key finding of this work is that substantial improvements in reliability can be realized with a very short expected delay and a slightly longer (but bounded) worst-case decoding delay guarantee in communication systems where the transmitter has access to even one bit per coherence interval of causal CSI. While similar in spirit to the recent work on communication systems based on automatic repeat requests (ARQ) where decoding failure is known at the transmitter and leads to re-transmission, here transmit side-information is purely based on CSI. The findings reported here also lend further support to an emerging understanding that decoding delay (related to throughput) and codeword blocklength (related to coding complexity and delays) are distinctly different design parameters which can be tuned to control reliability., Comment: 5 pages, 2 figures, to appear in the Proceedings of the IEEE International Symposium on Information Theory, Nice, France, 24-29 June, 2007

The problem of sampling a discrete-time sequence of spatially bandlimited fields with a bounded dynamic range, in a distributed, communication-constrained, processing environment is addressed. A central unit, having access to the data gathered by a dense network of fixed-precision sensors, operating under stringent inter-node communication constraints, is required to reconstruct the field snapshots to maximum accuracy. Both deterministic and stochastic field models are considered. For stochastic fields, results are established in the almost-sure sense. The feasibility of having a flexible tradeoff between the oversampling rate (sensor density) and the analog-to-digital converter (ADC) precision, while achieving an exponential accuracy in the number of bits per Nyquist-interval per snapshot is demonstrated. This exposes an underlying ``conservation of bits'' principle: the bit-budget per Nyquist-interval per snapshot (the rate) can be distributed along the amplitude axis (sensor-precision) and space (sensor density) in an almost arbitrary discrete-valued manner, while retaining the same (exponential) distortion-rate characteristics. Achievable information scaling laws for field reconstruction over a bounded region are also derived: With N one-bit sensors per Nyquist-interval, $\Theta(\log N)$ Nyquist-intervals, and total network bitrate $R_{net} = \Theta((\log N)^2)$ (per-sensor bitrate $\Theta((\log N)/N)$), the maximum pointwise distortion goes to zero as $D = O((\log N)^2/N)$ or $D = O(R_{net} 2^{-\beta \sqrt{R_{net}}})$. This is shown to be possible with only nearest-neighbor communication, distributed coding, and appropriate interpolation algorithms. For a fixed, nonzero target distortion, the number of fixed-precision sensors and the network rate needed is always finite., Comment: 17 pages, 6 figures; paper withdrawn from IEEE Transactions on Signal Processing and re-submitted to the IEEE Transactions on Information Theory

The reconstruction of a deterministic data field from binary-quantized noisy observations of sensors which are randomly deployed over the field domain is studied. The study focuses on the extremes of lack of deterministic control in the sensor deployment, lack of knowledge of the noise distribution, and lack of sensing precision and reliability. Such adverse conditions are motivated by possible real-world scenarios where a large collection of low-cost, crudely manufactured sensors are mass-deployed in an environment where little can be assumed about the ambient noise. A simple estimator that reconstructs the entire data field from these unreliable, binary-quantized, noisy observations is proposed. Technical conditions for the almost sure and integrated mean squared error (MSE) convergence of the estimate to the data field, as the number of sensors tends to infinity, are derived and their implications are discussed. For finite-dimensional, bounded-variation, and Sobolev-differentiable function classes, specific integrated MSE decay rates are derived. For the first and third function classes these rates are found to be minimax order optimal with respect to infinite precision sensing and known noise distribution., Comment: 10 pages, 1 figure. Significantly expanded version with consideration of general deployment distribution models and new results ragarding almost sure convergence and minimax convergence rates. Submitted to Transactions on Signal Processing

Motivated by video coding applications, the problem of sequential coding of correlated sources with encoding and/or decoding frame-delays is studied. The fundamental tradeoffs between individual frame rates, individual frame distortions, and encoding/decoding frame-delays are derived in terms of a single-letter information-theoretic characterization of the rate-distortion region for general inter-frame source correlations and certain types of potentially frame specific and coupled single-letter fidelity criteria. The sum-rate-distortion region is characterized in terms of generalized directed information measures highlighting their role in delayed sequential source coding problems. For video sources which are spatially stationary memoryless and temporally Gauss-Markov, MSE frame distortions, and a sum-rate constraint, our results expose the optimality of idealized differential predictive coding among all causal sequential coders, when the encoder uses a positive rate to describe each frame. Somewhat surprisingly, causal sequential encoding with one-frame-delayed noncausal sequential decoding can exactly match the sum-rate-MSE performance of joint coding for all nontrivial MSE-tuples satisfying certain positive semi-definiteness conditions. Thus, even a single frame-delay holds potential for yielding significant performance improvements. Generalizations to higher order Markov sources are also presented and discussed. A rate-distortion performance equivalence between, causal sequential encoding with delayed noncausal sequential decoding, and, delayed noncausal sequential encoding with causal sequential decoding, is also established., Comment: 35 pages, 7 figures. This work has been submitted to the IEEE for possible publication. Parts of this work were presented at 2007 Information Theory and Applications Workshop (ITA'07) and 2007 IEEE International Symposium on Information Theory (ISIT'07)

This paper formulates and studies a general distributed field reconstruction problem using a dense network of noisy one-bit randomized scalar quantizers in the presence of additive observation noise of unknown distribution. A constructive quantization, coding, and field reconstruction scheme is developed and an upper-bound to the associated mean squared error (MSE) at any point and any snapshot is derived in terms of the local spatio-temporal smoothness properties of the underlying field. It is shown that when the noise, sensor placement pattern, and the sensor schedule satisfy certain weak technical requirements, it is possible to drive the MSE to zero with increasing sensor density at points of field continuity while ensuring that the per-sensor bitrate and sensing-related network overhead rate simultaneously go to zero. The proposed scheme achieves the order-optimal MSE versus sensor density scaling behavior for the class of spatially constant spatio-temporal fields., Comment: Fixed typos, otherwise same as V2. 27 pages (in one column review format), 4 figures. Submitted to IEEE Transactions on Signal Processing. Current version is updated for journal submission: revised author list, modified formulation and framework. Previous version appeared in Proceedings of Allerton Conference On Communication, Control, and Computing 2006

A broad set of sufficient conditions that guarantees the existence of the maximum entropy (maxent) distribution consistent with specified bounds on certain generalized moments is derived. Most results in the literature are either focused on the minimum cross-entropy distribution or apply only to distributions with a bounded-volume support or address only equality constraints. The results of this work hold for general moment inequality constraints for probability distributions with possibly unbounded support, and the technical conditions are explicitly on the underlying generalized moment functions. An analytical characterization of the maxent distribution is also derived using results from the theory of constrained optimization in infinite-dimensional normed linear spaces. Several auxiliary results of independent interest pertaining to certain properties of convex coercive functions are also presented., Comment: 13 pages; accepted for publication in the IEEE Transactions on Information Theory