In the online setting, a user continuously releases a time-series that is correlated with his private data, to a service provider to derive some utility. Due to correlations, the continual observation of the time-series puts the user at risk of inference attacks against his private data. To protect the user's privacy, the time-series is randomized prior to its release according to a probabilistic privacy mapping. This mapping should be designed in a way that balances privacy and utility requirements over time. First, we formalize the framework for the design of utility-aware privacy mappings for time-series, under both online and batch models. We introduce two threat models, for which we respectively show that under the log-loss cost function, the information leakage can be modeled by the mutual or directed information between the randomized time-series and the private data. Second, we prove that the design of the privacy mapping can be cast as a convex optimization. We provide a sequential online scheme that allows to design privacy mappings at scale, that accounts for privacy risk from the history of released data and future releases to come. Third, we prove the equivalence of the optimal mappings under the batch and the online models, in the case of a Hidden Markov Model. Evaluations on real-world time-series data show that smart-meter data can be randomized to prevent disaggregation of per-device energy consumption, while maintaining the utility of the randomized series.

We focus on the privacy-utility trade-off encountered by users who wish to disclose some information to an analyst, that is correlated with their private data, in the hope of receiving some utility. We rely on a general privacy statistical inference framework, under which data is transformed before it is disclosed, according to a probabilistic privacy mapping. We show that when the log-loss is introduced in this framework in both the privacy metric and the distortion metric, the privacy leakage and the utility constraint can be reduced to the mutual information between private data and disclosed data, and between non-private data and disclosed data respectively. We justify the relevance and generality of the privacy metric under the log-loss by proving that the inference threat under any bounded cost function can be upperbounded by an explicit function of the mutual information between private data and disclosed data. We then show that the privacy-utility tradeoff under the log-loss can be cast as the non-convex Privacy Funnel optimization, and we leverage its connection to the Information Bottleneck, to provide a greedy algorithm that is locally optimal. We evaluate its performance on the US census dataset. Finally, we characterize the optimal privacy mapping for the Gaussian Privacy Funnel.

Online services routinely mine user data to predict user preferences, make recommendations, and place targeted ads. Recent research has demonstrated that several private user attributes (such as political affiliation, sexual orientation, and gender) can be inferred from such data. Can a privacy-conscious user benefit from personalization while simultaneously protecting her private attributes? We study this question in the context of a rating prediction service based on matrix factorization. We construct a protocol of interactions between the service and users that has remarkable optimality properties: it is privacy-preserving, in that no inference algorithm can succeed in inferring a user's private attribute with a probability better than random guessing; it has maximal accuracy, in that no other privacy-preserving protocol improves rating prediction; and, finally, it involves a minimal disclosure, as the prediction accuracy strictly decreases when the service reveals less information. We extensively evaluate our protocol using several rating datasets, demonstrating that it successfully blocks the inference of gender, age and political affiliation, while incurring less than 5% decrease in the accuracy of rating prediction.

In many monitoring applications, recent data is more important than distant data. How does this affect privacy of data analysis? We study a general class of data analyses --- predicate sums --- in this context.

This paper shows how to reduce the otherwise hard joint relay positioning and flow optimization problem into a sequence a two simpler decoupled problems. We consider a class of wireless multicast hypergraphs not limited by interference and are mainly characterized by their hyperarc rate functions, that are increasing and convex in power, and decreasing in distance between the transmit node and the farthest end node of the hyperarc. The set-up consists of a single multicast flow session involving a source, multiple destinations and a relay that can be positioned freely. The first problem formulates the relay positioning problem in a purely geometric sense, and once the optimal relay position is obtained the second problem addresses the flow optimization. Furthermore, simple and efficient algorithms are presented that solve these problems.

We consider the broadcast relay channel (BRC), where a single source transmits to multiple destinations with the help of a relay, in the limit of a large bandwidth. We address the problem of optimal relay positioning and power allocations at source and relay, to maximize the multicast rate from source to all destinations. To solve such a network planning problem, we develop a three-faceted approach based on an underlying information theoretic model, computational geometric aspects, and network optimization tools. Firstly, assuming superposition coding and frequency division between the source and the relay, the information theoretic framework yields a hypergraph model of the wideband BRC, which captures the dependency of achievable rate-tuples on the network topology. As the relay position varies, so does the set of hyperarcs constituting the hypergraph, rendering the combinatorial nature of optimization problem. We show that the convex hull C of all nodes in the 2-D plane can be divided into disjoint regions corresponding to distinct hyperarcs sets. These sets are obtained by superimposing all k-th order Voronoi tessellation of C. We propose an easy and efficient algorithm to compute all hyperarc sets, and prove they are polynomially bounded. Then, we circumvent the combinatorial nature of the problem by introducing continuous switch functions, that allows adapting the network hypergraph in a continuous manner. Using this switched hypergraph approach, we model the original problem as a continuous yet non-convex network optimization program. Ultimately, availing on the techniques of geometric programming and p-norm surrogate approximation, we derive a good convex approximation. We provide a detailed characterization of the problem for collinearly located destinations, and then give a generalization for arbitrarily located destinations. Finally, we show strong gains for the optimal relay positioning compared to seemingly interesting positions.

