Privacy-Preserving Surveillance: Design and Implementation

D

e

s

i

g

n

a

n

d

I

m

p

l

e

m

e

n

t

a

t

i

o

n

o

f

P

r

i

v

a

c

y

‑

P

r

e

s

e

r

v

i

n

g

S

u

r

v

e

i

l

l

a

n

c

e

A

a

r

o

n

S

e

g

a

l

Yale University

May 11, 2016

Advisor: Joan Feigenbaum

“…an unspeakable blasphemy.” - @Dymaxion

O

v

e

r

v

i

e

w

•

Introduction – Surveillance and Privacy

•

P

r

i

v

a

c

y

P

r

i

n

c

i

p

l

e

s

f

o

r

O

p

e

n

S

u

r

v

e

i

l

l

a

n

c

e

P

r

o

c

e

s

s

e

s

•

Lawful Set Intersection and the High Country Bandits

•

Contact Chaining

•

Anonymity through Tor and Verdict

T

h

e

P

r

o

b

l

e

m

•

Open season on private personal data

•

No accountability

•

No guarantees

•

The government is part of the problem

M

o

t

i

v

a

t

i

o

n

&

G

o

a

l

s

R

e

p

l

a

c

e

l

a

w

e

n

f

o

r

c

e

m

e

n

t

’

s

s

e

c

r

e

t

i

v

e

,

u

n

p

r

i

n

c

i

p

l

e

d

t

r

e

a

t

m

e

n

t

o

f

c

i

t

i

z

e

n

s

’

b

i

g

d

a

t

a

w

i

t

h

a

n

o

p

e

n

p

r

i

v

a

c

y

p

o

l

i

c

y

.

-

S

e

c

r

e

t

p

r

o

c

e

s

s

e

s

f

o

r

d

a

t

a

c

o

l

l

e

c

t

i

o

n

-

P

u

b

l

i

c

i

s

a

s

k

e

d

t

o

t

r

u

s

t

t

h

e

g

o

v

e

r

n

m

e

n

t

-

P

r

e

s

u

m

e

d

t

r

a

d

e

o

f

f

b

e

t

w

e

e

n

n

a

t

i

o

n

a

l

s

e

c

u

r

i

t

y

a

n

d

p

e

r

s

o

n

a

l

p

r

i

v

a

c

y

-

I

d

e

a

l

w

o

r

l

d

:

N

o

s

u

r

v

e

i

l

l

a

n

c

e

M

o

t

i

v

a

t

i

o

n

&

G

o

a

l

s

R

e

p

l

a

c

e

l

a

w

e

n

f

o

r

c

e

m

e

n

t

’

s

s

e

c

r

e

t

i

v

e

,

u

n

p

r

i

n

c

i

p

l

e

d

t

r

e

a

t

m

e

n

t

o

f

c

i

t

i

z

e

n

s

’

b

i

g

d

a

t

a

w

i

t

h

a

n

o

p

e

n

p

r

i

v

a

c

y

p

o

l

i

c

y

.

-

S

e

c

r

e

t

p

r

o

c

e

s

s

e

s

f

o

r

d

a

t

a

c

o

l

l

e

c

t

i

o

n

-

P

u

b

l

i

c

i

s

a

s

k

e

d

t

o

t

r

u

s

t

t

h

e

g

o

v

e

r

n

m

e

n

t

-

P

r

e

s

u

m

e

d

t

r

a

d

e

o

f

f

b

e

t

w

e

e

n

n

a

t

i

o

n

a

l

s

e

c

u

r

i

t

y

a

n

d

p

e

r

s

o

n

a

l

p

r

i

v

a

c

y

-

I

d

e

a

l

w

o

r

l

d

:

N

o

s

u

r

v

e

i

l

l

a

n

c

e

•

R

e

a

l

i

s

t

i

c

g

o

a

l

:

S

u

r

v

e

i

l

l

a

n

c

e

w

i

t

h

p

r

i

v

a

c

y

p

r

e

s

e

r

v

a

t

i

o

n

M

o

t

i

v

a

t

i

o

n

&

G

o

a

l

s

R

e

p

l

a

c

e

l

a

w

e

n

f

o

r

c

e

m

e

n

t

’

s

s

