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

Morimae, Tomoyuki; Shirakawa, Yuki; Yamakawa, Takashi

doi:10.4230/LIPIcs.ICALP.2026.143

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

Tomoyuki Morimae

Yukawa Institute for Theoretical Physics, Kyoto University, Japan Yuki Shirakawa

Yukawa Institute for Theoretical Physics, Kyoto University, Japan Takashi Yamakawa

NTT Social Informatics Laboratories, Tokyo, Japan
NTT Research Center for Theoretical Quantum Information, Atsugi, Japan
Yukawa Institute for Theoretical Physics, Kyoto University, Japan

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}$ .

Keywords and phrases:

Quantum cryptography, Indistinguishability Obfuscation

Category:

Track A: Algorithms, Complexity and Games

Funding:

Tomoyuki Morimae: JST CREST JPMJCR23I3, JST Moonshot R&D JPMJMS2061-5-1-1, JST FOREST, MEXT QLEAP, the Grant-in Aid for Transformative Research Areas (A) 21H05183, and the Grant-in-Aid for Scientific Research (A) No.22H00522.

Yuki Shirakawa: JST SPRING JPMJSP2110.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Cryptographic primitives

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Obfuscation enables us to transform a program into an unintelligible, “scrambled” form while preserving its functionality. The cryptographic study of obfuscation was initiated by Barak et al. [6], who formalized the notion and introduced the concept of virtual black-box (VBB) security. While they showed that VBB security is unachievable in general, they proposed a weaker notion called indistinguishability obfuscation (iO), leaving open the possibility of its realization.

About a decade later,¹¹1A preliminary version of [6] was published at CRYPTO 2001 and a preliminary version of [26] was published at FOCS 2013. Garg et al. [26] proposed the first candidate construction of iO. This breakthrough led to a cascade of results: it was soon discovered that iO, when combined with one-way functions (OWFs), enables the construction of a wide array of powerful cryptographic primitives (e.g., [32, 30, 51, 10, 39, 21, 40, 22]), some of which had no known constructions prior to iO. As a result, iO has come to be viewed as a “central hub” [51] in cryptography.

Given its remarkable utility, iO has attracted extensive research interest, both in terms of proposing new constructions (e.g., [24, 5, 14, 25, 28, 4, 27, 13], and developing attacks (e.g., [18, 33, 47, 16, 19, 17]). This line of work culminated in a landmark result by Jain, Lin, and Sahai [35], who gave a construction of iO based on long-studied and well-founded cryptographic assumptions.

Despite the tremendous power of iO when combined with OWFs, it is notable that iO alone does not yield any cryptographic primitives. For example, in a hypothetical world where $\mathsf{P}=\mathsf{NP}$ (or even $\mathsf{BPP}=\mathsf{NP}$ ), no cryptographic primitives can exist, yet iO still exists [38]. This highlights the fact that, for iO to be cryptographically useful, one must at least assume the worst-case hardness of $\mathsf{NP}$ .

In this context, Komargodski et al. [38] showed that, assuming only the (infinitely-often) worst-case hardness of $\mathsf{NP}$ (i.e., $\mathsf{NP}\not\subseteq\mathsf{i.o.BPP}$ ),²²2Here, a language $L$ is in $\mathsf{i.o.BPP}$ if all $x\in L\cap\{0,1\}^{n}$ are correctly decided in probabilistic polynomial time for infinitely-many $n\in\mathbb{N}$ . one can already construct OWFs from iO. Once OWFs are obtained, combining them with iO yields public-key encryption (PKE) and many other advanced cryptographic primitives.

The construction of a OWF based on iO in [38] is quite simple, at least assuming the perfect correctness of the obfuscator. Given an obfuscator $\mathsf{Obf}$ , one can define a function $f$ by

\displaystyle f(r)\coloneq\mathsf{Obf}(Z;r)

(1)

where $Z$ denotes the zero-function that outputs $0$ on all inputs, and the notation “ $; r$ ” indicates that $\mathsf{Obf}$ uses randomness $r$ . The authors showed that the one-wayness of $f$ follows from the assumption that $\mathsf{NP}\not\subseteq\mathsf{i.o.BPP}$ . They also demonstrated that even an imperfectly correct iO suffices to construct OWFs, although the construction in that case is more intricate.

As the above construction illustrates, a key requirement in [38] is that the obfuscator $\mathsf{Obf}$ is derandomizable, meaning that it behaves deterministically when given fixed randomness. In contrast, recent works [2, 1, 15, 8, 7, 23, 34] have considered quantum obfuscation, where $\mathsf{Obf}$ is a quantum algorithm that obfuscates either classical or quantum circuits. In this setting, the implicit assumption of derandomizability in [38] breaks down: quantum algorithms inherently involve randomness due to measurement, and thus cannot be derandomized. As a result, the classical approach of [38] does not extend to quantum obfuscation. In fact, it appears unlikely that quantum iO implies OWFs, since a quantum obfuscator is intrinsically a randomized object, making it intuitively useless for constructing deterministic primitives such as OWFs. Nonetheless, recent works [41, 42, 43, 45] have identified several cryptographic primitives that may exist even in the absence of OWFs, including one-way state generators (OWSGs) [49, 50], pseudorandom state generators (PRSGs) [36], pseudorandom unitaries (PRUs) [36, 46], EFI pairs [12], efficiently-verifiable one-way puzzles (EV-OWPuzzs) [20], one-way puzzles (OWPuzzs) [37], etc. These primitives lie below OWFs in known implications, and their existence under weaker assumptions raises the possibility that quantum iO, together with quantum worst-case hardness of $\mathsf{NP}$ , may suffice to construct them. This leads us to the central question of this work:

Does quantum iO imply any quantum cryptographic primitive,
assuming only the quantum worst-case hardness of $\mathsf{NP}$ ?

1.1 Our Result

In this work, we show that quantum iO for classical circuits, when combined with the infinitely-often quantum worst-case hardness of $\mathsf{NP}$ (i.e., $\mathsf{NP}\not\subseteq\mathsf{i.o.BQP}$ ), implies a range of quantum cryptographic primitives. The specific primitives that can be constructed depend on which components of the assumed iO, such as the obfuscation algorithm, the evaluation algorithm, and the description of obfuscated circuit, are quantum and which remain classical. We elaborate on these distinctions and their implications below.

To capture the various flavors of quantum iO, we formalize it as a pair of quantum polynomial-time (QPT) algorithms: an obfuscation algorithm $\mathsf{Obf}$ and an evaluation algorithm $\mathsf{Eval}$ :

: $\mathsf{Obf}(1^{\lambda},C)$ : The obfuscation algorithm takes the security parameter $1^{\lambda}$ and a classical circuit $C$ as input and outputs an obfuscated encoding $\hat{C}$ , which may be a quantum state.
: $\mathsf{Eval}(\hat{C},x)$ : The evaluation algorithm takes an obfuscated encoding $\hat{C}$ and an input $x$ , and outputs $C(x)$ (with overwhelming probability).

The security requirement is that, for any pair of functionally equivalent classical circuits $C_{0}$ and $C_{1}$ , the obfuscations $\mathsf{Obf}(C_{0})$ and $\mathsf{Obf}(C_{1})$ must be computationally indistinguishable to any QPT distinguisher.

We consider several variants of quantum iO, distinguished by whether each component, namely, the obfuscator $\mathsf{Obf}$ , the evaluator $\mathsf{Eval}$ , and the obfuscated encoding $\hat{C}$ , is quantum or classical. Specifically, for each $(\mathtt{X},\mathtt{Y},\mathtt{Z})\in\{\mathtt{Q},\mathtt{C}\}^{3}$ , we define $(\mathtt{X},\mathtt{Y},\mathtt{Z})$ -iO as follows:

$\blacksquare$

If $\mathtt{X}=\mathtt{Q}$ , then $\mathsf{Obf}$ is a quantum algorithm; if $\mathtt{X}=\mathtt{C}$ , then $\mathsf{Obf}$ is classical.
$\blacksquare$

If $\mathtt{Y}=\mathtt{Q}$ , then $\mathsf{Eval}$ is a quantum algorithm; if $\mathtt{Y}=\mathtt{C}$ , then $\mathsf{Eval}$ is classical.
$\blacksquare$

If $\mathtt{Z}=\mathtt{Q}$ , then the obfuscated encoding $\hat{C}$ is a quantum state; if $\mathtt{Z}=\mathtt{C}$ , then $\hat{C}$ is a classical string.

While there are eight possible combinations of $(\mathtt{X},\mathtt{Y},\mathtt{Z})$ , not all are meaningful. In particular, the case $\mathtt{Z}=\mathtt{Q}$ only makes sense when both $\mathtt{X}=\mathtt{Q}$ and $\mathtt{Y}=\mathtt{Q}$ , since a classical obfuscator cannot generate a quantum state and a classical evaluator cannot take a quantum state as input. Accordingly, we focus on the five meaningful variants: $(\mathtt{Q},\mathtt{Q},\mathtt{Q})$ , $(\mathtt{Q},\mathtt{Q},\mathtt{C})$ , $(\mathtt{Q},\mathtt{C},\mathtt{C})$ , $(\mathtt{C},\mathtt{Q},\mathtt{C})$ , and $(\mathtt{C},\mathtt{C},\mathtt{C})$ .

We emphasize that, throughout, the circuit being obfuscated is always a classical circuit. This modeling choice only strengthens our results since our goal is to identify lower bounds of quantum iO³³3Note that obfuscation for quantum circuits implies obfuscation for classical circuits as a special case..

Assuming $\mathsf{NP}\not\subseteq\mathsf{i.o.BQP}$ , we show the following results:

$\blacksquare$

$(\mathtt{Q},\mathtt{Q},\mathtt{Q})$ -iO implies IND-CPA secure quantum symmetric key encryption (QSKE), where the secret key is classical but the ciphertext is quantum. In particular, it implies OWSGs and EFI pairs.
$\blacksquare$

$(\mathtt{Q},\mathtt{Q},\mathtt{C})$ -iO implies IND-CPA secure symmetric key encryption (SKE) in the quantum-computation classical-communication (QCCC) model, referred to as QCCC SKE, where all communication is classical, but local computations, such as encryption and decryption, may be quantum. In particular, it implies EV-OWPuzz, OWPuzzs, OWSGs, QEFID pairs and EFI pairs.
$\blacksquare$

$(\mathtt{Q},\mathtt{C},\mathtt{C})$ -iO implies IND-CPA secure public key encryption (PKE) in the QCCC model, referred to as QCCC PKE. In particular, it implies EV-OWPuzz, OWPuzzs, OWSGs, QEFID pairs and EFI pairs.
$\blacksquare$

$(\mathtt{C},\mathtt{Q},\mathtt{C})$ -iO implies IND-CPA secure QCCC PKE and (post-quantum) OWFs. In particular, it implies all Microcrypt primitives implied by PRUs.
$\blacksquare$

$(\mathtt{C},\mathtt{C},\mathtt{C})$ -iO implies IND-CPA secure PKE and (post-quantum) OWFs. In particular, it implies all Microcrypt primitives implied by PRUs.

We remark that the implication of $(\mathtt{C},\mathtt{C},\mathtt{C})$ -iO can be obtained via a straightforward adaptation of the construction in [38], as all components involved are classical, except that we consider quantum adversaries. Nonetheless, we believe that our proof is arguably simpler than that of [38], which requires cascaded obfuscation, i.e., obfuscating an already obfuscated circuit, whereas our approach avoids it. In addition, an advantage of our approach is that it only requires obfuscation for 3CNF formulas, rather than for general classical circuits. This resolves the open problem left by [38], namely, constructing OWFs from imperfectly correct iO under the assumption of worst-case hardness of $\mathsf{NP}$ . We note, however, that this open problem has been recently resolved (in a stronger form that only requires witness encryption) by completely different techniques [31, 44].

1.2 Technical Overview

Throughout this technical overview, we assume the infinitely-often quantum worst-case hardness of $\mathsf{NP}$ (i.e., $\mathsf{NP}\not\subseteq\mathsf{i.o.BQP}$ ). Our starting point is the Valiant-Vazirani theorem [52], which provides a randomized classical reduction from any $\mathsf{NP}$ instance to a $\mathsf{UP}$ instance.⁴⁴4 $\mathsf{UP}$ is a subclass of $\mathsf{NP}$ consisting of problems where every yes-instance admits a unique witness. This immediately implies that $\mathsf{NP}\not\subseteq\mathsf{i.o.BQP}$ implies $\mathsf{UP}\not\subseteq\mathsf{i.o.BQP}$ as well. Therefore, in proving cryptographic implications, we may assume $\mathsf{UP}\not\subseteq\mathsf{i.o.BQP}$ without loss of generality.

The case of $(\mathtt{C},\mathtt{C},\mathtt{C})$ -iO

We begin by focusing on the case of $(\mathtt{C},\mathtt{C},\mathtt{C})$ -iO, as the other cases build on similar ideas. In this setting, we construct a (post-quantum) OWF and a PKE scheme. Since a PKE scheme can be easily constructed from $(\mathtt{C},\mathtt{C},\mathtt{C})$ -iO and OWFs using the same approach as in the classical construction of [51], it suffices to focus on constructing OWFs.

Our main technical result is the following simple yet powerful statement. Let $\lambda$ be the security parameter. For $n\in\mathbb{N}$ and a string $k\in\{0,1\}^{n}$ , let $P_{k}$ denote a circuit computing the point function with target $k$ , i.e., $P_{k}(k)=1$ and $P_{k}(k^{\prime})=0$ for all $k^{\prime}\neq k$ . Let $Z_{n}$ be a circuit computing the zero function on $n$ -bit inputs, that is, $Z_{n}(k^{\prime})=0$ for all $k^{\prime}\in\{0,1\}^{n}$ . Then, for some polynomial $m=m(\lambda)$ , assuming $\mathsf{NP}\not\subseteq\mathsf{i.o.BQP}$ , we show that

\displaystyle\mathsf{Obf}(1^{\lambda},P_{k})\approx_{c}\mathsf{Obf}(1^{\lambda% },Z_{m}),

(2)

where $k\leftarrow\{0,1\}^{m}$ ,⁵⁵5Here $k\leftarrow\{0,1\}^{m}$ means that $k$ is sampled uniformly at random from $\{0,1\}^{m}$ . and $\approx_{c}$ means computational indistinguishability against QPT distinguishers.⁶⁶6In the actual theorem, we account for the circuit sizes of $P_{k}$ and $Z_{m}$ , but omit these details here for simplicity.

This indistinguishability directly implies the existence of OWFs. Intuitively, the distributions $\mathsf{Obf}(1^{\lambda},P_{k})$ and $\mathsf{Obf}(1^{\lambda},Z_{m})$ should be statistically far, since the obfuscation of $P_{k}$ is functionally equivalent to a point function, while the obfuscation of $Z_{m}$ is functionally equivalent to a constant-zero function. Moreover, since $\mathsf{Obf}$ is assumed to be classical, both distributions are classically efficiently samplable. Such pairs of classically efficiently samplable, statistically far, but computationally indistinguishable distributions are known as EFID pairs [29, 12], and existentially equivalent to OWFs.⁷⁷7The proof of this fact in [29] only considers classical adversaries, but it extends to the post-quantum setting in a straightforward manner.

We now describe the idea for proving the computational indistinguishability between $\mathsf{Obf}(1^{\lambda},P_{k})$ and $\mathsf{Obf}(1^{\lambda},Z_{m})$ . As discussed above, we may assume $\mathsf{UP}\not\subseteq\mathsf{i.o.BQP}$ . Therefore, to prove the above indistinguishability under the assumption, it suffices to show that any distinguisher between $\mathsf{Obf}(1^{\lambda},P_{k})$ and $\mathsf{Obf}(1^{\lambda},Z_{m})$ can be used to recover the unique witness of a yes-instance of a $\mathsf{UP}$ problem.

Let $x$ be a yes-instance of a $\mathsf{UP}$ language with a unique witness $w\in\{0,1\}^{m}$ , and let $M$ be the corresponding verification algorithm. Our goal is to recover $w$ given $x$ and $M$ . To do so, we take a uniformly random $v\in\{0,1\}^{m}$ and define a circuit $V[x,v](z)$ that outputs $1$ if $M(x,v\oplus z)=1$ and otherwise outputs $0$ . Note that $V[x,v](z)$ outputs $1$ only when $z=w\oplus v$ , so it is functionally equivalent to the point function $P_{w\oplus v}$ . Hence, by the security of iO, for each $v\in\{0,1\}^{m}$ , we have

\displaystyle\mathsf{Obf}(1^{\lambda},V[x,v])\approx_{c}\mathsf{Obf}(1^{% \lambda},P_{w\oplus v}).

(3)

Moreover, since $v$ is chosen uniformly at random, $w\oplus v$ is also uniformly random, and so

\displaystyle\mathsf{Obf}(1^{\lambda},P_{w\oplus v})\equiv\mathsf{Obf}(1^{% \lambda},P_{k}),

(4)

where $\equiv$ denotes distributional equivalence and $v,k\leftarrow\{0,1\}^{m}$ . Therefore, a distinguisher that distinguishes $\mathsf{Obf}(1^{\lambda},P_{k})$ with $k\leftarrow\{0,1\}^{m}$ from $\mathsf{Obf}(1^{\lambda},Z_{m})$ also distinguishes $\mathsf{Obf}(1^{\lambda},V[x,v])$ with $v\leftarrow\{0,1\}^{m}$ from $\mathsf{Obf}(1^{\lambda},Z_{m})$ .

While $V[x,v]$ and $Z_{m}$ are not functionally equivalent, they differ on only a single input, namely $w\oplus v$ . It is known that any iO also satisfies the notion of differing-inputs obfuscation (diO) [6, 3, 11] in the single differing-input setting. This means that if one can distinguish two circuits that differ on only one input, then one can efficiently extract that input. Thus, a distinguisher between $\mathsf{Obf}(1^{\lambda},V[x,v])$ with $v\leftarrow\{0,1\}^{m}$ and $\mathsf{Obf}(1^{\lambda},Z_{m})$ can be used to extract $w\oplus v$ .

Since $v$ is chosen independently of both $x$ and $w$ , we can construct a reduction algorithm that chooses $v$ on its own, extracts $w\oplus v$ , and thereby recovers $w$ . This completes the proof of the computational indistinguishability.

The case of $(\mathtt{C},\mathtt{Q},\mathtt{C})$ -iO

In this setting, we construct a (post-quantum) OWF and a QCCC PKE scheme.

To construct a OWF, we use the same argument as in the $(\mathtt{C},\mathtt{C},\mathtt{C})$ setting. Notably, that construction does not rely on the assumption that $\mathsf{Eval}$ is classical, so the proof remains valid even when $\mathsf{Eval}$ is quantum.⁸⁸8Interestingly, the proof remains valid even if $\mathsf{Eval}$ is inefficient.

For constructing a QCCC PKE scheme, we again follow the classical construction of [51]. The only difference is that evaluating the obfuscated program now involves quantum computation, making the encryption algorithm quantum and thus yielding a QCCC PKE scheme.

The case of $(\mathtt{Q},\mathtt{C},\mathtt{C})$ -iO

In this setting, we construct a QCCC PKE scheme. Since $\mathsf{Obf}$ cannot be derandomized in this setting, it is unlikely that OWFs can be constructed. Therefore, we need a different approach from the classical construction of [51].

We begin by noting that the following indistinguishability still holds in this setting:

\displaystyle\mathsf{Obf}(1^{\lambda},P_{k})\approx_{c}\mathsf{Obf}(1^{\lambda% },Z_{m}),

(5)

where $k\leftarrow\{0,1\}^{m}$ . Based on this, we construct a QCCC PKE scheme as follows:

$\blacksquare$

Key generation: Choose $k\leftarrow\{0,1\}^{m}$ , and output the public key $\hat{P}_{k}\leftarrow\mathsf{Obf}(1^{\lambda},P_{k})$ and the secret key $k$ .
$\blacksquare$

Encryption: On input a public key $\hat{P}_{k}$ and a message $\mathsf{msg}$ , define a classical circuit $C[\hat{P}_{k},\mathsf{msg}]$ that takes $k^{\prime}\in\{0,1\}^{m}$ as input and outputs $\mathsf{msg}$ if $\mathsf{Eval}(\hat{P}_{k},k^{\prime})=1$ , and outputs $\bot$ otherwise. Here, we assume for simplicity that $\mathsf{Eval}$ is deterministic (see the full proof in Section 5.3 for how to handle randomized $\mathsf{Eval}$ ). The ciphertext is defined as $\hat{C}[\hat{P}_{k},\mathsf{msg}]\leftarrow\mathsf{Obf}(1^{\lambda},C[\hat{P}_% {k},\mathsf{msg}])$ .
$\blacksquare$

Decryption: On input a ciphertext $\hat{C}[\hat{P}_{k},\mathsf{msg}]$ and the secret key $k$ , evaluate the obfuscated circuit on input $k$ and output the result $\mathsf{msg}^{\prime}$ .

The correctness of the scheme follows directly from the correctness of the iO.

We now argue IND-CPA security of the scheme. First, consider a hybrid where the public key is replaced with $\mathsf{Obf}(1^{\lambda},Z_{m})$ . This is computationally indistinguishable from the real scheme by the indistinguishability between $\mathsf{Obf}(1^{\lambda},P_{k})$ and $\mathsf{Obf}(1^{\lambda},Z_{m})$ , which has already been established.

Next, consider a second hybrid where the ciphertext is replaced with $\mathsf{Obf}(1^{\lambda},Z_{m})$ . This is indistinguishable from the previous hybrid because, when the public key is $\mathsf{Obf}(1^{\lambda},Z_{m})$ , the circuit $C[\mathsf{Obf}(1^{\lambda},Z_{m}),\mathsf{msg}]$ is functionally equivalent to the zero function regardless of the message $\mathsf{msg}$ , and hence its obfuscation is indistinguishable from that of $Z_{m}$ by the security of iO.

In the final hybrid, the ciphertext reveals no information about the message $\mathsf{msg}$ , so the scheme satisfies IND-CPA security.

The case of $(\mathtt{Q},\mathtt{Q},\mathtt{C})$ -iO

In this setting, we construct a QCCC SKE scheme.

The idea is quite simple. We construct a QCCC SKE scheme for single-bit messages as follows: let $k\leftarrow\{0,1\}^{m}$ be the secret key. To encrypt the message $0$ , output the ciphertext $\mathsf{Obf}(1^{\lambda},Z_{m})$ ; to encrypt the message $1$ , output $\mathsf{Obf}(1^{\lambda},P_{k})$ . Decryption is performed by evaluating the obfuscated program (i.e., the ciphertext) on input $k$ and outputting the result, which will be either $0$ or $1$ accordingly.

While we have already established the indistinguishability between $\mathsf{Obf}(1^{\lambda},Z_{m})$ and $\mathsf{Obf}(1^{\lambda},P_{k})$ , this alone is not sufficient to guarantee IND-CPA security of the above scheme. However, by carefully examining the proof of this indistinguishability, one can see that it extends to the case where the distinguisher is given multiple samples from the respective distributions, all generated using the same secret key $k$ . This extension immediately implies the IND-CPA security of the scheme.

The case of $(\mathtt{Q},\mathtt{Q},\mathtt{Q})$ -iO

In this setting, we construct a QSKE scheme, where the secret key is classical but the ciphertext is quantum. The construction is exactly the same as in the $(\mathtt{Q},\mathtt{Q},\mathtt{C})$ case described above. The only difference is that the output of $\mathsf{Obf}$ is a quantum state, which means the ciphertexts are quantum. As a result, the scheme realizes QSKE rather than QCCC SKE.

2 Preliminaries

Notations

We use standard notations of quantum computing and cryptography. We use $\lambda$ as the security parameter. $[n]$ means the set $\{1,2,...,n\}$ . For a finite set $S$ , $x\leftarrow S$ means that an element $x$ is sampled uniformly at random from the set $S$ . ${\mathsf{negl}}$ is a negligible function, and ${\mathrm{poly}}$ is a polynomial. PPT stands for (classical) probabilistic polynomial-time and QPT stands for quantum polynomial-time. We refer to a non-uniform QPT algorithm as a QPT algorithm with polynomial-size quantum advice. We stress that the running time of the algorithm can be polynomial in $\lambda$ rather than in $\log\lambda$ . For an algorithm $A$ , $y\leftarrow A(x)$ means that the algorithm $A$ outputs $y$ on input $x$ .

2.1 Cryptographic Primitives

Here, we give definitions of basic cryptographic primitives.

Definition 1 (One-Way Functions (OWFs)).

A function $f:\{0,1\}^{*}\to\{0,1\}^{*}$ is a (quantumly-secure) one-way function (OWF) if it is computable in classical deterministic polynomial-time, and for any QPT adversary $\mathcal{A}$ , there exists a negligible function ${\mathsf{negl}}$ such that

\Pr[f(x^{\prime})=f(x):x\leftarrow\{0,1\}^{\lambda},x^{\prime}\leftarrow% \mathcal{A}(1^{\lambda},f(x))]\leq{\mathsf{negl}}(\lambda).

(6)

Definition 2 (Quantum Symmetric Key Encryption (QSKE) [50]).

A QSKE scheme is a tuple $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ of QPT algorithms with the following syntax:

$\blacksquare$

$\mathsf{Gen}(1^{\lambda})\to\mathsf{sk}$ : A key generation algorithm takes the security parameter $1^{\lambda}$ as input and outputs a classical secret key $\mathsf{sk}$ .
$\blacksquare$

$\mathsf{Enc}(\mathsf{sk},\mathsf{msg})\to\mathsf{ct}$ : An encryption algorithm takes a secret key $\mathsf{sk}$ and a message $\mathsf{msg}\in\{0,1\}^{*}$ as input and outputs a (possibly mixed) quantum ciphertext $\mathsf{ct}$ .
$\blacksquare$

$\mathsf{Dec}(\mathsf{sk},\mathsf{ct})\to\mathsf{msg}^{\prime}$ : A decryption algorithm takes a secret key $\mathsf{sk}$ and a ciphertext $\mathsf{ct}$ as input and outputs a message $\mathsf{msg}^{\prime}\in\{0,1\}^{*}$ .

We require the following correctness and IND-CPA security:

\blacksquare

Correctness: For all $\mathsf{msg}\in\{0,1\}^{*}$ of polynomial length in $\lambda$ ,

\displaystyle\Pr\left[\mathsf{msg}^{\prime}=\mathsf{msg}:\begin{matrix}\mathsf% {sk}\leftarrow\mathsf{Gen}(1^{\lambda})\\ \mathsf{ct}\leftarrow\mathsf{Enc}(\mathsf{sk},\mathsf{msg})\\ \mathsf{msg}^{\prime}\leftarrow\mathsf{Dec}(\mathsf{sk},\mathsf{ct})\end{% matrix}\right]\geq 1-{\mathsf{negl}}(\lambda).

(7)

$\blacksquare$
IND-CPA Security: For a security parameter $\lambda\in\mathbb{N}$ and a bit $b\in\{0,1\}$ , consider the following game between a challenger and an adversary $\mathcal{A}$ :
1. 1.
  
  The challenger runs $\mathsf{sk}\leftarrow\mathsf{Gen}(1^{\lambda})$ .
2. 2.
  
  $\mathcal{A}$ can make arbitrarily many classical queries to the encryption oracle, which takes a message $\mathsf{msg}\in\{0,1\}^{*}$ as input and returns $\mathsf{Enc}(\mathsf{sk},\mathsf{msg})$ .
3. 3.
  
  $\mathcal{A}$ chooses $(\mathsf{msg}_{0},\mathsf{msg}_{1})\in(\{0,1\}^{*})^{2}$ of the same length and sends them to the challenger.
4. 4.
  
  The challenger runs $\mathsf{ct}_{b}\leftarrow\mathsf{Enc}(\mathsf{sk},\mathsf{msg}_{b})$ and sends $\mathsf{ct}_{b}$ to $\mathcal{A}$ .
5. 5.
  
  Again, $\mathcal{A}$ can make arbitrarily many classical queries to the encryption oracle.
6. 6.
  
  $\mathcal{A}$ outputs $b^{\prime}$ .
We say that a QSKE scheme satisfies the IND-CPA security if for any QPT adversary $\mathcal{A}$ ,

$\displaystyle|\Pr[b^{\prime}=1|b=1]-\Pr[b^{\prime}=1|b=0]|\leq{\mathsf{negl}}(% \lambda).$ (8)

$\blacktriangleright$ Remark 3.

In the above definition, we only consider security against QPT adversaries that receive a single copy of the quantum ciphertext $\mathsf{ct}_{b}$ . However, by a standard hybrid argument, such single-copy security is equivalent to security against QPT adversaries that receive $\mathsf{ct}_{b}^{\otimes t(\lambda)}$ for any polynomial $t$ .

We define SKE and PKE schemes in the quantum-computation classical-communication (QCCC) model, in which all local computations are quantum and all communication is classical.

Definition 4 (QCCC SKE [37]).

A QCCC SKE scheme is defined similarly to a QSKE scheme as defined in Definition 2 except that a ciphertext $\mathsf{ct}$ output by $\mathsf{Enc}$ is required to be classical.

Definition 5 (QCCC Public Key Encryption (QCCC PKE) [37]).

A QCCC PKE scheme is a tuple $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ of QPT algorithms with the following syntax:

$\blacksquare$

$\mathsf{Gen}(1^{\lambda})\to(\mathsf{pk},\mathsf{sk})$ : A key generation algorithm takes the security parameter $1^{\lambda}$ as input and outputs a classical public key $\mathsf{pk}$ and classical secret key $\mathsf{sk}$ .
$\blacksquare$

$\mathsf{Enc}(\mathsf{pk},\mathsf{msg})\to\mathsf{ct}$ : An encryption algorithm takes a public key $\mathsf{pk}$ and a message $\mathsf{msg}\in\{0,1\}^{*}$ as input and outputs a classical ciphertext $\mathsf{ct}$ .
$\blacksquare$

$\mathsf{Dec}(\mathsf{sk},\mathsf{ct})\to\mathsf{msg}^{\prime}$ : A decryption algorithm takes a secret key $\mathsf{sk}$ and a ciphertext $\mathsf{ct}$ as input and outputs a message $\mathsf{msg}^{\prime}\in\{0,1\}^{*}$ .

We require the following correctness and IND-CPA security:

\blacksquare

Correctness: For all $\mathsf{msg}\in\{0,1\}^{*}$ of polynomial length in $\lambda$ ,

\displaystyle\Pr\left[\mathsf{msg}^{\prime}=\mathsf{msg}:\begin{matrix}(% \mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})\\ \mathsf{ct}\leftarrow\mathsf{Enc}(\mathsf{pk},\mathsf{msg})\\ \mathsf{msg}^{\prime}\leftarrow\mathsf{Dec}(\mathsf{sk},\mathsf{ct})\end{% matrix}\right]\geq 1-{\mathsf{negl}}(\lambda).

