Transcript Private Information Retrieval report(new2

Private Information Retrieval
Benny Chor, Oded Goldreich,
Eyal Kushilevitz and Madhu Sudan
Journal of ACM Vol.45 No6. 1998
Reporter : Chen, Chun-Hua
Date : 2003/10/14
Outline







Motivation
Introduction
Formal Model & Definition
Notation
A Basic Two-Server Scheme
A Multi-Server Scheme
Conclusion
Motivation


In e-commerce the protection of user privacy
was not considered feasible until PIR
problem was stated(Private Information
Retrieve 36th IEEE FOCS , pp.41~50,1995)
Rough Def of Private Information
Retrieve(PIR)

A PIR protocol allows a user to retrieve a record
from a database while hiding the identity of the
record from a database server
Motivation

Where did the need for PIR come from

Patent(專利) Databases


If the patent server knows which patent the user is
interested in , this could cause a lot of problem
Pharmaceutical(製藥) Databases

To hide the plans of the company drug designers buy
the entire Pharmaceutical Database
Introduction

Consider a user makes a query to a database



A lot of research was devoted to methods to
protect the database against a curious user
But there are no methods to protect the privacy
of the user(before 1995)
However, it is not difficult to prove that if the
user wants to keep its privacy, the only thing
he can do is to ask for a copy of the whole
database --- it is unacceptable
Introduction

Because the rapid development of distributed
databases and fast communication network,it
may be possible to make queries to several servers
such that from the answers the desired
information can be obtained while each server
get no information on the identity of the item the
user is interested

Assumption



The database is a binary string x = x1x2…xn of length n
Identical copies of this string are stored by k >= 2 servers
The user is interested in the value of bit xi
Introduction

Private Information Retrieval Scheme : The
user queries each of the k servers and gets
replies from which the desired bit xi can be
computed. The query to each server is
distributed independently of i and therefore
each server gains no information about i. A
scheme with these properties is called a
Private Information Retrieval scheme
Introduction



Two server scheme with communication complexity
O(n1/3)
Scheme of k servers with communication
complexity O(n1/k)  O(n1/(2k-1))
A scheme for 1/3*log2n+1 servers with total
communication complexity
1/3*(1+O(1))*(log2n)2*log2log2(2n)
(Ref : Private Information Retrieve 36th IEEE
FOCS , pp.41~50,1995)
Formal Model & Definition





Index i  [n] => {1,2,3,…,n}
Random input r of length Lrnd
Produces k queries of length Lq to k servers :
Q1(i,r),…,Qk(i,r)
The servers respond A1,…,Ak of length La
according to the content of X and the
corresponding query
The user reconstructs the desired bit xi from
these k replies
Formal Model & Definition

Definition 1 A k-servers Private Information
Retrieval(PIR) scheme for database length n consists of




k query functions Q1,…,Qk : [n] x {0,1}Lrnd  {0,1}Lq
k answer functions, A1,…,Ak :
{0,1}n x {0,1}Lq  {0,1}Lq
a reconstruction function ,R :
[n] x {0,1}n x {0,1}Lrnd x ({0,1}La)k  {0,1}
These functions should satisfy Correctness & Privacy
Formal Model & Definition


Correctness : For every x  {0,1}n , i
and r  {0,1}Lrnd

R(i, r, A1(x,Q1(i,r)),…,Ak(x,Qk(i,r))) = xi

Pr(Qs(i,r) = q) = Pr(Qs(j,r) = q)
where the probabilities are taken over uniformly chosen
r  {0,1}Lrnd
Privacy : For every i,j  [n], s  [k],
and q  {0,1}Lq



 [n],
Extensions : PIR of Blocks
Single Bit PIR Schemes
Notation

Notation : the following notations throughout the paper






U : a user
SRV1,…,SRVk : the servers
x = x1…xn a string in {0,1}n , known to each server
representing the database
i : the index in x in which U is interested
[m] => {1,2,…,m}
For a set S and an element a let
S a => S Ù {a} if a  S
= > S \ {a} if a  S
A Basic Two-Server Scheme

The steps of the scheme are as below :




The user uniformly selects a random set S  [n]
The user sends S to SRV1 and S i to SRV2
Each server replies with a single bit which is the
Exclusive OR of the bits with indices from SRV1,2
(SRV1 replies with j S xj
SRV2 replies with j S i xj )
The user Exclusive OR all the answers it has
received thus retrieving the desired bit xi
A Basic Two-Server Scheme

The steps of the scheme are as below :




The user uniformly selects a random set S  [n]
The user sends S to SRV1 and S i to SRV2
Each server replies with a single bit which is the
Exclusive OR of the bits with indices from SRV1,2
(SRV1 replies with j S xj
SRV2 replies with j S i xj )
The user Exclusive OR all the answers it has
received thus retrieving the desired bit xi
A Basic Two-Server Scheme (Example)

User randomly choice S = {5,15,47}
(n=100 , index i = 15, S i = {5,47})
(3) x5
x15
x47
(1) S ={5,15,47}
(2) S
(4) x5 x47
SRV1
i ={5,47}
SRV2
A Basic Two-Server Scheme (Example)

User compute the desired bit xi
 (SRV1  )
(SRV2  )
 ( x5  x15  x47 )  ( x5  x47 )
 ( x5  x5 )  ( x47  x47 )  x15
 0  0  x15
 x15
( x  y  y  x
x  ( y  z)  ( x  y)  z  x  y  z
xi  0  0  xi  xi )
A Multi-Server Scheme

A scheme for any number k≧2 servers



The scheme allows the user to obtain the desired bit by
asking queries to k =2d servers. For any d≧1, it requires
total communication complexity of
2d * (d * n1/d + 1)
The key idea is to associate [n] with the d dimensional
cube [L]d and generalize the two-server scheme which may
be viewed as the 1-dimensional case (i.e. d = 1)
Assume n = [L]d and embed x in a d-dimensional cube.
Associate each position j  n with a d-tuple (j1,…,jd) [L]d .
In particular
the index i of the desired bit is associated with a d-tuple
(j1,…,jd) [L]d
A Multi-Server Scheme (Steps)
Conclusion

Some feelings of research




Remember the study of algorithm
Research the topic slowly
Treasure the beauty of the papers
Research groups




Cryptography and Information Security Group:
Private Information Retrieval (Research topic at
MIT)
Private Information Retrieval Research at BGU
PIR Research (Dartmouth (old research))
Amos Beimel
Conclusion

Research Directions

Extension of PIR



Relax some requirement


Robust PIR
T-privacy
encryption is permitted for
one server O(Nε), ε>0
Make PIR pratical



H/w
Combination with Datebase
Application on EC