Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness

on YouTube ↗49m

" summary

Proves a concrete conditional separation: assuming UP not in RP (which follows from injective one‑way functions), with probability 1 over a random oracle O one gets P^O ≠ NP^O ∩ coNP^O. The proof builds a new NIZK with unbounded prover for NP in the random‑oracle / URS model by introducing a Z‑tamperable hidden bits model and instantiating it from a delta‑dense pseudo‑random hash function (or a random oracle), uses statistical tests and Borel‑Cantelli for soundness, and gives a constructive recipe for candidate languages; prover efficiency and non‑oracle instantiations remain open.

AI-written summary · about

" chapters (4)

1. 0:00Start
2. 8:01Random Oracle Separations of Complexity Classes
3. 26:56NIZK Proofs for NP in Random Oracle Model
4. 39:35Instantiating the HB model with Random Oracle and URS?

" related talks

• 33mHow to Share an NP Statement or Combiners for Zero-Knowledge ProofsBenny Applebaum · Secure Computation 2025
• 01h 15mProofs - TheoryYael Tauman Kalai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 13mA Zero-Knowledge PCP TheoremNicholas Spooner · Proofs (Simons Institute)
• 01h 15mTo interact or not to interact: Cryptographic proof systems and the Fiat-Shamir heuristicAlex Lombardi · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 08mIncrementally Verifiable Computation for NP from Standard AssumptionsSurya Mathialagan · Proofs (Simons Institute)
• 48mUnstructured Hardness to Average-Case RandomnessRoei Tell · Lower Bounds, Learning, and Average-Case Complexity
• 47mNatural Proofs in Algebraic Circuit ComplexityAnamay Tengse · Proof Complexity and Meta-Mathematics 2023
• 29mKolmogorov Complexity Characterizes Statistical Zero KnowledgeShuichi Hirahara, Eric Allender, Harsha Tirumala · ITCS 2023