Secure Computation of Constant-Depth Circuits with Applications to Database Search Problems Omer Barkol Yuval Ishai Technion Motivation: private database search ?D Client Server q D fermat and (last theorem or great theorem) Article f(q,D) on Fermats Last Theorem PIR [CGKS95]: f(q,D)=Dq OT/SPIR ?q on ?What is he working Want: Server work: O(|D|) Client work: O(|q|)

Communication: O(|q|) Current approaches Send all of D to the client q f(q,D) Too much communication (|D|) No server privacy Use general purpose secure computation [Yao86,GMW87] Communication > circuit size > |D| Use PIR as a building block: PIR + data-structures [CGN97,FIPR05,OS05] Oh Applies to a very limited class of problems: set membership / keyword search approximate nearest neighbor no! This might !take me 7 years Communication preserving protocol compiler [NN01] Benchmark: partial match? Generally requires exponential computation f( *1*0 , 0010 0110 1111 )=1 Nothing

D Observation: Many database search problems can be implemented by constant-depth circuits output depth 2 x1 x2 xm inputs Gates: OR,AND,NOT and XOR Unbounded fan-in and fan-out Depth: length of the longest inputoutput path Observation: Many database search problems can be implemented by constant-depth circuits q D f(q,D) x

C x1 C(x) = f(q,D) x2 x5 x6 Example: partial match 1010 *1*0 0110 1011 1110 Preprocess: 0 10 1 01

* 11 1 1 0 1 1 1 1 0 Observation: Many database search problems can be implemented by constant-depth circuits q D f(q,D) Computing on encrypted data C longstanding question x Case of 2-DNF recently solved [BGN05]

x1 (x1 C(x) x3 ) =(xf(q,D) 2 x4 ) (x3 x4 ) x2 x5 x6 Relaxation: multiple servers C x C C C(x) Used in information theoretic PIR Replicated databases are common p2p networks Web content delivery (e.g., Akamai) t-privacy Client can choose servers he trusts x1 ?x

x2 t servers x5 x6 Main results t-secure protocol with: Servers: t(log|C|)depth-1 Communication: (|x|) Client computation: (|x|) Server computation: (|C|) Rounds: 1 Communication and work are optimal !Yehup to polylog factors C C C x1 x2

x5 x6 Main results: DNF/CNF/partial match n-term DNF / database with n entries Security threshold 1 D has 230 Secure protocol with: entries Servers: logn Communication: (|x|) We need Client computation: (|x|) ~15 servers Server computation: (n) C C C x1 x2 x5 x6 Second model: multiparty computation party

input: x2 party party input: x1 Const-depth circuit C input: x3 C(x) x=x1x2.... xk x1 party input: x5 x2 x5 x6 party input: x4 General purpose secure computation [GMW87,BGW88,CCD88] Communication > circuit size

