Privacy-Preserving Fair Rendez-Vous Point (PPFRVP)

Report
Privacy-Preserving Optimal Meeting
Location Determination on Mobile Devices
Igor Bilogrevic, Member, IEEE, Murtuza Jadliwala,
Member, IEEE, Vishal Joneja, Kübra Kalkan,
Jean-Pierre Hubaux, Fellow, IEEE, and Imad Aad
• Introduction & Problem
Outline
Definition
• Problem Formulation &
System Architecture
• Proposed Solution
• Privacy Requirements &
Definitions
• Privacy & Complexity
Analysis
• Experimental Evaluation
• Introduction & Problem
Outline
Definition
• Problem Formulation &
System Architecture
• Proposed Solution
• Privacy Requirements &
Definitions
• Privacy & Complexity
Analysis
• Experimental Evaluation
Introduction
• Two popular feature of LBS :
Location check-ins and location sharing
• Near 88% of 35 participants were not comfortable
sharing their location information
Fair Rendez-Vous Point Problem
• To determine a location among the such that the
maximum distance between this location and all
other users’ locations is minimized
Fair Rendez-Vous Point Problem
• To determine a location among the such that the
maximum distance between this location and all
other users’ locations is minimized
k-center Problem
• To determine k locations from N candidate places
for placing facilities such that the maximum distance
from any place to its closest facility is minimized.
k-center Problem
• To determine k locations from N candidate places
for placing facilities such that the maximum distance
from any place to its closest facility is minimized.
• Introduction & Problem
Outline
Definition
• Problem Formulation &
System Architecture
• Proposed Solution
• Privacy Requirements &
Definitions
• Privacy & Complexity
Analysis
• Experimental Evaluation
System Architecture
•  = 1 , … , 
•  =  ,  ∈ ℕ2
•  ,  is used to verify the messages that are
sent to the LDS.
• LDS : Location Determination Server
• A shared public/private key pair  , 
System Architecture
•  = 1 , … , 
•  =  ,  ∈ ℕ2
•  ,  is used to verify the messages that are
sent to the LDS.
• LDS : Location Determination Server
• A shared public/private key pair  , 
C.-H. O. Chen et al., “GAnGS: Gather, authenticate’n group securely,”in Proc. 14th ACM
Int. Conf. Mobile Computing Networking, 2008,pp. 92–103.
Y.-H. Lin et al., “SPATE: Small-group PKI-less authenticated trust establishment,” in Proc.
7th Int. Conf. MobiSys, 2009, pp. 1–14.
System Architecture
• Privacy-Preserving Fair Rendez-Vous Point (PPFRVP)
algorithm A
Input
{E(L1)||E(L2)||…||E(LN)}
Output
E(Lfair)=g(E(L1)||E(L2)||…||E(LN))
System Architecture
• Privacy-Preserving Fair Rendez-Vous Point (PPFRVP)
algorithm A
Input
{E(L1)||E(L2)||…||E(LN)}
, ∀,  ∈ 1, … , 
Output
E(Lfair)=g(E(L1)||E(L2)||…||E(LN))
min max , ∀,  ∈ 1, … , 

max , ∀,  ∈ 1, … , 


System Architecture
• Privacy-Preserving Fair Rendez-Vous Point (PPFRVP)
algorithm A
Input
{E(L1)||E(L2)||…||E(LN)}
Output
E(Lfair)=g(E(L1)||E(L2)||…||E(LN))
• Introduction & Problem
Outline
Definition
• Problem Formulation &
System Architecture
• Proposed Solution
• Privacy Requirements &
Definitions
• Privacy & Complexity
Analysis
• Experimental Evaluation
Transformation Function f
• Boneh-Goh-Nissim (BGN) cryptosystems
• ElGamal and Paillier cryptosystems
About BGN-based Cryptosystem
• The cryptosystem devised by Boneh, Goh, and
Nissim was the first to allow both additions and
multiplications with a constant-size ciphertext.
• However, only one multiplication is permitted.
• One of the key ideas in the BGN system is to use
elliptic curve groups whose order is a composite
number n that is hard to factor.
Homomorphic Encryption and the BGN Cryptosystem
David Mandell Freeman
November 18, 2011
Fairness Function g
• A. Distance Computation
• B. MAX Computation
• C. ARGMIN MAX Computation
Fairness Function g
• A. Distance Computation
• B. MAX Computation
• C. ARGMIN MAX Computation
Distance Computation(BGN)
∀ ∈ 1, … , 
  =< 1 , … , 6 >
=  2
  − 2

 1
  − 2
 2
 1
  =< 1 , … , 6 >
=
 1
 
 2
 
 1
 2
T is the modulus of the plaintext domain.
Distance Computation(BGN)
∀ ∈ 1, … , 
  =< 1 , … , 6 >
=  2
  − 2

 1
  − 2
 2
 1
  =< 1 , … , 6 >
