Privacy-Preserving Function Computation by Exploitation of Friendships in Social Networks

We study the problem of privacy-preserving computation of functions of data that belong to users in a social network under the assumption that users are willing to share their private data with trusted friends in the network. We demonstrate that such trust relationships can be exploited to significantly improve the trade-off between the privacy of users’ data and the accuracy of the computation. Under a one-hop trust model we design an algorithm for partitioning the users into circles of trust and develop a differentially private scheme for computing the global function using results of local computations within each circle. We quantify the improvement in the privacy--accuracy trade-off of our scheme with respect to other mechanisms that do not exploit inter-user trust. We verify the efficiency of our algorithm by implementing it on social networks with up to one million nodes. Applications of our method include surveys, elections, and recommendation systems.


Published in:
2014 Ieee International Conference On Acoustics, Speech And Signal Processing (Icassp), 6250-6254
Presented at:
IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Florence, Italy, May 4-9, 2014
Year:
2014
Publisher:
New York, Ieee
ISSN:
1520-6149
ISBN:
978-1-4799-2893-4
Laboratories:




 Record created 2014-02-10, last modified 2018-09-13

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)