(9)

$\blacksquare$
IND-CPA Security: For a security parameter $\lambda\in\mathbb{N}$ and a bit $b\in\{0,1\}$ , consider the following game between a challenger and an adversary $\mathcal{A}$ :
1. 1.
  
  The challenger runs $(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})$ and sends $\mathsf{pk}$ to $\mathcal{A}$ .
2. 2.
  
  $\mathcal{A}$ chooses $\mathsf{msg}_{0},\mathsf{msg}_{1}\in(\{0,1\}^{*})^{2}$ of the same length and sends them to the challenger.
3. 3.
  
  The challenger runs $\mathsf{ct}_{b}\leftarrow\mathsf{Enc}(\mathsf{pk},\mathsf{msg}_{b})$ and sends $\mathsf{ct}_{b}$ to $\mathcal{A}$ .
4. 4.
  
  $\mathcal{A}$ outputs $b^{\prime}$ .
We say that a QCCC PKE scheme satisfies the IND-CPA security if for any QPT adversary $\mathcal{A}$ ,

$\displaystyle|\Pr[b^{\prime}=1|b=1]-\Pr[b^{\prime}=1|b=0]|\leq{\mathsf{negl}}(% \lambda).$ (10)

We omit definitions of other cryptographic primitives, such as EV-OWPuzzs [20], OWPuzzs [37], OWSGs [50], QEFID pairs [20], PRUs [36], and EFI pairs [12], since we obtain them only as corollaries. For their definitions, we refer the reader to the respective cited works. One remark regarding the definition of OWSGs is that, unless stated otherwise, we refer to OWSGs with mixed-state outputs as defined in [50].

2.2 Complexity Theory

Here we explain basic complexity classes we use.

Definition 6 (i.o.BQP).

A promise problem $\Pi=(\Pi_{yes},\Pi_{no})$ is in $\mathsf{i.o.BQP}$ if there exist a QPT algorithm $Q$ and infinitely many $\lambda\in\mathbb{N}$ such that for all $x\in\Pi_{yes}\cup\Pi_{no}$ ,

$\blacksquare$

if $x\in\Pi_{yes}\cap\{0,1\}^{\lambda}$ , then $\Pr[1\leftarrow Q(x)]\geq 2/3$ .
$\blacksquare$

