Cryptographic Complexity of the Worst Functions Unveiled

on the cryptographic complexity of the worst l.w
1 / 46
Embed
Share

Delve into the cryptographic complexity of the worst functions with expert insights from Amos Beimel, Yuval Ishai, Ranjit Kumaresan, and Eyal Kushilevitz. Explore the models, security considerations, and advancements in secure computation within information-theoretic frameworks. Understand the challenges and possibilities in achieving secure communication and randomness complexity in cryptographic protocols.

  • Cryptography
  • Complexity Theory
  • Security Models
  • Secure Computation
  • Information Theoretic
rayaanacharya
nayd_871 Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. On the Cryptographic Complexity of the Worst Functions Amos Beimel (BGU) Yuval Ishai (Technion) Ranjit Kumaresan (Technion) Eyal Kushilevitz (Technion)

  2. How Bad are the Worst Functions? Function class FN of all functions f : [N] [N] {0,1} Standard Complexity Theoretic Measures Circuit complexity (N2/log N) [Sha48,Lup58] 2-party communication complexity (log N) [Yao79] Information-theoretic Cryptography Communication complexity Randomness complexity This work: Cryptographic complexity of the worst functions

  3. Model Security Model Information-theoretic Unbounded adversaries Statistical/perfect security Semi-honest adversary No deviation from protocol Crypto Primitives Secure Computation Various models Communication/randomness Secret Sharing Share complexity Functions Function class FN : Class of all two argument functions f : [N] [N] {0,1} Interested in worst f FN

  4. Secure Computation What is Known? y x Information Theoretic Security Honest majority [RB89,BGW88] 2-party in the OT-hybrid or preprocessing model [Kil88,Bea95] Impossible in plain model [Kus89] Private Simultaneous Messages [FKN94] f1(x,y) f2(x,y) Can communication complexity be made logarithmic in N? Best upper bounds linear in N Sublinear if big honest majority [BFKR90,IK04] Counting arguments yield weak lower bounds

  5. 2-Party Secure Computation (2PC) What is Known? y x Information Theoretic Security Impossible in plain model [Kus89] OT-hybrid/preprocessing model Popular protocols [GMW87, Y86] f1(x,y) f2(x,y) Information-theoretic garbled circuits [Yao86] Depends on circuit structure Quadratic in formula depth Exponential in depth overhead for circuits GMW [GMW87] Gate-by-gate evaluation of given circuit #OTs required: Twice #AND gates Communication cost: Twice #AND gates

  6. *Slide created before revelations OT-Hybrid Model Oblivious Transfer [Rab81,EGL85] b x0 , x1 x0 , x1 b xb ??? xb Complete OT Extension Impossible in information theoretic setting [Bea97] OT as an atomic currency Given ideal OT oracle, can get information theoretic 2-party secure computation [Kil88,GV88] y0 , y1 c, yc d = c b Pre-computation Random OT correlations can be corrected [Bea95] b x0 , x1 z0 = x0 yd z1 = x1 y1-d zb yc

  7. OT Complexity OT Complexity of a function f Number of (bit) OTs required to securely evaluate f LetFNbe the class of all 2-party f : [N] [N] {0,1} What is the OT complexity of the worst function in FN? Circuit based 2PC: O(N2/log N) [GMW87] Truth-table based 2PC: O(N) via1-out-of-N OT 1-out-of-N OT from O(N) 1-out-of-2 OTs [BCR86] f(x,1) f(x,2) . . f(x,N) y x y ??? f(x,y) This work: O(N2/3) OT complexity

  8. Preprocessing Model Correlated Randomness Offline Phase Correlated Randomness Independent of inputs May depend on f rA rB Online Phase OT Correlations Special case Pre-computed OTs Simpler correlations Indep. of function x y rA rB f(x,y) f(x,y)

  9. Correlated Randomness Complexity Correlated Randomness Complexity of a function f Size of correlated randomness required to securely evaluate f LetFNbe the class of all 2-party f : [N] [N] {0,1} Correlated randomness complexity of the worst function in FN? O(log N) online communication [IKMOP13] Correlated randomness: O(N2) Truth-table based 2PC: O(N) Via 1-out-of-N OT [BCR86] This work: 2 ( log N) correlated randomness

  10. Private Simultaneous Messages (PSM) What is Known? f (x,y) Model [FKN94] Multiple clients Share randomness Single referee Non-interactive Referee learns only f(x,y) No collusion x r r y Why PSM? Minimal model of secure computation [FKN94] Applications in round-efficient protocol design [IKP10] Connections to secret sharing! [BI01]

  11. PSM Complexity PSM Complexity of a function f Communication complexity of PSM protocol for f What is the PSM complexity of the worst function in FN? f(x,y) f(x,1+s) + r1 f(x,2+s) + r2 . . f(x,N+s) + rN f(x,1) f(x,2) . . f(x,N) [FKN94,IK97] Efficient for f with small formulas, branching programs Worst case f : O(N) Lower bound: 3logN-4 y-s, ry-s x r r y r = s, (r1, , rN) This work: O( N) PSM complexity

  12. Secret Sharing What is Known? Model External dealer + n parties Dealer has input secret s Sends shares to parties Then, inactive Access structure Set of authorized subsets Secret hidden from unauth. subsets Any auth. subset can reconstruct s Share Complexity Size of each share Poly(n) share complexity for every n-party access structure? Best upper bound: 2O(n) [BL90,Bri89,KW93] Best lower bound: (n/log n) [Csi97]

  13. Share Complexity Forbidden Graph Access Structures Forbidden Graph [SS97] Graph G = (V,E) with |V| = N Authorized subsets: Sets {u,v} with (u,v) E Any set of size 3 What is the share complexity of the worst N-vertex graph? Na ve solution: O(N) [SS97,BL90] O(N/log N) share complexity [BDGV96,EP97,Bub86] This work: O( N) share complexity

  14. Talk Outline Main Technical Tool PIR OT Complexity Correlated Randomness Complexity PSM Complexity Share Complexity for Forbidden Graphs

  15. Private Information Retrieval DB DB Model [CGKS95] Single client Multiple servers Each server has same DB Size of DB = N (bits) DB unknown to client Client input: index i [N] Privately retrieve DB[ i ] No collusion among servers Goal: min. communication q1 q2 a1 a2 i q2 a2 z q1 a1 r Query generation (q1, q2) Q(i , r) Answer generation ak A( k, qk, DB) Best Known PIR Schemes 2-server: O(N1/3) [CGKS95] 3-server: 2 ( log N) [Yek07,Efr09] Reconstruction z R(i , r, a1, a2)

  16. Talk Outline Main Technical Tool PIR OT Complexity Upper bound: O(N2/3) Correlated Randomness Complexity 2-server PIR PSM Complexity Share Complexity for Forbidden Graphs

  17. OT-Hybrid Model (Recap) OT is complete Pre-computation No OT extension x0 , x1 b xb OT Complexity of a function f Number of (bit) OTs required to securely evaluate f LetFNbe the class of all 2-party f : [N] [N] {0,1} What is the OT complexity of the worst function in FN? Circuit based 2PC for worst f : O(N2/log N) [GMW87] Truth-table based 2PC for worst f : O(N), 1-out-of-N OT [BCR86]

  18. O(N2/3) Upper Bound on OT Complexity Via 2-server PIR Q = Q(x||y, r1 r2) High-level idea Use 2 party secure computation to emulate client + 2 PIR servers DB = truth table of f Client query = x||y x r1 r2 y GMW(C(Q )) q1 q2 a1 = A(1, q1, f ) a2 = A(2, q2, f ) Notation R = R(x||y, r1 r2, a1, a2) PIR Algorithms: Q, A, R (q1, q2) Q(i , r) ak A( k, qk, DB) z R(i , r, a1, a2) Circuit for alg. B: C(B) |C(B)|= #ANDs in C(B) x r1 a1 a2 r2 y GMW(C(R )) f(x,y) f(x,y)

  19. O(N2/3) Upper Bound on OT Complexity Via 2-server PIR Q = Q(x||y, r1 r2) Privacy x r1 r2 y Privacy of GMW Privacy of 2-server PIR Query does not leak additional info GMW(C(Q )) q1 q2 a1 = A(1, q1, f ) a2 = A(2, q2, f ) Efficiency 2-server PIR [CGKS95] |C(Q)|=|C(R)|= O(N2/3) By property of GMW: O(N2/3) OT comp. O(N2/3) communication R = R(x||y, r1 r2, a1, a2) x r1 a1 a2 r2 y GMW(C(R )) f(x,y) f(x,y)

  20. More Applications Honest majority secure computation Efficient in circuit size [RB89,BGW88] Specific setting: n = 3 parties with at most 1 corruption Communication 2 ( log N)via 3-server PIR - Secure Sampling from joint distribution D [PP12] Protocol lets Alice & Bob to sample (x,y) from D Alice knows nothing about y (over what is implied by D) Bob knows nothing about x (over what is implied by D) Rate of secure sampling D [N] [N]from OT New upper bound: O(N2/3 poly(log N, 1/ ))

  21. Talk Outline Main Technical Tool PIR OT Complexity Upper bound: O(N2/3) Correlated Randomness Complexity Upper bound: 2 ( log N) PSM Complexity 2-server PIR 3-server PIR Share Complexity for Forbidden Graphs

  22. Preprocessing Model (Recap) Correlated Randomness Offline Phase Correlated Randomness Independent of inputs May depend on f OT correlations special case Correlated Randomness Complexity of a function f Size of correlated randomness required to securely evaluate f rA rB Online Phase Correlated randomness complexity of the worst function in FN? x y rA rB Truth-table based 2PC: O(N) Via 1-out-of-N OT [BCR86] f(x,y) f(x,y)

  23. Correlated Randomness Complexity: 2O( log N) Upper Bound Via 3-server PIR Offline Phase High-level idea Use 2 party secure computation to emulate client + 3 PIR servers DB = truth table of f Client query = x||y q3=Q3(r1 r2) r1 r2 a3 = a3,1 a3,2 a3 = A(3, q3, f ) a3,1 a3,2 OTA OTB Key Observation Individual PIR query independent of input Q = (Q1,2 , Q3) (q1, q2) Q1,2(i, r) q3 Q3 (r) r1 a3,1 OTA OTB a3,2 r2

  24. Correlated Randomness Complexity: 2O( log N) Upper Bound Q = Q1,2(x||y, r1 r2) Online Phase x r1 r2 y GMW(C(Q )) Correlated Randomness Shares of randomness for PIR query generation alg. Shares of answer to third PIR query OT correlations for GMW q1 q2 a1 = A(1, q1, f ) a2 = A(2, q2, f ) R = R(x||y, r1 r2, a1, a2, a3,1 a3,1) x r1 a1 a3,1 a3,2 a2 r2 y Notation PIR Algorithms: Q, A, R Circuit for alg. B: C(B) |C(B)|= #ANDs in C(B) GMW(C(R )) f(x,y) f(x,y)

  25. Correlated Randomness Complexity: 2O( log N) Upper Bound Q = Q1,2(x||y, r1 r2) Privacy Additive secret sharing Privacy of GMW Privacy of 3-server PIR Query does not leak additional info x r1 a3,1 a3,2 r2 y GMW(C(Q )) q1 q2 a1 = A(1, q1, f ) a2 = A(2, q2, f ) Efficiency 3-server PIR [Efr09] |C(Q)|=|C(R)|=2 ( log N) By property of GMW: 2 ( log N) OT correlations 2 ( log N) communication Correlated rand.: 2 ( log N) R = R(x||y, r1 r2, a1, a2, a3,1 a3,1) x r1 a1 a3,1 a3,2 a2 r2 y GMW(C(R )) f(x,y) f(x,y)

  26. Improving the Bounds? (OT + communication) complexity of 2PC Bounded by communication complexity of 2-server PIR Client shares its input, then acts as OT oracle (Cor. Rand. + communication) complexity of 2PC Bounded by communication comp. of 3-server PIR [IKM+13] 3rd server provides correlated randomness to servers 1 & 2 Qualitative explanation of difference in efficiency 2-server PIR ~ 2PC with OT preprocessing 3-server PIR ~ 2PC with arbitrary preprocessing

  27. Summary Main Technical Tool PIR OT Complexity Upper bound: O(N2/3) Correlated Randomness Complexity Upper bound: 2 ( log N) PSM Complexity Upper bound: O( N) Share Complexity for Forbidden Graphs Upper bound: O( N) 2-server PIR 3-server PIR 4-server PIR Using PSM above

  28. Thank You! Preliminary Version: www.cs.umd.edu/~ranjit/BIKK.pdf Slides: www.cs.umd.edu/~ranjit/BIKK.pptx

  29. Talk Outline Main Technical Tool PIR OT Complexity Upper bound: O(N2/3) Correlated Randomness Complexity Upper bound: 2 ( log N) PSM Complexity Upper bound: O( N) Share Complexity for Forbidden Graphs Upper bound: O( N) 2-server PIR 3-server PIR 4-server PIR Using PSM above

  30. Share Complexity (Recap) Forbidden Graph Access Structures Model External dealer + n parties Dealer inactive after sending shares Access structure: authorized subsets Forbidden Graph [SS97] Graph G = (V,E) with |V| = N Authorized subsets: Sets {u,v} with (u,v) E Any set of size 3 Share Complexity Size of each share What is the share complexity of the worst N-vertex graph? O(N/log N) share complexity [DPGV96,EP97,B86]

  31. Bipartite Case Forbidden Bipartite Graph Graph G = (L,R,E) with |L| = |R| = N Authorized subsets: {x,y} with x L, y R, (x,y) E Any set of size 3 G associated with f :[N] [N] {0,1} Secret Sharing Share s using 3-out-of-2N Shamir secret sharing Also secret share s = sL sR s Send sL to x L Send sR to y R How to share s ?

  32. PSM & Secret Sharing High-level Idea Shares : PSM messages Reconstruction : PSM reconstruction r x L y R Bf (y,r) Af (x,r) Secret Sharing Scheme for s If dealer input s = 0 x L : Af (x0,r) y R : Bf(y0,r) If dealer input s = 1 x L : Af (x,r) y R : Bf(y,r) PSM Notation Shared rand. : r Alice with input x Message: Af (x,r) Bob with input y Message: Bf (y,r) Good for s = 1 For s = 0 Pick some x0, y0 s.t f (x0 , y0) = 0

  33. Forbidden Graph Access Structures From Bipartite to General Graphs Decomposed into log N bipartite graphs Apply standard techniques [BL90,Sti94] Forbidden graph access structures O( N) share complexity Via O( N) PSM Scheme is non-linear (?) Matches best known lower bound for linear schemes: ( N) [Min12]

  34. Summary Cryptographic complexity of worst functions Main Technical Tool - PIR OT Complexity Upper bound: O(N2/3) Correlated Randomness Complexity Upper bound: 2 ( log N) PSM Complexity Upper bound: O( N) Share Complexity for Forbidden Graphs Upper bound: O( N) 2-server PIR 3-server PIR 4-server PIR Using PSM above

  35. Thank You! Preliminary Version: www.cs.umd.edu/~ranjit/BIKK.pdf Slides: www.cs.umd.edu/~ranjit/BIKK.pptx

  36. Talk Outline Main Technical Tool PIR OT Complexity Upper bound: O(N2/3) Correlated Randomness Complexity Upper bound: 2 ( log N) PSM Complexity Upper bound: O( N) Share Complexity for Forbidden Graphs 2-server PIR 3-server PIR 4-server PIR

  37. PIR Examples [CGKS95] 2d server PIR with O(N1/d) communication DB T1 DB T c PIR Queries T1 R [N] T2 = T1 i T2 T {c}, if c T T \{c}, if c T A(1,T1) A(2,T2) i T1 T2 PIR Answers DB[ j ] j T z = A(1,T1) A(2,T2) Efficiency Client Server j : O(N) bits Server j Client : 1 bit

  38. PIR Examples [CGKS95] 2d server PIR with O(N1/d) communication DB DB DB as d-dim. hypercube Index i (i1, , id) Binary rep of (i -1) d T11 1 T00...0 A(1, T00...0) A(2d,T11 1) PIR Queries Pick (T1 , , Td) R [N1/d]d Server k : Query T (T1 (k1 i1), ,Td (kd id)) where k (k1, , kd) i S1 S2d k1 , ,kd z = A(1,T00..0) A(2d,T11..1 ) PIR Answers DB[k1, , kd] k1 T1 , ,kd Td Efficiency Client Server j : O(dN1/d) bits Server j Client : 1 bit

  39. Reducing the #Servers [CGKS95] Key Observation Any server can emulate d other servers with cost O(N1/d) Query T for Server k (T1 (k1 i1), ,Td (kd id)) where k ( k1, , kd) k1 , ,kd Example: 2-server O(N1/3) PIR Server 1: Query T000 = (T1 , T2 , T3) List potential queries for T100: (T1 t, T2 , T3) for t [N1/3] Similarly for T010: (T1, T2 t, T3) & T001: (T1, T2, T3 t) Answer query & 3N1/3 potential queries Server 2: Query T111 =(T1 i1, T2 i2, T3 i3) List potential queries for T011 ,T101 , T110 Answer query & 3N1/3 potential queries Clientpicks correct answer in each answer list and XORs them

  40. Private Simultaneous Messages (Recap) Model [FKN94] Single referee Two (or more) clients Non-interactive Referee learns only f(x,y) Clients share randomness Unknown to referee All parties know f No collusion f(x,y) x r r y PSM Complexity of a function f Communication complexity of PSM protocol for f What is the PSM complexity of the worst function in FN? Efficient for small-depth formulae Worst case f : O(N) [FKN94]

  41. O(N)Upper Bound on PSM Complexity Via 4-server PIR High-level idea Clients use shared randomness & referee s help to emulate client + 3 PIR servers in 4-server PIR scheme of [CGKS95] DB = truth table of f Client query i = x||y f(x,y) x r r y Key Observation Index i (i1 , i2 , i3 , i4) Input x specifies i1, i2 Input y specifies i3, i4 15 of 16 servers emulated by clients 4-server PIR [CGKS95] Obtained by collapsing basic 16-server O(N1/4) PIR scheme

  42. O(N)Upper Bound on PSM Complexity Via 4-server PIR Query T for Server k (T1 (k1 i1), ,T4 (k4 i4)) where k ( k1, , k4) Query + Answer Generation Alice knows T1 i1 , T2 i2 Answers for T**00 Potential answers for T**01, T**10 Bob knows T3 i3 , T4 i4 Answers for T00** Potential answers for T01**, T10** Missing query T1111 equals (T1 i1 , T2 i2, T3 i3 , T4 i4) Answer to T1111 computed by referee k1 , ,kd Key Observation i (i1 , i2 , i3 , i4) x specifies i1, i2 y specifies i3, i4 T1111 i1 x i2 i3 i4 y T0000=(T1, ,T4) T1 i1 T2 i2 T**01 T3 i3 T4 i4 T**00 T00** T**10 T01** T10**

  43. O(N)Upper Bound on PSM Complexity Via 4-server PIR Reconstruction Selecting from potential answer list Use known PSM (small-depth circuit) PSM outputs XOR of these 15 answers Remaining answer computed by referee Finally, XORs this with PSM output Query + Answer Generation Answers for T**00,T00** Potential answers for T**01, T**10 ,T01**, T10** Referee answers T1111 Referee s reconstruction function is non-universal

  44. Summary Cryptographic complexity of worst functions Main Technical Tool - PIR OT Complexity Upper bound: O(N2/3) Correlated Randomness Complexity Upper bound: 2 ( log N) PSM Complexity Upper bound: O( N) Share Complexity for Forbidden Graphs Upper bound: O( N) 2-server PIR 3-server PIR 4-server PIR Using PSM above

  45. Thank You! Preliminary Version: www.cs.umd.edu/~ranjit/BIKK.pdf Slides: www.cs.umd.edu/~ranjit/BIKK.pptx

  46. The research leading to these results has received funding from the European Union's Seventh Framework Programme (FP7/2007-2013) under grant agreement no. 259426 ERC Cryptography and Complexity

Related


No related presentations.

More Related Content