Transcript Using low-degree Homomorphism for Private Conjunction Queries

July 18, 2015
Using low-degree
Homomorphism for
Private Conjunction
Queries
Dan Boneh, Craig Gentry, Shai Halevi, Frank Wang, David Wu
1
Private Conjunction Queries
SELECT ⋆ FROM db WHERE a1=v1 AND … AND at=vt
• Want to hide the values vi from the serve
• maybe also the attributes ai themselves
July 18, 2015
• Clinet has an SQL query of the type
• Our protocols return the indexes of the matching records
• The client can use PIR or ORAM to fetch the records
themselves
2
The Basic Approach
• A set S is encoded as a polynomial P(X) s.t. P(s)=0 for all s  S
• Use Kissner-Song trick
• If P1(X), P2(X) represent S1, S2, the a random linear combination
A X = 𝑅1 𝑋 𝑃1 𝑋 + 𝑅2 𝑋 𝑃2 (𝑋) represents the intersection
of S1, S2, whp.
• If deg 𝑅1 = deg(𝑃2 ) and deg 𝑅2 = deg(𝑃1 ) then A(X) does not
leak any information beyond the intersection
July 18, 2015
• Encode database as a polynomial
3
• Server has database
• Client has secret-key for SWHE scheme
• Server encode database as bivariate polynomial D(x,y)
July 18, 2015
Two-Party Settings
• D(r,a)=v if record r has attribute a=value v
• Size of D ~ size of database
4
Conjunction Queries
• Client interpolates Q(y) s.t. Q(attri)=vali
• Send the encrypted Q to server
• For simplicity send also attr1,…,attrt in the clear
July 18, 2015
• “attr1=val1 AND … AND attrt=valt”
• Server computes 𝐴(𝑥, 𝑦) = 𝐷(𝑥, 𝑦) − 𝑄(𝑦)
• Additive homomorphism suffices
• A(r,attri)=0 iff D(r,attri)=vali
• Server defines Ai(X) = A(X,attri)
• Roots of Ai(X) are records that have attri=vali
5
• Server uses Kissner-Song trick, set 𝐵(𝑋) =
𝑡
𝑖=1 𝑅𝑖 (𝑋)𝐴𝑖 (𝑋) for random 𝑅𝑖 ’s
• Whp roots of B are the records in the intersection of the 𝐴𝑖 ’s
• Still additive homomorphism is enough
July 18, 2015
Conjunction Queries (cont.)
• Need more if attri’s are not send in the clear
• Server sends encrypted 𝐵 to client
• Client decrypts, find roots 𝑟𝑖 , uses PIR/ORAM to get
actual records
• To hide also the attributes we need higher-degree
homomorphism
6
• Proxy has encrypted inverted index
• For every attr=val in DB, keeps a pair (t, Enc(P))
• Tag t = Hash(“attr=val”)
• P is polynomial s.t. P(r)=0 if record #r contains this “attr=val” pair
July 18, 2015
Three parties: Client-ProxyServer
• Client sends tags ti for attri=valuei in query
• Proxy chooses randomizers Ri sets 𝑄 = 𝑖 𝑃𝑖 𝑅𝑖
• Q has roots in the intersection
• Server obliviously decrypts for Client
• Client factors Q, finds roots 𝑟𝑖 , uses PIR/ORAM to get
actual records
7
Conserving Bandwidth
𝑖 𝑃𝑖 𝑅𝑖
is a wasteful representation
• Degree ~ 2 max(deg(Pi))
• High degree needed for Q to not leak information on the Pi’s
• Reducing to max(deg(Pi))+min(deg(Pi)) easy:
• Say P1 has smallest degree, then set 𝑄 ′ =
July 18, 2015
• 𝑄=
𝑛
𝑖=2 𝑃𝑖 𝑠𝑖
• The si’s are random scalars
• 𝑄 = 𝑃1 𝑅 + 𝑄’𝑅’, deg(R)=deg(Q’), deg(R’)=def(P1)
• Can we reduce it further?
• We show how to get min(deg(Pi))
8
Polynomial GCD
• 𝑃𝑏 (𝑋) =
𝑖∈𝑆𝑏 (𝑋
− 𝑖)
• The smallest polynomial defining 𝑆1 ∩ 𝑆2 is 𝐺(𝑋) =
𝐺𝐶𝐷 𝑃1 , 𝑃2 = 𝑖∈𝑆1∩𝑆2(𝑋 − 𝑖)
July 18, 2015
• P1, P2 are (monic) polynomials for the sets S1,S2
• G does not leak information on P1,P2 beyond the intersection
• Computing Enc(G) from {Enc(Pb)}b takes high
homomorphic capacity
9
Reducing The Degree
′ = 𝑄 𝑚𝑜𝑑 𝑃
𝑅
𝑃
,
use
Q
1
𝑖 𝑖 𝑖
• It has degree ≤ deg 𝑃1 − 1
• If Q is a random multiple of G, so is Q’
• Computing Enc(Q mod P1) is easier
• Basic Solution:
July 18, 2015
• Instead of 𝑄 =
• Store also 𝐸𝑛𝑐 𝑋𝑖 𝑚𝑜𝑑 𝑃1 ∀𝑖
• Given the encrypted coefficeints of Q
• 𝐸𝑛𝑐 𝑞0 , … , 𝐸𝑛𝑐 𝑞𝑑 , … 𝐸𝑛𝑐 𝑞𝑛
• Compute Enc(
𝑛
𝑖
𝑖=0 𝑞𝑖 (𝑋 𝑚𝑜𝑑
(𝑑 = deg(𝑃1))
𝑃1 ))
• Only takes quadratic homomorphism
10
Reducing The Degree (cont.)
• Can store less encryptions of 𝑋𝑖 𝑚𝑜𝑑 𝑃1 by using higher
homomorphic capacity
• E.g., Store 𝐸𝑛𝑐
𝑡
2
𝑋
𝑚𝑜𝑑 𝑃1 , t = 0,1,2, …
July 18, 2015
• Storage/homomorphism tradeoff
• When deg(Q)=d+m, it takes log m steps to reduce Q mod P1
• Using 𝑄 𝑋 ≡
𝑡
2
𝑖 𝑄𝑖 𝑋 𝑋 𝑚𝑜𝑑 𝑃1
deg < 2t
𝑚𝑜𝑑 𝑃1
deg < d
11
Speedup Using Batching
• L is at least a few hundred, maybe more
• Can use it to get significant speedup:
• Break the database into L small db’s
July 18, 2015
• Recall: a HE ciphertext encrypts an array of L values
• Each record is places at random in one of the small db’s
• Run the same query against all the small db’s at once
• The i’th database in the i’th entry of all the cipehrtexts
• So we get L lists of indexes instead of one
• i’th list has the indexes of the records in the i’th database that match
the query
• Lists are much shorter polynomials have much smaller degree
12
Implementing 3-party protocol
• Only the basic scheme using additive cryptosystem (Pallier)
• The full scheme using the [Bra’12] HE
• Only the 2nd implementation scales to large databases
July 18, 2015
• Two implementation:
• Batching is key
• With and without the bandwidth-reduction GCD trick
• Without it we need lower homomorphism, smaller parameters
• All tests run against a 1-million record database,
executing a 5-attribute conjunction (𝑎1 = 𝑣1 , … , 𝑎5 = 𝑣5 )
• Balanced tests: each 𝑎𝑖 = 𝑣𝑖 matches roughly same # or records
• Unbalanced: 𝑎1 = 𝑣1 matches only ~5% as many as 𝑎5 = 𝑣5
13
Balanced Queries
~2000 matches per tag,
8 minutes, 1MB
July 18, 2015
Time (minutes)
14
Bandwidth (MB)
Unbalanced Queries – Time (min)
157.6
July 18, 2015
180
160
140
120
100
80
60
40
20
0
124.1
83.6
65.2
32.4
34.3
23.7 20.8
Query 1
(2.5K,2.5K,5K,10K,50K)
17.9
Query 2
(10K,20K,25K,50K,200K)
Query 3
(2.5K,2.5K,5K,5K,350K)
NOMR: No modular reduction
MR: With modular reduction
15
Unbalanced Queries – Bandwidth (MB)
35
July 18, 2015
29.4
30
25
19.9
20
15
10
5
12.1
7.9
4.4
8.2
6.3
3.4
4.8
0
Query 1
(2.5K,2.5K,5K,10K,50K)
Query 2
(10K,20K,25K,50K,200K)
Query 3
(2.5K,2.5K,5K,5K,350K)
NOMR: No modular reduction
MR: With modular reduction
MRNoKS: modular reduction, no key-switching
16