e

c

r

e

t

i

v

e

,

u

n

p

r

i

n

c

i

p

l

e

d

t

r

e

a

t

m

e

n

t

o

f

c

i

t

i

z

e

n

s

’

b

i

g

d

a

t

a

w

i

t

h

a

n

o

p

e

n

p

r

i

v

a

c

y

p

o

l

i

c

y

.

-

S

e

c

r

e

t

p

r

o

c

e

s

s

e

s

f

o

r

d

a

t

a

c

o

l

l

e

c

t

i

o

n

-

P

u

b

l

i

c

i

s

a

s

k

e

d

t

o

t

r

u

s

t

t

h

e

g

o

v

e

r

n

m

e

n

t

-

P

r

e

s

u

m

e

d

t

r

a

d

e

o

f

f

b

e

t

w

e

e

n

n

a

t

i

o

n

a

l

s

e

c

u

r

i

t

y

a

n

d

p

e

r

s

o

n

a

l

p

r

i

v

a

c

y

•

N

o

n

e

e

d

t

o

a

b

a

n

d

o

n

p

e

r

s

o

n

a

l

p

r

i

v

a

c

y

t

o

e

n

s

u

r

e

n

a

t

i

o

n

a

l

s

e

c

u

r

i

t

y

-

I

d

e

a

l

w

o

r

l

d

:

N

o

s

u

r

v

e

i

l

l

a

n

c

e

•

R

e

a

l

i

s

t

i

c

g

o

a

l

:

S

u

r

v

e

i

l

l

a

n

c

e

w

i

t

h

p

r

i

v

a

c

y

p

r

e

s

e

r

v

a

t

i

o

n

M

o

t

i

v

a

t

i

o

n

&

G

o

a

l

s

R

e

p

l

a

c

e

l

a

w

e

n

f

o

r

c

e

m

e

n

t

’

s

s

e

c

r

e

t

i

v

e

,

u

n

p

r

i

n

c

i

p

l

e

d

t

r

e

a

t

m

e

n

t

o

f

c

i

t

i

z

e

n

s

’

b

i

g

d

a

t

a

w

i

t

h

a

n

o

p

e

n

p

r

i

v

a

c

y

p

o

l

i

c

y

.

-

S

e

c

r

e

t

p

r

o

c

e

s

s

e

s

f

o

r

d

a

t

a

c

o

l

l

e

c

t

i

o

n

-

P

u

b

l

i

c

i

s

a

s

k

e

d

t

o

t

r

u

s

t

t

h

e

g

o

v

e

r

n

m

e

n

t

•

A

c

c

o

u

n

t

a

b

i

l

i

t

y

g

u

a

r

a

n

t

e

e

d

b

y

e

x

i

s

t

i

n

g

c

r

y

p

t

o

g

r

a

p

h

i

c

t

e

c

h

n

o

l

o

g

y

-

P

r

e

s

u

m

e

d

t

r

a

d

e

o

f

f

b

e

t

w

e

e

n

n

a

t

i

o

n

a

l

s

e

c

u

r

i

t

y

a

n

d

p

e

r

s

o

n

a

l

p

r

i

v

a

c

y

•

N

o

n

e

e

d

t

o

a

b

a

n

d

o

n

p

e

r

s

o

n

a

l

p

r

i

v

a

c

y

t

o

e

n

s

u

r

e

n

a

t

i

o

n

a

l

s

e

c

u

r

i

t

y

-

I

d

e

a

l

w

o

r

l

d

:

N

o

s

u

r

v

e

i

l

l

a

n

c

e

•

R

e

a

l

i

s

t

i

c

g

o

a

l

:

S

u

r

v

e

i

l

l

a

n

c

e

w

i

t

h

p

r

i

v

a

c

y

p

r

e

s

e

r

v

a

t

i

o

n

M

o

t

i

v

a

t

i

o

n

&

G

o

a

l

s

R

e

p

l

a

c

e

l

a

w

e

n

f

o

r

c

e

m

e

n

t

’

s

s

e

c

r

e

t

i

v

e

,

u

n

p

r

i

n

c

i

p

l

e

d

t

r

e

a

t

m

e

n

t

o

f

c

i

t

i

z

e

n

s

’

b