Communication efficient multiparty computation [BFKR90] Computation exponential in |x| Number of servers (x) Results: multiparty setting t-secure multiparty protocol with Parties: t(log|C|)depth-1 Communication: (|x|poly(#parties)) Computation: (|C|) Rounds: O(1) optimal up to polylog factors x1 x2 x5 x6 Roadmap From database search to protocol Server Server Server Server

Server Server Server Database D p1(x) n p2(x) 1 2 Server 3 Polynomial s x1 x2 x5 x6 Circuit pj(x)

Polynomials Client Roadmap From database search to circuit Server Server Server Server Server Server Server Database D p1(x) n p2(x) 1 2 Server 3

Polynomial s x1 x2 x5 x6 Circuit pj(x) Polynomials Client Roadmap From circuit to polynomials Server Server Server Server Server Server Server Database D p1(x)

n p2(x) 1 2 Server 3 Polynomial s x1 x2 x5 x6 Circuit pj(x) Polynomials Client From circuit to polynomials Step A: Represent a circuit by a low-degree randomized multivariate polynomial Field = GF(2) deg 1 Rely on technique of [Raz87, Smo87]

x1+x2+x4 x1 x2 no error x4 Goal: x: Probr[pr(x) C(x)] 2- From circuit to polynomials Goal: x: Probr[pr(x) C(x)] 2- r1 r2 r11 r1 r12 r2 rt

rr1tt tt t deg t1 t noerr error 2 rj(1 xr 1 (1 r x ) (1 x )) 1(1 x ) j ij j jj ij

- j1 j1 i1 i 1 j j1 1 -biased PRG r x1 x2 xt set = From circuit to polynomials Goal: x: Probr[pr(x) C(x)] 2- Prob[pr(x) C(x)] (n+1)2 n-term DNF deg err 2 deg err 2 For error 2- set = + log(n+1) -

Total degree = ( +2log(n+1))2 deg - x1 - err 2 x2 deg - x3 x4 x5 - err 2 x6

deg - err 2 From circuit to polynomials Step B: Optimizations example for n-term DNF Goal: Vector pr(x) s.t. x: Probr[R(pr(x)) C(x)] 2- - pr1(x) For error set set = logn + 3 Total degree = 3( logn+3) 3 deg err 2 deg 3 err Prob[pr(x) C(x)] n2 + deg -

x1 err 2 x2 deg - x3 x4 x5 - err 2 x6 deg - err 2 From circuit to polynomials Step B: Optimizations example for n-term DNF degree logn+2

More careful analysis: C(x)=0: Prob[p(x)=1] Recover RecoverC(x) C(x)using usingMajority Threshold C(x)=1: Prob[p(x)=1] deg 3logn err pr1(x) r1 pr2(x) x r2 pr3(x) x r3 x prO()(x)

rO() x From circuit to polynomials Step B: Optimizations example for n-term DNF O() polynomials of degree logn+2 C(x)=0 C(x)=1 pr1(x) pr2(x) 0 Prob[th(pr(x)) C(x)] 2 - prO()(x) !I have no privacy Server n From circuit to polynomials Step C: Server Privacy

pr1(x,) pr2(x,) pr1(x) Server pr2(x) th:{0,1}O(){0,1} Randomizing polynomials for threshold n [IK00] prO()(x) prO(1)(x,) private randomness Roadmap From polynomials to protocol Server Server Server Server Server Server Server Database

D p1(x) n p2(x) 1 2 Server 3 Polynomial s x1 x2 x5 x6 Circuit pj(x) Polynomials Client Client-Servers protocols from polynomials Goal: evaluate multivariate polynomials held by the servers on a point held by the client.

Standard techniques for secure computation [BGW88, CCD88, BF90] Number of servers proportional to the degree p p Communication proportional to # of polynomials (and p clients input) Shamir-shares of x p x Public randomness r p Enhancements: Evaluate p on shares r Protecting server privacy [GIKM98] Recover Reducing of servers [WY05] pr(x) number by interpolation Multiparty protocols from polynomials Goal: evaluate multivariate polynomials known to all on distributed input and randomness. Standard techniques for secure computation [BGW88, CCD88, GRR98] Number of parties proportional to the degree Communication proportional to # of polynomials (and input lenght) Randomness:

Public randomness (r) independent of the inputs Private randomness () should remain a secret Roadmap Secure computation of constant-depth circuits with applications to database search problems Server Server Server Server Server Server Server Database D pr1(x,) n 1 2 pr2(x,) Server 3

Polynomial s x1 x2 x5 x6 Circuit prj(x,) Polynomials Client Conclusions Practically feasible solutions to large scale database search problems, e.g., partial match Nearly optimal communication and computation Reasonable number of servers (logn for partial match) No expensive crypto (e.g., public key operations) Challenge: obtain similar protocols in 2-party setting Extend [BGN05] from degree 2 to degree logn? Multiparty setting: Nearly optimal communication and computation for a useful class of functions (AC0) Communication almost does not grow with circuit size Challenge: Higher complexity classes, e.g., NC1 Server Server Database n

D Ser Ser Server ver Ser Server P1(x,r) P2(x) 2 1 x1 x2 3 x5 x6 r) Questions?