Abstract-We provide a geometric solution to the problem of optimal relay positioning to maximize the multicast rate for low SNR networks. The network we consider consists of a single source, multiple receivers and the only intermediate and locatable node as the relay. We construct network the hypergraph of the system nodes from the underlying information theoretic model of low-SNR regime that operates using superposition coding and FDMA in conjunction (which we call the "achievable hypergraph model"). We make the following contributions. 1) We show that the problem of optimal relay positioning maximizing the multicast rate can be completely decoupled from the flow optimization by noticing and exploiting geometric properties of multicast flow. 2) All the flow maximizing the multicast rate is sent over at most two paths, in succession. The relay position depends on only one path (out of the two), irrespective of the number of receiver nodes in the system. Subsequently, we propose simple and efficient geometric algorithms to compute the optimal relay position. 3) Finally, we show that in our model at the optimal relay position, the difference between the maximized multicast rate and the cut-set bound is minimum. We solve the problem for all (Ps,Pr) pairs of source and relay transmit powers and the path loss exponent α ≥ 2.

We investigate the multipath fading relay channel in the limit of a large bandwidth, and in the non-coherent setting, where the channel state is unknown to all terminals, including the relay and the destination. We derive a lower bound on the capacity by proposing and analyzing a peaky frequency binning scheme. The achievable rate obtained coincides with the block-Markov lower bound on the capacity of the wideband frequency-division Gaussian relay channel. When the broadcast channel is physically degraded, this achievable rate meets the cut-set upper-bound, and thus reaches the capacity of the noncoherent wideband multipath fading relay channel. In this case, a hypergraph model of the multipath fading relay channel is proposed, and the relaying scheme of concern is shown to reach its min-cut. Even if the source treats the broadcast channel as physically degraded when it is stochastically degraded, the achievable hypergraph bound is the min-cut.

A multihop relaying system is analyzed where data sent by a multi-antenna source is relayed by successive multi-antenna relays until it reaches a multi-antenna destination. Assuming correlated fading at each hop, each relay receives a faded version of the signal from the previous level, performs linear precoding and retransmits it to the next level. Using free probability theory and assuming that the noise power at relays— but not at destination— is negligible, the closed-form expression of the asymptotic instantaneous end-to-end mutual information is derived as the number of antennas at all levels grows large. The so-obtained deterministic expression is independent from the channel realizations while depending only on channel statistics. This expression is also shown to be equal to the asymptotic average end-to-end mutual information. The singular vectors of the optimal precoding matrices, maximizing the average mutual information with finite number of antennas at all levels, are also obtained. It turns out that these vectors are aligned to the eigenvectors of the channel correlation matrices. Thus, they can be determined using only the channel statistics. As the structure of the singular vectors of the optimal precoders is independent from the system size, it is also optimal in the asymptotic regime.

We investigate the multipath fading relay channel in the limit of a large bandwidth, and in the non-coherent setting, where the channel state is unknown to all terminals, including the relay and the destination.We propose a hypergraph model of the wideband multipath fading relay channel, and show that its min-cut is achieved by a non-coherent peaky frequency binning scheme. The so-obtained lower bound on the capacity of the wideband multipath fading relay channel turns out to coincide with the block-Markov lower bound on the capacity of the wideband frequency-division Gaussian (FD-AWGN) relay channel. In certain cases, this achievable rate also meets the cut-set upper-bound, and thus reaches the capacity of the non-coherent wideband multipath fading relay channel.

We analyze a multi-level MIMO relaying system where a multiple-antenna transmitter sends data to a multiple-antenna receiver through several relay levels, also equipped with multiple antennas. Assuming correlated fading in each hop, each relay receives a faded version of the signal transmitted by the previous level, performs precoding on the received signal and retransmits it to the next level. Using free probability theory and assuming that the noise power at the relay levels - but not at the receiver - is negligible, a closed-form expression of the end-to-end asymptotic instantaneous mutual information is derived as the number of antennas in all levels grow large with the same rate. This asymptotic expression is shown to be independent from the channel realizations, to only depend on the channel statistics and to also serve as the asymptotic value of the end-to-end average mutual information. We also provide the optimal singular vectors of the precoding matrices that maximize the asymptotic mutual information : the optimal transmit directions represented by the singular vectors of the precoding matrices are aligned on the eigenvectors of the channel correlation matrices, therefore they can be determined only using the known statistics of the channel matrices and do not depend on a particular channel realization.

We propose a dynamic blind beamforming scheme which allows to benefit from antenna directivity in large mobile ad hoc networks while avoiding heavy feedback to track mobile nodes localization. By orienting its directional antenna successively in all directions, a source surely but blindly hits its destination without knowing its exact position. Performance is analyzed in terms of total network throughput and connectivity and the optimal number of rotations allowing to maximize performance is shown to result from a trade-off between delay and improvements in terms of interference. In large ad hoc networks, known to be interference limited, we show that dynamic blind beamforming can outperform omnidirectional transmissions both in terms of capacity and connectivity.

We develop and analyze new cooperative strategies for ad hoc networks that are more spectrally efficient than classical decode & forward (DF) protocols. Using analog network coding, our strategies preserve the practical half-duplex assumption but relax the orthogonality constraint. The introduction of interference due to non-orthogonality is mitigated thanks to precoding, in particular dirty paper coding. Combined with smart power allocation, our cooperation strategies allow to save time and lead to a more efficient use of the bandwidth and to improved network throughput with respect to classical repetition-DF and parallel-DF.