Transcript a 1 - AI LAB

Public Key
Encryption that
Allows PIR Queries
Dan Boneh、Eyal Kushilevitz、
Rafail Ostrovsky and William E. Skeith
Crypto 2007
Private Information Retrieval
(PIR)
i
j
i {1,…n}
x=x1,x2 , . . ., xn
SERVER
{0,1}n
xi
USER
PIR
• allows a user to retrieve an item from a
server in possession of a database
without revealing which item she is
retrieving.
• existing PIR solutions
– retrieving a (plain or encrypted) record of
the database by address
– search by keyword in a non-encrypted data
Query
Answer
Outline
• Introduction
• Tools:
– Bloom Filter
– Modifying Encrypted Data in a
Communication Efficient Way
• Definition
• Main Construction
Introduction
• Interesting in:
– communication-efficient
– complete privacy.
• Technique:
– Receiver: creates a public key .
– Sender: message M is accompanied by an
“encoded” list of keywords .
Bloom Filters
• Basic idea:
Suppose
a  S hi : 0,1  m
1
*
2
3
4
5
6
…
h1(a)
…
h2(a)
…
h3(a)
aS
…
…
hk(a)
T
m
0
1
1
1
1
0
…
1
Bloom Filters (cont.)
• What to store :
– certain element is in a set
– value v V which are associated to the
element in the set.
• Definition. As same to above. But
together with a collection of
sets, B  ,where B  V . Then to insert a
pair (a, v) into this structure, v is added
to B for all i  [k ] . The set of values
associated with a  S is simply    B .
m
j i 1
j
hi (a )
i k
hi ( a )
then (a2, v2) … check
Insert (a1, v1)
h1(a1)
V1
B1
V1 ,V2
B2
V3
h2(a2)
B3
hk(ak)
V1
Bm
V1
V2 ,V3
V1 ,V3
{V1 ,V2}
∩
h2(a2)
…….
…….
…….
V1
V2
h1(a1)
hk(ak)
{V1}
∩
{V1 ,V3}
||
V1
Modifying Encrypted Data in a
Communication Efficient Way
• Based on group homomorphic encryption
with communication O(√n).
• Technique :
– xij i , j 1: database (not encrypted)
– (i*,j*): the position of particular element
– α: the value we want to add.
– v , w: two vector of length √n where
vi   ii*
w j   jj
– Here δkl = 1 when k=l and 0 otherwise
– Then
 if (i  i*  j  j * )
n
*
vi w j  
0
otherwise
Modifying Encrypted Data in a
Communication Efficient Way
(cont.)
• Parameters:
– (K, E, D): a CPA-secure public-key
encryption
u


c

E
(
x
)
– l
l l 1: an array of ciphertexts which is
held by a party S.
– Define F(X, Y, Z)=X+YZ. By our
assumption, there exists some F~ such that
~
D( F ( E ( x), E ( y ), E ( z )))  F ( x, y, z )
Modifying Encrypted Data in a
Communication Efficient Way
(cont.)
•
Protocol: ModifyU,S(l, α) where l and α
are private input to U.
1. U compute i*, j* as the coordinates of l
(i.e., i* and j* are quotient and remainder
of l/n, respectively)
n
n




v

E
(

)
,
w

E
(

)
2. U sends i
to S
j
ii
jj
i 1
j 1
where all values are encrypted under
Apublic.
~
3. S computes F (cij , vi , w j ) for all i, j   n , and
replaces each cij with the corresponding
resulting ciphertext.
*
*
Definition
• Parameters:
– X: message sending parties.
– Y: message receiving party.
– S: server/storage provider.
• Definition 1:probabilistic polynomial time
algorithms and protocols:
– KeyGen(1S)
– SendX,S(M, K, Apublic)
– RetrieveY,S(w, Aprivate)
Main Construction
• S maintains in its storage space
encryptions of the buffers, denote these
m
encryptions B j j 1
*


w

0
,
1
• For
, we defined H w  hi (w) i  k 
• KeyGen(k) :Run K(1s), generate Apublic
and Aprivate.
SendX,S(M, K, Apublic)
Sender
Storage Provider
E (M )
ρ
γ copies of the
address ρ
E ( M )  M  K
E (M )
A public
ModifyX,S(x, α)
ρ
ρ
ρ
ρ
ρ
Message
Buffer
Bloom
Filter
Buffer
B 
j jH
w
RetrieveY,S(w, Aprivate)
Receiver
Storage Provider
PIR Query
B 
j jH
w
PIR Query
B 
j jH
w
 
Dec

Bj
E (M )
jH w
L   jH B j B j jH
compute
w
M private
 D( E ( M ))
A
Modifyy,S(x, α)
w
Message Bloom
Buffer
Filter
Buffer
B 
E ( M ) 
 L
po int
j jH
w