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