Kai-Min Chung

Quantum computing introduces many well-motivated problems rooted in physics, asking to compute information from input quantum states. Identifying the computational hardness of these problems yields potential applications with far-reaching impacts across both the realms of computer science and physics. However, these new problems do not neatly fit within the scope of existing complexity theory. The standard classes primarily cater to problems with classical inputs and outputs, leaving a gap to characterize problems involving quantum states as inputs. For instance, breaking new quantum cryptographic primitives involves solving problems with quantum inputs; this significantly changes Impagliazzo’s five-world while the complexity classes central to Pessiland, Heuristica, and Algorithmica are grounded in problems with classical inputs and outputs. To bridge these knowledge gaps, we explore the complexity theory for quantum promise problems and potential applications. Quantum promise problems are quantum-input decision problems asking to identify whether input quantum states satisfy specific properties. We begin by establishing structural results for several fundamental quantum complexity classes: p/mBQP, p/mQ(C)MA, p/mQSZKhv, p/mQIP, p/mBQP/qpoly, p/mBQP/poly, and p/mPSPACE. This includes identifying complete problems, as well as proving containment and separation results among these classes. Here, p/mC denotes the corresponding quantum promise complexity class with pure (p) or mixed (m) quantum input states for any classical complexity class C. Surprisingly, our findings uncover relationships that diverge from their classical analogues — specifically, we show unconditionally that p/mQIP \neq p/mPSPACE and p/mBQP/qpoly \neq p/mBQP/poly. This starkly contrasts the classical setting, where QIP=PSPACE and separations such as BQP/qpoly \neq BQP/poly are only known relative to oracles. This new framework has numerous applications in quantum cryptography, particularly in the contexts of Microcrypt and unconditional cryptography [Qia24, MNY24]. For Microcrypt, we provide a better characterization of its primitives; for example, we show that OWSG and PRS can be broken by a p/mQCMA oracle, leading to a natural quantum analogue of Impagliazzo’s five worlds by substituting the classical complexity classes in Pessiland, Heuristica, and Algorithmica with mBQP and mQCMA. Moreover, we establish the relativization barrier for proving the existence of EFI, noting that no such barrier currently exists within traditional complexity theory. For unconditional cryptography, our framework is the first to capture the notion of unconditional computational hardness, resolving the open problem in [Qia24,MNY24] by constructing an unconditionally secure auxiliary-input quantum commitment scheme with computational binding and statistical hiding. Our framework also has other applications in quantum property testing and unitary synthesis.

Zero-Knowledge (ZK) protocols have been a subject of intensive study due to their fundamental importance and versatility in modern cryptography. However, the inherently different nature of quantum information significantly alters the landscape, necessitating a re-examination of ZK designs. A crucial aspect of ZK protocols is their round complexity, intricately linked to *simulation*, which forms the foundation of their formal definition and security proofs. In the *post-quantum* setting, where honest parties and their communication channels are all classical but the adversaries could be quantum, Chia, Chung, Liu, and Yamakawa [FOCS'21 & QIP'22] demonstrated the non-existence of constant-round *black-box-simulatable* ZK arguments (BBZK) for NP unless NP is in BQP. However, this problem remains widely open in the full-fledged quantum future that will eventually arrive, where all parties (including the honest ones) and their communication are naturally quantum. Indeed, this problem is of interest to the broader theory of quantum computing. It has been an important theme to investigate how quantum power fundamentally alters traditional computational tasks, such as the *unconditional* security of Quantum Key Distribution and the incorporation of Oblivious Transfers in MiniQCrypt. Moreover, quantum communication has led to round compression for commitments and interactive arguments. Along this line, the above problem is of great significance in understanding whether quantum computing could also change the nature of ZK protocols in some fundamentally manner. We resolved this problem by proving that only languages in *BQP* admit constant-round *fully-quantum* BBZK. This result holds significant implications. Firstly, it illuminates the nature of quantum zero-knowledge and provides valuable insights for designing future protocols in the quantum realm. Secondly, it relates ZK round complexity with the intriguing problem of BQP vs QMA, which is out of the reach of previous analogue impossibility results in the classical or post-quantum setting. Lastly, it justifies the need for the non-black-box simulation techniques or the relaxed security notions employed in existing constant-round fully-quantum BBZK protocols.

