Transcript Document

Privacy-Preserving Route
Planning
Keith Frikken and Mikhail Atallah
WPES 2004
October 28, 2004
Overview




Motivation/Problem Specification
Related Work
Protocol
Summary/Future Work
Motivation


Location-aware mobile devices
Use location to provide new applications



Find nearest coffee shop near a route
Determine if route is close to a friend’s route
Privacy Problems
Application #1




Bob is visiting unfamiliar area
Alice collects large volumes of data about areas
Bob wants to know information about routes
Privacy Problem:



Bob does not want to reveal route
Alice does not want to reveal all information
Question: Does a set of lines get near a set of
points?
Application #2




Alice has a restraining order against Bob
Alice wants to avoid Bob
Bob wants to avoid Alice
Privacy Problem:



Alice does not want to reveal route to Bob
Bob does not want to reveal route to Alice
Question: Do two lines get close to each
other?
Application #3




Military applications
“Uneasy” allies
Lower information disclosure
Prevent “friendly-fire” accidents
Problem Statement

Solve several geometry problems of the form is
X within a threshold distance t of object Y
privately:




Distance between segment and point
Distance between two parametric equations (constant
velocity)
Distance between two segments
Assumptions




Two dimensions
Integer coordinates
Non-negative coordinates
Honest-but-curious model
Variations


Distance threshold could be specified in
many ways (we assume threshold is with
one-party)
Routes can contain several segments
Overview




Motivation/Problem Specification
Related Work
Protocol
Summary/Future Work
SMC (General Results)





Introduced by (Yao, 1982)
Honest-but-curious constant round protocol
(Yao, 1986)
Extensions to Multiple parties (Goldreich et al,
1987)
Malicious constant round version (Katz et al,
2004)
Universal constructions (Canetti et al, 2002)
Constant Round Construction

Given a circuit for evaluating a function of with N
inputs and M gates, it requires:





N 1-out-of-2 OTs
M evaluations of a pseudorandom function
Communication proportional to M
Constant rounds
Fairplay (Malkhi et al, 2004) introduced toolset
for implementation
Domain Specific Solutions

(Du, 01) Several geometry problems




Distance between points
Points contained in polygons
Intersection of polygons
(Atallah et al, 04) Other approaches

Nearest neighbor problem
Overview




Motivation/Problem Specification
Related Work
Protocol
Summary/Future Work
Distance between Point and
Segment

Input:



Alice has point P(x,y) along with distance
threshold T
Bob has a segment S((x1,y1),(x2,y2))
Output

A Boolean value that signifies if distance
between P and S is smaller than T
Diagram: All points close to a
Segment

Tasks



Point to point distance (Du, 01)
Point and Line Distance
Point between two lines
Distance between Point and Line

Inputs:





Alice: P(x,y) and threshold T
Bob: L(Ax+By+C)
Output: Is distance between P and L ≤T
Ax  By  C
Dist(P,L)= A  B
Goal (Ax+By+C)2 ≤T2(A2+B2)
2
2
Point between Lines

Input:



Alice has P(x,y)
Bob has lines L1(Ax+By+C1) and
L2(Ax+By+C2), C2>C1
Goal: C1 ≤ Ax+By ≤ C2
What we need



Need scalar product of two vectors
Need comparison
Need to be able to do above and compose
results
Problems with Circuit Evaluation


Standard circuit for k-bit multiplication is
O(k2) in size
Asymptotic improvements:


Schoenhage-Strassen O(k(logk)(loglogk))
Large constants
Building Block: Homomorphic
Encryption





E(x)E(y)=E(x+y)
E(x)c=E(xc)
Semantic Security
Modular
Examples


(Paillier, 99)
(Damgard et al, 01)
Our approach



Use Homomorphic multiply
Use Circuits for comparison
Difficulties:


Homomorphic multiply is modular
Base has many bits
Comparing Modular Values




Alice has x’ and y’, Bob has x’’ and y’’ in
range [0,M)
However x=x’+x’’ mod M in range [0,m)
and y=y’+y’’ mod M in range [0,m)
M≥2m
Given above comparison is about twice as
expensive as standard comparison
Example 1



M=8, m=4
x’=3 and y’=2 
x’’{5,6,7,0} and
y’’{6,7,0,1}
(x≤y)x’’y’’{4,5,6,7}
6(0)
7(1)
0(2)
1(3)
5(0)
7
6
5
4
6(1)
0
7
6
5
7(2)
1
0
7
6
0(3)
2
1
0
7
Example 2


x’=3 and y’=4 
x’’{5,6,7,0} and
y’’{4,5,6,7}
(x≤y)x’’-y’’{1,0,7,6}
4(0)
5(1)
6(2)
7(3)
5(0)
1
0
7
6
6(1)
2
1
0
7
7(2)
3
2
1
0
0(3)
4
3
2
1
Example 2


x’=3 and y’=4 
x’’{5,6,7,0} and
y’’{4,5,6,7}
(x≤y)x’’-y’’{2,3,4}
4(0)
5(1)
6(2)
7(3)
5(0)
1
0
7
6
6(1)
2
1
0
7
7(2)
3
2
1
0
0(3)
4
3
2
1
Protocol for x≤y

Alice:



Bob:


Computes d=y’’-x’’
Alice and Bob:


Computes a=y’-x’-m+1, b=y’-x’, c=false
If a≥b, a=y’-x’+1, b=y’-x’+m-1, c=true
Engage in a Secure Circuit to evaluate:
(d≥a)AND(d≤b) obtaining XOR-split result rA and rB
Alice:

If c=true, she inverts her value
Base Reduction

Input




Output




Alice has x’ and Bob has x’’
Both values in [0,M)
However, x’+x’’ mod M in [0,m) where M≥2m
Alice has y’ and Bob has y’’
Both values in [0,m)
y’+y’’ mod m = x’+x’’ mod M
Above can be done with a single 1-out-of-2 OT
Composition of Protocols

All intermediate results are shared
between Alice and Bob



For products, the values are additively split
modular some base
Binary values are stored with XOR shares
between the parties
Composition Theorems (Canetti, 00) can
be used to prove security
Other Results




Details of Protocols
Protocol for Parametric Equations with
constant velocity
Protocol for two line segments
Extensions to Higher Dimensions
Overview




Motivation/Problem Specification
Related Work
Protocol
Summary/Future Work
Conclusions/Future Work




Location aware devices offer new services
Privacy concerns
First step towards private computation of results
Future Work:




Parametric lines with acceleration
Implementation
Computing routes
Private Location Awareness