Insights on Hardness Assumptions for Extreme PRGs

BPP=P requires certain complexity theoretical hardness assumptions. Recent advancements aim for extreme high-end PRGs based on stronger assumptions, presenting challenges in black-box proofing and loss factors. The cost of hybrid arguments for PRGs is analyzed, highlighting the need for qualitatively stronger assumptions leading to acceptable constant factor losses.

• Complexity theory
• Derandomization
• High-end PRGs
• Hardness assumptions

daen_76 Follow

Uploaded on Sep 06, 2024 | 2 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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. On Hardness Assumptions Needed for Extreme High-End PRGs and Fast Derandomization Ronen Shaltiel University of Haifa Emanuele Viola Northeastern University

2. Summary and Outline [IW97]: BPP=P assuming certain complexity theoretic hardness assumptions. [IW97] construct high-end PRGs that are optimal up to constant factors, based on assumptions that are necessary (up to constant factors). High-end PRG BPP=P ( ?: ?????? ? ????? ??). Recently, motivated by fast derandomization (that is minimizing ?), [DMOZ20,CT21] construct extreme high-end PRGs (that are optimal up to 1 ? 1 factors) based on stronger assumptions (both quantitatively, and qualitatively). Quantitatively stronger assumptions are necessary for quantitatively stronger PRGs. Is it possible to show that: (quantitatively properly scaled) IW assumption extreme high-end PRG? Question: Is there a black-box proof showing that: (quantitatively properly scaled) IW assumption extreme high-end PRG? We don t know, but we can rule out certain approaches. Interpretation: Our results show that the approaches of [DMOZ20,CT21] cannot yield such a black-box proof.

3. Extreme high-end PRG: ? = 1 + ? 1 Hardness vs. Randomness (state of the art) (optimal up to 1 ? 1 factors). log?. High-end: Thm [IW97]: High-end IW hardness assumption: Exists ?: 0,1 0,1 s.t. ? not computable by size 2 ( ) circuits. ? ? = 2? ???? ? = 2? . Extreme high-end: Open problem, show that: Extreme high-end IW hardness assumption: Exists ?: 0,1 0,1 s.t. ? not computable by size 21 o 1 circuits. ????? = 22+? 1 . |Pr ? ? ?? = 1 Pr ? ?? = 1 | ?(?)= Time to compute ? on a single input. ????? = Time to compute ? on all 2 inputs. Dfn: ?: 0,1? 0,1? is a PRG if ? of size m, 1 10 Implies extreme high-end PRG: High-end PRG: ? = ?(log?). (optimal up to constant factors). Implies high-end PRG: ?: 0,1?=?( ) 0,1?=2 ( ) with ? ? = 2? ???? ? = 2? . How small can ? be? Thm: [CGIMPS16] ? 2 ? 1 assuming fine grained complexity assumptions. High-end PRG ? = 2 + ?(1) . (?????? ? ????? ??). ?: 0,1?= 1+? 1 0,1?=21 o 1 High-end PRG BPP=P ( ?: ?????? ? ????? ??). with ????? = 22+? 1 . [IW97] G matches the PRG implied by the hardness assumption up to constant factors. [CT21a,CT21b]: In terms of both input length n, and time m(n) the right answer may be: ?????? ?(?) ????? ? ? ?1+? 1. Here, G needs to match the PRG implied by the hardness assumption up to 1 ? 1 factors. How small can ? be? What if we had extreme high-end PRGs (that are optimal up to 1 ? 1 factors)? Assumption remains plausible when scaled by constants. (Can afford losing constant factors). Assumption becomes false when scaled by constants. (Cannot afford losing constant factors).

4. The cost of the hybrid argument High-end: Thm [IW97]: High-end IW hardness assumption: Exists ?: 0,1 0,1 s.t. ? not computable by size 2 ( ) circuits. ? ? = 2? ???? ? = 2? . Extreme high-end: Open problem, show that: Extreme high-end IW hardness assumption: Exists ?: 0,1 0,1 s.t. ? not computable by size 21 o 1 circuits. ????? = 22+? 1 . Implies extreme high-end PRG: Implies high-end PRG: ?: 0,1?=?( ) 0,1?=2 ( ) with ? ? = 2? ???? ? = 2? . ?: 0,1?= 1+? 1 0,1?=21 o 1 with ????? = 22+? 1 . Here, we cannot afford the losses incurred by Hardness Amplification + Hybrid Argument . [IW97] and later proofs [STV99,SU01,U02] use Hardness Amplification + Hybrid Argument . [DMOZ20,CT21] bypass this barrier and give extreme high-end PRGs, albeit under qualitatively stronger assumptions (that we now survey). This (as well as other issues) results in losses of constant factors (that we can afford).

