Paul Cuff

Shang Shang, Paul Cuff, Pan Hui et al.

We analyze a class of distributed quantized consensus algorithms for arbitrary static networks. In the initial setting, each node in the network has an integer value. Nodes exchange their current estimate of the mean value in the network, and then update their estimation by communicating with their neighbors in a limited capacity channel in an asynchronous clock setting. Eventually, all nodes reach consensus with quantized precision. We analyze the expected convergence time for the general quantized consensus algorithm proposed by Kashyap et al \cite{Kashyap}. We use the theory of electric networks, random walks, and couplings of Markov chains to derive an $O(N^3\log N)$ upper bound for the expected convergence time on an arbitrary graph of size $N$, improving on the state of art bound of $O(N^5)$ for quantized consensus algorithms. Our result is not dependent on graph topology. Example of complete graphs is given to show how to extend the analysis to graphs of given topology.

Paul Cuff, Lanqing Yu

Differential privacy is a precise mathematical constraint meant to ensure privacy of individual pieces of information in a database even while queries are being answered about the aggregate. Intuitively, one must come to terms with what differential privacy does and does not guarantee. For example, the definition prevents a strong adversary who knows all but one entry in the database from further inferring about the last one. This strong adversary assumption can be overlooked, resulting in misinterpretation of the privacy guarantee of differential privacy. Herein we give an equivalent definition of privacy using mutual information that makes plain some of the subtleties of differential privacy. The mutual-information differential privacy is in fact sandwiched between $ε$-differential privacy and $(ε,δ)$-differential privacy in terms of its strength. In contrast to previous works using unconditional mutual information, differential privacy is fundamentally related to conditional mutual information, accompanied by a maximization over the database distribution. The conceptual advantage of using mutual information, aside from yielding a simpler and more intuitive definition of differential privacy, is that its properties are well understood. Several properties of differential privacy are easily verified for the mutual information alternative, such as composition theorems.

Sameer Wagh, Paul Cuff, Prateek Mittal

In this work, we investigate if statistical privacy can enhance the performance of ORAM mechanisms while providing rigorous privacy guarantees. We propose a formal and rigorous framework for developing ORAM protocols with statistical security viz., a differentially private ORAM (DP-ORAM). We present Root ORAM, a family of DP-ORAMs that provide a tunable, multi-dimensional trade-off between the desired bandwidth overhead, local storage and system security. We theoretically analyze Root ORAM to quantify both its security and performance. We experimentally demonstrate the benefits of Root ORAM and find that (1) Root ORAM can reduce local storage overhead by about 2x for a reasonable values of privacy budget, significantly enhancing performance in memory limited platforms such as trusted execution environments, and (2) Root ORAM allows tunable trade-offs between bandwidth, storage, and privacy, reducing bandwidth overheads by up to 2x-10x (at the cost of increased storage/statistical privacy), enabling significant reductions in ORAM access latencies for cloud environments. We also analyze the privacy guarantees of DP-ORAMs through the lens of information theoretic metrics of Shannon entropy and Min-entropy [16]. Finally, Root ORAM is ideally suited for applications which have a similar access pattern, and we showcase its utility via the application of Private Information Retrieval.

Shang Shang, Tiance Wang, Paul Cuff et al.

The potential risk of privacy leakage prevents users from sharing their honest opinions on social platforms. This paper addresses the problem of privacy preservation if the query returns the histogram of rankings. The framework of differential privacy is applied to rank aggregation. The error probability of the aggregated ranking is analyzed as a result of noise added in order to achieve differential privacy. Upper bounds on the error rates for any positional ranking rule are derived under the assumption that profiles are uniformly distributed. Simulation results are provided to validate the probabilistic analysis.

Jingbo Liu, Paul Cuff, Sergio Verdú

We show that for product sources, rate splitting is optimal for secret key agreement using limited one-way communication between two terminals. This yields an alternative information-theoretic-converse-style proof of the tensorization property of a strong data processing inequality originally studied by Erkip and Cover and amended recently by Anantharam et al. We derive a water-filling solution of the communication-rate--key-rate tradeoff for a wide class of discrete memoryless vector Gaussian sources which subsumes the case without an eavesdropper. Moreover, we derive an explicit formula for the maximum secret key per bit of communication for all discrete memoryless vector Gaussian sources using a tensorization property and a variation on the enhanced channel technique of Weingarten et al. Finally, a one-shot information spectrum achievability bound for key generation is proved from which we characterize the communication-rate--key-rate tradeoff for stationary Gaussian processes.