if $x\in\Pi_{no}\cap\{0,1\}^{\lambda}$ , then $\Pr[1\leftarrow Q(x)]\leq 1/3$ .

Definition 7 (UP).

A promise problem $\Pi=(\Pi_{yes},\Pi_{no})$ is in $\mathsf{UP}$ if there exist a classical polynomial-time (deterministic) Turing machine $M$ and a polynomial $m$ such that

$\blacksquare$

if $x\in\Pi_{yes}$ , then there exists a unique $w\in\{0,1\}^{m(|x|)}$ such that $M(x,w)=1$ .
$\blacksquare$

if $x\in\Pi_{no}$ , then for all $w\in\{0,1\}^{m(|x|)}$ , $M(x,w)=0$ .

The following lemma follows from the Valiant-Vazirani theorem [52].

Lemma 8.

If $\mathsf{NP}\nsubseteq\mathsf{i.o.BQP}$ , then $\mathsf{UP}\nsubseteq\mathsf{i.o.BQP}$ .

3 Definitions of Quantum Obfuscation

We introduce definitions of quantum indistinguishability obfuscation for classical circuits and its variants.

Definition 9 (Quantum iO for Classical Circuits).

A quantum indistinguishability obfuscator (quantum iO) for classical circuits consists of two QPT algorithms $(\mathsf{Obf},\mathsf{Eval})$ with the following syntax:

$\blacksquare$

$\mathsf{Obf}(1^{\lambda},C)\to\hat{C}$ : An obfuscation algorithm takes the security parameter $1^{\lambda}$ and a classical circuit $C$ as input and outputs a quantum state $\hat{C}$ , which we refer to as an obfuscated encoding of $C$ .
$\blacksquare$

$\mathsf{Eval}(\hat{C},x)\to y$ : An evaluation algorithm takes an obfuscated encoding $\hat{C}$ and a classical input $x$ as input and outputs a classical output $y$ .

We require the following correctness and security.

$\blacksquare$

Correctness: For any family $\{C_{\lambda}\}_{\lambda\in\mathbb{N}}$ of polynomial-size classical circuits of input length $n_{\lambda}$ , and for any polynomial $p$ , there exists $N\in\mathbb{N}$ such that

$\displaystyle\Pr_{\hat{C}_{\lambda}\leftarrow\mathsf{Obf}(1^{\lambda},C_{% \lambda})}\left[\forall x\in\{0,1\}^{n_{\lambda}},\Pr[\mathsf{Eval}(\hat{C}_{% \lambda},x)=C_{\lambda}(x)]\geq 1-\frac{1}{p(\lambda)}\right]\geq 1-\frac{1}{p% (\lambda)}$ (11)

holds for all $\lambda\geq N$ , where the inner probability is taken over the randomness of the execution of $\mathsf{Eval}(\hat{C}_{\lambda},x)$ .
$\blacksquare$

Security: For any families $\{C_{0,\lambda}\}_{\lambda\in\mathbb{N}}$ and $\{C_{1,\lambda}\}_{\lambda\in\mathbb{N}}$ of polynomial-size classical circuits such that $C_{0,\lambda}$ and $C_{1,\lambda}$ are functionally equivalent and of the same size, and for any non-uniform QPT adversary $\mathcal{A}$ ,

$\displaystyle|\Pr[1\leftarrow\mathcal{A}(1^{\lambda},\mathsf{Obf}(1^{\lambda},% C_{0,\lambda}))]-\Pr[1\leftarrow\mathcal{A}(1^{\lambda},\mathsf{Obf}(1^{% \lambda},C_{1,\lambda}))]|\leq{\mathsf{negl}}(\lambda).$ (12)

$\blacktriangleright$ Remark 10.

The correctness notion defined above may seem strong, as it requires that the evaluation returns the correct output for all inputs simultaneously with overwhelming probability. However, this stronger guarantee can be generically achieved assuming only a quantum iO with a weaker, input-wise correctness – that is, for each fixed input, the evaluation returns the correct output with overwhelming probability. To achieve stronger correctness, we can simply repeat the obfuscation algorithm multiple times to obtain independent copies of the (possibly quantum) obfuscated encoding. To evaluate the program on a given input, we evaluate each fresh copy of the obfuscated program on that input and take a majority vote of the outputs. By choosing the number of copies to be sufficiently large, the failure probability on any fixed input can be reduced exponentially. A union bound then implies that the overall probability of failure on any input remains negligible. This argument closely parallels the classical case presented in [38, Appendix B], and we therefore omit the details.

$\blacktriangleright$ Remark 11.

In the above definition, we only consider security against QPT adversaries that receive a single copy of the obfuscated program $\mathsf{Obf}(1^{\lambda},C_{b,\lambda})$ . However, by a standard hybrid argument, we can show that such single-copy security is equivalent to security against adversaries that receive $\mathsf{Obf}(1^{\lambda},C_{b,\lambda})^{\otimes t(\lambda)}$ for any polynomial $t$ .

$\blacktriangleright$ Remark 12.

We require the security of iO to hold against non-uniform quantum QPT adversaries, even though our final goal is to construct cryptographic primitives with uniform security. This is because a uniform version of the security, where a uniform QPT adversary $\mathcal{A}$ chooses two functionally equivalent circuits $C_{0}$ and $C_{1}$ and then tries to distinguish obfuscations of them, would not suffice for our purpose, since we must consider a reduction algorithm that hardwires an arbitrary choice of an $\mathsf{NP}$ instance into the circuits. Although this point is not explicitly discussed, we believe the same applies even in the classical setting of [38]. In addition, we note that the non-uniform security notion aligns more closely with the standard formalization in the literature on iO.

Definition 13 (Variations of Quantum iO).

For $(\mathtt{X},\mathtt{Y},\mathtt{Z})\in\{\mathtt{Q},\mathtt{C}\}^{3}$ , $(\mathtt{X},\mathtt{Y},\mathtt{Z})$ -iO for classical circuits is defined similarly to quantum iO for classical circuits as defined in Definition 9 except that:

$\blacksquare$

If $\mathtt{X}=\mathtt{C}$ , $\mathsf{Obf}$ is a PPT algorithm whereas if $\mathtt{X}=\mathtt{Q}$ , $\mathsf{Obf}$ is a QPT algorithm;
$\blacksquare$

If $\mathtt{Y}=\mathtt{C}$ , $\mathsf{Eval}$ is a PPT algorithm whereas if $\mathtt{Y}=\mathtt{Q}$ , $\mathsf{Eval}$ is a QPT algorithm;
$\blacksquare$

If $\mathtt{Z}=\mathtt{C}$ , an encoding $\hat{C}$ output by $\mathsf{Obf}$ is a classical string whereas if $\mathtt{Z}=\mathtt{Q}$ , $\hat{C}$ is a quantum state.

$\blacktriangleright$ Remark 14.

While there are $8$ possible choices for $(\mathtt{X},\mathtt{Y},\mathtt{Z})$ , some of them are meaningless. In particular, it makes sense to have $\mathtt{Z}=\mathtt{Q}$ only if $\mathtt{X}=\mathtt{Y}=\mathtt{Q}$ since classical $\mathsf{Obf}$ cannot output quantum $\hat{C}$ and classical $\mathsf{Eval}$ cannot take quantum $\hat{C}$ as input. Thus, there are $5$ meaningful choices: $(\mathtt{Q},\mathtt{Q},\mathtt{Q})$ , $(\mathtt{Q},\mathtt{Q},\mathtt{C})$ , $(\mathtt{Q},\mathtt{C},\mathtt{C})$ , $(\mathtt{C},\mathtt{Q},\mathtt{C})$ , and $(\mathtt{C},\mathtt{C},\mathtt{C})$ . $(\mathtt{Q},\mathtt{Q},\mathtt{Q})$ -iO corresponds to quantum iO as defined in Definition 9 and $(\mathtt{C},\mathtt{C},\mathtt{C})$ -iO corresponds to (post-quantum) classical iO. We stress that we consider obfuscation of classical circuits and security against quantum adversaries in all the variant.

In the security definition of iO, the two circuits are required to be functionally equivalent, that is, they must agree on all inputs. The notion of differing-inputs obfuscation (diO) [6, 3, 11] relaxes this requirement by allowing circuits that may differ on some inputs, as long as those inputs are hard to find. This results in a strictly stronger security notion than iO. It is known that in the classical setting, iO and diO are equivalent when the number of differing inputs is polynomial. We observe that this equivalence extends to the quantum setting as well. For our purposes, we present the definition of diO in the case where there is only a single differing input, which suffices for our applications.

Definition 15 (Single-Point Differing-Inputs Obfuscation (diO)).

For $(\mathtt{X},\mathtt{Y},\mathtt{Z})\in\{\mathtt{Q},\mathtt{C}\}^{3}$ , $(\mathtt{X},\mathtt{Y},\mathtt{Z})$ -single-point diO for classical circuits is defined similarly to $(\mathtt{X},\mathtt{Y},\mathtt{Z})$ -iO except that the security is replaced with extractability defined as follows:

\blacksquare

Extractability (for single-differing-point): For any QPT adversary $\mathcal{A}$ and any polynomial $p$ , there exist a QPT algorithm $\mathsf{Ext}$ and a polynomial $q$ for which the following holds. For any pair of families of polynomial-size classical circuits $\{C_{0,\lambda}\}_{\lambda\in\mathbb{N}}$ and $\{C_{1,\lambda}\}_{\lambda\in\mathbb{N}}$ , such that for each $\lambda$ , $C_{0,\lambda}$ and $C_{1,\lambda}$ have the same size and input length, and differ on at most a single input, and for any family of polynomial-size classical strings $\{z_{\lambda}\}_{\lambda\in\mathbb{N}}$ , the following holds for all sufficiently large $\lambda\in\mathbb{N}$ :

	$\displaystyle\Pr\left[b^{\prime}=b:\begin{matrix}b\leftarrow\{0,1\}\\ \hat{C}_{\lambda}\leftarrow\mathsf{Obf}(1^{\lambda},C_{b,\lambda})\\ b^{\prime}\leftarrow\mathcal{A}(1^{\lambda},\hat{C}_{\lambda},C_{0,\lambda},C_% {1,\lambda},z_{\lambda})\end{matrix}\right]\geq\frac{1}{2}+\frac{1}{p(\lambda)}$		(13)
	$\displaystyle\quad\Longrightarrow\Pr\left[C_{0,\lambda}(x)\neq C_{1,\lambda}(x% ):x\leftarrow\mathsf{Ext}(1^{\lambda},C_{0,\lambda},C_{1,\lambda},z_{\lambda})% \right]\geq\frac{1}{q(\lambda)}.$		(14)

$\blacktriangleright$ Remark 16.

Zhandry [53] observed that defining diO involves subtle challenges when considering security against quantum adversaries with quantum advice. In contrast, we restrict our attention to quantum adversaries with classical advice. As a result, these complications do not arise in our setting, allowing us to define diO in a manner that closely mirrors the classical definition from [11].

In the classical advice setting considered above, the equivalence between iO and single-point diO can be proven using essentially the same argument as in the classical case, as shown in [11].

Lemma 17 (Adapted from [11]).

For $(\mathtt{X},\mathtt{Y},\mathtt{Z})\in\{\mathtt{Q},\mathtt{C}\}^{3}$ , if $(\mathsf{Obf},\mathsf{Eval})$ is an $(\mathtt{X},\mathtt{Y},\mathtt{Z})$ -iO for classical circuits, then it is also $(\mathtt{X},\mathtt{Y},\mathtt{Z})$ -single-point diO for classical circuits.

4 Main Technical Theorem

We prove a technical theorem that is the basis of all our cryptographic implications.

Let $s_{min}$ be a polynomial such that, for any $m\in\mathbb{N}$ and any $k\in\{0,1\}^{m}$ , there exist classical circuits of size at most $s_{min}(m)$ that compute the following functions on $m$ -bit inputs:

$\blacksquare$

the point function at target point $k$ , which outputs $1$ on input $k$ and $0$ on all other inputs; and
$\blacksquare$

the zero function, which outputs 0 on all $m$ -bit inputs.

For $m\in\mathbb{N}$ , $k\in\{0,1\}^{m}$ , and $s\geq s_{min}(m)$ , let $P_{k,s}$ denote a canonical classical circuit of size $s$ that computes the point function on the target point $k$ , and let $Z_{m,s}$ be a canonical classical circuit of size $s$ that computes the zero-function on $m$ -bit inputs. Here, “canonical” refers to a fixed but arbitrary choice of circuit construction, provided that the descriptions of $P_{k,s}$ and $Z_{m,s}$ are computable in classical polynomial time from $(k,1^{s})$ and $(1^{m},1^{s})$ , respectively. The specific choice of canonical circuits does not affect our results.

Then we prove the following theorem.

Theorem 18.

Suppose $\mathsf{NP}\nsubseteq\mathsf{i.o.BQP}$ and $(\mathsf{Obf},\mathsf{Eval})$ is an $(\mathtt{X},\mathtt{Y},\mathtt{Z})$ -iO for classical circuits for $(\mathtt{X},\mathtt{Y},\mathtt{Z})\in\{\mathtt{Q},\mathtt{C}\}^{3}$ . Then, there are classical-polynomial-time-computable polynomials $m$ and $s$ such that for any polynomial $\ell$ , the following two distributions (over classical bit strings if $\mathtt{Z}=\mathtt{C}$ and over quantum states if $\mathtt{Z}=\mathtt{Q}$ ) are computationally indistinguishable against uniform QPT adversaries:

$\blacksquare$

$\mathcal{D}_{0}(\lambda)$ : Sample $k\leftarrow\{0,1\}^{m(\lambda)}$ , run $\hat{P}_{k,s(\lambda)}^{i}\leftarrow\mathsf{Obf}(1^{\lambda},P_{k,s(\lambda)})$ for $i\in[\ell(\lambda)]$ , and output $(1^{\lambda},\hat{P}_{k,s(\lambda)}^{1},\hat{P}_{k,s(\lambda)}^{2},\ldots,\hat% {P}_{k,s(\lambda)}^{\ell(\lambda)})$ .
$\blacksquare$

$\mathcal{D}_{1}(\lambda)$ : Run $\hat{Z}_{m(\lambda),s(\lambda)}^{i}\leftarrow\mathsf{Obf}(1^{\lambda},Z_{m(% \lambda),s(\lambda)})$ for $i\in[\ell(\lambda)]$ and output $(1^{\lambda},\hat{Z}_{m(\lambda),s(\lambda)}^{1},$ $\hat{Z}_{m(\lambda),s(\lambda)}^{2},$ $\ldots,$ $\hat{Z}_{m(\lambda),s(\lambda)}^{\ell(\lambda)})$ .

Proof of Theorem 18.

By Lemma 8, we have $\mathsf{UP}\nsubseteq\mathsf{i.o.BQP}$ . Then, there exists a promise problem $\Pi=(\Pi_{yes},\Pi_{no})\in\mathsf{UP}$ such that $\Pi\notin\mathsf{i.o.BQP}$ . By the definition of $\mathsf{UP}$ , there exist a polynomial $m$ and a deterministic polynomial-time Turing machine $M$ such that

$\blacksquare$

If $x\in\Pi_{yes}$ , then there exists a unique $w\in\{0,1\}^{m(|x|)}$ such that $M(x,w)=1$ .
$\blacksquare$

If $x\in\Pi_{no}$ , $M(x,w)=0$ for any $w\in\{0,1\}^{m(|x|)}$ .

Without loss of generality, we can assume that $m$ is classical-polynomial-time-computable because we can pad $w$ so that its length matches (an upper bound of) the running time of $M$ .

For the sake of contradiction, let us assume that for any classical-polynomial-time-computable polynomial $s$ , the following holds: There exist polynomials $\ell$ and $p$ , and a uniform QPT algorithm $\mathcal{A}$ such that

\displaystyle\Pr_{k\leftarrow\{0,1\}^{m(\lambda)}}[1\leftarrow\mathcal{A}(1^{% \lambda},\hat{P}_{k,s(\lambda)}^{1},...,\hat{P}_{k,s(\lambda)}^{\ell(\lambda)}% )]-\Pr[1\leftarrow\mathcal{A}(1^{\lambda},\hat{Z}_{m(\lambda),s(\lambda)}^{1},% ...,\hat{Z}_{m(\lambda),s(\lambda)}^{\ell(\lambda)})]\geq\frac{1}{p(\lambda)}

(15)

