University of Surrey

Test tubes in the lab Research in the ATI Dance Research

Private Discovery of Common Social Contacts

Cristofaro, ED, Manulis, M and Poettering, B (2011) Private Discovery of Common Social Contacts In: 9th International Conference on Applied Cryptography and Network Security (ACNS 2011), 2011-06-07 - 2011-06-10, Nerja, Spain.

[img]
Preview
PDF
DeMaPo_ACNS11.pdf
Available under License : See the attached licence file.

Download (290kB)
[img]
Preview
PDF (licence)
SRI_deposit_agreement.pdf

Download (33kB)

Abstract

The increasing use of computing devices for social interactions propels the proliferation of online social applications, yet, it prompts a number of privacy concerns. One common problem occurs when two unfamiliar users, in the process of establishing social relationships, want to assess their social proximity by discovering mutual contacts. In this paper, we introduce Private Contact Discovery, a novel cryptographic primitive that lets two users, on input their respective contact lists, learn their common contacts (if any), and nothing else. We present an efficient and provably secure construction, that (i) prevents arbitrary list manipulation by means of contact certification, and (ii) guarantees user authentication and revocability. Following a rigorous cryptographic treatment of the problem, we define the privacy-protecting contact-hiding property and prove it for our solution, under the RSA assumption in the Random Oracle Model (ROM). We also show that other related cryptographic techniques, such as Private Set Intersection and Secret Handshakes, are unsuitable in this context. Experimental analysis attests to the practicality of our technique, which achieves computational and communication overhead (almost) linear in the number of contacts.

Item Type: Conference or Workshop Item (Conference Paper)
Divisions : Faculty of Engineering and Physical Sciences > Computing Science
Authors :
AuthorsEmailORCID
Cristofaro, EDUNSPECIFIEDUNSPECIFIED
Manulis, MUNSPECIFIEDUNSPECIFIED
Poettering, BUNSPECIFIEDUNSPECIFIED
Date : 2011
Identification Number : 10.1007/978-3-642-21554-4_9
Contributors :
ContributionNameEmailORCID
PublisherSpringer Berlin Heidelberg, UNSPECIFIEDUNSPECIFIED
Additional Information : The original publication is available at http://www.springerlink.com
Depositing User : Symplectic Elements
Date Deposited : 12 Jun 2013 13:42
Last Modified : 09 Jun 2014 13:32
URI: http://epubs.surrey.ac.uk/id/eprint/755197

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year


Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800