Transcript PPT

Constant-Round
Private Database
Queries
Nenad Dedic and Payman Mohassel
Boston University
UC Davis
Outline





Introduction
Element rank protocol
Other protocols
Equivalence to one-round PIR
Open problems
Succinct Computation
• Computing f(x,y)
• One round of interaction
q = Q(x)
x
Server
Client
Dec(a) = f(x,y)
y
a = A(q,y)
• Communication Complexity
•|q| +|a| = O(poly(log(|x|), log(|y|), |f(x,y)|, s))
•Or linear in |f(x,y)|
Privacy


Computational setting
Client side


Server side


For any x, x’, Q(x) and Q(x’) are indistinguishable
Simulator S, simulates A(x,y) given x and f(x,y)
Semi-honest adversaries
Private Database Queries



Server’s input is a database
Client’s input is a query
Private information retrieval (PIR)


f(i, (x1,x2,…,xn)) = xi
Private Keyword search (PKS)
f(w, {(x1,v1),…,(xn,vn)}) =
va if there is xa= w
┴ otherwise
Existing Solutions

PIR / SPIR



[KO97], [Lipmaa05], …
One-round, sublinear communication
PKS



[FIPR05]
One-round, polylog(n) communication
PIR and homomorphic encryption
How about more general queries?
More General Queries

General MPC


Circuits with look-up tables [NN01]



Communication efficient
High round complexity
One-round secure computation [CCKM00]



Not efficient
Round efficient
High comm.
Computing BP on encrypted data [IP07]



Independent work
Round and communication efficient
Strong assumption
Private Element Rank

Interval Labeling


Element Rank



f(b, (x1,x2,…,xn,v1,…,vn)) =
vi such that b є (xi, xi+1]
Add x0 = -∞ and xn+1=+∞
vi = i
Applications



Ranking in auctions
Online testing services
Use to design other protocols
Interval Labeling Protocol
b, x1,x2,…,xn є {0,1}k
Run a PKS for every prefix of b




jth query = j-bit prefix of b
Create and use a database D
Interval Labeling Protocol
0
1
0
1
0
1
v4
0
1
v0
0
v1
v1
x1
x2
1
0
1
v2
v2
v3
0
1
v2
x3
x4
D = {(000,v0),(001,v1),(0100,v1) , (0101,v2),(011,v2),(100,v2),(101,v3),(11,v4)}
Interval Labeling Protocol
b = 1000
0
1
0
1
0
b1 = 1
1
b2 =10
v4
0
1
v0
0
v1
b3 =100
v2
v1
x1
1
x2
0
1
v2
v3
0
1
v2
b4 =1000
x3
x4
D = {(000,v0),(001,v1),(0100,v1) , (0101,v2),(011,v2),(100,v2),(101,v3),(11,v4)}
Interval Labeling Protocol

w’ is w with last bit flipped

Database D, where |D| ≤ 2kn

For every 1≤ j ≤ k, let w be j-bit prefix of xi:
1.
2.

Add (w,vi) to D if:
[w||0k-j, w||1k-j]
[xi,xi+1] , but not true for w’
Add (w’,vi) to D if:
[w’||0k-j, w’||1k-j]
[xt ,xt+1] , but not true for w
Prefixes of xi’s and/or their siblings
Interval Labeling





ri = PKSA(bi ,D) for 1 ≤ i ≤ k
Randomly permute (r1, r2, … ,rk) and send
Decode; retrieve the only ri ≠ ┴ in the list
One round, polylog(n) communication
Reduced to PKS
Other Protocols

Private Rectangle Labeling




Which rectangle is query point in?
Extension to higher dimensions
One round
Private Range Queries




Retrieve all the points in the range
On a line or in a plane
Constant round
Comm. proportional to number of retrieved points
Other Protocols




mth ranked element
Alice holds database A
Bob holds database B
Find mth ranked element in (A U B)


[AMP04], O(log(m)) rounds, and sublinear comm.
We use our rank protocol as subprotocol


O(log(log(m))) rounds
Still sublinear comm.
PKS to PIR
f(w, {(x1 ,v1),…,(xn ,vn )}) =

[FIPR05]




va if there is xa= w
┴ otherwise
Database
 Hash function h : {0,1}n
{0,1}n/log(n)
 Hash keywords (xi’s) to n/log(n) bins
 Create degree log(n) polynomials for each bin
Client
 Compute h(w)
 Send E(h(w)) , E(h(w)2), …, E(h(w)log(n))
Database evaluates all polynomials at h(w)
Client gets one result via PIR
PKS to PIR


Assumption: One-round PIR
Replace polynomials with Yao’s garbled circuit


Yao’s protocol




Circuit of size O(polylog(n)) size
Pseudorandom function, OT
Can be reduced to one-round PIR
 [CMO00], [BIKM99]
One-round PKS
One-round Rank
one-round PIR
one-round PKS
Open Problems

Succinct Computation of



Branching programs (not length-bounded)
General circuits
Reduction to one-round PIR



Any special functionality
Decision trees
Branching programs
Thank you!