holds for infinitely many $\lambda$ , where $\hat{P}_{k,s(\lambda)}^{i}\leftarrow\mathsf{Obf}(1^{\lambda},P_{k,s(\lambda)})$ and $\hat{Z}_{m(\lambda),s(\lambda)}^{i}\leftarrow\mathsf{Obf}(1^{\lambda},Z_{m(% \lambda),s(\lambda)})$ for each $i\in[\ell(\lambda)]$ . Our goal is to construct a QPT algorithm that solves $\Pi$ for infinitely many input lengths, thereby showing that $\Pi\in\mathsf{i.o.BQP}$ . To do this, it suffices to show that there exist a QPT algorithm $\mathcal{B}$ and a polynomial $r$ such that for infinitely many $\lambda\in\mathbb{N}$

\displaystyle\Pr[M(x,w)=1:w\leftarrow\mathcal{B}(x)]\geq\frac{1}{r(\lambda)}

(16)

is satisfied for all $x\in\Pi_{yes}\cap\{0,1\}^{\lambda}$ . Then, a QPT algorithm $\mathcal{C}$ that on input $x\in\{0,1\}^{\lambda}$ , runs $w\leftarrow\mathcal{B}(x)$ and outputs $M(x,w)$ satisfies,

$\blacksquare$

if $x\in\Pi_{yes}$ , $\Pr[1\leftarrow\mathcal{C}(x)]=\Pr[M(x,w)=1:w\leftarrow\mathcal{B}(x)]\geq% \frac{1}{r(\lambda)}$ ,
$\blacksquare$

if $x\in\Pi_{no}$ , $\Pr[1\leftarrow\mathcal{C}(x)]=\Pr[M(x,w)=1:w\leftarrow\mathcal{B}(x)]=0$ ,

for infinitely many $\lambda\in\mathbb{N}$ . The completeness-soundness gap is $1/r(\lambda)=1/{\mathrm{poly}}(\lambda)$ and therefore $\Pi\in\mathsf{i.o.BQP}$ .

In the remaining part, we show the existence of a polynomial $r$ and a QPT algorithm $\mathcal{B}$ that satisfy Equation 16. There exists a family $\{V_{\lambda}[x,v]\}_{\lambda\in\mathbb{N}}$ of polynomial-size classical circuits such that for each $\lambda$ , $V_{\lambda}[x,v]$ is parametrized by $x\in\{0,1\}^{\lambda}$ and $v\in\{0,1\}^{m(\lambda)}$ , operates on $m(\lambda)$ bits, and computes the function

\displaystyle V_{\lambda}[x,v](z):=\begin{cases}1&\text{if }M(x,v\oplus z)=1\\ 0&\text{otherwise},\end{cases}

(17)

where the description of $V_{\lambda}[x,v]$ is computable in classical polynomial time from $(x,v)$ . Let $s(\lambda)$ be the size of $V_{\lambda}[x,v]$ . Then, $s$ is classical-polynomial-time-computable because there exists a Turing machine that on input $1^{\lambda}$ , computes $1^{m(\lambda)}$ , computes the description of $V_{\lambda}[1^{\lambda},1^{m(\lambda)}]$ from $(1^{\lambda},1^{m(\lambda)})$ , and outputs $s(\lambda)=|V_{\lambda}[1^{\lambda},1^{m(\lambda)}]|$ . We can choose $s$ such that $s(\lambda)\geq s_{min}(m(\lambda))$ by adding dummy gates that do not change the functionality of $V_{\lambda}[x,v]$ .

For each $x\in\Pi_{yes}$ and $v\in\{0,1\}^{m(|x|)}$ , $V_{|x|}[x,v]$ has the same functionality with $P_{w\oplus v,s(|x|)}$ , where $w\in\{0,1\}^{m(|x|)}$ is the unique witness for $x$ .

Then, by the security of iO, for any uniform QPT algorithm $\mathcal{A}^{\prime}$ and for any polynomial $b$ , there exists $N\in\mathbb{N}$ such that

\displaystyle\Bigg|\Pr[1\leftarrow\mathcal{A}^{\prime}(1^{\lambda},\hat{V}_{x,% v}^{1},...,\hat{V}_{x,v}^{\ell(\lambda)})]-\Pr[1\leftarrow\mathcal{A}^{\prime}% (1^{\lambda},\hat{P}_{w\oplus v,s(\lambda)}^{1},...,\hat{P}_{w\oplus v,s(% \lambda)}^{\ell(\lambda)})]\Bigg|\leq\frac{1}{b(\lambda)}

(18)

for all $v\in\{0,1\}^{m(\lambda)}$ , all $x\in\Pi_{yes}\cap\{0,1\}^{\lambda}$ and all $\lambda$ such that $\lambda\geq N$ , where $\hat{V}_{x,v}^{i}\leftarrow\mathsf{Obf}(1^{\lambda},V_{\lambda}[x,v])$ and $\hat{P}_{w\oplus v,s(\lambda)}^{i}\leftarrow\mathsf{Obf}(1^{\lambda},P_{w% \oplus v,s(\lambda)})$ for each $i\in[\ell(\lambda)]$ . Then, for the QPT algorithm $\mathcal{A}$ that satisfies Equation 15, there exist infinitely many $\lambda\in\mathbb{N}$ such that for all $x\in\Pi_{yes}\cap\{0,1\}^{\lambda}$ ,

	$\displaystyle\Pr_{v\leftarrow\{0,1\}^{m(\lambda)}}[1\leftarrow\mathcal{A}(1^{% \lambda},\hat{V}_{x,v}^{1},...,\hat{V}_{x,v}^{\ell(\lambda)})]-\Pr[1\leftarrow% \mathcal{A}(1^{\lambda},\hat{Z}_{m(\lambda),s(\lambda)}^{1},...,\hat{Z}_{m(% \lambda),s(\lambda)}^{\ell(\lambda)})]$		(19)
	$\displaystyle=\Pr_{v\leftarrow\{0,1\}^{m(\lambda)}}[1\leftarrow\mathcal{A}(1^{% \lambda},\hat{P}_{v,s(\lambda)}^{1},...,\hat{P}_{v,s(\lambda)}^{\ell(\lambda)}% )]-\Pr[1\leftarrow\mathcal{A}(1^{\lambda},\hat{Z}_{m(\lambda),s(\lambda)}^{1},% ...,\hat{Z}_{m(\lambda),s(\lambda)}^{\ell(\lambda)})]$		(20)
	$\displaystyle\quad+\Pr_{v\leftarrow\{0,1\}^{m(\lambda)}}[1\leftarrow\mathcal{A% }(1^{\lambda},\hat{V}_{x,v}^{1},...,\hat{V}_{x,v}^{\ell(\lambda)})]-\Pr_{v% \leftarrow\{0,1\}^{m(\lambda)}}[1\leftarrow\mathcal{A}(1^{\lambda},\hat{P}_{v,% s(\lambda)}^{1},...,\hat{P}_{v,s(\lambda)}^{\ell(\lambda)})]$		(21)
	$\displaystyle=\Pr_{v\leftarrow\{0,1\}^{m(\lambda)}}[1\leftarrow\mathcal{A}(1^{% \lambda},\hat{P}_{v,s(\lambda)}^{1},...,\hat{P}_{v,s(\lambda)}^{\ell(\lambda)}% )]-\Pr[1\leftarrow\mathcal{A}(1^{\lambda},\hat{Z}_{m(\lambda),s(\lambda)}^{1},% ...,\hat{Z}_{m(\lambda),s(\lambda)}^{\ell(\lambda)})]$		(22)
	$\displaystyle\quad+\Pr_{v\leftarrow\{0,1\}^{m(\lambda)}}[1\leftarrow\mathcal{A% }(1^{\lambda},\hat{V}_{x,v}^{1},...,\hat{V}_{x,v}^{\ell(\lambda)})]-\Pr_{v% \leftarrow\{0,1\}^{m(\lambda)}}[1\leftarrow\mathcal{A}(1^{\lambda},\hat{P}_{w% \oplus v,s(\lambda)}^{1},...,\hat{P}_{w\oplus v,s(\lambda)}^{\ell(\lambda)})]$		(23)
	$\displaystyle\geq\frac{1}{p(\lambda)}-\frac{1}{2p(\lambda)}\quad(\text{By % \lx@cref{creftypeplural~refnum}{eq:assump_main} and\nobreakspace\lx@cref{% refnum}{eq:ind_V_P}.})$		(24)
	$\displaystyle=\frac{1}{2p(\lambda)},$		(25)

where $\hat{V}_{x,v}^{i}\leftarrow\mathsf{Obf}(1^{\lambda},V_{\lambda}[x,v])$ , $\hat{P}_{k,s(\lambda)}^{i}\leftarrow\mathsf{Obf}(1^{\lambda},P_{k,s(\lambda)})$ , and $\hat{Z}_{m(\lambda),s(\lambda)}^{i}\leftarrow\mathsf{Obf}(1^{\lambda},Z_{m(% \lambda),s(\lambda)})$ for each $i\in[\ell(\lambda)]$ . Let us consider the following QPT algorithm $\mathcal{E}$ :

1.

Take $(1^{\lambda},\hat{C}^{1},...,\hat{C}^{\ell(\lambda)},V_{\lambda}[x,v],Z_{m(% \lambda),s(\lambda)})$ as input, where $\hat{C}^{i}\in\{\hat{V}_{x,v}^{i},\hat{Z}^{i}_{m(\lambda),s(\lambda)}\}$ for all $i\in[\ell(\lambda)]$ .
2.

Run $b\leftarrow\mathcal{A}(1^{\lambda},\hat{C}^{1},...,\hat{C}^{\ell(\lambda)})$ .
3.

Output $b$ .

By Equation 25, there exist infinitely many $\lambda\in\mathbb{N}$ such that for all $x\in\Pi_{yes}\cap\{0,1\}^{\lambda}$ ,

	$\displaystyle\underset{v\leftarrow\{0,1\}^{m(\lambda)}}{\mathbb{E}}\Bigg[\Pr[1% \leftarrow\mathcal{E}(1^{\lambda},\hat{V}_{x,v}^{1},...,\hat{V}_{x,v}^{\ell(% \lambda)},V_{\lambda}[x,v],Z_{m(\lambda),s(\lambda)})]$		(26)
	$\displaystyle\qquad-\Pr[1\leftarrow\mathcal{E}(1^{\lambda},\hat{Z}_{m(\lambda)% ,s(\lambda)}^{1},...,\hat{Z}_{m(\lambda),s(\lambda)}^{\ell(\lambda)},V_{% \lambda}[x,v],Z_{m(\lambda),s(\lambda)})]\Bigg]$		(27)
	$\displaystyle=\Pr_{v\leftarrow\{0,1\}^{m(\lambda)}}[1\leftarrow\mathcal{A}(1^{% \lambda},\hat{V}_{x,v}^{1},...,\hat{V}_{x,v}^{\ell(\lambda)})]-\Pr[1\leftarrow% \mathcal{A}(1^{\lambda},\hat{Z}_{m(\lambda),s(\lambda)}^{1},...,\hat{Z}_{m(% \lambda),s(\lambda)}^{\ell(\lambda)})]$		(28)
	$\displaystyle\geq\frac{1}{2p(\lambda)}.$		(29)

For each $\lambda\in\mathbb{N}$ and each $x\in\{0,1\}^{\lambda}$ , define a set

	$\displaystyle\mathsf{Good}_{\lambda,x}:=$		(30)
	$\displaystyle\Bigg\{v\in\{0,1\}^{m(\lambda)}:\begin{aligned} &\Pr[1\leftarrow% \mathcal{E}(1^{\lambda},\hat{V}_{x,v}^{1},...,\hat{V}_{x,v}^{\ell(\lambda)},V_% {\lambda}[x,v],Z_{m(\lambda),s(\lambda)})]\\ &-\Pr[1\leftarrow\mathcal{E}(1^{\lambda},\hat{Z}_{m(\lambda),s(\lambda)}^{1},.% ..,\hat{Z}_{m(\lambda),s(\lambda)}^{\ell(\lambda)},V_{\lambda}[x,v],Z_{m(% \lambda),s(\lambda)})]\geq\frac{1}{4p(\lambda)}\end{aligned}\Bigg\}.$		(31)

By Equation 29,

\displaystyle\frac{1}{2p(\lambda)}

\displaystyle\leq\Pr_{v\leftarrow\{0,1\}^{m(\lambda)}}[v\in\mathsf{Good}_{% \lambda,x}]+\left(1-\Pr_{v\leftarrow\{0,1\}^{m(\lambda)}}[v\in\mathsf{Good}_{% \lambda,x}]\right)\frac{1}{4p(\lambda)}.

(32)

Thus, for infinitely many $\lambda\in\mathbb{N}$ and for all $x\in\Pi_{yes}\cap\{0,1\}^{\lambda}$ ,

\displaystyle\Pr_{v\leftarrow\{0,1\}^{m(\lambda)}}[v\in\mathsf{Good}_{\lambda,% x}]\geq\frac{1}{4p(\lambda)-1}.

(33)

By Lemma 17, $(\mathsf{Obf},\mathsf{Eval})$ is also a single-point diO for classical circuits. Therefore, there exist a QPT algorithm $\mathsf{Ext}$ and a polynomial $q$ such that the following holds: There exist infinitely many $\lambda\in\mathbb{N}$ such that for all $x\in\Pi_{yes}\cap\{0,1\}^{\lambda}$ and all $v\in\mathsf{Good}_{\lambda,x}$ ,

\displaystyle\Pr\left[V_{\lambda}[x,v](z)\neq Z_{m(\lambda),s(\lambda)}(z):% \begin{matrix}z\leftarrow\mathsf{Ext}(1^{\lambda},V_{\lambda}[x,v],Z_{m(% \lambda),s(\lambda)})\end{matrix}\right]\geq\frac{1}{q(\lambda)}.

(34)

By using such $\mathsf{Ext}$ , we construct a QPT algorithm $\mathcal{B}$ as follows:

$\blacksquare$

Take $x\in\{0,1\}^{*}$ as input. Set $\lambda\coloneqq|x|$ .
$\blacksquare$

Compute $m(\lambda)$ . Here $m(\lambda)$ is the classical-polynomial-time-computable polynomial that corresponds to the witness length for $x$ .
$\blacksquare$

Sample $v\leftarrow\{0,1\}^{m(\lambda)}$ .
$\blacksquare$

Compute $s(\lambda)$ . Here $s(\lambda)$ is the classical-polynomial-time-computable polynomial that corresponds to the size of $V_{\lambda}[x,v]$ .
$\blacksquare$

Run $z\leftarrow\mathsf{Ext}(1^{\lambda},V_{\lambda}[x,v],Z_{m(\lambda),s(\lambda)})$ .
$\blacksquare$

Output $z\oplus v$ .

Then, for infinitely many $\lambda\in\mathbb{N}$ ,

	$\displaystyle\Pr[M(x,w)=1:w\leftarrow\mathcal{B}(x)]$		(35)
	$\displaystyle\geq\Pr\left[v\in\mathsf{Good}_{\lambda,x}\land V_{\lambda}[x,v](% z)\neq Z_{m(\lambda),s(\lambda)}(z):\begin{matrix}v\leftarrow\{0,1\}^{m(% \lambda)};\\ z\leftarrow\mathsf{Ext}(1^{\lambda},V_{\lambda}[x,v],Z_{m(\lambda),s(\lambda)}% )\end{matrix}\right]$		(36)
	$\displaystyle\geq\frac{1}{q(\lambda)(4p(\lambda)-1)},$		(37)

holds for all $x\in\Pi_{yes}\cap\{0,1\}^{\lambda}$ . We have the QPT algorithm $\mathcal{B}$ and a polynomial $r(\lambda):=q(\lambda)(4p(\lambda)-1)$ that satisfy Equation 16, and therefore we complete the proof. $\hfill\blacktriangleleft$

5 Cryptographic Implications

In this section, we use Theorem 18 to demonstrate cryptographic implications of various quantum iO variants (as defined in Definition 13), when combined with the worst-case hardness of $\mathsf{NP}$ .

5.1 Q-Obf, Q-Eval, and Q-Encoding

Here, we study implications of $(\mathtt{Q},\mathtt{Q},\mathtt{Q})$ -iO, where both $\mathsf{Obf}$ and $\mathsf{Eval}$ are quantum algorithms and an obfuscated encoding $\hat{C}$ is a quantum state. We prove the following theorem:

Theorem 19.

Suppose $\mathsf{NP}\nsubseteq\mathsf{i.o.BQP}$ and there exists $(\mathtt{Q},\mathtt{Q},\mathtt{Q})$ -iO for classical circuits. Then there exists an IND-CPA secure QSKE scheme.

Proof of Theorem 19.

