Secure Computation of Constant-Depth Circuits with ...

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?

Recently Viewed Presentations

  • 5 Types of Reactions - West Branch High School

    5 Types of Reactions - West Branch High School

    5 Types of Reactions Combination/Synthesis Rxns. A + B AB H2 + O2 Be + O2 Mg3N2 Types of Synthesis Reactions Metal + Oxygen metal oxide Nonmetal + Oxygen nonmetallic oxide Metal oxide + water metallic hydroxide Nonmetallic oxide +...
  • 112016 ABP internal PPT template - Humber

    112016 ABP internal PPT template - Humber

    Humber Estuary Services. ABP is both the Statutory Harbour Authority (SHA) and Competent Harbour Authority (CHA) for the Humber. An SHA is a harbour authority, which has been given a range of statutory powers or duties for the purpose of...
  • Penguin Math Book - Mrs. Lemacks's Computer Lab

    Penguin Math Book - Mrs. Lemacks's Computer Lab

    By: Group and add similar penguins, then type a number sentence! Put the penguins in order by their Roman Numeral. I II IX VIII VII VI V IV X III Type the correct number sentence in the blue box for...
  • 包子 Bāozī - University of Virginia

    包子 Bāozī - University of Virginia

    Shàngkè le! 上课了! Tóngxué menhăo. Lăoshī hăo. 同学们好!老师好! * Xiàkè le, qǐng qǐ lì. 下课了!请起立。 Xièxie lăoshī ...
  • Persia, the Greeks and Alexander

    Persia, the Greeks and Alexander

    Creates the League of Corinth. Elected to lead the Greek army against Persia. Assassinated. Sarissa - 13-20 feet long. Alexander III of Macedon "The Great"July 356 - June 323 BCE. 337 BCE - Became king on his father's death. Bloody...
  • 13th Indo-American Corporate Excellence Awards, 2017 - Nomination

    13th Indo-American Corporate Excellence Awards, 2017 - Nomination

    Business Mogul . of . the Year. The award is aimed at recognizing the leaders with outstanding contributions impacting all spheres of the corporate ecosystem - business, industry and the overall community. ... Indo-Us Trade Driver of the year -...
  • "The Gift of the Magi"

    "The Gift of the Magi"

    "The Gift of the Magi" O. Henry Allusion A reference in one work of literature to a historical event, person, or another work of literature, often used to deepen the meaning of the story. According to Christian tradition, the Magi...
  • Crew Resource Management Refresher 2002

    Crew Resource Management Refresher 2002

    Operational Risk Management (ORM) Step #2: Identify Hazards Use the "PEACE" Model to remember the 5 risk factors: Planning Event Complexity Asset Selection Communications Environmental Conditions Step #3: Assess the Risks SPE RISK ASSESSMENT MODEL Risk=Severity x Probability x Exposure...