5. The PRG of [DMOZ20]: Assume also that ? is hard for circuits equipped with nondeterminism and randomness Extreme high-end: Open problem, show that: Thm [DMOZ20]: Extreme high-end IW hardness assumption: Exists ?: 0,1 0,1 s.t. ? not computable by size 21 o 1 circuits ????? = 22+? 1 . High-end: Thm [IW97]: High-end IW hardness assumption: Exists ?: 0,1 0,1 s.t. ? not computable by size 2 ( ) circuits. ? ? = 2? ???? ? = 2? . that are also equipped with nondeterminism and randomness Implies extreme high-end PRG: Implies high-end PRG: ?: 0,1?=?( ) 0,1?=2 ( ) with ? ? = 2? ???? ? = 2? . ?: 0,1?= 1+? 1 0,1?=21 o 1 with ????? = 22+? 1 . Here, we cannot afford the losses incurred by Hardness Amplification + Hybrid Argument . [IW97] and later proofs [STV99,SU01,U02] use Hardness Amplification + Hybrid Argument . [DMOZ20,CT21] bypass this barrier and give extreme high-end PRGs, albeit under qualitatively stronger assumptions (that we now survey). This (as well as other issues) results in losses of constant factors (that we can afford).

6. The PRG of [CT21]: Assume also that one-way functions exist Extreme high-end: Open problem, show that: Thm [CT21]: Extreme high-end IW hardness assumption: Exists ?: 0,1 0,1 s.t. ? not computable by size 21 o 1 circuits. ????? = 22+? 1 . and in addition that one-way functions exist. High-end: Thm [IW97]: High-end IW hardness assumption: Exists ?: 0,1 0,1 s.t. ? not computable by size 2 ( ) circuits. ? ? = 2? ???? ? = 2? . Implies extreme high-end PRG: Implies high-end PRG: ?: 0,1?=?( ) 0,1?=2 ( ) with ? ? = 2? ???? ? = 2? . ?: 0,1?= 1+? 1 0,1?=21 o 1 with ????? = 22+? 1 . Here, we cannot afford the losses incurred by Hardness Amplification + Hybrid Argument . [IW97] and later proofs [STV99,SU01,U02] use Hardness Amplification + Hybrid Argument . [DMOZ20,CT21] bypass this barrier and give extreme high-end PRGs, albeit under qualitatively stronger assumptions (that we now survey). This (as well as other issues) results in losses of constant factors (that we can afford).

7. Summary and Outline [IW97]: BPP=P assuming certain complexity theoretic hardness assumptions. [IW97] construct high-end PRGs that are optimal up to constant factors, based on assumptions that are necessary (up to constant factors). High-end PRG BPP=P ( ?: ?????? ? ????? ??). Recently, motivated by fast derandomization (that is minimizing ?), [DMOZ20,CT21] construct extreme high-end PRGs (that are optimal up to 1 ? 1 factors) based on stronger assumptions (both quantitatively, and qualitatively). Quantitatively stronger assumptions are necessary for quantitatively stronger PRGs. Is it possible to show that: Extreme high-end IW hardness assumption extreme high-end PRG? Question: Is there a black-box proof showing that: Extreme high-end IW hardness assumption extreme high-end PRG? We don t know, but we can rule out certain approaches. Interpretation: Our results show that the approaches of [DMOZ20,CT21] cannot yield such a black-box proof.

8. Black-box proofs for showing: extreme high-end IW hardness assumption extreme high-end PRG Extreme high-end: Open problem, show that: Extreme high-end IW hardness assumption: Exists ?: 0,1 0,1 s.t. ? not computable by size 21 o 1 circuits. ????? = 22+? 1 . All known PRGs have black-box proofs: construction map: ? mapping ? to ??, reduction ?( ), s.t. functions ?,?: If ? breaks ?? then: ?? computes ? using few queries to ?.* Implies extreme high-end PRG: (If ? is a small circuit then ?? is a small circuit, and so, ? is not hard). *? is a (non-uniform) reduction, meaning that ??also receives a short advice string about ?,?. (This is the right notion ). ?: 0,1?= 1+? 1 0,1?=21 o 1 with ????? = 22+? 1 . Question: Does there exist an extreme black-box proof ? Namely, a bb-proof showing: extreme high-end IW hardness assumption extreme high-end PRG. Answer: We don t know, but we can rule out certain approaches.