i

g

d

a

t

a

w

i

t

h

a

n

o

p

e

n

p

r

i

v

a

c

y

p

o

l

i

c

y

.

-

S

e

c

r

e

t

p

r

o

c

e

s

s

e

s

f

o

r

d

a

t

a

c

o

l

l

e

c

t

i

o

n

•

O

p

e

n

p

r

o

c

e

s

s

e

s

f

o

r

d

a

t

a

c

o

l

l

e

c

t

i

o

n

w

i

t

h

a

p

r

i

n

c

i

p

l

e

d

p

r

i

v

a

c

y

p

o

l

i

c

y

-

P

u

b

l

i

c

i

s

a

s

k

e

d

t

o

t

r

u

s

t

t

h

e

g

o

v

e

r

n

m

e

n

t

•

A

c

c

o

u

n

t

a

b

i

l

i

t

y

g

u

a

r

a

n

t

e

e

d

b

y

e

x

i

s

t

i

n

g

c

r

y

p

t

o

g

r

a

p

h

i

c

t

e

c

h

n

o

l

o

g

y

-

P

r

e

s

u

m

e

d

t

r

a

d

e

o

f

f

b

e

t

w

e

e

n

n

a

t

i

o

n

a

l

s

e

c

u

r

i

t

y

a

n

d

p

e

r

s

o

n

a

l

p

r

i

v

a

c

y

•

N

o

n

e

e

d

t

o

a

b

a

n

d

o

n

p

e

r

s

o

n

a

l

p

r

i

v

a

c

y

t

o

e

n

s

u

r

e

n

a

t

i

o

n

a

l

s

e

c

u

r

i

t

y

-

I

d

e

a

l

w

o

r

l

d

:

N

o

s

u

r

v

e

i

l

l

a

n

c

e

•

R

e

a

l

i

s

t

i

c

g

o

a

l

:

S

u

r

v

e

i

l

l

a

n

c

e

w

i

t

h

p

r

i

v

a

c

y

p

r

e

s

e

r

v

a

t

i

o

n

S

o

m

e

P

r

i

v

a

c

y

P

r

i

n

c

i

p

l

e

s

f

o

r

L

a

w

f

u

l

S

u

r

v

e

i

l

l

a

n

c

e

(

1

)

Open processes

-

M

u

s

t

f

o

l

l

o

w

r

u

l

e

s

a

n

d

p

r

o

c

e

d

u

r

e

s

o

f

p

u

b

l

i

c

l

a

w

-

N

e

e

d

n

o

t

d

i

s

c

l

o

s

e

t

a

r

g

e

t

s

a

n

d

d

e

t

a

i

l

s

o

f

i

n

v

e

s

t

i

g

a

t

i

o

n

s

Two types of users:

•

Targeted users

-

U

n

d

e

r

s

u

s

p

i

c

i

o

n

-

S

u

b

j

e

c

t

o

f

a

w

a

r

r

a

n

t

-

Can be 

known 

or 

unknown

•

Untargeted users

-

No probable cause

-

Not targets of investigation

-

The vast majority of internet users

O

p

e

n

P

r

i

v

a

c

y

F

i

r

e

w

a

l

l

I.

A

n

y

s

u

r

v

e

i

l

l

a

n

c

e

o

r

l

a

w

-

e

n

f

o

r

c

e

m

e

n

t

p

r

o

c

e

s

s

t

h

a

t

o

b

t

a

i

n

s

o

r

u

s

e

s

p

r

i

v

a

t

e

i

n

f

o

r

m

a

t

i

o

n

a

b

o

u

t

u

n

t

a

r

g

e

t

e

d

u

s

e

r

s

s

h

a

l

l

b

e

a

n

o

p

e

n

,

p

u

b

l

i

c

,

u

n

c

l

a

s

s

i

f

i

e

d

p

r

o

c

e

s

s

.

II.

A

n

y

s

e

c

r

e

t

s

u

r

v

e

i

l

l

a

n

c

e

o

r

l

a

w

-

e

n

f

o

r

c

e

m

e

n

t

p

r

o

c

e

s

s

s

h

a

l

l

u

s

e

o

n

l

y

:

a.

public information, and

b.

private information about 

targeted users 