By Theorem 18, there exist classical-polynomial-time-computable polynomials $m$ and $s$ such that for any polynomial $\ell$ , the following two distributions over quantum states are computationally indistinguishable:

$\blacksquare$

$\mathcal{D}_{0}(\lambda)$ : Sample $k\leftarrow\{0,1\}^{m(\lambda)}$ , run $\hat{P}_{k,s(\lambda)}^{i}\leftarrow\mathsf{Obf}(1^{\lambda},P_{k,s(\lambda)})$ for $i\in[\ell(\lambda)]$ , and output $(1^{\lambda},\hat{P}_{k,s(\lambda)}^{1},...,\hat{P}_{k,s(\lambda)}^{\ell(% \lambda)})$ .
$\blacksquare$

$\mathcal{D}_{1}(\lambda)$ : Run $\hat{Z}_{m(\lambda),s(\lambda)}^{i}\leftarrow\mathsf{Obf}(1^{\lambda},Z_{m(% \lambda),s(\lambda)})$ for $i\in[\ell(\lambda)]$ and output $(1^{\lambda},\hat{Z}_{m(\lambda),s(\lambda)}^{1},...,$ $\hat{Z}_{m(\lambda),s(\lambda)}^{\ell(\lambda)})$ .

Without loss of generality, it suffices to construct an IND-CPA secure QSKE scheme $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ for single-bit message. We construct $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ as follows:

$\blacksquare$

$\mathsf{Gen}(1^{\lambda})\to\mathsf{sk}$ : Take the security parameter $1^{\lambda}$ as input, compute $m(\lambda)$ , and sample $k\leftarrow\{0,1\}^{m(\lambda)}$ . Output $\mathsf{sk}:=k$ .
$\blacksquare$

$\mathsf{Enc}(\mathsf{sk},b)\to\mathsf{ct}$ : Take the secret key $\mathsf{sk}$ and a message $b\in\{0,1\}$ as input. Let $C_{0}:=Z_{m(\lambda),s(\lambda)}$ and $C_{1}:=P_{\mathsf{sk},s(\lambda)}$ . Sample $\hat{C}_{b}\leftarrow\mathsf{Obf}(1^{\lambda},C_{b})$ and output $\mathsf{ct}:=\hat{C}_{b}$ .
$\blacksquare$

$\mathsf{Dec}(\mathsf{sk},\mathsf{ct})\to b^{\prime}$ : Take $\mathsf{sk}$ and $\mathsf{ct}$ as input. Run $b^{\prime}\leftarrow\mathsf{Eval}(\mathsf{ct},\mathsf{sk})$ and output $b^{\prime}$ .

The correctness of $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ follows from the correctness of iO: For all $b\in\{0,1\}$ ,

$\displaystyle\Pr\left[b^{\prime}=b:\begin{matrix}\mathsf{sk}\leftarrow\mathsf{% Gen}(1^{\lambda});\\ \mathsf{ct}\leftarrow\mathsf{Enc}(\mathsf{sk},b);\\ b^{\prime}\leftarrow\mathsf{Dec}(\mathsf{sk},\mathsf{ct})\end{matrix}\right]$	$\displaystyle=\Pr\left[b^{\prime}=b:\begin{matrix}k\leftarrow\{0,1\}^{m(% \lambda)};\\ \hat{C}_{b}\leftarrow\mathsf{Obf}(1^{\lambda},C_{b});\\ b^{\prime}\leftarrow\mathsf{Eval}(\hat{C}_{b},k)\end{matrix}\right]$	(38)
	$\displaystyle=\Pr\left[\mathsf{Eval}(\hat{C}_{b},k)=C_{b}(k):\begin{matrix}k% \leftarrow\{0,1\}^{m(\lambda)};\\ \hat{C}_{b}\leftarrow\mathsf{Obf}(1^{\lambda},C_{b})\end{matrix}\right]$	(39)
	$\displaystyle\geq 1-{\mathsf{negl}}(\lambda).$	(40)

We show the IND-CPA security of $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ . In the IND-CPA security game of $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ , it suffices to consider any QPT adversary that makes polynomially many queries only on message 1 to the encryption oracle because the ciphertext for message 0 can be computed without the secret key by simply running $\mathsf{Obf}(1^{\lambda},Z_{m(\lambda),s(\lambda)})$ . Thus, our goal is to show that for any polynomial $t$ , the following two distributions are computationally indistinguishable:

$\blacksquare$

$\mathcal{D}_{0}^{\prime}(\lambda)$ : Sample $\mathsf{sk}\leftarrow\mathsf{Gen}(1^{\lambda})$ , run $\mathsf{ct}_{1}^{i}\leftarrow\mathsf{Enc}(\mathsf{sk},1)$ for $i\in[t(\lambda)]$ and $\mathsf{ct}^{*}_{1}\leftarrow\mathsf{Enc}(\mathsf{sk},1)$ , and output $(\mathsf{ct}_{1}^{1},...,\mathsf{ct}_{1}^{t(\lambda)},\mathsf{ct}^{*}_{1})$ .
$\blacksquare$

$\mathcal{D}_{1}^{\prime}(\lambda)$ : Sample $\mathsf{sk}\leftarrow\mathsf{Gen}(1^{\lambda})$ run $\mathsf{ct}_{1}^{i}\leftarrow\mathsf{Enc}(\mathsf{sk},1)$ for $i\in[t(\lambda)]$ and $\mathsf{ct}^{*}_{0}\leftarrow\mathsf{Enc}(\mathsf{sk},0)$ , and output $(\mathsf{ct}_{1}^{1},...,\mathsf{ct}_{1}^{t(\lambda)},\mathsf{ct}^{*}_{0})$ .

When $\ell(\lambda)=t(\lambda)+1$ , the distribution $\mathcal{D}^{\prime}_{0}(\lambda)$ is identical to the distribution $\mathcal{D}_{0}(\lambda)$ . Thus, for any polynomial $t$ and for any QPT adversary $\mathcal{A}$ ,

	$\displaystyle\left\|\Pr[1\leftarrow\mathcal{A}(1^{\lambda},\mathcal{D}^{\prime}% _{0}(\lambda))]-\Pr[1\leftarrow\mathcal{A}(1^{\lambda},\mathcal{D}^{\prime}_{1% }(\lambda))]\right\|$		(41)
	$\displaystyle=\left\|\Pr[1\leftarrow\mathcal{A}(1^{\lambda},\mathcal{D}_{0}(% \lambda))]-\Pr[1\leftarrow\mathcal{A}(1^{\lambda},\mathcal{D}^{\prime}_{1}(% \lambda))]\right\|$		(42)
	$\displaystyle\leq\left\|\Pr[1\leftarrow\mathcal{A}(1^{\lambda},\mathcal{D}_{0}(% \lambda))]-\Pr[1\leftarrow\mathcal{A}(1^{\lambda},\mathcal{D}_{1}(\lambda))]\right\|$		(43)
	$\displaystyle\quad+\left\|\Pr[1\leftarrow\mathcal{A}(1^{\lambda},\mathcal{D}_{1% }(\lambda))]-\Pr[1\leftarrow\mathcal{A}(1^{\lambda},\mathcal{D}^{\prime}_{1}(% \lambda))]\right\|$		(44)
	$\displaystyle\leq{\mathsf{negl}}(\lambda)+\left\|\Pr[1\leftarrow\mathcal{A}(1^{% \lambda},\mathcal{D}_{1}(\lambda))]-\Pr[1\leftarrow\mathcal{A}(1^{\lambda},% \mathcal{D}^{\prime}_{1}(\lambda))]\right\|.\quad(\text{By \lx@cref{% creftype~refnum}{thm:main}.})$		(45)

To show the computational indistinguishability between $\mathcal{D}_{0}^{\prime}(\lambda)$ and $\mathcal{D}^{\prime}_{1}(\lambda)$ , it suffices to show that $\mathcal{D}_{1}(\lambda)$ and $\mathcal{D}^{\prime}_{1}(\lambda)$ are computationally indistinguishable. For the sake of contradiction, assume that there exist polynomials $t$ and $p$ and a QPT algorithm $\mathcal{A}$ such that

$\displaystyle\frac{1}{p(\lambda)}$	$\displaystyle\leq\left\|\Pr[1\leftarrow\mathcal{A}(1^{\lambda},\mathcal{D}_{1}(% \lambda))]-\Pr[1\leftarrow\mathcal{A}(1^{\lambda},\mathcal{D}^{\prime}_{1}(% \lambda))]\right\|$	(46)
	$\displaystyle=\Bigg\|\Pr[1\leftarrow\mathcal{A}(1^{\lambda},\hat{Z}^{1}_{m(% \lambda),s(\lambda)},...,\hat{Z}^{t(\lambda)}_{m(\lambda),s(\lambda)},\hat{Z}^% {t(\lambda)+1}_{m(\lambda),s(\lambda)})]$	(47)
	$\displaystyle\qquad-\Pr_{k\leftarrow\{0,1\}^{m(\lambda)}}[1\leftarrow\mathcal{% A}(1^{\lambda},\hat{P}^{1}_{k,s(\lambda)},...,\hat{P}^{t(\lambda)}_{k,s(% \lambda)},\hat{Z}^{t(\lambda)+1}_{m(\lambda),s(\lambda)})]\Bigg\|$	(48)

for infinitely many $\lambda\in\mathbb{N}$ , where $\hat{Z}^{i}_{m(\lambda),s(\lambda)}\leftarrow\mathsf{Obf}(1^{\lambda},Z_{m(% \lambda),s(\lambda)})$ and $\hat{P}^{i}_{k,s(\lambda)}\leftarrow\mathsf{Obf}(1^{\lambda},P_{k,s(\lambda)})$ for $i\in[t(\lambda)+1]$ . Let us consider a QPT algorithm $\mathcal{B}$ that on input $(1^{\lambda},\hat{C}_{b}^{1},...,\hat{C}_{b}^{t(\lambda)})$ , runs $\hat{Z}_{m(\lambda),s(\lambda)}\leftarrow\mathsf{Obf}(1^{\lambda},Z_{m(\lambda% ),s(\lambda)})$ and $b^{\prime}\leftarrow\mathcal{A}(1^{\lambda},\hat{C}_{b}^{1},...,\hat{C}_{b}^{t% (\lambda)},\hat{Z}_{m(\lambda),s(\lambda)})$ , and outputs $b^{\prime}$ . Then,

	$\displaystyle\Bigg\|\Pr[1\leftarrow\mathcal{B}(1^{\lambda},\hat{Z}_{m(\lambda),% s(\lambda)}^{1},...,\hat{Z}_{m(\lambda),s(\lambda)}^{t(\lambda)})]-\Pr_{k% \leftarrow\{0,1\}^{m(\lambda)}}[1\leftarrow\mathcal{B}(1^{\lambda},\hat{P}^{1}% _{k,s(\lambda)},...,\hat{P}^{t(\lambda)}_{k,s(\lambda)})]\Bigg\|$		(49)
	$\displaystyle=\Bigg\|\Pr[1\leftarrow\mathcal{A}(1^{\lambda},\hat{Z}^{1}_{m(% \lambda),s(\lambda)},...,\hat{Z}^{t(\lambda)}_{m(\lambda),s(\lambda)},\hat{Z}^% {t(\lambda)+1}_{m(\lambda),s(\lambda)})]$		(50)
	$\displaystyle\qquad-\Pr_{k\leftarrow\{0,1\}^{m(\lambda)}}[1\leftarrow\mathcal{% A}(1^{\lambda},\hat{P}^{1}_{k,s(\lambda)},...,\hat{P}^{t(\lambda)}_{k,s(% \lambda)},\hat{Z}^{t(\lambda)+1}_{m(\lambda),s(\lambda)})]\Bigg\|$		(51)
	$\displaystyle\geq\frac{1}{p(\lambda)}$		(52)

for infinitely many $\lambda\in\mathbb{N}$ . This contradicts Theorem 18 and therefore the distributions $\mathcal{D}^{\prime}_{1}(\lambda)$ and $\mathcal{D}_{1}(\lambda)$ are computationally indistinguishable. Hence we complete the proof of IND-CPA security. $\hfill\blacktriangleleft$

Since IND-CPA secure QSKE implies OWSGs and EFI pairs [50, 37, 9], we have the following corollary.

Corollary 20.

Suppose $\mathsf{NP}\nsubseteq\mathsf{i.o.BQP}$ and there exists $(\mathtt{Q},\mathtt{Q},\mathtt{Q})$ -iO for classical circuits. Then there exist OWSGs and EFI pairs.

5.2 Q-Obf, Q-Eval, and C-Encoding

Here, we study implications of $(\mathtt{Q},\mathtt{Q},\mathtt{C})$ -iO, where both $\mathsf{Obf}$ and $\mathsf{Eval}$ are quantum algorithms, but an obfuscated encoding $\hat{C}$ is classical. This can be regarded as an iO in the QCCC model. We prove the following theorem:

Theorem 21.

Suppose $\mathsf{NP}\nsubseteq\mathsf{i.o.BQP}$ and there exists $(\mathtt{Q},\mathtt{Q},\mathtt{C})$ -iO for classical circuits. Then there exists an IND-CPA secure QCCC SKE scheme.

Proof of Theorem 21.

The proof of this theorem is quite similar to Theorem 19. The only difference is that the output of $\mathsf{Obf}$ is a classical string rather than a quantum state. The proof of Theorem 19 heavily relies on Theorem 18 that is also valid for $(\mathtt{Q},\mathtt{Q},\mathtt{C})$ -iO. Thus, we can easily extend the proof of Theorem 19 to the $(\mathtt{Q},\mathtt{Q},\mathtt{C})$ -iO. $\hfill\blacktriangleleft$

IND-CPA secure QCCC SKE implies IND-CPA secure QSKE and EV-OWPuzz. Since IND-CPA secure QSKE implies OWSGs [50] and EV-OWPuzz implies OWPuzz, QEFID pairs, and EFI pairs [37, 20], we have the following corollary.

Corollary 22.

Suppose $\mathsf{NP}\nsubseteq\mathsf{i.o.BQP}$ and there exists $(\mathtt{Q},\mathtt{Q},\mathtt{C})$ -iO for classical circuits. Then there exist EV-OWPuzz, OWPuzz, OWSGs, QEFID pairs, and EFI pairs.

5.3 Q-Obf, C-Eval, and C-Encoding

Here, we study implications of $(\mathtt{Q},\mathtt{C},\mathtt{C})$ -iO, where $\mathsf{Obf}$ is a quantum algorithm, $\mathsf{Eval}$ is a classical algorithm, and an obfuscated encoding $\hat{C}$ is classical. We prove the following theorem:

Theorem 23.

Suppose $\mathsf{NP}\nsubseteq\mathsf{i.o.BQP}$ and there exists $(\mathtt{Q},\mathtt{C},\mathtt{C})$ -iO for classical circuits. Then there exists an IND-CPA secure QCCC PKE scheme.

To prove this theorem, we first show that $(\mathtt{Q},\mathtt{C},\mathtt{C})$ -iO can be modified to satisfy a stronger notion of correctness that holds even for fixed randomness.

Lemma 24.

Suppose that there exists $(\mathtt{Q},\mathtt{C},\mathtt{C})$ -iO for classical circuits. Then there exists $(\mathtt{Q},\mathtt{C},\mathtt{C})$ -iO for classical circuits that satisfies the fixed randomness correctness, defined below:

$\blacksquare$

Fixed randomness correctness: For any family $\{C_{\lambda}\}_{\lambda\in\mathbb{N}}$ of polynomial-size classical circuits of input length $n_{\lambda}$ ,

$\displaystyle\Pr_{\begin{subarray}{c}\hat{C}_{\lambda}\leftarrow\mathsf{Obf}(1% ^{\lambda},C_{\lambda})\\ r\leftarrow\mathcal{R}_{\lambda}\end{subarray}}\left[\forall x\in\{0,1\}^{n_{% \lambda}},\mathsf{Eval}(\hat{C}_{\lambda},x;r)=C_{\lambda}(x)\right]\geq 1-{% \mathsf{negl}}(\lambda)$ (53)

where $\mathcal{R}_{\lambda}$ denotes the randomness space of $\mathsf{Eval}(\hat{C}_{\lambda},x)$ , and $\mathsf{Eval}(\hat{C}_{\lambda},x;r)$ denotes the execution with the fixed randomness $r$ .⁹⁹9We assume without loss of generality that the randomness space of $\mathsf{Eval}(\hat{C}_{\lambda},x)$ only depends on $\lambda$ and does not depend on $C_{\lambda}$ and $x$ .

Proof of Lemma 24.

