[Resource Topic] 2025/1185: From Worst-Case Hardness of $\mathsf{NP}$ to Quantum Cryptography via Quantum Indistinguishability Obfuscation

Resource Foundations
1

Welcome to the resource topic for 2025/1185

Title:
From Worst-Case Hardness of \mathsf{NP} to Quantum Cryptography via Quantum Indistinguishability Obfuscation

Authors: Tomoyuki Morimae, Yuki Shirakawa, Takashi Yamakawa

Abstract:

Indistinguishability obfuscation (iO) has emerged as a powerful cryptographic primitive with many implications. While classical iO, combined with the infinitely-often worst-case hardness of \mathsf{NP}, is known to imply one-way functions (OWFs) and a range of advanced cryptographic primitives, the cryptographic implications of quantum iO remain poorly understood. In this work, we initiate a study of the power of quantum iO. We define several natural variants of quantum iO, distinguished by whether the obfuscation algorithm, evaluation algorithm, and description of obfuscated program are classical or quantum. For each variant, we identify quantum cryptographic primitives that can be constructed under the assumption of quantum iO and the infinitely-often quantum worst-case hardness of \mathsf{NP} (i.e., \mathsf{NP}\not\subseteq \mathsf{i.o.BQP}). In particular, we construct pseudorandom unitaries, QCCC quantum public-key encryption and (QCCC) quantum symmetric-key encryption, and several primitives implied by them such as one-way state generators, (efficiently-verifiable) one-way puzzles, and EFI pairs, etc. While our main focus is on quantum iO, even in the classical setting, our techniques yield a new and arguably simpler construction of OWFs from classical (imperfect) iO and the infinitely-often worst-case hardness of \mathsf{NP}.

ePrint: https://eprint.iacr.org/2025/1185

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .

2

IYH If a fully-fledged quantum indistinguishability obfuscator (iO) can ever be built, the authors show it becomes a cryptographic Swiss-army knife.

Under the lone extra assumption that NP problems stay hard for quantum computers on infinitely many input sizes, a spectrum of primitives (eg one-way functions, quantum/classical public- and symmetric-key encryption, pseudorandom unitaries) follow automatically. This restructures the post-quantum research map: “get quantum iO → get almost everything else.”

Core Contributions

  1. Taxonomy of Five Quantum iO Flavours
    (Q,Q,Q), (Q,Q,C), (Q,C,C), (C,Q,C), (C,C,C) – differing in whether the obfuscator, evaluator and encoding are quantum (Q) or classical (C).
  2. Main Technical Theorem
    Obfuscations of a point function and the zero function are computationally indistinguishable; any distinguisher would break UP-hardness, contradicting NP ⊄ i.o.BQP.
  3. Simpler OWF Construction
    Works with imperfect iO and needs only 3-CNF obfuscation—resolving an open problem left by Komargodski et al. (2014).
  4. Derived Primitives by Variant
    • (Q,Q,Q) ⇒ Quantum SKE (ciphertext is quantum).
    • (Q,Q,C) ⇒ QCCC SKE (all traffic classical).
    • (Q,C,C) ⇒ QCCC PKE.
    • (C,Q,C) ⇒ post-quantum OWFs + QCCC PKE.
    • (C,C,C) ⇒ classical PKE + OWFs (post-quantum secure).

Counter-Intuitive / Surprising Findings

  1. Quantum iO Alone ≠ Useless: Despite earlier intuitions that a randomized quantum obfuscator could not yield deterministic primitives like OWFs, the authors show OWFs do follow in several iO variants.
  2. Simpler OWF Construction: Classical imperfect iO already implied OWFs (Komargodski et al., 2014) but required “cascading” obfuscations. The new proof removes that cascade and only needs iO for 3-CNF formulas, solving an open problem.
  3. Single-Point Extractability Works in Quantum Setting: The classical equivalence between iO and single-point differing-inputs obfuscation (diO) extends cleanly to quantum adversaries with classical advice, a non-trivial generalization exploited in the proofs.

Take-Home for Researchers

Focus efforts on constructing practical quantum iO (even restricted variants). Success there would cascade into a broad, assumption-light cryptographic toolkit and may supersede many current post-quantum schemes.

Technical notes