Project Two
Jiaqi Zhou
Analysis
• Let the number of items in the database be n, so the database is x1 . . . xn .
• Pad the database with dummy items so that n = l3 (l ∈ Z+ ). Represent the database as a
cube {Xu,v,w : u, v, w ∈ {1, . . . , l}} so that each Xu,v,w corresponds to a unique item among
x1 . . . xn , and any item’s position can be represented as (u, v, w).
• To retrieve an item at the position (u, v, w), a client chooses a pair of prime numbers (p, q)
such that p ̸= q, computes public key pk = N = pq and secret key sk = (p, q) for Paillier
encryption, and sends pk = N along with the following three query vectors to the server:
• (a1 , . . . , al ): for i = 1, . . . , l:
• If i ̸= u, let αi = 0, ri ← ZN
∗ , a = Enc(pk, α ) = r N mod N 2 .
i i i
• If i = u, let αi = 1, ri ← ZN
∗ , a = Enc(pk, α ) = (1 + N )r N mod N 2 .
i i i
• (b1 , . . . , bl ): for j = 1, . . . , l:
• If j ̸= v, let βj = 0, sj ← ZN
∗ , b = Enc(pk, β ) = sN mod N 2 .
j j j
• If j = v, let βj = 1, sj ← ZN
∗ , b = Enc(pk, β ) = (1 + N )sN mod N 2 .
j j j
• (c1 , . . . , cl ): for k = 1, . . . , l:
• If k ̸= w, let γk = 0, tk ← ZN
∗ , c = Enc(pk, γ ) = tN mod N 2 .
k k k
• If k = w, let γk = 1, tk ← ZN ∗ , c = Enc(pk, γ ) = (1 + N )tN mod N 2 .
k k k
Q
l Xi,j,k
• For each j = 1, . . . , l, k = 1, . . . l, the server computes fj,k = a
i=1 i mod N 2 .
• For each
Q k = 1, . . . , l, the
server computes
Q
l (fj,k mod N ) 2 ′ l ⌊fj,k /N ⌋
gk = j=1 bj mod N , gk = j=1 bj mod N 2 .
• The server computes Q
Ql (gk mod N ) l ⌊gk /N ⌋
h= k=1 ck mod N 2 , h′ = k=1 ck mod N 2 ,
Q ′
(gk mod N )
Q ′
⌊gk /N ⌋
l l
h′′ = c
k=1 k mod N 2 , h′′′ =
k=1 kc mod N 2 .
• The server sends (h, h′ , h′′ , h′′′ ) to the client.
• By the homomorphic
P property of Paillier encryption,
l
fj,k = Enc pk, Xi,j,k αi mod N ,
P i=1 P
l ′ = Enc pk, l
gk = Enc pk, (fj,k mod N )β j mod N , g ⌊f j,k /N ⌋β j mod N ,
P j=1 k
P j=1
l l
h = Enc pk, (gk mod N )γk mod N , h′ = Enc pk, k=1 ⌊gk /N ⌋γk mod N ,
Pk=1 P
l l
h′′ = Enc pk, k=1 k(g ′ mod N )γ
k mod N , h′′′ = Enc pk, ⌊g
k=1 k
′ /N ⌋γ
k mod N .
1
• Additionally, fj,k , gk , gk′ ∈ ZN 2 =⇒ ⌊fj,k /N ⌋, ⌊gk /N ⌋, ⌊gk′ /N ⌋ ∈ ZN .
• Assuming Xu,v,w ∈ ZN , the client computes the following:
P
l
• Dec(sk, h) = k=1 k (g mod N )γ k mod N = gw mod N .
P
l
• Dec(sk, h′ ) = k=1 ⌊gk /N ⌋γk mod N = ⌊gw /N ⌋.
P
l
• Dec(sk, h′′ ) = (g
k=1 k
′ mod N )γ
k
′ mod N .
mod N = gw
P
l
• Dec(sk, h′′′ ) = ⌊g
k=1 k
′ /N ⌋γ
k mod N = ⌊gw′ /N ⌋.
• gw = (gw mod N ) + N ⌊gw /N ⌋ = Dec(sk, h) + N · Dec(sk, h′ ).
• gw
′ = (g ′ mod N ) + N ⌊g ′ /N ⌋ = Dec(sk, h′′ ) + N · Dec(sk, h′′′ ).
w w
P
l
• Dec(sk, gw ) = j=1 (fj,w mod N )β j mod N = fv,w mod N .
P
l
• Dec(sk, gw′ )=
j=1 ⌊fj,w /N ⌋βj mod N = ⌊fv,w /N ⌋.
• fv,w = (fv,w mod N ) + N ⌊fv,w /N ⌋ = Dec(sk, gw ) + N · Dec(sk, gw
′ ).
P
l
• Dec(sk, fv,w ) = i=1 Xi,v,w α i mod N = Xu,v,w .
• The client has retrieved Xu,v,w from the server without learning information about any other
database items, only sending 3l = O(n1/3 ) Paillier ciphertexts to the server, while (u, v, w)
remains secret from the server.
Implementation
The project code consists of the following three Python files:
• [Link]: A PIR client that is given the number of database items and the server address,
and retrieves an item from the server when an item index is entered at a prompt.
• It includes an implementation of Paillier encryption that ensures the two primes (p, q) both
have 2048 bits.
• After computing l, pk and sk, it does the following in a loop:
• Prompt for the index of an item to retrieve.
• Compute (u, v, w) from the index and the edge length.
• Compute the query vectors from (u, v, w).
• Send pk and the three query vectors as JSON to the server in an HTTP POST request.
• Receive (h, h′ , h′′ , h′′′ ) as JSON in the server’s response.
• Compute Xu,v,w from (h, h′ , h′′ , h′′′ ) and print it.
• [Link]: A PIR server that is given the database content (as a file) and a server address,
and responds to PIR requests from clients. It does the following:
• Compute l, and store the database items in a cube, using 0 as the padding item.
• Upon receiving a public key and three query vectors as JSON in an HTTP POST request,
compute (h, h′ , h′′ , h′′′ ), and send them as JSON in the response.
• [Link]: A generator that generates a random database (with a specific number of items)
in the format desired by [Link] for testing.