The correctness (as in Definition 9) implies that, for any family $\{C_{\lambda}\}_{\lambda\in\mathbb{N}}$ of polynomial-size classical circuits of input length $n_{\lambda}$ and for any $x\in\{0,1\}^{n_{\lambda}}$ ,

\displaystyle\Pr_{\begin{subarray}{c}\hat{C}_{\lambda}\leftarrow\mathsf{Obf}(1% ^{\lambda},C_{\lambda})\\ r\leftarrow\mathcal{R}_{\lambda}\end{subarray}}\left[\mathsf{Eval}(\hat{C}_{% \lambda},x;r)=C_{\lambda}(x)\right]\geq 1-{\mathsf{negl}}(\lambda)\geq 2/3.

(54)

Thus, if we modify $\mathsf{Obf}$ to run $M=O(\lambda+n_{\lambda})$ times to output $M$ independently generated obfuscated encodings of $C_{\lambda}$ , and $\mathsf{Eval}$ to evaluate each of the $M$ obfuscated encodings and take the majority result, we can ensure that it satisfies¹⁰¹⁰10Due to the modifications to $\mathsf{Eval}$ , $\mathcal{R}_{\lambda}$ is also updated accordingly; it now consists of $M$ -tuples of the randomness used in the original $\mathsf{Eval}$ .

\displaystyle\Pr_{\begin{subarray}{c}\hat{C}_{\lambda}\leftarrow\mathsf{Obf}(1% ^{\lambda},C_{\lambda})\\ r\leftarrow\mathcal{R}_{\lambda}\end{subarray}}\left[\mathsf{Eval}(\hat{C}_{% \lambda},x;r)=C_{\lambda}(x)\right]\geq 1-2^{-(\lambda+n_{\lambda})}.

(55)

By taking the union bound over $x\in\{0,1\}^{n_{\lambda}}$ it implies Equation 53. Moreover, the modification of $\mathsf{Obf}$ and $\mathsf{Eval}$ does not affect the security. Thus, this completes the proof of Lemma 24. $\hfill\blacktriangleleft$ Then we prove Theorem 23.

Proof of Theorem 23.

Let $(\mathsf{Obf},\mathsf{Eval})$ be a $(\mathtt{Q},\mathtt{C},\mathtt{C})$ -iO for classical circuits. By Lemma 24, we can assume that it satisfies fixed randomness correctness without loss of generality. Let $m$ and $s$ be polynomials as in Theorem 18. Then we construct a QCCC PKE scheme $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ as follows:

$\blacksquare$

$\mathsf{Gen}(1^{\lambda})$ : Choose $k\leftarrow\{0,1\}^{m(\lambda)}$ , and compute $\hat{P}_{k,s(\lambda)}\leftarrow\mathsf{Obf}(1^{\lambda},P_{k,s(\lambda)})$ , where we recall that $P_{k,s(\lambda)}$ denotes the canonical circuit of size $s(\lambda)$ for the point function with target $k$ . Output the classical public key $\mathsf{pk}\coloneqq(1^{\lambda},\hat{P}_{k,s(\lambda)})$ and the classical secret key $\mathsf{sk}\coloneqq k$ .
$\blacksquare$

$\mathsf{Enc}(\mathsf{pk}=(1^{\lambda},\hat{P}_{k,s(\lambda)}),\mathsf{msg})$ : Choose $r\leftarrow\mathcal{R}_{\lambda}$ where $\mathcal{R}_{\lambda}$ is the randomness space of $\mathsf{Eval}(\hat{P}_{k,s(\lambda)},k^{\prime})$ for $k^{\prime}\in\{0,1\}^{m(\lambda)}$ . Let $C[\hat{P}_{k,s(\lambda)},\mathsf{msg},r]$ be a classical circuit that takes $k^{\prime}\in\{0,1\}^{m(\lambda)}$ as input and outputs $\mathsf{msg}$ if $\mathsf{Eval}(\hat{P}_{k,s(\lambda)},k^{\prime};r)=1$ and $0$ otherwise. Compute $\hat{C}[\hat{P}_{k,s(\lambda)},\mathsf{msg},r]\leftarrow\mathsf{Obf}(1^{% \lambda},C[\hat{P}_{k,s(\lambda)},\mathsf{msg},r])$ . Output the ciphertext $\mathsf{ct}=\hat{C}[\hat{P}_{k,s(\lambda)},\mathsf{msg},r]$ .
$\blacksquare$

$\mathsf{Dec}(\mathsf{sk}=k,\mathsf{ct}=\hat{C}[\hat{P}_{k,s(\lambda)},\mathsf{% msg},r])$ : Compute $\mathsf{msg}^{\prime}\leftarrow\mathsf{Eval}(\hat{C}[\hat{P}_{k,s(\lambda)},% \mathsf{msg},r],k)$ and output $\mathsf{msg}^{\prime}$ .

By the correctness of $(\mathtt{Q},\mathtt{C},\mathtt{C})$ -iO, the above scheme clearly satisfies the correctness of PKE.

Below, we prove that it satisfies the IND-CPA security. For any QPT adversary $\mathcal{A}$ and $b\in\{0,1\}$ , we consider the following hybrid experiments:

$H_{1,b}$ :

This is the original IND-CPA security experiment. That is, it works as follows:

1.

The challenger generates $\hat{P}_{k,s(\lambda)}\leftarrow\mathsf{Obf}(1^{\lambda},P_{k,s(\lambda)})$ for $k\leftarrow\{0,1\}^{m(\lambda)}$ , and sends $\mathsf{pk}=(1^{\lambda},\hat{P}_{k,s(\lambda)})$ to $\mathcal{A}$ .
2.

$\mathcal{A}$ chooses $\mathsf{msg}_{0},\mathsf{msg}_{1}\in(\{0,1\}^{*})^{2}$ of the same length and sends them to the challenger.
3.

The challenger generates $\hat{C}[\hat{P}_{k,s(\lambda)},\mathsf{msg}_{b},r]\leftarrow\mathsf{Obf}(1^{% \lambda},C[\hat{P}_{k,s(\lambda)},\mathsf{msg}_{b},r])$ for $r\leftarrow\mathcal{R}_{\lambda}$ , and sends $\mathsf{ct}_{b}=\hat{C}[\hat{P}_{k,s(\lambda)},\mathsf{msg}_{b},r]$ to $\mathcal{A}$ .
4.

$\mathcal{A}$ outputs $b^{\prime}$ , which is the output of the experiment.

Our goal is to prove that $|\Pr[H_{1,0}=1]-\Pr[H_{1,1}=1]|\leq{\mathsf{negl}}(\lambda)$ .

$H_{2,b}$ :

This is identical to $H_{1,b}$ except that $\mathsf{pk}$ is set to be $\hat{Z}_{m(\lambda),s(\lambda)}\leftarrow\mathsf{Obf}(1^{\lambda},Z_{m(\lambda% ),s(\lambda)})$ , and consequently $\mathsf{ct}_{b}$ is set to be $\hat{C}[\hat{Z}_{m(\lambda),s(\lambda)},\mathsf{msg}_{b},r]\leftarrow\mathsf{% Obf}(1^{\lambda},C[\hat{Z}_{m(\lambda),s(\lambda)},\mathsf{msg}_{b},r])$ where we recall that $Z_{m(\lambda),s(\lambda)}$ denotes the canonical zero-function on $m(\lambda)$ -bit inputs of size $s(\lambda)$ . By a straightforward reduction to Theorem 18 for the case of $\ell=1$ , we have $|\Pr[H_{1,b}=1]-\Pr[H_{2,b}=1]|\leq{\mathsf{negl}}(\lambda)$ for $b\in\{0,1\}$ .

$H_{3,b}$ :

This is identical to $H_{2,b}$ except that $\mathsf{ct}_{b}$ is set to be $\hat{Z}_{m(\lambda),s^{\prime}(\lambda)}\leftarrow\mathsf{Obf}(1^{\lambda},Z_{% m(\lambda),s^{\prime}(\lambda)})$ , where $s^{\prime}(\lambda)$ is the size of $C[\hat{Z}_{m(\lambda),s(\lambda)},\mathsf{msg}_{b},r]$ . (We assume without loss of generality that the size only depends on $\lambda$ by padding.) By the fixed randomness correctness of the $(\mathtt{Q},\mathtt{C},\mathtt{C})$ -iO, $C[\hat{Z}_{m(\lambda),s(\lambda)},\mathsf{msg}_{b},r]$ is functionally equivalent to $Z_{m(\lambda),s^{\prime}(\lambda)}$ with overwhelming probability over the choice of $r$ . Thus, by a straightforward reduction to the security of $(\mathtt{Q},\mathtt{C},\mathtt{C})$ -iO, we have $|\Pr[H_{2,b}=1]-\Pr[H_{3,b}=1]|\leq{\mathsf{negl}}(\lambda)$ for $b\in\{0,1\}$ .

Moreover, in $H_{3,b}$ , no information of $b$ is given to $\mathcal{A}$ , and thus $\Pr[H_{3,0}=1]=\Pr[H_{3,1}=1]$ .

Combining the above, we obtain $|\Pr[H_{1,0}=1]-\Pr[H_{1,1}=1]|\leq{\mathsf{negl}}(\lambda)$ . This completes the proof of IND-CPA security. $\hfill\blacktriangleleft$ IND-CPA secure QCCC PKE implies IND-CPA secure QSKE and EV-OWPuzz. Since IND-CPA secure QSKE implies OWSGs [50] and EV-OWPuzz implies OWPuzz, QEFID pairs, and EFI pairs [37, 20], we have the following corollary.

Corollary 25.

Suppose $\mathsf{NP}\nsubseteq\mathsf{i.o.BQP}$ and there exists $(\mathtt{Q},\mathtt{C},\mathtt{C})$ -iO for classical circuits. Then there exist EV-OWPuzz, OWPuzz, OWSGs, QEFID pairs, and EFI pairs.

5.4 C-Obf, Q-Eval, and C-Encoding

Here, we study implications of $(\mathtt{C},\mathtt{Q},\mathtt{C})$ -iO, where $\mathsf{Obf}$ is a classical algorithm, $\mathsf{Eval}$ is a quantum algorithms, and an obfuscated encoding $\hat{C}$ is classical. We prove the following theorem:

Theorem 26.

Suppose $\mathsf{NP}\nsubseteq\mathsf{i.o.BQP}$ and there exists $(\mathtt{C},\mathtt{Q},\mathtt{C})$ -iO for classical circuits. Then there exist OWFs and an IND-CPA secure QCCC PKE scheme.

To show Theorem 26, we rely on the following lemma:

Lemma 27 ([29]).

The following two conditions are equivalent:

$\blacksquare$

There exist OWFs.
$\blacksquare$

There exist pairs of classical-polynomial-time-samplable distributions that are statistically far but computationally indistinguishable.

Lemma 28 ([51]).

If there exist $(\mathtt{C},\mathtt{C},\mathtt{C})$ -iO for classical circuits and OWFs, then there exist IND-CPA secure PKE schemes.

In the construction of [51], the encryption algorithm runs $\mathsf{Eval}$ . Thus, by adapting their construction to $(\mathtt{C},\mathtt{Q},\mathtt{C})$ -iO in which only $\mathsf{Eval}$ is quantum algorithm but both of $\mathsf{Obf}$ and the obfuscated encoding are classical, we obtain QCCC PKE scheme in which only the encryption algorithm is quantum.

Corollary 29.

If there exist $(\mathtt{C},\mathtt{Q},\mathtt{C})$ -iO for classical circuits and OWFs, then there exist IND-CPA secure QCCC PKE schemes.

Now we are ready to prove Theorem 26.

Proof of Theorem 26.

By Lemmas 27 and 29, it suffices to construct a pair of classical-polynomial-time-samplable distributions that are statistically far but computationally indistinguishable. By applying Theorem 18 for $\ell=1$ , there exist classical-polynomial-time-computable polynomials $m$ and $s$ such that the following two distributions are computationally indistinguishable:

$\blacksquare$

$\mathcal{D}_{0}(\lambda)$ : Sample $k\leftarrow\{0,1\}^{m(\lambda)}$ , run $\hat{P}_{k,s(\lambda)}\leftarrow\mathsf{Obf}(1^{\lambda},P_{k,s(\lambda)})$ , and output $\hat{P}_{k,s(\lambda)}$ .
$\blacksquare$

$\mathcal{D}_{1}(\lambda)$ : Run $\hat{Z}_{m(\lambda),s(\lambda)}\leftarrow\mathsf{Obf}(1^{\lambda},Z_{m(\lambda% ),s(\lambda)})$ and output $\hat{Z}_{m(\lambda),s(\lambda)}$ .

Moreover both of $\mathcal{D}_{0}(\lambda)$ and $\mathcal{D}_{1}(\lambda)$ are classical-polynomial-time-samplable because $m$ and $s$ are classical-polynomial-time-computable and $\mathsf{Obf}$ is a PPT algorithm. Thus, to complete the proof, we show that $\mathcal{D}_{0}(\lambda)$ and $\mathcal{D}_{1}(\lambda)$ are statistically far. To show this, we construct an unbounded-time distinguisher $\mathcal{A}$ that distinguishes $\mathcal{D}_{0}(\lambda)$ and $\mathcal{D}_{1}(\lambda)$ .

$\mathcal{A}(\hat{C})$ :: Upon receiving an obfuscated encoding $\hat{C}$ , it computes $p_{k^{\prime}}:=\Pr[\mathsf{Eval}(\hat{C},k^{\prime})=1]$ for all $k^{\prime}\in\{0,1\}^{m(\lambda)}$ . If there is $k^{\prime}\in\{0,1\}^{m(\lambda)}$ such that $p_{k^{\prime}}\geq 1/2$ , it outputs $0$ , otherwise it outputs $1$ .

If $\hat{C}=\hat{P}_{k,s(\lambda)}\leftarrow\mathcal{D}_{0}(\lambda)$ , the correctness of the iO implies that $\Pr[p_{k}\geq 1-{\mathsf{negl}}(\lambda)]\geq 1-{\mathsf{negl}}(\lambda)$ where the probability is taken over the randomness in the sampling procedure of $\mathcal{D}_{0}$ . Thus, we have $\Pr[\mathcal{A}(\hat{C})=0]\geq 1-{\mathsf{negl}}(\lambda)$ . On the other hand, if $\hat{C}=\hat{Z}_{m(\lambda),s(\lambda)}\leftarrow\mathcal{D}_{1}(\lambda)$ , the correctness of the iO implies that $\Pr[\forall k^{\prime}\in\{0,1\}^{m(\lambda)},p_{k^{\prime}}\leq{\mathsf{negl}% }(\lambda)]\geq 1-{\mathsf{negl}}(\lambda)$ where the probability is taken over the randomness in the sampling procedure of $\mathcal{D}_{1}$ . Thus, we have $\Pr[\mathcal{A}(\hat{C})=1]\geq 1-{\mathsf{negl}}(\lambda)$ . Therefore, $\mathcal{D}_{0}(\lambda)$ and $\mathcal{D}_{1}(\lambda)$ are statistically far and we complete the proof. $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 30.

One might think that Theorem 26 directly follows from an adaptation of the technique of [38] since we can derandomize $\mathsf{Obf}$ when it is classical. In fact, this is true in the perfectly correct case. On the other hand, this does not work in the imperfect case (as in Definition 9) since their proof in the imperfect setting involves obfuscation of an obfuscated circuit, but this is not possible in our setting since $\mathsf{Eval}$ is a quantum algorithm and thus cannot be obfuscated by iO for classical circuits as is considered in this paper.

Note that $\mathsf{NP}\nsubseteq\mathsf{i.o.BQP}$ and the existence of $(\mathtt{C},\mathtt{Q},\mathtt{C})$ -iO for classical circuits imply all Microcrypt primitives since they imply the existence of OWFs (and therefore PRUs [46]).

5.5 C-Obf, C-Eval, and C-Encoding

Here, we study implications of $(\mathtt{C},\mathtt{C},\mathtt{C})$ -iO, where both $\mathsf{Obf}$ and $\mathsf{Eval}$ are classical algorithms and an obfuscated encoding $\hat{C}$ is classical. This is oftend referred to as post-quantum iO. We prove the following theorem:

Theorem 31.

Suppose $\mathsf{NP}\nsubseteq\mathsf{i.o.BQP}$ and there exists $(\mathtt{C},\mathtt{C},\mathtt{C})$ -iO for classical circuits. Then there exist OWFs and an IND-CPA secure PKE scheme.

Proof of Theorem 31.