=
 1
 
 2
 
 1
 2
  ∙   =  2 − 2  + 2 − 2  + 2 + 2
2
=  
Distance Computation(E-P)
∀ ∈ 1, … , 
  =< 1 , … ,  4 >
=   2  

 2
ELG 
Distance Computation(E-P)
∀ ∈ 1, … , 
  =< 1 , … ,  4 >
=   2  

 2
ELG 
LDS Compute  = LG   ( − 2, ) and   ( − 2, )
n is the modulus of the Pailliar cryptosystem.
, , , are random values for randomizing these result
Distance Computation(E-P)
∀ ∈ 1, … , 
  =< 1 , … ,  4 >
=   2  

 2
ELG 
LDS Compute LG   ( − 2, ) and   ( − 2, )
Fairness Function g
• Distance Computation
• B. MAX Computation
• C. ARGMIN MAX Computation
MAX Computation
• For each index i, the LDS generates two random
values (ri & si) to scale and shift the encrypted square
distance between Li and other location preferences)
MAX Computation
• For each index i, the LDS generates two random
values (ri & si) to scale and shift the encrypted square
distance between Li and other location preferences)
ARGMIN MAX Computation
• For each index i, the LDS generates two random
values (ri & si) to scale and shift the encrypted square
distance between Li and other location preferences)
Finally…
• In Step C.3, each user knows which identifier
corresponds to himself
• And the user whose preferred location has the
minimum distance sends to all other users the fair
rendezvous location in an anonymous way.
• After the last step, each user receives the final fair
rendezvous location, but no other information
regarding non-fair locations or distances is leaked
• Introduction & Problem
Outline
Definition
• Problem Formulation &
System Architecture
• Proposed Solution
• Privacy Requirements &
Definitions
• Privacy & Complexity
Analysis
• Experimental Evaluation
Privacy Requirements & Definitions
• Identifiability advantage  
• Distance-linkability advantage − 
• Coordinate-linkability advantage − 
Challenge-Response Games
Challenger setup :
ℂ collects the preferred rendez-vous
locations L1 ~ LN
Algorithm execution :
ℂ execute algorithm A and compute
  =   1 , … ,   ,  
(weak) Identifiability
Challenge :
ℂ chooses a random k ∈ {1, . . . , N} and
sends Lk to the adversary ua.
Guess :
ua chooses a value k’ ∈ {1, . . . , N} and
sends it back to the challenger.
Distance-Linkability
Challenge :
ℂ chooses a random value s and two
distinct users uj , uk , ∀ j, k ∈ {1, . . . , N},
j ≠ k. ℂ sends ( j, k, s) to the adversary.
− 
= Pr  ∗ = 0 ∧ , ≥ 
+ Pr  ∗ = 1 ∧ , <  Guess :
−1/2
ua responds with a value s∗ ∈ {0, 1}.
ua wins the game if s∗ = 0 and dj,k ≥ s,
or if s∗ = 1 and d < s.
Coordinate-Linkability
− 
= Pr  = 0 ∧  ≤ 
+ Pr  = 1 ∧  > 
−1/2
Challenge :
ℂ throws an unbiased coin to select a
coordinate axis b| ∈ {x, y}, and randomly
chooses j, k ∈{1, 2, . . . , N}, j ≠ k.
ℂ sends { j, k, b} to ua
Guess :
ua responds with a value r ∈ {0, 1}
ua wins the game if r = 0 and bj ≤ bk,
or if r = 1 and bj > bk.
• Introduction & Problem
Outline
Definition
• Problem Formulation &
System Architecture
• Proposed Solution
• Privacy Requirements &
Definitions
• Privacy & Complexity
Analysis
• Experimental Evaluation
Privacy Analysis
• Probability advantages under passive attack are 0s
Privacy Analysis(Active Attack)
• Collusion ( between the LDS and a participant)
• Fake Users
• Generated by the LDS
• Generated by a legitimate participant
• Unfair RV(Malicious modification or
untruthful reporting of the maximum masked values)
Unfair RV
• even if a user falsely reports one of his values to be
the maximum, this would cause the algorithm to
select a non-fair rendez-vous location if and only if
no other user selected a smaller value as the
maximum distance.
Complexity Analysis
Complexity Analysis
Complexity Analysis
Complexity Analysis
• Introduction & Problem
Outline
Definition
• Problem Formulation &
System Architecture
• Proposed Solution
• Privacy Requirements &
Definitions
• Privacy & Complexity
Analysis
• Experimental Evaluation
Complexity Analysis
(LDS implementation is running on a standard Linux PC)
(2 GHz CPU, 3 GB RAM, Ubuntu Linux).
Dist
MAX
ARGMIN
Complexity Analysis
(client application is implemented on Nokia N810)
(ARM 400 MHz CPU, 256 MB RAM, Linux Maemo OS)
Dist
MAX+ARGMIN
all
END

similar documents