Eva C. Song, Paul Cuff, H. Vincent Poor

In this paper, the compression of an independent and identically distributed Gaussian source sequence is studied in an unsecure network. Within a game theoretic setting for a three-party noiseless communication network (sender Alice, legitimate receiver Bob, and eavesdropper Eve), the problem of how to efficiently compress a Gaussian source with limited secret key in order to guarantee that Bob can reconstruct with high fidelity while preventing Eve from estimating an accurate reconstruction is investigated. It is assumed that Alice and Bob share a secret key with limited rate. Three scenarios are studied, in which the eavesdropper ranges from weak to strong in terms of the causal side information she has. It is shown that one bit of secret key per source symbol is enough to achieve perfect secrecy performance in the Gaussian squared error setting, and the information theoretic region is not optimized by joint Gaussian random variables.

Curt Schieler, Paul Cuff

Secrecy in communication systems is measured herein by the distortion that an adversary incurs. The transmitter and receiver share secret key, which they use to encrypt communication and ensure distortion at an adversary. A model is considered in which an adversary not only intercepts the communication from the transmitter to the receiver, but also potentially has side information. Specifically, the adversary may have causal or noncausal access to a signal that is correlated with the source sequence or the receiver's reconstruction sequence. The main contribution is the characterization of the optimal tradeoff among communication rate, secret key rate, distortion at the adversary, and distortion at the legitimate receiver. It is demonstrated that causal side information at the adversary plays a pivotal role in this tradeoff. It is also shown that measures of secrecy based on normalized equivocation are a special case of the framework.

Shang Shang, Yuk Hui, Pan Hui et al.

Recommendation systems have received considerable attention in the recent decades. Yet with the development of information technology and social media, the risk in revealing private data to service providers has been a growing concern to more and more users. Trade-offs between quality and privacy in recommendation systems naturally arise. In this paper, we present a privacy preserving recommendation framework based on groups. The main idea is to use groups as a natural middleware to preserve users' privacy. A distributed preference exchange algorithm is proposed to ensure the anonymity of data, wherein the effective size of the anonymity set asymptotically approaches the group size with time. We construct a hybrid collaborative filtering model based on Markov random walks to provide recommendations and predictions to group members. Experimental results on the MovieLens and Epinions datasets show that our proposed methods outperform the baseline methods, L+ and ItemRank, two state-of-the-art personalized recommendation algorithms, for both recommendation precision and hit rate despite the absence of personal preference information.

Eva C. Song, Emina Soljanin, Paul Cuff et al.

Optical networks are vulnerable to physical layer attacks; wiretappers can improperly receive messages intended for legitimate recipients. Our work considers an aspect of this security problem within the domain of multimode fiber (MMF) transmission. MMF transmission can be modeled via a broadcast channel in which both the legitimate receiver's and wiretapper's channels are multiple-input-multiple-output complex Gaussian channels. Source-channel coding analyses based on the use of distortion as the metric for secrecy are developed. Alice has a source sequence to be encoded and transmitted over this broadcast channel so that the legitimate user Bob can reliably decode while forcing the distortion of wiretapper, or eavesdropper, Eve's estimate as high as possible. Tradeoffs between transmission rate and distortion under two extreme scenarios are examined: the best case where Eve has only her channel output and the worst case where she also knows the past realization of the source. It is shown that under the best case, an operationally separate source-channel coding scheme guarantees maximum distortion at the same rate as needed for reliable transmission. Theoretical bounds are given, and particularized for MMF. Numerical results showing the rate distortion tradeoff are presented and compared with corresponding results for the perfect secrecy case.

Curt Schieler, Paul Cuff

A secret key can be used to conceal information from an eavesdropper during communication, as in Shannon's cipher system. Most theoretical guarantees of secrecy require the secret key space to grow exponentially with the length of communication. Here we show that when an eavesdropper attempts to reconstruct an information sequence, as posed in the literature by Yamamoto, very little secret key is required to effect unconditionally maximal distortion; specifically, we only need the secret key space to increase unboundedly, growing arbitrarily slowly with the blocklength. As a corollary, even with a secret key of constant size we can still cause the adversary arbitrarily close to maximal distortion, regardless of the length of the information sequence.