This proof is essentially same as the proof of Theorem 26. By Lemmas 27 and 28, it suffices to construct a pair of classical-polynomial-time-samplable distributions that are statistically far but computationally indistinguishable. By applying Theorem 18 for $\ell=1$ , there exist classical-polynomial-time-computable polynomials $m$ and $s$ such that the distributions over $\mathsf{Obf}(1^{\lambda},P_{k,s(\lambda)})$ and $\mathsf{Obf}(1^{\lambda},Z_{m(\lambda),s(\lambda)})$ are computationally indistinguishable, where $k\leftarrow\{0,1\}^{m(\lambda)}$ . We can show that they are classical-polynomial-time-samplable and statistically far by adapting the same argument used in the proof of Theorem 26. $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 32.

We could also prove Theorem 31 by a straightforward adaptation of [38]. On the other hand, an advantage of our approach is that it in fact only needs iO for 3CNF formulas rather than general classical circuits. Constructing OWFs from imperfect iO for 3CNF formulas was an open problem left by [38], and our alternative proof resolves this open problem, though the open problem itself was also recently resolved (in a stronger form) in [31, 44] by completely different techniques.

Note that $\mathsf{NP}\nsubseteq\mathsf{i.o.BQP}$ and the existence of $(\mathtt{C},\mathtt{C},\mathtt{C})$ -iO for classical circuits imply all Microcrypt primitives since they imply the existence of OWFs.

References

[1] Gorjan Alagic, Zvika Brakerski, Yfke Dulek, and Christian Schaffner. Impossibility of quantum virtual black-box obfuscation of classical circuits. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part I, volume 12825 of LNCS, pages 497–525, Virtual Event, August 2021. Springer, Cham. doi:10.1007/978-3-030-84242-0_18.
[2] Gorjan Alagic and Bill Fefferman. On quantum obfuscation, 2016. arXiv:1602.01771.
[3] Prabhanjan Ananth, Dan Boneh, Sanjam Garg, Amit Sahai, and Mark Zhandry. Differing-inputs obfuscation and applications. Cryptology ePrint Archive, Report 2013/689, 2013. URL: https://eprint.iacr.org/2013/689.
[4] Saikrishna Badrinarayanan, Eric Miles, Amit Sahai, and Mark Zhandry. Post-zeroizing obfuscation: New mathematical tools, and the case of evasive circuits. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, pages 764–791. Springer, Berlin, Heidelberg, May 2016. doi:10.1007/978-3-662-49896-5_27.
[5] Boaz Barak, Sanjam Garg, Yael Tauman Kalai, Omer Paneth, and Amit Sahai. Protecting obfuscation against algebraic attacks. In Phong Q. Nguyen and Elisabeth Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, pages 221–238. Springer, Berlin, Heidelberg, May 2014. doi:10.1007/978-3-642-55220-5_13.
[6] Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. Journal of the ACM, 59(2):6:1–6:48, 2012. doi:10.1145/2160158.2160159.
[7] James Bartusek, Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa. Obfuscation of pseudo-deterministic quantum circuits. In Barna Saha and Rocco A. Servedio, editors, 55th ACM STOC, pages 1567–1578. ACM Press, June 2023. doi:10.1145/3564246.3585179.
[8] James Bartusek and Giulio Malavolta. Indistinguishability obfuscation of null quantum circuits and applications. In Mark Braverman, editor, ITCS 2022, volume 215, pages 15:1–15:13. LIPIcs, January / February 2022. doi:10.4230/LIPIcs.ITCS.2022.15.
[9] Rishabh Batra and Rahul Jain. Commitments are equivalent to statistically-verifiable one-way state generators. In 65th FOCS, pages 1178–1192. IEEE Computer Society Press, October 2024. doi:10.1109/FOCS61266.2024.00077.
[10] Dan Boneh and Mark Zhandry. Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation. In Juan A. Garay and Rosario Gennaro, editors, CRYPTO 2014, Part I, volume 8616 of LNCS, pages 480–499. Springer, Berlin, Heidelberg, August 2014. doi:10.1007/978-3-662-44371-2_27.
[11] Elette Boyle, Kai-Min Chung, and Rafael Pass. On extractability obfuscation. In Yehuda Lindell, editor, TCC 2014, volume 8349 of LNCS, pages 52–73. Springer, Berlin, Heidelberg, February 2014. doi:10.1007/978-3-642-54242-8_3.
[12] Zvika Brakerski, Ran Canetti, and Luowen Qian. On the computational hardness needed for quantum cryptography. ITCS 2023, 2023.
[13] Zvika Brakerski, Nico Döttling, Sanjam Garg, and Giulio Malavolta. Candidate iO from homomorphic encryption schemes. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part I, volume 12105 of LNCS, pages 79–109. Springer, Cham, May 2020. doi:10.1007/978-3-030-45721-1_4.
[14] Zvika Brakerski and Guy N. Rothblum. Virtual black-box obfuscation for all circuits via generic graded encoding. In Yehuda Lindell, editor, TCC 2014, volume 8349 of LNCS, pages 1–25. Springer, Berlin, Heidelberg, February 2014. doi:10.1007/978-3-642-54242-8_1.
[15] Anne Broadbent and Raza Ali Kazmi. Constructions for quantum indistinguishability obfuscation. In Patrick Longa and Carla Ràfols, editors, Progress in Cryptology - LATINCRYPT 2021 - 7th International Conference on Cryptology and Information Security in Latin America, Bogotá, Colombia, October 6-8, 2021, Proceedings, volume 12912 of Lecture Notes in Computer Science, pages 24–43. Springer, 2021. doi:10.1007/978-3-030-88238-9_2.
[16] Yilei Chen, Craig Gentry, and Shai Halevi. Cryptanalyses of candidate branching program obfuscators. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, EUROCRYPT 2017, Part III, volume 10212 of LNCS, pages 278–307. Springer, Cham, April / May 2017. doi:10.1007/978-3-319-56617-7_10.
[17] Jung Hee Cheon, Wonhee Cho, Minki Hhan, Jiseung Kim, and Changmin Lee. Statistical zeroizing attack: Cryptanalysis of candidates of BP obfuscation over GGH15 multilinear map. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part III, volume 11694 of LNCS, pages 253–283. Springer, Cham, August 2019. doi:10.1007/978-3-030-26954-8_9.
[18] Jung Hee Cheon, Kyoohyung Han, Changmin Lee, Hansol Ryu, and Damien Stehlé. Cryptanalysis of the multilinear map over the integers. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part I, volume 9056 of LNCS, pages 3–12. Springer, Berlin, Heidelberg, April 2015. doi:10.1007/978-3-662-46800-5_1.
[19] Jung Hee Cheon, Minki Hhan, Jiseung Kim, and Changmin Lee. Cryptanalyses of branching program obfuscations over GGH13 multilinear map from the NTRU problem. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, pages 184–210. Springer, Cham, August 2018. doi:10.1007/978-3-319-96878-0_7.
[20] Kai-Min Chung, Eli Goldin, and Matthew Gray. On central primitives for quantum cryptography with classical communication. In Leonid Reyzin and Douglas Stebila, editors, CRYPTO 2024, Part VII, volume 14926 of LNCS, pages 215–248. Springer, Cham, August 2024. doi:10.1007/978-3-031-68394-7_8.
[21] Kai-Min Chung, Huijia Lin, and Rafael Pass. Constant-round concurrent zero-knowledge from indistinguishability obfuscation. In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part I, volume 9215 of LNCS, pages 287–307. Springer, Berlin, Heidelberg, August 2015. doi:10.1007/978-3-662-47989-6_14.
[22] Aloni Cohen, Justin Holmgren, Ryo Nishimaki, Vinod Vaikuntanathan, and Daniel Wichs. Watermarking cryptographic capabilities. In Daniel Wichs and Yishay Mansour, editors, 48th ACM STOC, pages 1115–1127. ACM Press, June 2016. doi:10.1145/2897518.2897651.
[23] Andrea Coladangelo and Sam Gunn. How to use quantum indistinguishability obfuscation. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, 56th ACM STOC, pages 1003–1008. ACM Press, June 2024. doi:10.1145/3618260.3649779.
[24] Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi. Practical multilinear maps over the integers. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part I, volume 8042 of LNCS, pages 476–493. Springer, Berlin, Heidelberg, August 2013. doi:10.1007/978-3-642-40041-4_26.
[25] Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi. New multilinear maps over the integers. In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part I, volume 9215 of LNCS, pages 267–286. Springer, Berlin, Heidelberg, August 2015. doi:10.1007/978-3-662-47989-6_13.
[26] Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. SIAM J. Comput., 45(3):882–929, 2016. doi:10.1137/14095772X.
[27] Sanjam Garg, Eric Miles, Pratyay Mukherjee, Amit Sahai, Akshayaram Srinivasan, and Mark Zhandry. Secure obfuscation in a weak multilinear map model. In Martin Hirt and Adam D. Smith, editors, TCC 2016-B, Part II, volume 9986 of LNCS, pages 241–268. Springer, Berlin, Heidelberg, October / November 2016. doi:10.1007/978-3-662-53644-5_10.
[28] Craig Gentry, Sergey Gorbunov, and Shai Halevi. Graph-induced multilinear maps from lattices. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, TCC 2015, Part II, volume 9015 of LNCS, pages 498–527. Springer, Berlin, Heidelberg, March 2015. doi:10.1007/978-3-662-46497-7_20.
[29] Oded Goldreich. A note on computational indistinguishability. Information Processing Letters 34.6 (1990), pp.277–281., 1990. doi:10.1016/0020-0190(90)90010-U.
[30] Shafi Goldwasser, S. Dov Gordon, Vipul Goyal, Abhishek Jain, Jonathan Katz, Feng-Hao Liu, Amit Sahai, Elaine Shi, and Hong-Sheng Zhou. Multi-input functional encryption. In Phong Q. Nguyen and Elisabeth Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, pages 578–602. Springer, Berlin, Heidelberg, May 2014. doi:10.1007/978-3-642-55220-5_32.
[31] Shuichi Hirahara and Mikito Nanashima. One-way functions and zero knowledge. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, 56th ACM STOC, pages 1731–1738. ACM Press, June 2024. doi:10.1145/3618260.3649701.
[32] Susan Hohenberger, Amit Sahai, and Brent Waters. Full domain hash from (leveled) multilinear maps and identity-based aggregate signatures. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part I, volume 8042 of LNCS, pages 494–512. Springer, Berlin, Heidelberg, August 2013. doi:10.1007/978-3-642-40041-4_27.
[33] Yupu Hu and Huiwen Jia. Cryptanalysis of GGH map. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part I, volume 9665 of LNCS, pages 537–565. Springer, Berlin, Heidelberg, May 2016. doi:10.1007/978-3-662-49890-3_21.
[34] Mi-Ying (Miryam) Huang and Er-Cheng Tang. Obfuscation of unitary quantum programs. Cryptology ePrint Archive, Paper 2025/891, 2025. URL: https://eprint.iacr.org/2025/891.
[35] Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from well-founded assumptions. In Samir Khuller and Virginia Vassilevska Williams, editors, 53rd ACM STOC, pages 60–73. ACM Press, June 2021. doi:10.1145/3406325.3451093.
[36] Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, pages 126–152. Springer, Cham, August 2018. doi:10.1007/978-3-319-96878-0_5.
[37] Dakshita Khurana and Kabir Tomer. Commitments from quantum one-wayness. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, 56th ACM STOC, pages 968–978. ACM Press, June 2024. doi:10.1145/3618260.3649654.
[38] Ilan Komargodski, Tal Moran, Moni Naor, Rafael Pass, Alon Rosen, and Eylon Yogev. One-way functions and (im)perfect obfuscation. In 55th FOCS, pages 374–383. IEEE Computer Society Press, October 2014. doi:10.1109/FOCS.2014.47.
[39] Ilan Komargodski, Moni Naor, and Eylon Yogev. Secret-sharing for NP. In Palash Sarkar and Tetsu Iwata, editors, ASIACRYPT 2014, Part II, volume 8874 of LNCS, pages 254–273. Springer, Berlin, Heidelberg, December 2014. doi:10.1007/978-3-662-45608-8_14.
[40] Venkata Koppula, Allison Bishop Lewko, and Brent Waters. Indistinguishability obfuscation for Turing machines with unbounded memory. In Rocco A. Servedio and Ronitt Rubinfeld, editors, 47th ACM STOC, pages 419–428. ACM Press, June 2015. doi:10.1145/2746539.2746614.
[41] W. Kretschmer. Quantum pseudorandomness and classical complexity. TQC 2021, 2021. doi:10.4230/LIPIcs.TQC.2021.2.
[42] William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal. Quantum cryptography in algorithmica. In Barna Saha and Rocco A. Servedio, editors, 55th ACM STOC, pages 1589–1602. ACM Press, June 2023. doi:10.1145/3564246.3585225.
[43] William Kretschmer, Luowen Qian, and Avishay Tal. Quantum-computable one-way functions without one-way functions, 2024. doi:10.48550/arXiv.2411.02554.
[44] Yanyi Liu, Noam Mazor, and Rafael Pass. A note on zero-knowledge for NP and one-way functions. Cryptology ePrint Archive, Paper 2024/800, 2024. URL: https://eprint.iacr.org/2024/800.
[45] Alex Lombardi, Fermi Ma, and John Wright. A one-query lower bound for unitary synthesis and breaking quantum cryptography. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, 56th ACM STOC, pages 979–990. ACM Press, June 2024. doi:10.1145/3618260.3649650.
[46] Fermi Ma and Hsin-Yuan Huang. How to construct random unitaries. Cryptology ePrint Archive, Paper 2024/1652, 2024. URL: https://eprint.iacr.org/2024/1652.
[47] Eric Miles, Amit Sahai, and Mark Zhandry. Annihilation attacks for multilinear maps: Cryptanalysis of indistinguishability obfuscation over GGH13. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part II, volume 9815 of LNCS, pages 629–658. Springer, Berlin, Heidelberg, August 2016. doi:10.1007/978-3-662-53008-5_22.
[48] Tomoyuki Morimae, Yuki Shirakawa, and Takashi Yamakawa. From worst-case hardness of NP to quantum cryptography via quantum indistinguishability obfuscation. arXiv preprint, 2025. arXiv:2506.19542.
[49] Tomoyuki Morimae and Takashi Yamakawa. Quantum commitments and signatures without one-way functions. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part I, volume 13507 of LNCS, pages 269–295. Springer, Cham, August 2022. doi:10.1007/978-3-031-15802-5_10.
[50] Tomoyuki Morimae and Takashi Yamakawa. One-wayness in quantum cryptography. In Frédéric Magniez and Alex Bredariol Grilo, editors, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2024, September 9-13, 2024, Okinawa, Japan, volume 310 of LIPIcs, pages 4:1–4:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.TQC.2024.4.
[51] Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: deniable encryption, and more. In David B. Shmoys, editor, 46th ACM STOC, pages 475–484. ACM Press, May / June 2014. doi:10.1145/2591796.2591825.
[52] Leslie G. Valiant and Vijay V. Vazirani. NP is as easy as detecting unique solutions. Theor. Comput. Sci., 47(3):85–93, 1986. doi:10.1016/0304-3975(86)90135-0.
[53] Mark Zhandry. Tracing quantum state distinguishers via backtracking. In Helena Handschuh and Anna Lysyanskaya, editors, CRYPTO 2023, Part V, volume 14085 of LNCS, pages 3–36. Springer, Cham, August 2023. doi:10.1007/978-3-031-38554-4_1.

[bib.bib1] [1] Gorjan Alagic, Zvika Brakerski, Yfke Dulek, and Christian Schaffner. Impossibility of quantum virtual black-box obfuscation of classical circuits. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part I, volume 12825 of LNCS, pages 497–525, Virtual Event, August 2021. Springer, Cham. doi:10.1007/978-3-030-84242-0_18.

[bib.bib2] [2] Gorjan Alagic and Bill Fefferman. On quantum obfuscation, 2016. arXiv:1602.01771.

[bib.bib3] [3] Prabhanjan Ananth, Dan Boneh, Sanjam Garg, Amit Sahai, and Mark Zhandry. Differing-inputs obfuscation and applications. Cryptology ePrint Archive, Report 2013/689, 2013. URL: https://eprint.iacr.org/2013/689.

[bib.bib4] [4] Saikrishna Badrinarayanan, Eric Miles, Amit Sahai, and Mark Zhandry. Post-zeroizing obfuscation: New mathematical tools, and the case of evasive circuits. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, pages 764–791. Springer, Berlin, Heidelberg, May 2016. doi:10.1007/978-3-662-49896-5_27.

[bib.bib5] [5] Boaz Barak, Sanjam Garg, Yael Tauman Kalai, Omer Paneth, and Amit Sahai. Protecting obfuscation against algebraic attacks. In Phong Q. Nguyen and Elisabeth Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, pages 221–238. Springer, Berlin, Heidelberg, May 2014. doi:10.1007/978-3-642-55220-5_13.