In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for NP secure against quantum attacks. However, their construction has several drawbacks compared to the classical counterparts. Specifically, their construction only achieves computational soundness, requires strong assumptions of quantum hardness of learning with errors (QLWE assumption) and the existence of quantum fully homomorphic encryption (QFHE), and relies on non-black-box simulation. In this paper, we resolve these issues at the cost of weakening the notion of zero-knowledge to what is called $\epsilon$-zero-knowledge. Concretely, we construct the following protocols: - We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box $\epsilon$-zero-knowledge against quantum attacks assuming the existence of collapsing hash functions, which is a quantum counterpart of collision-resistant hash functions. Interestingly, this construction is just an adapted version of the classical protocol by Goldreich and Kahan (JoC '96) though the proof of $\epsilon$-zero-knowledge property against quantum adversaries requires novel ideas. - We construct a constant round interactive argument for NP that satisfies computational soundness and black-box $\epsilon$-zero-knowledge against quantum attacks only assuming the existence of post-quantum one-way functions. At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier while simulating verifier's internal state in an appropriate sense.

We revisit the so-called compressed oracle technique, introduced by Zhandry for analyzing quantum algorithms in the quantum random oracle model (QROM). To start off with, we offer a concise exposition of the technique, which easily extends to the parallel-query QROM, where in each query-round the considered algorithm may make several queries to the QROM in parallel. This variant of the QROM allows for a more fine-grained query-complexity analysis. Our main technical contribution is a framework that simplifies the use of (the parallel-query generalization of) the compressed oracle technique for proving query complexity results. With our framework in place, whenever applicable, it is possible to prove quantum query complexity lower bounds by means of purely classical reasoning. More than that, for typical examples the crucial classical observations that give rise to the classical bounds are sufficient to conclude the corresponding quantum bounds. We demonstrate this on a few examples, recovering known results (like the optimality of parallel Grover), but also obtaining new results (like the optimality of parallel BHT collision search). Our main target is the hardness of finding a q-chain with fewer than q parallel queries, i.e., a sequence x_0, x_1..., x_q with x_i = H(x_{i-1}) for all 1 <= i <= q. The above problem of finding a hash chain is of fundamental importance in the context of proofs of sequential work. Indeed, as a concrete cryptographic application of our techniques, we prove that the "Simple Proofs of Sequential Work" proposed by Cohen and Pietrzak remains secure against quantum attacks. Such an analysis is not simply a matter of plugging in our new bound; the entire protocol needs to be analyzed in the light of a quantum attack. Thanks to our framework, this can now be done with purely classical reasoning.

We investigate the existence of constant-round post-quantum black-box zero-knowledge protocols for $\mathbf{NP}$. As a main result, we show that there is no constant-round post-quantum black-box zero-knowledge argument for $\mathbf{NP}$ unless $\mathbf{NP}\subseteq \mathbf{BQP}$. As constant-round black-box zero-knowledge arguments for $\mathbf{NP}$ exist in the classical setting, our main result points out a fundamental difference between post-quantum and classical zero-knowledge protocols. Combining previous results, we conclude that unless $\mathbf{NP}\subseteq \mathbf{BQP}$, constant-round post-quantum zero-knowledge protocols for $\mathbf{NP}$ exist if and only if we use non-black-box techniques or relax certain security requirements such as relaxing standard zero-knowledge to $\epsilon$-zero-knowledge. Additionally, we also prove that three-round and public-coin constant-round post-quantum black-box $\epsilon$-zero-knowledge arguments for $\mathbf{NP}$ do not exist unless $\mathbf{NP}\subseteq \mathbf{BQP}$.