obtained under authorized warrants

via open surveillance processes.

S

o

m

e

P

r

i

v

a

c

y

P

r

i

n

c

i

p

l

e

s

f

o

r

L

a

w

f

u

l

S

u

r

v

e

i

l

l

a

n

c

e

(

2

)

•

Distributed trust

-

No one agency can compromise privacy.

•

Enforced scope limiting

-

No overly broad group of users’ data are captured.

•

Sealing time and notification

-

After a finite, reasonable time, surveilled users are notified.

•

Accountability

-

Surveillance statistics are maintained and audited.

C

a

s

e

S

t

u

d

y

–

H

i

g

h

C

o

u

n

t

r

y

B

a

n

d

i

t

s

2010 case – string of bank robberies

in Arizona, Colorado

FBI Intersection attack compared 3

cell tower dumps totaling 150,000

users

•

1 number found in all 3 cell dumps –

led to arrest

•

149,999 innocent users’ information

acquired

I

n

t

e

r

s

e

c

t

i

n

g

C

e

l

l

-

T

o

w

e

r

D

u

m

p

s

•

Law enforcement goal: Find 

targeted

, 

unknown

 user whose phone

number will appear in the intersection of cell-tower dumps

•

Used in: High Country Bandits case, CO-TRAVELER program

-

Same principle for any collection of metadata

I

n

t

e

r

s

e

c

t

i

n

g

C

e

l

l

-

T

o

w

e

r

D

u

m

p

s

•

Law enforcement goal: Find 

targeted

, 

unknown

 user whose phone

number will appear in the intersection of cell-tower dumps

•

Used in: High Country Bandits case, CO-TRAVELER program

-

Same principle for any collection of metadata

P

r

i

v

a

c

y

-

P

r

e

s

e

r

v

i

n

g

S

o

l

u

t

i

o

n

[

S

F

F

,

F

O

C

I

’

1

4

]

•

A 

private set intersection protocol

 built to satisfy surveillance privacy

principles 

(based on Vaidya-Clifton ‘05)

•

Catching Bandits and 

Only

 Bandits: Privacy-Preserving Intersection

Warrants for Lawful Surveillance

-

Presented at the 4

th

 USENIX Workshop on Free and Open Communications