[bib.bib6] [6] Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. Journal of the ACM, 59(2):6:1–6:48, 2012. doi:10.1145/2160158.2160159.

[bib.bib7] [7] James Bartusek, Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa. Obfuscation of pseudo-deterministic quantum circuits. In Barna Saha and Rocco A. Servedio, editors, 55th ACM STOC, pages 1567–1578. ACM Press, June 2023. doi:10.1145/3564246.3585179.

[bib.bib8] [8] James Bartusek and Giulio Malavolta. Indistinguishability obfuscation of null quantum circuits and applications. In Mark Braverman, editor, ITCS 2022, volume 215, pages 15:1–15:13. LIPIcs, January / February 2022. doi:10.4230/LIPIcs.ITCS.2022.15.

[bib.bib9] [9] Rishabh Batra and Rahul Jain. Commitments are equivalent to statistically-verifiable one-way state generators. In 65th FOCS, pages 1178–1192. IEEE Computer Society Press, October 2024. doi:10.1109/FOCS61266.2024.00077.

[bib.bib10] [10] Dan Boneh and Mark Zhandry. Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation. In Juan A. Garay and Rosario Gennaro, editors, CRYPTO 2014, Part I, volume 8616 of LNCS, pages 480–499. Springer, Berlin, Heidelberg, August 2014. doi:10.1007/978-3-662-44371-2_27.

[bib.bib11] [11] Elette Boyle, Kai-Min Chung, and Rafael Pass. On extractability obfuscation. In Yehuda Lindell, editor, TCC 2014, volume 8349 of LNCS, pages 52–73. Springer, Berlin, Heidelberg, February 2014. doi:10.1007/978-3-642-54242-8_3.

[bib.bib12] [12] Zvika Brakerski, Ran Canetti, and Luowen Qian. On the computational hardness needed for quantum cryptography. ITCS 2023, 2023.

[bib.bib13] [13] Zvika Brakerski, Nico Döttling, Sanjam Garg, and Giulio Malavolta. Candidate iO from homomorphic encryption schemes. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part I, volume 12105 of LNCS, pages 79–109. Springer, Cham, May 2020. doi:10.1007/978-3-030-45721-1_4.

[bib.bib14] [14] Zvika Brakerski and Guy N. Rothblum. Virtual black-box obfuscation for all circuits via generic graded encoding. In Yehuda Lindell, editor, TCC 2014, volume 8349 of LNCS, pages 1–25. Springer, Berlin, Heidelberg, February 2014. doi:10.1007/978-3-642-54242-8_1.

[bib.bib15] [15] Anne Broadbent and Raza Ali Kazmi. Constructions for quantum indistinguishability obfuscation. In Patrick Longa and Carla Ràfols, editors, Progress in Cryptology - LATINCRYPT 2021 - 7th International Conference on Cryptology and Information Security in Latin America, Bogotá, Colombia, October 6-8, 2021, Proceedings, volume 12912 of Lecture Notes in Computer Science, pages 24–43. Springer, 2021. doi:10.1007/978-3-030-88238-9_2.

[bib.bib16] [16] Yilei Chen, Craig Gentry, and Shai Halevi. Cryptanalyses of candidate branching program obfuscators. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, EUROCRYPT 2017, Part III, volume 10212 of LNCS, pages 278–307. Springer, Cham, April / May 2017. doi:10.1007/978-3-319-56617-7_10.

[bib.bib17] [17] Jung Hee Cheon, Wonhee Cho, Minki Hhan, Jiseung Kim, and Changmin Lee. Statistical zeroizing attack: Cryptanalysis of candidates of BP obfuscation over GGH15 multilinear map. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part III, volume 11694 of LNCS, pages 253–283. Springer, Cham, August 2019. doi:10.1007/978-3-030-26954-8_9.

[bib.bib18] [18] Jung Hee Cheon, Kyoohyung Han, Changmin Lee, Hansol Ryu, and Damien Stehlé. Cryptanalysis of the multilinear map over the integers. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part I, volume 9056 of LNCS, pages 3–12. Springer, Berlin, Heidelberg, April 2015. doi:10.1007/978-3-662-46800-5_1.

[bib.bib19] [19] Jung Hee Cheon, Minki Hhan, Jiseung Kim, and Changmin Lee. Cryptanalyses of branching program obfuscations over GGH13 multilinear map from the NTRU problem. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, pages 184–210. Springer, Cham, August 2018. doi:10.1007/978-3-319-96878-0_7.

[bib.bib20] [20] Kai-Min Chung, Eli Goldin, and Matthew Gray. On central primitives for quantum cryptography with classical communication. In Leonid Reyzin and Douglas Stebila, editors, CRYPTO 2024, Part VII, volume 14926 of LNCS, pages 215–248. Springer, Cham, August 2024. doi:10.1007/978-3-031-68394-7_8.

[bib.bib21] [21] Kai-Min Chung, Huijia Lin, and Rafael Pass. Constant-round concurrent zero-knowledge from indistinguishability obfuscation. In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part I, volume 9215 of LNCS, pages 287–307. Springer, Berlin, Heidelberg, August 2015. doi:10.1007/978-3-662-47989-6_14.

[bib.bib22] [22] Aloni Cohen, Justin Holmgren, Ryo Nishimaki, Vinod Vaikuntanathan, and Daniel Wichs. Watermarking cryptographic capabilities. In Daniel Wichs and Yishay Mansour, editors, 48th ACM STOC, pages 1115–1127. ACM Press, June 2016. doi:10.1145/2897518.2897651.

[bib.bib23] [23] Andrea Coladangelo and Sam Gunn. How to use quantum indistinguishability obfuscation. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, 56th ACM STOC, pages 1003–1008. ACM Press, June 2024. doi:10.1145/3618260.3649779.

[bib.bib24] [24] Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi. Practical multilinear maps over the integers. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part I, volume 8042 of LNCS, pages 476–493. Springer, Berlin, Heidelberg, August 2013. doi:10.1007/978-3-642-40041-4_26.

[bib.bib25] [25] Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi. New multilinear maps over the integers. In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part I, volume 9215 of LNCS, pages 267–286. Springer, Berlin, Heidelberg, August 2015. doi:10.1007/978-3-662-47989-6_13.

[bib.bib26] [26] Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. SIAM J. Comput., 45(3):882–929, 2016. doi:10.1137/14095772X.

[bib.bib27] [27] Sanjam Garg, Eric Miles, Pratyay Mukherjee, Amit Sahai, Akshayaram Srinivasan, and Mark Zhandry. Secure obfuscation in a weak multilinear map model. In Martin Hirt and Adam D. Smith, editors, TCC 2016-B, Part II, volume 9986 of LNCS, pages 241–268. Springer, Berlin, Heidelberg, October / November 2016. doi:10.1007/978-3-662-53644-5_10.

[bib.bib28] [28] Craig Gentry, Sergey Gorbunov, and Shai Halevi. Graph-induced multilinear maps from lattices. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, TCC 2015, Part II, volume 9015 of LNCS, pages 498–527. Springer, Berlin, Heidelberg, March 2015. doi:10.1007/978-3-662-46497-7_20.

[bib.bib29] [29] Oded Goldreich. A note on computational indistinguishability. Information Processing Letters 34.6 (1990), pp.277–281., 1990. doi:10.1016/0020-0190(90)90010-U.

[bib.bib30] [30] Shafi Goldwasser, S. Dov Gordon, Vipul Goyal, Abhishek Jain, Jonathan Katz, Feng-Hao Liu, Amit Sahai, Elaine Shi, and Hong-Sheng Zhou. Multi-input functional encryption. In Phong Q. Nguyen and Elisabeth Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, pages 578–602. Springer, Berlin, Heidelberg, May 2014. doi:10.1007/978-3-642-55220-5_32.

[bib.bib31] [31] Shuichi Hirahara and Mikito Nanashima. One-way functions and zero knowledge. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, 56th ACM STOC, pages 1731–1738. ACM Press, June 2024. doi:10.1145/3618260.3649701.

[bib.bib32] [32] Susan Hohenberger, Amit Sahai, and Brent Waters. Full domain hash from (leveled) multilinear maps and identity-based aggregate signatures. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part I, volume 8042 of LNCS, pages 494–512. Springer, Berlin, Heidelberg, August 2013. doi:10.1007/978-3-642-40041-4_27.

[bib.bib33] [33] Yupu Hu and Huiwen Jia. Cryptanalysis of GGH map. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part I, volume 9665 of LNCS, pages 537–565. Springer, Berlin, Heidelberg, May 2016. doi:10.1007/978-3-662-49890-3_21.

[bib.bib34] [34] Mi-Ying (Miryam) Huang and Er-Cheng Tang. Obfuscation of unitary quantum programs. Cryptology ePrint Archive, Paper 2025/891, 2025. URL: https://eprint.iacr.org/2025/891.

[bib.bib35] [35] Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from well-founded assumptions. In Samir Khuller and Virginia Vassilevska Williams, editors, 53rd ACM STOC, pages 60–73. ACM Press, June 2021. doi:10.1145/3406325.3451093.

[bib.bib36] [36] Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, pages 126–152. Springer, Cham, August 2018. doi:10.1007/978-3-319-96878-0_5.

[bib.bib37] [37] Dakshita Khurana and Kabir Tomer. Commitments from quantum one-wayness. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, 56th ACM STOC, pages 968–978. ACM Press, June 2024. doi:10.1145/3618260.3649654.

[bib.bib38] [38] Ilan Komargodski, Tal Moran, Moni Naor, Rafael Pass, Alon Rosen, and Eylon Yogev. One-way functions and (im)perfect obfuscation. In 55th FOCS, pages 374–383. IEEE Computer Society Press, October 2014. doi:10.1109/FOCS.2014.47.

[bib.bib39] [39] Ilan Komargodski, Moni Naor, and Eylon Yogev. Secret-sharing for NP. In Palash Sarkar and Tetsu Iwata, editors, ASIACRYPT 2014, Part II, volume 8874 of LNCS, pages 254–273. Springer, Berlin, Heidelberg, December 2014. doi:10.1007/978-3-662-45608-8_14.

[bib.bib40] [40] Venkata Koppula, Allison Bishop Lewko, and Brent Waters. Indistinguishability obfuscation for Turing machines with unbounded memory. In Rocco A. Servedio and Ronitt Rubinfeld, editors, 47th ACM STOC, pages 419–428. ACM Press, June 2015. doi:10.1145/2746539.2746614.

[bib.bib41] [41] W. Kretschmer. Quantum pseudorandomness and classical complexity. TQC 2021, 2021. doi:10.4230/LIPIcs.TQC.2021.2.

[bib.bib42] [42] William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal. Quantum cryptography in algorithmica. In Barna Saha and Rocco A. Servedio, editors, 55th ACM STOC, pages 1589–1602. ACM Press, June 2023. doi:10.1145/3564246.3585225.

[bib.bib43] [43] William Kretschmer, Luowen Qian, and Avishay Tal. Quantum-computable one-way functions without one-way functions, 2024. doi:10.48550/arXiv.2411.02554.

[bib.bib44] [44] Yanyi Liu, Noam Mazor, and Rafael Pass. A note on zero-knowledge for NP and one-way functions. Cryptology ePrint Archive, Paper 2024/800, 2024. URL: https://eprint.iacr.org/2024/800.

[bib.bib45] [45] Alex Lombardi, Fermi Ma, and John Wright. A one-query lower bound for unitary synthesis and breaking quantum cryptography. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, 56th ACM STOC, pages 979–990. ACM Press, June 2024. doi:10.1145/3618260.3649650.

[bib.bib46] [46] Fermi Ma and Hsin-Yuan Huang. How to construct random unitaries. Cryptology ePrint Archive, Paper 2024/1652, 2024. URL: https://eprint.iacr.org/2024/1652.

[bib.bib47] [47] Eric Miles, Amit Sahai, and Mark Zhandry. Annihilation attacks for multilinear maps: Cryptanalysis of indistinguishability obfuscation over GGH13. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part II, volume 9815 of LNCS, pages 629–658. Springer, Berlin, Heidelberg, August 2016. doi:10.1007/978-3-662-53008-5_22.

[bib.bib48] [48] Tomoyuki Morimae, Yuki Shirakawa, and Takashi Yamakawa. From worst-case hardness of NP to quantum cryptography via quantum indistinguishability obfuscation. arXiv preprint, 2025. arXiv:2506.19542.

[bib.bib49] [49] Tomoyuki Morimae and Takashi Yamakawa. Quantum commitments and signatures without one-way functions. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part I, volume 13507 of LNCS, pages 269–295. Springer, Cham, August 2022. doi:10.1007/978-3-031-15802-5_10.

[bib.bib50] [50] Tomoyuki Morimae and Takashi Yamakawa. One-wayness in quantum cryptography. In Frédéric Magniez and Alex Bredariol Grilo, editors, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2024, September 9-13, 2024, Okinawa, Japan, volume 310 of LIPIcs, pages 4:1–4:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.TQC.2024.4.

[bib.bib51] [51] Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: deniable encryption, and more. In David B. Shmoys, editor, 46th ACM STOC, pages 475–484. ACM Press, May / June 2014. doi:10.1145/2591796.2591825.

[bib.bib52] [52] Leslie G. Valiant and Vijay V. Vazirani. NP is as easy as detecting unique solutions. Theor. Comput. Sci., 47(3):85–93, 1986. doi:10.1016/0304-3975(86)90135-0.

[bib.bib53] [53] Mark Zhandry. Tracing quantum state distinguishers via backtracking. In Helena Handschuh and Anna Lysyanskaya, editors, CRYPTO 2023, Part V, volume 14085 of LNCS, pages 3–36. Springer, Cham, August 2023. doi:10.1007/978-3-031-38554-4_1.

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

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Our Result

1.2 Technical Overview

The case of (𝙲,𝙲,𝙲)-iO

The case of (𝙲,𝚀,𝙲)-iO

The case of (𝚀,𝙲,𝙲)-iO

The case of (𝚀,𝚀,𝙲)-iO

The case of (𝚀,𝚀,𝚀)-iO

2 Preliminaries

Notations

2.1 Cryptographic Primitives

Definition 1 (One-Way Functions (OWFs)).

Definition 2 (Quantum Symmetric Key Encryption (QSKE) [50]).

▶ Remark 3.

Definition 4 (QCCC SKE [37]).

Definition 5 (QCCC Public Key Encryption (QCCC PKE) [37]).

2.2 Complexity Theory

Definition 6 (i.o.BQP).

Definition 7 (UP).

Lemma 8.

3 Definitions of Quantum Obfuscation

Definition 9 (Quantum iO for Classical Circuits).

▶ Remark 10.

▶ Remark 11.

▶ Remark 12.

Definition 13 (Variations of Quantum iO).

▶ Remark 14.

Definition 15 (Single-Point Differing-Inputs Obfuscation (diO)).

▶ Remark 16.

Lemma 17 (Adapted from [11]).

4 Main Technical Theorem

Theorem 18.

Proof of Theorem 18.

5 Cryptographic Implications

5.1 Q-Obf, Q-Eval, and Q-Encoding

Theorem 19.

Proof of Theorem 19.

Corollary 20.

5.2 Q-Obf, Q-Eval, and C-Encoding

Theorem 21.

Proof of Theorem 21.

Corollary 22.

5.3 Q-Obf, C-Eval, and C-Encoding

Theorem 23.

Lemma 24.

Proof of Lemma 24.

Proof of Theorem 23.

Corollary 25.

5.4 C-Obf, Q-Eval, and C-Encoding

Theorem 26.

Lemma 27 ([29]).

Lemma 28 ([51]).

Corollary 29.

Proof of Theorem 26.

▶ Remark 30.

5.5 C-Obf, C-Eval, and C-Encoding

Theorem 31.

Proof of Theorem 31.

▶ Remark 32.

References

The case of $(\mathtt{C},\mathtt{C},\mathtt{C})$ -iO

The case of $(\mathtt{C},\mathtt{Q},\mathtt{C})$ -iO

The case of $(\mathtt{Q},\mathtt{C},\mathtt{C})$ -iO

The case of $(\mathtt{Q},\mathtt{Q},\mathtt{C})$ -iO

The case of $(\mathtt{Q},\mathtt{Q},\mathtt{Q})$ -iO

$\blacktriangleright$ Remark 3.

$\blacktriangleright$ Remark 10.

$\blacktriangleright$ Remark 11.

$\blacktriangleright$ Remark 12.

$\blacktriangleright$ Remark 14.

$\blacktriangleright$ Remark 16.

$\blacktriangleright$ Remark 30.

$\blacktriangleright$ Remark 32.