Loading presentation...

Present Remotely

Send the link below via email or IM


Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.


Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks


Secure Location Based Android Application for Group Nearest Neighbor Query

Syed Jibranuddin

on 20 August 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Cryptography

Secure Location Based Android Application for Group Nearest Neighbor Query By :
Syed Jibranuddin (50026775)
Bhaavyaa Kapoor(50026253) Motivation for the Proposal Presentation Outline Location Based Services – Introduction Problem Definition Various approaches for LBS References Cryptographic Protocols used Application details Application Overview What are Location Based Services?
Location-based services are a general class of computer program-level services used to include specific controls for location and time data as control features in computer programs. It can be defined as an information that is used extensively in todays Social Networking, that is accessed by mobile devices and is based on geographical location of users of that mobile device.
LBS comprises of : the service provider's software application, a mobile network that sending geographic location and requesting for service, a content provider to supply the end user with geo-specific information, a positioning component (GPS) and the end user's mobile device
Ex: Nearest restaurant, gas station, ATM etc.
Since users request for services to LBS servers along with their exact locations, this location information of the users can be exploited by malicious users. With untrustworthy LBS providers, the revealed private location information could be abused by adversaries Location Based Services
Introduction Today location services of android phones have become very popular. There is huge development in the field of technologies that use location tracking such as anonymous web surfing services.
This has endangered the privacy of individuals that are using these services. The vulnerability to privacy threats has immensely increased.
The goal of this project is to access these location based services and make sure that no confidential or private information is revealed.
The objective of our survey is to access LBS while guaranteeing at some private information is not revealed even when exact user location is known Motivation
A mechanism should be introduced to deal with the users’ privacy protection
An algorithms which uses cryptographic technique to assure privacy in Location based services Problem Definition Fundamental Approaches for privacy of user’s location information Anonymity and Cloaking Based Approach:
The user information is disguised among K-1 other user location or spatial extension is used i.e. extended from a point location. Thus anonymity set is formed which is sent to the server instead of a precise location.
A trusted third party exists which is a server for all other users
Transformation-Based Approach:
Space filling curves are used for one way transformation to encode location of users and point of interests into an encrypted space and query is evaluated in this transformed space. Fundamental Approaches for privacy of user’s location information Cryptographic Based Approach:
The untrusted party is made blind by secure multi-party computation scheme.

Private Information Retrieval -Based Approach:
This approach constructs spatial indexes on top of PIR operations to provide efficient spatial query processing, while the underlying PIR scheme guarantees privacy. Application overview We are assuming the model to be peer-to-peer( No Centralized trusted third party server)
We are going to design a Mobile application on Android Platform.
In this application we calculate the group nearest neighbor of a group of android devices by summing up the Euclidean distance between devices locations and then calculating the minimum distance to decide the meeting point. Motivation First finding the leader who is going to execute Distance calculation function by hashing the ID’s of the Android devices using SHA-1 and finding the highest ID node using Multicast among the devices.
Once the leader is elected, We are going to use Diffie Hellman key exchange variant STS between the leader and all other peers.
Once the keys have been exchanged, the location is exchanged between the leader and the rest of the peers using Public Key Cryptography.
Then the meeting point is calculated and is sent to each peer encrypted with its public key, so that only the right device is able to decrypt the meeting location. Application Details SHA-1:
SHA stands for "secure hash algorithm”.
160-bit message digest
Goal: to provide a unique “fingerprint” of the message.
Fast , One way and Strongly Collision free.
Public Key Cryptography for Key and Location Exchange Cryptographic Protocols used Locking key Unlocking key Choose two random large prime numbers p and q
Equal length 512 bits
Compute the Product
Choose a random integer e< Φ(n)
must be relatively prime
Compute the Unique inverse RSA Public Key Cryptosystem
Key Generation Algorithm n = p*q Φ(n) = (p-1)*(q-1) d = e-1 mod Φ(n) Public Key (n,e) Private Key (n,d) Application overview None of the papers mentioned in references described the privacy aspect of this group nearest neighbor queries.
They assume that people are willing to share their location information with all other people to compute meeting point, which would reveal their individual locations.
So what we are going to do ?? Demo Application Details Selection of a Leader Randomly.
Leader Generates Key Pair Using RSA
Sends it to others Application users along with Hash and ID
Users receive this Public Key and checks the hash.
Users send their public keys to leader along with hash and this whole message is encrypted using leaders master key.
Leader initiates sharing of location.
Everybody sends their location as : Hash of Location ID Encrypted with Leaders Public Key Encrypted with Nodes PR Key Location Leader receives the message first Decrypt it with its own Private key
Then decrypt the hash with users Public key and matches the hash for authentication.
Calculates the Group nearest meeting point.
Sends the location to everyone in the similar manner as user sends it the location. Application Details Hash of Location ID Encrypted with each Node Public Key Encrypted with Masters PR Key Location Encryption of X

Decryption of Y

Encryption and Decryption are Symmetric Operations RSA Public Key Cryptosystem
Key Generation Algorithm Y = X mod (n) X = Y mod (n)
M. Yiu, C. Jensen, X. Huang, and H. Lu, “Spacetwist: managing
the trade-offs among location privacy, query performance and query
accuracy in road networks,” in Proc. of ICDE ’08, 2008, pp. 366–375.
M.L. Yiu, N. Mamoulis, and D. Papadias, Aggregate nearest neighbour queries in road networks, IEEE TKDE, 2005, pp. 820{833.
D. Papadias, Y. Tao, J. Zhang, and N. Mamoulis, Query processing in spatial network databases, VLDB, 2003, pp. 802{813.
C. Shahabi, M.R. Kolahdouzan, and M. Sharifzadeh, A road network embedding technique for k-nearest neighbour search in moving object databases, ACM GIS, 2002, pp. 94{100.
D. Papadias, Q. Shen, Y. Tao, and K. Mouratidis, Group nearest neighbour queries, ICDE, 2004, pp. 301{313.
C.S. Jensen, J. Kolar, and T.B. Pedersen adn I. Timko, Nearest neighbour queries in road networks, ACM GIS, 2003, pp. 1{8. References Demo Thank you..!!!! e d
Full transcript