DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.143

From Worst-Case Hardness of NP to Quantum Cryptography via Quantum Indistinguishability Obfuscation

Authors: Tomoyuki Morimae, Yuki Shirakawa, and Takashi Yamakawa

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

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 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 NP (i.e., NP ⊈ 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 NP.

Cite as

Tomoyuki Morimae, Yuki Shirakawa, and Takashi Yamakawa. From Worst-Case Hardness of NP to Quantum Cryptography via Quantum Indistinguishability Obfuscation. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 143:1-143:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{morimae_et_al:LIPIcs.ICALP.2026.143,
  author =	{Morimae, Tomoyuki and Shirakawa, Yuki and Yamakawa, Takashi},
  title =	{{From Worst-Case Hardness of NP to Quantum Cryptography via Quantum Indistinguishability Obfuscation}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{143:1--143:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.143},
  URN =		{urn:nbn:de:0030-drops-265321},
  doi =		{10.4230/LIPIcs.ICALP.2026.143},
  annote =	{Keywords: Quantum cryptography, Indistinguishability Obfuscation}
}

Search Results

Documents authored by Shirakawa, Yuki

From Worst-Case Hardness of NP to Quantum Cryptography via Quantum Indistinguishability Obfuscation

Abstract

Cite as

Thanks for your feedback!

Could not send message