Location Privacy via Private Proximity Testing.
Published 1 January 2011
Arvind Narayanan, Narendran Thiagarajan, Mugdha Lakhani, Michael Hamburg, Dan Boneh
Citations325
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work describes several secure protocols that support private proximity testing at various levels of granularity and studies the use of “location tags” generated from the physical environment in order to strengthen the security of proximity testing.
Abstract
We study privacy-preserving tests for proximity: Alice can test if she is close to Bob without either party revealing any other information about their location. We describe several secure protocols that support private proximity testing at various levels of granularity. We study the use of “location tags ” generated from the physical environment in order to strengthen the security of proximity testing. We implemented our system on the Android platform and report on its effectiveness. Our system uses a social network (Facebook) to manage user public keys. 1
Keywords
Computer Science
Choice Reviews OnlineHandbook of applied cryptography
10,469 Citations1997Menezes, Alfred J., Oorschot, Paul C. van +1 more
Fully homomorphic encryption using ideal lattices
6,381 Citations2009Craig Gentry
This work proposes a fully homomorphic encryption scheme that allows one to evaluate circuits over encrypted data without being able to decrypt, and describes a public key encryption scheme using ideal lattices that is almost bootstrappable.
How to generate and exchange secrets
3,712 Citations1986Andrew Chi-Chih Yao
It is shown how two parties A and B can interactively generate a random integer N = p¿q such that its secret, i.e., the prime factors, is hidden from either party individually but is recoverable jointly if desired.
Completeness theorems for non-cryptographic fault-tolerant distributed computation
2,515 Citations1988Michael Ben-Or, Avi Wigderson
The above bounds on t, where t is the number of players in actors, are tight!
Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking
2,283 Citations2003Marco Gruteser, Dirk Grunwald
A middleware architecture and algorithms that can be used by a centralized location broker service that adjusts the resolution of location information along spatial or temporal dimensions to meet specified anonymity constraints based on the entities who may be using location services within a given area.
Proceedings of the National Academy of SciencesInferring friendship network structure by using mobile phone data
1,886 Citations2009Nathan Eagle, Alex Pentland +1 more
It is demonstrated that it is possible to accurately infer 95% of friendships based on the observational data alone, where friend dyads demonstrate distinctive temporal and spatial patterns in their physical proximity and calling patterns that allow the prediction of individual-level outcomes such as job satisfaction.
IEEE Pervasive ComputingLocation privacy in pervasive computing
1,567 Citations2003Alastair R. Beresford, Frank Stajano
The mix zone is introduced-a new construction inspired by anonymous communication techniques-together with metrics for assessing user anonymity, based on frequently changing pseudonyms.
De-anonymizing Social Networks
1,321 Citations2009Arvind Narayanan, Vitaly Shmatikov
A framework for analyzing privacy and anonymity in social networks is presented and a new re-identification algorithm targeting anonymized social-network graphs is developed, showing that a third of the users who can be verified to have accounts on both Twitter and Flickr can be re-identified in the anonymous Twitter graph.
Lecture notes in computer scienceEfficient Private Matching and Set Intersection
1,254 Citations2004Michael J. Freedman, Kobbi Nissim +1 more
This work considers the problem of computing the intersection of private datasets of two parties, where the datasets contain lists of elements taken from a large domain, and presents protocols, based on the use of homomorphic encryption and balanced hashing, for both semi-honest and malicious environments.
Why Johnny can't encrypt: a usability evaluation of PGP 5.0
1,094 Citations1999Alma Whitten, J. D. Tygar
It is concluded that PGP 5.0 is not usable enough to provide effective security for most computer users, despite its attractive graphical user interface, supporting the hypothesis that user interface design for effective security remains an open problem.
The security of vehicular ad hoc networks
970 Citations2005Maxim Raya, Jean‐Pierre Hubaux
A set of security protocols are provided, it is shown that they protect privacy and the robustness of these protocols are analyzed, and a quantitative assessment of the proposed solution is carried out.
Private queries in location based services
752 Citations2008Gabriel Ghinita, Panos Kalnis +3 more
This work proposes a novel framework to support private location-dependent queries, based on the theoretical work on Private Information Retrieval (PIR), which achieves stronger privacy for snapshots of user locations and is the first to provide provable privacy guarantees against correlation attacks.
A distributed trust model
705 Citations1997Alfarez Abdul-Rahman, Stephen Hailes
This paper outlines the shortcomings of current security approaches for managing trust and proposes a model for trust, based on distributed recommendations, that can be used for secure on-line interaction.
Bounded-width polynomial-size branching programs recognize exactly those languages in <i>NC</i><sup>1</sup>
683 Citations1986David A. Mix Barrington
The method of proof is extended to investigate the complexity of the word problem for a fixed permutation group and show that polynomial size circuits of width 4 also recognize exactly nonuniform NC 1.
Lecture notes in computer sciencePrivacy-Preserving Set Operations
650 Citations2005Lea Kissner, Dawn Song
By building a framework of multiset operations, employing the mathematical properties of polynomials, this work designs efficient, secure, and composable methods to enable privacy-preserving computation of the union, intersection, and element reduction operations.
Oblivious transfer and polynomial evaluation
630 Citations1999Moni Naor, Benny Pinkas
The efficiency of the new OT protocols makes them useful for a variety of applications, including oblivious sampling which can be used to securely compare the sizes of web search engines, protocols for privately solving the list intersection problem and for mutually authenticated key exchange based on (possibly weak) passwords, and protocols for anonymity preserving web usage metering.
Secure verification of location claims
613 Citations2003Naveen Sastry, Umesh Shankar +1 more
The Echo protocol is extremely lightweight: it does not require time synchronization, cryptography, or very precise clocks, and it is believed that it is well suited for use in small, cheap, mobile devices.
Persona
495 Citations2009Randy Baden, Adam Bender +3 more
This work presents Persona, an OSN where users dictate who may access their information, and describes an implementation of Persona that replicates Facebook applications and shows how Persona provides the functionality of existing online social networks with additional privacy benefits.
Lecture notes in computer sciencePractical Private Set Intersection Protocols with Linear Complexity
413 Citations2010Emiliano De Cristofaro, Gene Tsudik
This paper explores some PSI variations and constructs several secure protocols that are appreciably more efficient than the state-of-the-art.
Lecture notes in computer scienceOn the Anonymity of Home/Work Location Pairs
373 Citations2009Philippe Golle, Kurt Partridge
If the approximate locations of an individual's home and workplace can both be deduced from a location trace, then the median size of the individual's anonymity set in the U.S. working population is 1, 21 and 34,980.
PKCS #5: Password-Based Cryptography Specification Version 2.0
366 Citations2000Burton S. Kaliski
This memo represents a republication of PKCS #5 v2.0 from RSA Laboratories' Public-Key Cryptography Standards (PKCS) series, and change control is retained within the PKCS process.
Lecture notes in computer scienceEfficient Oblivious Pseudorandom Function with Applications to Adaptive OT and Secure Computation of Set Intersection
297 Citations2009Stanisław Jarecki, Xiaomin Liu
It is shown that the OPRF implies a new practical fully-simulatable adaptive adaptive (and committed) OT protocol secure without ROM and implies the first secure computation protocol of set intersection on committed data with computational cost of O (N ) exponentiations where N is the maximum size of both data sets.
Lecture notes in computer scienceEfficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries
266 Citations2008Carmit Hazay, Yehuda Lindell
Lecture notes in computer scienceSecure Multi-party Computational Geometry
235 Citations2001Mikhail J. Atallah, Wenliang Du
This paper gives simple solutions to some specific geometric problems and develops some building blocks that it is believed will be useful in the solution of other geometric and combinatorial problems as well.
Preserving location privacy in wireless lans
212 Citations2007Tao Jiang, Helen J. Wang +1 more
This paper analyzes the problem of location privacy in wireless networks and presents a protocol for improving location privacy, which allows users to choose the level of privacy they desire, thereby increasing the performance of less private users (while not sacrificing private users' privacy at the same time).
Communications of the ACMComparing information without leaking it
202 Citations1996Ronald Fagin, Moni Naor +1 more
This work considers simple means by which two people may determine whether they possess the same information without revealing anything else to each other in case of disagreement.
Lecture notes in computer scienceFast Secure Computation of Set Intersection
189 Citations2010Stanisław Jarecki, Xiaomin Liu
It is shown that a simple protocol using |X|+4|Y| modular exponentiations and one round of interaction is a secure computation of the adaptive set intersection functionality against malicious adversaries in the Random Oracle Model (ROM) under a One-More Gap Diffie-Hellman (OMGDH) assumption.
Lecture notes in computer scienceLouis, Lester and Pierre: Three Protocols for Location Privacy
180 Citations2007Ge Zhong, Ian Goldberg +1 more
This paper introduces three protocols--Louis, Lester and Pierre--that provide location privacy for a service that alerts people of nearby friends that are distributed and do not require a separate service provider that is aware of people's locations.
Discrete Applied MathematicsA fair and efficient solution to the socialist millionaires’ problem
176 Citations2001Fabrice Boudot, Berry Schoenmakers +1 more
In this paper, a solution to the Tierce problem is presented, in which two players want to know whether they have backed the same combination (but neither player wants to disclose its combination to the other one).
Lecture notes in computer scienceEfficient Robust Private Set Intersection
164 Citations2009Dana Dachman-Soled, Tal Malkin +2 more
N-smarts
162 Citations2008Richard E. Honicky, Kyle Palos +2 more
A hardware and software platform for exploring algorithms and data gathered from pollution sensors integrated into cell phones, and discusses the main research agenda going forward.
Journal of the ACMEfficient generation of shared RSA keys
153 Citations2001Dan Boneh, Matthew Franklin
Efficient techniques for a number of parties to jointly generate an RSA key are described and each party holds a share of the private exponent that enables threshold decryption.
Privately querying location-based services with SybilQuery
131 Citations2009Pravin Shankar, Vinod Ganapathy +1 more
The design and implementation of SybilQuery is presented, a fully decentralized and autonomous k-anonymization-based scheme to privately query location-based services and can efficiently generate Sybil queries, which are indistinguishable from real queries.
Lecture notes in computer sciencePrivate Intersection of Certified Sets
119 Citations2009Jan Camenisch, Gregory M. Zaverucha
This paper introduces certified sets to the private set intersection problem, a trusted party ensures the inputs are valid and binds them to each participant, and improves existing malicious modelPrivate set intersection protocols by a constant factor.
Lecture notes in computer scienceVerifiable Homomorphic Oblivious Transfer and Private Equality Test
106 Citations2003Helger Lipmaa
A slightly modified version of the Aiello-Ishai-Reingold oblivious transfer protocol from Eurocrypt 2001 is described, which will be what the authors call weakly secure when coupled with many different homomorphic semantically secure public-key cryptosystems.
VPriv: protecting privacy in location-based vehicular services
105 Citations2009Raluca Ada Popa, Hari Balakrishnan +1 more
VPriv provides the first practical protocol to compute path functions for various kinds of tolling, speed and delay estimation, and insurance calculations in a way that does not reveal anything more than the result of the function to the server, and an out-of-band enforcement mechanism using random spot checks that allows the server and application to handle misbehaving users.
Cybercasing the joint: on the privacy implications of geo-tagging
105 Citations2010Gerald Friedland, Robin Sommer
It is argued that the security and privacy community needs to shape the further development of geo-location technology for better protecting users from the consequences of using geo-tagged information to mount real-world attacks.
Lecture notes in computer scienceA Location Privacy Aware Friend Locator
78 Citations2009Laurynas Šikšnys, Jeppe Rishede Thomsen +3 more
This work develops a client-server solution for proximity detection based on an encrypted, grid-based mapping of locations that is efficient and scalable to a large number of users.
Calhoun: The Naval Postgraduate School Institutional Archive (Naval Postgraduate School)A Location Based Encryption Technique and Some of Its Applications
69 Citations2003Logan Scott, Dorothy E. Denning
Journal of CryptologyEfficient Set Operations in the Presence of Malicious Adversaries
59 Citations2011Carmit Hazay, Kobbi Nissim
We saw each other on the subway
35 Citations2009Justin Manweiler, Ryan Scudellari +2 more
K-anonymity techniques to maintain location privacy and cryptographic techniques to provide both a proof of this co-location and an end-to-end confidential channel that is invulnerable to server snooping and man-in-the-middle attacks are presented.
Capturing social networking privacy preferences
34 Citations2009Ramprasad Ravichandran, Michael Benisch +2 more
It is suggested that providing users with a small number of canonical default policies to choose from can help reduce user burden when it comes to customizing the rich privacy settings they seem to require.
Computer Law & Security ReportThe tolls of privacy: An underestimated roadblock for electronic toll collection usage
34 Citations2008Patrick Riley
It is suggested that either a change in consumers' perception of privacy in the FasTrak system, or a fiduciary compensation must be offered to Bay Area drivers' in exchange for their perceived reduction of privacy, if any significant increase of FasTraK usage is to be achieved.
Geoencryption Using Loran
28 Citations2007Di Qiu, Sherman Lo +3 more
The benefits of using Loran forGeoencryption and the implementation of geoenc encryption on Loran are examined.
IACR Cryptology ePrint ArchiveFaceTrust: assessing the credibility of online personas via social networks
22 Citations2009Michael Sirivianos
Proceedings of the 2009 International Technical Meeting of The Institute of NavigationRobust Location Tag Generation from Noisy Location Data for Security Applications
15 Citations2009Di Qiu, Dan Boneh +2 more
Fuzzy extractor scheme to generate strong location tag from noisy location data is proposed and different constructions of fuzzy extractor for various parameter distance measures: Euclidean and Hamming metrics are developed.