On Basing Auxiliary-Input Cryptography on NP-hardness via Nonadaptive Black-Box Reductions

on YouTube ↗29m

" summary

Shows that non-adaptive black-box reductions from NP-hard languages to an auxiliary-input pseudorandom generator would collapse the polynomial hierarchy, using a reduction to an errorless average-case NP problem via the generator's image. For auxiliary-input one-way functions and hitting-set generators the same style of reduction does not yield collapse but instead yields an NP-based one-way function: construction uses Karp reductions, simulating the reduction’s parallel queries, classifying queries as light or heavy, and a universal extrapolation to replace inverting oracles.

AI-written summary · about

" chapters (7)

1. 0:00Introduction
2. 3:20AuxiliaryInput Cryptography
3. 5:32Nonadaptive BlackBox Reduction
4. 9:49Proof Sketch
5. 13:25Second auxiliary input
6. 19:15Third auxiliary input
7. 26:30Conclusion

" related talks

• 13mPseudorandom Self-Reductions for NP-Complete ProblemsReyad Abed Elrazik, Robert Robere, Assaf Schuster, Gal Yehuda · ITCS 2022
• 46mOn Hardness Assumptions Needed for ``Extreme High-End'' PRGs and Fast DerandomizationEmanuele Viola, Ronen Shaltiel · ITCS 2022
• 56mToward Obfuscation from Affine Determinant ProgramsMark Zhandry · Obfuscation
• 55mFoundations 2Iftach Haitner · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 59mBeyond P versus NP: Using Complexity Theory in Obfuscation and Vice-VersaAlex Lombardi, Rahul Ilango · Obfuscation
• 38mAdvisor-Verifier-Prover Games and the Hardness of Information Theoretic CryptographyBenny Applebaum · Minimal Complexity Assumptions for Cryptography 2023
• 46mCryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov ComplexityYanyi Liu · Lower Bounds, Learning, and Average-Case Complexity
• 31mIndistinguishability Obfuscation, Range Avoidance, and Bounded ArithmeticRahul Ilango · Proof Complexity and Meta-Mathematics 2023