Hardness Self-Amplification from Feasible Hard-Core Sets

FOCS2022

Transcript

1. Nobutaka Shimizu Tokyo Institute of Technology Hardness Self-Amplification from Feasible Hard-Core Sets Shuichi Hirahara National Institute of Informatics FOCS2022
2. • : class of algorithms (or circuits) • is worst-case hard (for ) if • is -hard if ‣ is drawn from some distribution (in this talk, uniform distribution) 𝒞 f 𝒞 ∀A ∈ 𝒞 , ∃x, A(x) ≠ f(x) f δ ∀A ∈ 𝒞 , Pr x [A(x) ≠ f(x)] ≥ δ x Average-Case Complexity 2
3. • : class of algorithms (or circuits) • is worst-case hard (for ) if • is -hard if ‣ is drawn from some distribution (in this talk, uniform distribution) 𝒞 f 𝒞 ∀A ∈ 𝒞 , ∃x, A(x) ≠ f(x) f δ ∀A ∈ 𝒞 , Pr x [A(x) ≠ f(x)] ≥ δ x Average-Case Complexity 3 perfect score is difficult
4. • : class of algorithms (or circuits) • is worst-case hard (for ) if • is -hard if ‣ is drawn from some distribution (in this talk, uniform distribution) 𝒞 f 𝒞 ∀A ∈ 𝒞 , ∃x, A(x) ≠ f(x) f δ ∀A ∈ 𝒞 , Pr x [A(x) ≠ f(x)] ≥ δ x Average-Case Complexity 4 perfect score is difficult even 50% is difficult
5. •Goal : construct a -hard for •Under “plausible” assumption ‣ ‣ #NSETH •cryptography, derandomization, etc δ f δ ≈ 1 𝖯 ≠ 𝖭 𝖯 Two Directions 5 ᶃ Explicit Construction ᶄ Practical Hardness of Problems •Target: specific over specific input distribution ‣ Find a maximum clique in ‣ Random SAT • efficient algo that succeeds on many inputs? •Avoid the pessimism of worst-case analysis f G(n, p) ∃ Are techniques in ᶃ useful for ᶄ ?
6. • : Boolean function ‣ is weakly hard if is -hard ‣ is strongly hard if is -hard f f f ϵ f f (1/2 − δ) Weak and Strong Hardness 6 Constant algo ( or ) succeeds on 1/2-fraction of inputs. A(x) = 1 A(x) = 0
7. • : Boolean function ‣ is weakly hard if is -hard ‣ is strongly hard if is -hard •Goal of Direction ᶃ : explicit construction of strongly hard f f f ϵ f f (1/2 − δ) f Weak and Strong Hardness 7 strongly hard worst-case hard
8. •Hardness Amplification ‣ Transform weakly hard into strongly hard f g Hardness Amplification 8 hardness amplification worst-case to average-case reduction strongly hard worst-case hard weakly hard
9. •Hardness Amplification ‣ Transform weakly hard into strongly hard •XOR lemma ‣ , where are independent •Derandomized XOR lemma ‣ , where have some correlation •Typically, is artificial ‣ They might be not suitable for Direction ᶄ without any modification f g g(x1 , …, xk ) = f(x1 ) ⊕ … ⊕ f(xk ) x1 , …, xk ∼ {0,1}n g(x1 , …, xk ) = f(x1 ) ⊕ … ⊕ f(xk ) x1 , …, xk g Hardness Amplification 9 [Yao 82][Levin 87] [Impagliazzo, Wigderson, 97]
10. •Framework of Hardness Self-Amplification ‣ i.e., hardness amplification with g = f Our Contribution 10
11. •Framework of Hardness Self-Amplification ‣ i.e., hardness amplification with •Application: Hardness amplification for Natural Problems ‣ Triangle counting mod 2 ‣ Online Vector-Matrix-Vector Multiplication over g = f 𝔽 2 Our Contribution 11
12. •Framework of Hardness Self-Amplification ‣ i.e., hardness amplification with •Application: Hardness amplification for Natural Problems ‣ Triangle counting mod 2 ‣ Online Vector-Matrix-Vector Multiplication over •Ingredient: New derandomized XOR lemma based on ‣ Feasible hard-core set : Generalization of hard-core set ‣ Computational design : Generalization of combinatorial design g = f 𝔽 2 Our Contribution 12 [Impagliazzo, 1995] [Nisan, Wigderson, 1994]
13. •Framework of Hardness Self-Amplification ‣ i.e., hardness amplification with •Application: Hardness amplification for Natural Problems ‣ Triangle counting mod 2 ‣ Online Vector-Matrix-Vector Multiplication over •Ingredient: New derandomized XOR lemma based on ‣ Feasible hard-core set : Generalization of hard-core set ‣ Computational design : Generalization of combinatorial design g = f 𝔽 2 Our Contribution 13 [Impagliazzo, 1995] [Nisan, Wigderson, 1994]
14. •k-clique counting •General subgraph •subgraph counting mod 2 Subgraph Counting on Random Graphs 14 [Goldreich and Rothblum, 2018] [Boix-Adserà, Brennan, Bresler, 2019] [Dalirrooyfard, Lincoln, Williams, 2020] [Boix-Adserà, Brennan, Bresler, 2019] [Goldreich, 2020] [Hirahara, Shimizu, 2021]
15. •k-clique counting •General subgraph •subgraph counting mod 2 • If Triangle Counting is worst-case hard for -time algo, then it is -hard (over Erdős–Rényi graph) • If Triangle Counting Mod 2 is worst-case hard for -time algo, then it is -hard for nω−ϵ 1/polylog(n) nω−ϵ δ δ = 2−9 ≈ 0.000004 Subgraph Counting on Random Graphs 15 [Goldreich and Rothblum, 2018] [Boix-Adserà, Brennan, Bresler, 2019] [Dalirrooyfard, Lincoln, Williams, 2020] [Boix-Adserà, Brennan, Bresler, 2019] [Goldreich, 2020] [Hirahara, Shimizu, 2021] Previous : weak hardness from wrs-hardness [Boix-Adserà, Brennan, Bresler, 2019] [Boix-Adserà, Brennan, Bresler, 2019] [Goldreich, 2020]
16. This Work: Triangle Counting Mod 2 16 Theorem (informal) Let be any constants. If is -hard for small circuits, then is -hard for small circuits. In particular, is -hard if it is worst-case hard. δ, ϵ > 0 𝖳 𝗋 𝗂 𝖯 𝖺 𝗋 𝗂 𝗍 𝗒 δ 𝖳 𝗋 𝗂 𝖯 𝖺 𝗋 𝗂 𝗍 𝗒 (1/2 − ϵ) 𝖳 𝗋 𝗂 𝖯 𝖺 𝗋 𝗂 𝗍 𝗒 (1/2 − ϵ) • … #triangles mod 2 in a tripartite graph 𝖳 𝗋 𝗂 𝖯 𝖺 𝗋 𝗂 𝗍 𝗒 : {0,1}3n2 → {0,1} vertices n vertices n vertices n Each possible edge appears with prob 1/2 Tripartite ER Graph
17. New Derandomized XOR from Computational Design
18. • … weakly hard function •For , let = -th block ( ) •Define by f: {0,1}n → {0,1} x ∈ {0,1}kn xi i |xi | = n g: {0,1}nk → {0,1} XOR Lemma 18 g(x) = f(x1 ) ⊕ ⋯ ⊕ f(xk ) x1 x2 x3 x4 x5 x = If is -hard, then is -hard for some . f δ g (1/2 − ϵ) k = O(log(1/ϵ)/δ) Theorem (informal) [Yao 84][Levin 87]
19. • … weakly hard function • … set family ( , ) •For , let •Define by f: {0,1}n → {0,1} 𝒮 = {S1 , …, Sk } Si ⊆ [ℓ] |Si | = n x ∈ {0,1}ℓ xi = x| Si g: {0,1}ℓ → {0,1} Derandomized XOR Lemma of NW 19 x1 x = g(x) = f(x1 ) ⊕ ⋯ ⊕ f(xk ) x2 x3 x4 Suppose is a combinatorial design. If is -hard, then is -hard for some . 𝒮 = (Si ) f δ g (1/2 − ϵ) k = k(δ, ϵ) Theorem (informal) [Impagliazzo, Wigderson, 1997]
20. • … weakly hard function • … set family ( , ) •For , let •Define by f: {0,1}n → {0,1} 𝒮 = {S1 , …, Sk } Si ⊆ [ℓ] |Si | = n x ∈ {0,1}ℓ xi = x| Si g: {0,1}ℓ → {0,1} Derandomized XOR Lemma of NW 20 x1 x = g(x) = f(x1 ) ⊕ ⋯ ⊕ f(xk ) x2 x3 x4 Suppose is a combinatorial design. If is -hard, then is -hard for some . 𝒮 = (Si ) f δ g (1/2 − ϵ) k = k(δ, ϵ) [Impagliazzo, Wigderson, 1997] Theorem (informal) is a -combinatorial design if for 𝒮 d |Si ∩ Sj | ≤ d ∀i ≠ j
21. • … weakly hard function • … set family ( , ) •For , let •Define by f: {0,1}n → {0,1} 𝒮 = {S1 , …, Sk } Si ⊆ [ℓ] |Si | = n x ∈ {0,1}ℓ xi = x| Si g: {0,1}ℓ → {0,1} New Derandomized XOR Lemma 21 x1 x = g(x) = f(x1 ) ⊕ ⋯ ⊕ f(xk ) x2 x3 x4 Suppose is a computational design. If is -hard, then is -hard for some . 𝒮 = (Si ) f δ g (1/2 − ϵ) k = k(δ, ϵ) Theorem (informal, this work)
22. • … weakly hard function • … set family ( , ) •For , let •Define by f: {0,1}n → {0,1} 𝒮 = {S1 , …, Sk } Si ⊆ [ℓ] |Si | = n x ∈ {0,1}ℓ xi = x| Si g: {0,1}ℓ → {0,1} New Derandomized XOR Lemma 22 x1 x = g(x) = f(x1 ) ⊕ ⋯ ⊕ f(xk ) x2 x3 x4 Suppose is a computational design. If is -hard, then is -hard for some . 𝒮 = (Si ) f δ g (1/2 − ϵ) k = k(δ, ϵ) Theorem (informal, this work) Roughly speaking, is a computational design if has a small “computational cost” 𝒮 Si ∩ Sj
23. • … weakly hard function • … set family ( , ) •For , let •Define by f: {0,1}n → {0,1} 𝒮 = {S1 , …, Sk } Si ⊆ [ℓ] |Si | = n x ∈ {0,1}ℓ xi = x| Si g: {0,1}ℓ → {0,1} New Derandomized XOR Lemma 23 x1 x = g(x) = f(x1 ) ⊕ ⋯ ⊕ f(xk ) x2 x3 x4 Suppose is a computational design. If is -hard, then is -hard for some . 𝒮 = (Si ) f δ g (1/2 − ϵ) k = k(δ, ϵ) Theorem (informal, this work) is a computational design for if can be computed by a small circuit given in advance. 𝒮 f f(xi ) x| Si ∖Sj
24. Derandomized XOR and TriParity 24 • … #triangles mod 2 in a tripartite graph • : tripartite set 𝖳 𝗋 𝗂 𝖯 𝖺 𝗋 𝗂 𝗍 𝗒 : {0,1}3n2 → {0,1} U, V, W V W U
25. Derandomized XOR and TriParity 25 • … #triangles mod 2 in a tripartite graph • : tripartite set • Divide them into 𝖳 𝗋 𝗂 𝖯 𝖺 𝗋 𝗂 𝗍 𝗒 : {0,1}3n2 → {0,1} U, V, W Ui , Vj , Wk U1 U0 V1 V0 W1 W0
26. • … #triangles mod 2 in a tripartite graph • : tripartite set • Divide them into • For , let 𝖳 𝗋 𝗂 𝖯 𝖺 𝗋 𝗂 𝗍 𝗒 : {0,1}3n2 → {0,1} U, V, W Ui , Vj , Wk (i, j, k) ∈ {0,1}3 Gijk = G[Ui , Vj , Wk ] Derandomized XOR and TriParity 26 𝖳𝗋 𝗂 𝖯 𝖺𝗋𝗂 𝗍 𝗒 (G) = ⨁ (i,j,k)∈{0,1}3 𝖳𝗋 𝗂𝖯𝖺 𝗋𝗂𝗍 𝗒 (Gijk ) U1 U0 V1 V0 W1 W0
27. • … #triangles mod 2 in a tripartite graph • : tripartite set • Divide them into • For , let 𝖳 𝗋 𝗂 𝖯 𝖺 𝗋 𝗂 𝗍 𝗒 : {0,1}3n2 → {0,1} U, V, W Ui , Vj , Wk (i, j, k) ∈ {0,1}3 Gijk = G[Ui , Vj , Wk ] Derandomized XOR and TriParity 27 𝖳𝗋 𝗂 𝖯 𝖺𝗋𝗂 𝗍 𝗒 (G) = ⨁ (i,j,k)∈{0,1}3 𝖳𝗋 𝗂𝖯𝖺 𝗋𝗂𝗍 𝗒 (Gijk ) f(x) = f(x| S1 ) ⊕ ⋯ ⊕ f(x| St ) U1 U0 V1 V0 W1 W0
28. • is NOT a combinatorial design ( and shares - edges) • Actually, is a computational design! (Gijk ) G000 G001 U0 V0 (Gijk ) Derandomized XOR and TriParity 28 𝖳𝗋 𝗂 𝖯 𝖺𝗋𝗂 𝗍 𝗒 (G) = ⨁ (i,j,k)∈{0,1}3 𝖳𝗋 𝗂𝖯𝖺 𝗋𝗂𝗍 𝗒 (Gijk ) U1 U0 V1 V0 W1 W0
29. Proof Sketch of New Derandomized XOR from Feasible Hard-core Set
30. DXOR and Hard-core Set 30 Theorem (hard-core lemma; Impagliazzo 95) If is -hard for size , then there is a set of such that is -hard over for size . f δ S H ⊆ {0,1}n |H| ≥ δ ⋅ 2n f (1/2 − ϵ) H O(ϵ2δ2S) • Such is called hard-core set • On a hard-core set, is strongly hard • We can derive DXOR of NW from hard-core lemma H f [Hearly, Vadhan, Viola, 2006]
31. DXOR: Roadmap 31 is not -hard, where f(x1 ) ⊕ … ⊕ f(xk ) (1/2 − ϵ) xi = x| Si
32. DXOR: Roadmap 32 is not -hard, where f(x1 ) ⊕ … ⊕ f(xk ) (1/2 − ϵ) xi = x| Si we can distinguish and (f(x1 ), …, f(xk )) (fH (x1 ), …, fH (xk )) fH (x) = { random bit if x ∈ H, f(x) otherwise . A circuit distinguishes and if C 𝒟 1 𝒟 2 | Pr x∼ 𝒟 1 [C(x) = 1] − Pr x∼ 𝒟 2 [C(x) = 1]| ≥ ϵ
33. DXOR: Roadmap 33 is not -hard, where f(x1 ) ⊕ … ⊕ f(xk ) (1/2 − ϵ) xi = x| Si we can distinguish and (f(x1 ), …, f(xk )) (fH (x1 ), …, fH (xk )) we can distinguish and (f(x1 ), …, f(xi−1 ), fH (xi ), fH (xi+1 ), …, fH (xk )) , fH (xi+1 ), …, fH (xk )) f(xi ) (f(x1 ), …, f(xi−1 ), hybrid argument for some i
34. DXOR: Roadmap 34 is not -hard, where f(x1 ) ⊕ … ⊕ f(xk ) (1/2 − ϵ) xi = x| Si we can distinguish and (f(x1 ), …, f(xk )) (fH (x1 ), …, fH (xk )) we can distinguish and (f(x1 ), …, f(xi−1 ), fH (xi ), fH (xi+1 ), …, fH (xk )) , fH (xi+1 ), …, fH (xk )) f(xi ) (f(x1 ), …, f(xi−1 ), hybrid argument combinatorial design we can distinguish and f(x) fH (x) for some i
35. DXOR: Roadmap 35 is not -hard, where f(x1 ) ⊕ … ⊕ f(xk ) (1/2 − ϵ) xi = x| Si we can distinguish and (f(x1 ), …, f(xk )) (fH (x1 ), …, fH (xk )) we can distinguish and (f(x1 ), …, f(xi−1 ), fH (xi ), fH (xi+1 ), …, fH (xk )) , fH (xi+1 ), …, fH (xk )) f(xi ) (f(x1 ), …, f(xi−1 ), hybrid argument combinatorial design we can distinguish and f(x) fH (x) next-bit predictor is not -hard over f(x) (1/2 − ϵ) H contradict to hard-core lemma! for some i
36. DXOR using Computational Design 36 is not -hard, where f(x1 ) ⊕ … ⊕ f(xk ) (1/2 − ϵ) xi = x| Si we can distinguish and (f(x1 ), …, f(xk )) (fH (x1 ), …, fH (xk )) we can distinguish and (f(x1 ), …, f(xi−1 ), fH (xi ), fH (xi+1 ), …, fH (xk )) , fH (xi+1 ), …, fH (xk )) f(xi ) (f(x1 ), …, f(xi−1 ), hybrid argument computational design next-bit predictor is not -hard over f(x) (1/2 − ϵ) H we can distinguish and f(x) fH (x) for some i
37. DXOR using Computational Design 37 is not -hard, where f(x1 ) ⊕ … ⊕ f(xk ) (1/2 − ϵ) xi = x| Si we can distinguish and (f(x1 ), …, f(xk )) (fH (x1 ), …, fH (xk )) we can distinguish and (f(x1 ), …, f(xi−1 ), fH (xi ), fH (xi+1 ), …, fH (xk )) , fH (xi+1 ), …, fH (xk )) f(xi ) (f(x1 ), …, f(xi−1 ), hybrid argument computational design is not -hard over f(x) (1/2 − ϵ) H we can distinguish and using -oracle f(x) fH (x) H next-bit predictor for some i
38. DXOR using Computational Design 38 is not -hard, where f(x1 ) ⊕ … ⊕ f(xk ) (1/2 − ϵ) xi = x| Si we can distinguish and (f(x1 ), …, f(xk )) (fH (x1 ), …, fH (xk )) we can distinguish and (f(x1 ), …, f(xi−1 ), fH (xi ), fH (xi+1 ), …, fH (xk )) , fH (xi+1 ), …, fH (xk )) f(xi ) (f(x1 ), …, f(xi−1 ), hybrid argument computational design is not -hard over for -oracle circuits f(x) (1/2 − ϵ) H H we can distinguish and using -oracle f(x) fH (x) H next-bit predictor for some i
39. DXOR using Computational Design 39 is not -hard, where f(x1 ) ⊕ … ⊕ f(xk ) (1/2 − ϵ) xi = x| Si we can distinguish and (f(x1 ), …, f(xk )) (fH (x1 ), …, fH (xk )) we can distinguish and (f(x1 ), …, f(xi−1 ), fH (xi ), fH (xi+1 ), …, fH (xk )) , fH (xi+1 ), …, fH (xk )) f(xi ) (f(x1 ), …, f(xi−1 ), hybrid argument computational design is not -hard over for -oracle circuits f(x) (1/2 − ϵ) H H we can distinguish and using -oracle f(x) fH (x) H we need to modify hard-core lemma next-bit predictor for some i
40. DXOR and Hard-core Set 40 Theorem (feasible hard-core lemma; informal) If is -hard for size , then there is a set of such that is -hard over for size trapdoor -oracle circuits. f δ S H ⊆ {0,1}n |H| ≥ δ ⋅ 2n f (1/2 − ϵ) H 2−poly(1/ϵ,1/δ)S H • We call such feasible hard-core set • trapdoor oracle circuit for “ can query whenever computes ” • Proof : Boosting algo of [Barak, Hardt, Kale, 09] H CH f C H(q) C f(q) serves as a “key” for the “trapdoor” f(q) H(q)
41. •counting other subgraphs (k-clique, k-cycle, etc) •mod 3? mod ? •nonuniform model (circuit) → uniform model (algorithm) p Open Problems 41