On Differentially Private Online Collaborative Recommendation Systems

In collaborative recommendation systems, privacy may be compromised, as users' opinions are used to generate recommendations for others. In this paper, we consider an online collaborative recommendation system, and we measure users' privacy in terms of the standard differential privacy. We give the first quantitative analysis of the trade-offs between recommendation quality and users' privacy in such a system by showing a lower bound on the best achievable privacy for any non-trivial algorithm, and proposing a near-optimal algorithm. From our results, we find that there is actually little trade-off between recommendation quality and privacy for any non-trivial algorithm. Our results also identify the key parameters that determine the best achievable privacy.

Comments: 35 pages, 2 figures

Similar Publications

In a recent paper, it is shown that functions of the form $L_1(x^3)+L_2(x^9)$, where $L_1$ and $L_2$ are linear, are a good source for construction of new infinite families of APN functions. In the present work we study necessary and sufficient conditions for such functions to be APN. Read More


A crucial privacy-driven issue nowadays is re-identifying anonymized social networks by mapping them to correlated cross-domain auxiliary networks. Prior works are typically based on modeling social networks as random graphs representing users and their relations, and subsequently quantify the quality of mappings through cost functions that are proposed without sufficient rationale. Also, it remains unknown how to algorithmically meet the demand of such quantifications, i. Read More


Since fall 2012, several National Centers of Academic Excellence in Cyber Defense Research (CAE-Rs) fielded a collaborative course to engage students in solving applied cybersecurity research problems. We describe our experiences with this Information Security Research and Education (INSuRE) research collaborative. We explain how we conducted our project-based research course, give examples of student projects, and discuss the outcomes and lessons learned. Read More


Bitcoin is a popular alternative to fiat money, widely used for its perceived anonymity properties. However, recent attacks on Bitcoin's peer-to-peer (P2P) network demonstrated that its gossip-based flooding protocols, which are used to ensure global network consistency, may enable user deanonymization---the linkage of a user's IP address with her pseudonym in the Bitcoin network. In 2015, the Bitcoin community responded to these attacks by changing the network's flooding mechanism to a different protocol, known as diffusion. Read More


In this paper, we present a simple bare-bones solution of a Zero-Knowledge authentication protocol which uses non-commutative algebra and a variation of the generalized symmetric decomposition problem (GSDP) as a one-way function. The cryptographic security is assured as long the GSDP problem is computationally hard to solve in non-commutative algebraic structures and belongs currently to the PQC category as no quantum computer attack is likely to exists. Read More


The increasing popular interest in personal telemetry, also called the Quantified Self or "lifelogging", has induced a popularity surge for wearable personal fitness trackers. Fitness trackers automatically collect sensor data about the user throughout the day, and integrate it into social network accounts. Solution providers have to strike a balance between many constraints, leading to a design process that often puts security in the back seat. Read More


A block cipher is a bijective function that transforms a plaintext to a ciphertext. A block cipher is a principle component in a cryptosystem because the security of a cryptosystem depends on the security of a block cipher. A Feistel network is the most widely used method to construct a block cipher. Read More


In this paper we compare the performance of various homomorphic encryption methods on a private search scheme that can achieve $k$-anonymity privacy. To make our benchmarking fair, we use open sourced cryptographic libraries which are written by experts and well scrutinized. We find that Goldwasser-Micali encryption achieves good enough performance for practical use, whereas fully homomorphic encryptions are much slower than partial ones like Goldwasser-Micali and Paillier. Read More


Here, we proposed an improved version of the deterministic random extractors $SEJ$ and $PEJ$ proposed by R. R. Farashahi in \cite{F} in 2009. Read More


In 2003 Dinur and Nissim showed an impossibility result for privacy that if the amount of noise is $o(\sqrt{n})$, then privacy is impossible to achieve (where the output space is binary "Yes" or "No"). $\Omega({\sqrt{n}})$ noise must be added to have at least weak notions of privacy. However, the question has remained open as to whether $O(n)$ noise is able to preserve accuracy in elementary private data operations such as aggregation and averaging in addition to protecting privacy both before and after data aggregation. Read More