9. Our results: Limitations on some approaches for extreme black-box proof 1. In every bb-proof (even not extreme) the construction map ? mapping ? to ??, must have certain special properties. Explains why it is hard to come up with bb-proofs. May help us to find new construction maps for bb-proofs. (The known ones [NW88,SU01] cannot succeed in the extreme high-end). Used to prove the next result. 2. The PEG + Extractor approach of [DMOZ20] can t yield an extreme bb-proof. Explains why [DMOZ20] uses additional assumptions. 3. The PRG composition approach of [CT21] can t yield an extreme bb-proof when using Hardness Amplification + Hybrid Argument . Explains why [CT21] uses additional assumptions. Doesn t rule out that the PRG composition approach can be carried out without Hardness amplification + Hybrid Argument .

10. 1. In every bb-proof (even not extreme) construction map ? mapping ? to ??, must have certain special properties By viewing ?: 0,1 {0,1} as an ? = 2 bit string. A construction map ? mapping ? to ?? can be viewed as: ?: 0,1?=2 0,1? 0,1?, by ? ?,? = ??? . Thm: [T99] every such ? is an extractor for every high entropy source ?, ?(?,??) is close to uniform. Our result: every such ? has the following special property: There is a high entropy source ? on which quite a few outputs of ?(?, ) are fixed. The two results are at a tension. In an extractor, it can t be that many outputs of ?(?, ) are fixed. Interpretation: a random function ? is: w.h.p. an extractor (standard). w.h.p. does not satisfy the special property not a part of a bb-proof. ? must be different than a typical extractor . We find this surprising, as we tend to think of bb-PRGs and extractors as similar. Intuition for proof: If all outputs of ?(??, ) have high entropy, then the reduction ?( ) will not be able to find such outputs, and will fail .

11. 2. The PEG + Extractor approach of [DMOZ20] can t yield an extreme bb-proof. [DMOZ20]: extreme high-end PRGs from a qualitatively stronger version of the extreme high-end IW hardness assumption: assuming hardness against circuits that are equipped with nondeterminism and randomness. [DMOZ20] use PEG + Extractor approach [HILL88,STV99,BSW03]. Use hard function ?: 0,1 0,1 to construct ???: 0,1? 0,121 ? 1 A PEG is a weak PRG which guarantees only that output has large computational entropy . Final PRG achieved by ? ?,? = ??? ??? ? ,? . Final seed length ? = ? + |?|. Since ? 1 ? 1 Our result: Every bb-proof: extreme high-end IW hardness assumption PEG: Must have ? 1 ? 1 . Impossible to have an extreme bb-proof using PEG + Extractor approach. Also implies limitations on PRGs for quantified derandomization . Proof idea: The aforementioned special property of PRGs also applies to PEGs. Tension between PEG and it s information theoretic analogue (Condenser). When |x| is very short the tension becomes a contradiction, and bb-proofs must have large |x|. , we need ? = ? .

12. 3. The PRG composition approach of [CT21] cant give an extreme bb-proof using Hardness Amplification + Hybrid Argument . [CT21]: extreme high-end PRGs from the extreme high-end IW hardness assumption. assuming also that one-way functions exist. [CT21] use PRG composition approach : ? ? = ?2(?1? ) where: ?1: 0,1 Constructed from extreme high-end IW hardness assumption using Hardness Amplification + Hybrid Argument . ?2: 0,1?1 0,121 ? 1 =?1 Composition requires that ?2 runs in time 21 ? 1 (almost linear in output length). Question: is there a bb-proof: extreme high-end IW hardness assumption ?2? Our result: Impossible for bb-proofs that use Hardness Amplification + Hybrid Argument . We show limitations on bb-proofs for hardness amplification in the extreme high-end. This extends [GSV18] that uses techniques that do not work in the extreme high-end. Builds on [ASSY15,RSV21] and also gives improved lower bounds on the number of queries required by locally list-decodable codes. 1+? 1 0,1?1=2 ( ) is a PRG for circuits of size 21 ? 1 . ? 1 (polynomial stretch PRG follows from OWFs).

13. Conclusion and Open Problems Summary: Main question: Is there a black-box proof showing that: (quantitatively properly scaled) IW assumption extreme high-end PRG? Answer: We don t know, but we can rule out certain approaches. Interpretation: Our results show that the approaches of [DMOZ20,CT21] cannot yield such a black-box proof. Comment: We focus on PRGs, but there are other approaches to prove: Hard functions BPP=P (without PRGs) [CT21b]. Open Problems: The quantitative bounds we prove for bb-proofs for hardness amplification at the extreme high-end are not tight. Is the cost of hardness amplification + hybrid argument necessary for bb-proofs for PRGs? Develop techniques to prove (even weak bounds) on general bb-proofs for PRGs. That s it. Thank you!

14. Thats it Thank you