on the Internet (FOCI '14)

P

r

i

v

a

c

y

-

P

r

e

s

e

r

v

i

n

g

C

r

y

p

t

o

g

r

a

p

h

y

a = "650-555-2840"

b = "650-555-2840"

print ElGamalEncrypt(a)

    > 

0x00d07e08ec44712b

print ElGamalEncrypt(b)

    > 

0x58c82a7f050f9683

a = "650-555-2840"

b = "650-555-2840"

print PohligHellmanEncrypt(a)

    > 

0x0cb508480f207ec5

print PohligHellmanEncrypt(b)

    > 

0x0cb508480f207ec5

Probabilistic 

ElGamal

encryption for secure

storage of cell-tower

records.

-

S

a

m

e

r

e

c

o

r

d

s

e

n

c

r

y

p

t

t

o

d

i

f

f

e

r

e

n

t

r

a

n

d

o

m

-

l

o

o

k

i

n

g

b

y

t

e

s

t

r

i

n

g

s

Deterministic 

Pohlig-Hellman

encryption for temporary, per-

execution blinding of those

records.

-

S

a

m

e

r

e

c

o

r

d

s

e

n

c

r

y

p

t

t

o

i

d

e

n

t

i

c

a

l

r

a

n

d

o

m

-

l

o

o

k

i

n

g

b

y

t

e

s

t

r

i

n

g

s

P

r

i

v

a

t

e

S

e

t

I

n

t

e

r

s

e

c

t

i

o

n

S

e

t

u

p

•

E

l

G

a

m

a

l

e

n

c

r

y

p

t

i

o

n

a

n

d

P

o

h

l

i

g

-

H

e

l

l

m

a

n

e

n

c

r

y

p

t

i

o

n

a

r

e

m

u

t

u

a

l

l

y

c

o

m

m

u

t

a

t

i

v

e

w

i

t

h

o

n

e

a

n

o

t

h

e

r

D

2

(

D

3

(

D

1

(

E

3

(

E

2

(

E

1

(

x

)))))) = x

D

3

(

D

2

(

E

3

(

D

1

(

E

2

(

E

1

(

x

)))))) = 

x

•

R

e

l

i

e

s

o

n

m

u

l

t

i

p

l

e

,

i

n

d

e

p

e

n

d

e

n

t

a

g

e

n

c

i

e

s

t

o

e

x

e

c

u

t

e

p

r

o

t

o

c

o

l

,

p

r

o

v

i

d

i

n

g

d

i

s

t

r

i

b

u

t

e

d

t

r

u

s

t

a

n

d

a

c

c

o

u

n

t

a

b

i

l

i

t

y

,

e

.

g

.

:

-

Executive agency (FBI, NSA)

-

Judicial agency (warrant-issuing court)

-

Legislative agency (oversight committee established by law)

•

Each agency must participate at each step or else no one can decrypt!

P

r

i

v

a

t

e

S

e

t

I

n

t

e

r

s

e

c

t

i

o

n

P

r

o

t

o

c

o

l

(

S

t

e

p

1

)

•

Repository serves data encrypted with

ElGamal 

encryption

-

Uses agencies’ long-term public (encryption) keys

Agencies encrypt the encryptions with Pohlig-

Hellman encryption

Uses agencies’ ephemeral encryption keys

Agencies decrypt the encrypted encryptions

with ElGamal decryption

-

Uses agencies’ long-term private (decryption) keys

Can now inspect data, which is encrypted under

Pohlig-Hellman

E

3

(

E

2

(

E

1

(

x

)))

1

2

3

P

r

i

v

a

t

e

S

e

t

I

n

t

e

r

s

e

c

t

i

o

n

P

r

o

t

o

c

o

l

(

S

t

e

p

1

)

•

Repository serves data encrypted with

ElGamal 

encryption

-

Uses agencies’ long-term public (encryption) keys

•

Agencies encrypt the encryptions with 

Pohlig-

Hellman

 encryption

-

Uses agencies’ ephemeral encryption keys

Agencies decrypt the encrypted encryptions

with ElGamal decryption

Uses agencies’ long-term private (decryption) keys

Can now inspect data, which is encrypted under

Pohlig-Hellman

E

3

(

E

2

(

E

1

(

E

3

(

E

2

(

E

1

(

x

))))))

1

1

2

2

3

3

P

r

i

v

a

t

e

S

e

t

I

n

t

e

r

s

e

c

t

i

o

n

P

r

o

t

o

c

o

l

(

S

t

e

p

1

)

•

Repository serves data encrypted with

ElGamal 

encryption

-

Uses agencies’ long-term public (encryption) keys

•

Agencies encrypt the encryptions with 

Pohlig-

Hellman

 encryption

-

Uses agencies’ ephemeral encryption keys

•

Agencies decrypt the encrypted encryptions

with 

ElGamal 

decryption

-

Uses agencies’ long-term private (decryption) keys

•

Can now inspect data, which is encrypted

under 

Pohlig-Hellman

E

3

(

E

2

(

E

1

(

x

)))

1

2

3

P

r

i

v

a

t

e

S

e

t

I

n

t

e

r

s

e

c

t

i

o

n

P

r

o

t

o

c

o

l

(

S

t

e

p

2

)

•

Accomplished: Moved from an 

ElGamal 

state to a 

Pohlig-Hellman

 state

without ever fully decrypting the private data!

•

Agencies can now inspect encrypted data to find matching records

•

Last step: decrypt 

only

 those records with 

Pohlig-Hellman

a = "650-555-2840"

b = "650-555-2840"

print ElGamalEncrypt(a)

    > 

0x00d07e08ec44712b

print ElGamalEncrypt(b)

    > 

0x58c82a7f050f9683

a = "650-555-2840"

b = "650-555-2840"

print PohligHellmanEncrypt(a)

    > 

0x0cb508480f207ec5

print PohligHellmanEncrypt(b)

    > 

0x0cb508480f207ec5

P

r

o

t

o

c

o

l

S

a

t

i

s

f

i

e

s

P

r

i

v

a

c

y

P

r

i

n

c

i

p

l

e

s

•

Open Process

-

Can openly standardize the protocol and the crypto 

without

 compromising

investigative power

•

Distributed trust

-

No one agency can decrypt or perform intersection.

•

Enforced scope limiting

-

Any agency can stop an execution if sets or intersection are too large.

•

Sealing time and notification

-

Implementable by policy – all agencies get final data set

•

Accountability

-

Because every agency must participate, no agency can perform illegitimate

surveillance without the other agencies’ learning and getting statistics.

E

v

a

l

u

a

t

i

o

n

o

f

I

m

p

l

e

m

e

n

t

a

t

i

o

n

•

Java implementation of protocol

run in parallel on Yale CS Cloud

•

High Country Bandits example

with 50,000 items per set takes

less than 11 minutes to complete.

•

Note that this is an 

offline

 process.

C

o

n

t

a

c

t

C

h

a

i

n

i

n

g

•

Government knows phone number of target X.

•

Goal: Consider the “k-contacts” of X (nodes within distance k).

x

P

r

i

v

a

c

y

-

P

r

e

s

e

r

v

i

n

g

C

o

n

t

a

c

t

C

h

a

i

n

i

n

g

G

o

a

l

s

•

Government learns actionable, relevant intelligence

•

Telecommunications companies learn nothing more about other

companies’ clients

x

P

r

i

v

a

c

y

-

P

r

e

s

e

r

v

i

n

g

C

o

n

t

a

c

t

C

h

a

i

n

i

n

g

G

o

a

l

s

•

Government learns actionable, relevant intelligence

•

Telecommunications companies learn nothing more about other

companies’ clients

P

r

i

v

a

c

y

-

P

r

e

s

e

r

v

i

n

g

C

o

n

t

a

c

t

C

h

a

i

n

i

n

g

G

o

a

l

s

•

Government learns actionable, relevant intelligence

•

Telecommunications companies learn nothing more about other

companies’ clients

R

e

s

t

r

i

c

t

i

o

n

s

o

n

C

o

n

t

a

c

t

C

h

a

i

n

i

n

g

•

Respect the distinction between targeted and untargeted users

•

Enforce scope limiting

•

Enforce division of trust between authorities

U

s

i

n

g

C

o

n

t

a

c

t

C

h

a

i

n

i

n

g

-

M

a

i

n

I

d

e

a

•

Use privacy-

preserving contact

chaining protocol to

get 

encryptions

 of

k

‑contacts of target

•

Use privacy-

preserving set

intersection to 

filter

k

‑contacts and

decrypt only new

targets

P

r

i

v

a

c

y

-

P

r

e

s

e

r

v

i

n

g

C

o

n

t

a

c

t

C

h

a

i

n

i

n

g

P

r

o

t

o

c

o

l

•

Government agencies agree on a warrant:

-

Initial target id 

X

-

Maximum chaining length 

k

-

Scope-limiting parameter 

d

 : Maximum degree

•

Each telecom has:

-

List of client identities served

-

Contact list for each client

•

Agencies repeatedly query telecoms about their data

P

r

i

v

a

c

y

-

P

r

e

s

e

r

v

i

n

g

C

o

n

t

a

c

t

C

h

a

i

n

i

n

g

P

r

o

t

o

c

o

l

S

e

t

u

p

•

Agencies perform a modified

parallel breadth-first search by

querying telecoms

•

Enc

T

(

a

)

(

a

) is a public-key

encryption of 

a 

under the

encryption key of 

T

(

a

), the

telecom that serves user 

a

•

Enc

Agencies

(

a

) is an 

ElGamal

encryption of 

a 

under the keys of

all agencies

Q

u

e

r

y

t

o

T

(

a

)

•

Enc

T

(

a

)

(

a

)

•

Signatures from all agencies

R

e

s

p

o

n

s

e

f

r

o

m

T

(

a

)

•

Enc

Agencies

(

a

)

•

Enc

T

(

b

)

(

b

) for all 

b

 in 

a

’s

set of neighbors

•

Signature from 

T

(

a

)

P

r

i

v

a

c

y

-

P

r

e

s

e

r

v

i

n

g

C

o

n

t

a

c

t

C

h

a

i

n

i

n

g

P

r

o

t

o

c

o

l

•

Step 0:

-

Query 

T

(

x

) on original target 

x

•

Step 1 through 

k

:

-

Query appropriate telecom on all

ciphertexts received during

previous step

-

Exception: If a single response has

more than 

d

 contacts, do not query

them

•

Output: Agency ciphertexts

received

Q

u

e

r

y

t

o

T

(

a

)

•

Enc

T

(

a

)

(

a

)

•

Signatures from all agencies

R

e

s

p

o

n

s

e

f

r

o

m

T

(

a

)

•

Enc

Agencies

(

a

)

•

Enc

T

(

b

)

(

b

) for all 

b

 in 

a

’s

set of neighbors

•

Signature from 

T

(

a

)

P

r

o

t

e

c

t

i

n

g

P

r

i

v

a

t

e

D

a

t

a

•

Agencies see 

no 

cleartext

identities from this contact

chaining protocol

•

Telecoms learn no information

about other telecoms’ users by

responding to queries

•

Signatures ensure validity of all

messages

Q

u

e

r

y

t

o

T

(

a

)

•

Enc

T

(

a

)

(

a

)

•

Signatures from all agencies

R

e

s

p

o

n

s

e

f

r

o

m

T

(

a

)

•

Enc

Agencies

(

a

)

•

Enc

T

(

b

)

(

b

) for all 

b

 in 

a

’s

set of neighbors

•

Signature from 

T

(

a

)

P

r

o

t

o

c

o

l

S

a

t

i

s

f

i

e

s

P

r

i

v

a

c

y

P

r

i

n

c

i

p

l

e

s

•

Open Process

-

Can openly standardize the protocol and the crypto 

without

 compromising

investigative power

•

Distributed trust

-

Telecoms disregard queries unless signed by all agencies

-

No one agency can decrypt responses

•

Enforced scope limiting

-

Any agency can block paths through high-degree vertices

•

Sealing time and notification

-

Agencies can notify targeted users after intersection step

•

Accountability

-

Surveillance statistics collected by any or all agencies

I

m

p

l

e

m

e

n

t

a

t

i

o

n

o

f

C

o

n

t

a

c

t

-

C

h

a

i

n

i

n

g

P

r

o

t

o

c

o

l

•

Java implementation of protocol run in parallel on Yale CS Cloud

•

Used actual network data from a Slovakian social network as

“realistic” stand-in for a telephone network

•

Created 4 “telecoms” owning 44%, 24%, 17%, and 15% of the

network to simulate proportional sizes of largest 4 telecoms

C

o

n

t

a

c

t

C

h

a

i

n

i

n

g

E

x

p

e

r

i

m

e

n

t

a

l

S

e

t

u

p

•

Java implementation of

protocol run in parallel on

Yale CS Cloud

•

Used actual network data

from a Slovakian social

network as “realistic”

stand-in for a telephone

network

C

o

n

t

a

c

t

C

h

a

i

n

i

n

g

E

x

p

e

r

i

m

e

n

t

a

l

R

e

s

u

l

t

s

•

Varied starting position,

k

, and 

d

 to examine a

variety of neighborhood

sizes

•

Measured

-

End-to-end running time

-

CPU time used by all

telecoms

-

Total bandwidth sent over

network

C

o

n

t

a

c

t

C

h

a

i

n

i

n

g

E

x

p

e

r

i

m

e

n

t

a

l

R

e

s

u

l

t

s

P

r

i

v

a

c

y

-

P

r

e

s

e

r

v

i

n

g

C

o

n

t

a

c

t

C

h

a

i

n

i

n

g

a

n

d

I

n

t

e

r

s

e

c

t

i

o

n

•

Privacy-preserving contact chaining & set intersection together

•

Our principles apply to other surveillance of private data

•

No need for new cryptographic tools, “backdoors,” or secret processes

A

n

o

n

y

m

i

t

y

:

U

s

e

r

s

P

r

o

t

e

c

t

i

n

g

T

h

e

m

s

e

l

v

e

s

W

i

t

h

T

o

r

•

Anonymous communication

dissociates network activity from

user identity

•

Tor: The Second-Generation Onion

Router [DMS 2004]

-

2 million Tor users daily

-

7000+ volunteer relays in the Tor

network

•

Connections made through three

relays: 

guard

, 

middle

, 

exit

•

Vulnerability: Adversary who can

view 

guard 

and 

exit

 traffic together

T

o

r

F

l

o

w

:

C

r

i

t

i

c

a

l

b

u

t

V

u

l

n

e

r

a

b

l

e

•

TorFlow conducts 

bandwidth scans 

to measure all 7000+ relays

•

Relays can determine when they’re being scanned

-

Exploit: Give better service to measurement authorities

•

Bandwidth scans use only 

two 

relays, not 

three

-

Exploit: Launch DoS on another relay by blocking traffic only when on a circuit

with that relay

•

Results of scans are used only to proportionally adjust 

self-reported

measurements

-

Exploit: Lie

P

e

e

r

F

l

o

w

:

S

e

c

u

r

e

L

o

a

d

B

a

l

a

n

c

i

n

g

A

l

t

e

r

n

a

t

i

v

e

•

Periodically estimate relay bandwidth and use estimates to calculate

selection weight

•

Three estimates of relay bandwidth:

1.

Measurements 

collected from relays about other relays

•

Use natural traffic to generate measurements

•

Ignore measurements made by smaller relays

•

Add random noise to measurements before sending

2.

Self-reports

 from relays

•

Relays report estimate of own capacity

•

Reports are not trusted

3.

Expected 

traffic carried

•

Based on selection weight in last measurement period

P

e

e

r

F

l

o

w

:

H

i

g

h

-

l

e

v

e

l

I

d

e

a

•

Use estimates to choose relay selection weight

-

Selection weight ~= fraction of traffic carried

If 

measured

bandwidth ≥ 

expected

 bandwidth and

self-reported

 bandwidth > 

measured

 bandwidth:

I

n

c

r

e

a

s

e

s

e

l

e

c

t

i

o

n

w

e

i

g

h

t

If 

measured

bandwidth < 

expected

 bandwidth and

self-reported

 bandwidth > 

measured

 bandwidth:

D

e

c

r

e

a

s

e

s

e

l

e

c

t

i

o

n

w

e

i

g

h

t

i

n

n

e

x

t

p

e

r

i

o

d

t

o

b

e

e

q

u

a

l

t

o

m

e

a

s

u

r

e

d

b

a

n

d

w

i

d

t

h

i

n

t

h

a

t

p

e

r

i

o

d

P

e

r

f

o

r

m

a

n

c

e

o

f

P

e

e

r

f

l

o

w

V

e

r

d

i

c

t

:

A

l

t

e

r

n

a

t

i

v

e

t

o

T

o

r

•

Verdict: accountable anonymity through Dining-Cryptographers

Networks (DC-Nets)

-

Original paper: Henry Corrigan-Gibbs, David Isaac Wolinsky, Bryan Ford

(USENIX 2013)

•

Not vulnerable to an adversary, even if they can view all messages

•

Trade-off: Users take turns sending messages over network,

increasing latency

•

Proof of security!

V

e

r

d

i

c

t

A

r

c

h

i

t

e

c

t

u

r

e

•

Multi-provider cloud

-

Each client connected with one or more servers

-

Each server connected with all other servers

•

Anytrust

-

At least one server is honest

V

e

r

d

i

c

t

P

r

o

p

e

r

t

i

e

s

P

r

o

v

e

n

•

A

c

c

o

u

n

t

a

b

i

l

i

t

y

-

Whenever the protocol fails, an honest node can produce a proof that shows a

deviation from the protocol on the part of one other participant

-

A dishonest participant can’t produce a proof blaming an honest participant

•

With every message, each participant sends a non-interactive zero-

knowledge proof that the sender is following the protocol

•

A

n

o

n

y

m

i

t

y

•

I

n

t

e

g

r

i

t

y

V

e

r

d

i

c

t

P

r

o

p

e

r

t

i

e

s

P

r

o

v

e

n

•

A

c

c

o

u

n

t

a

b

i

l

i

t

y

•

A

n

o

n

y

m

i

t

y

-

As long as there are two honest clients, no other participant can tell which client

sends which message, even if they can see all messages being sent over the

wire

•

A

d

v

e

r

s

a

r

y

c

a

n

’

t

d

i

s

t

i

n

g

u

i

s

h