Kai-Min Chung

TACAS Conference 2026 Conference Paper

Equivalence Checking of Quantum Circuits via Path-Sum and Weighted Model Counting

• Wei-Jia Huang
• Christophe Chareton
• Yu-Fang Chen
• Kai-Min Chung
• Min-Hsiu Hsieh
• Alfons Laarman
• Jingyi Mei

FOCS Conference 2021 Conference Paper

On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Round

• Nai-Hui Chia
• Kai-Min Chung
• Qipeng Liu 0001
• Takashi Yamakawa

We investigate the existence of constant-round post-quantum black-box zero-knowledge protocols for NP. As a main result, we show that there is no constant-round post-quantum black-box zero-knowledge argument for NP unless $\text{NP} \subseteq \text{BQP}$. As constant-round black-box zero-knowledge arguments for 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 $\text{NP} \subseteq \text{BQP}$, constant-round post-quantum zero-knowledge protocols for 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 NP do not exist unless $\text{NP} \subseteq \text{BQP}$.

STOC Conference 2020 Conference Paper

On the need for large quantum depth

• Nai-Hui Chia
• Kai-Min Chung
• Ching-Yi Lai

FOCS Conference 2020 Conference Paper

Tight Quantum Time-Space Tradeoffs for Function Inversion

• Kai-Min Chung
• Siyao Guo 0001
• Qipeng Liu 0001
• Luowen Qian

In function inversion, we are given a function $f: [N]\rightarrow[N]$, and want to prepare some advice of size $S$, such that we can efficiently invert any image in time $T$. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower bounds. Investigation of this problem in the quantum setting was initiated by Nayebi, Aaronson, Belovs, and Trevisan (2015), who proved a lower bound of $ST^{2}=\tilde{\Omega}(N)$ for random permutations against classical advice, leaving open an intriguing possibility that Grover's search can be sped up to time $\tilde{O}(\sqrt{N/S})$. Recent works by Hhan, Xagawa, and Yamakawa (2019), and Chung, Liao, and Qian (2019) extended the argument for random functions and quantum advice, but the lower bound remains $ST^{2}=\tilde{\Omega}(N)$. In this work, we prove that even with quantum advice, $ST+ T^{2}=\tilde{\Omega}(N)$, is required for an algorithm to invert random functions. This demonstrates that Grover's search is optimal for $S=\tilde{O}(\sqrt{N})$, ruling out any substantial speed-up for Grover's search even with quantum advice. Further improvements to our bounds would imply new classical circuit lower bounds, as shown by Corrigan-Gibbs and Kogan (2019). To prove this result, we develop a general framework for establishing quantum time-space lower bounds. We further demonstrate the power of our framework by proving the following results. •Yao's box problem: We prove a tight quantum time-space lower bound for classical advice. For quantum advice, we prove a first time-space lower bound using shadow tomography. These results resolve two open problems posted by Nayebi et al (2015). •Salted cryptography: We show that “salting generically provably defeats preprocessing, ” a result shown by Coretti, Dodis, Guo, and Steinberger (2018), also holds in the quantum setting. In particular, we prove quantum time-space lower bounds for a wide class of salted cryptographic primitives in the quantum random oracle model. This yields the first quantum time-space lower bound for salted collision-finding, which in turn implies that $\text{PWPP}^{\mathcal{O}} \nsubseteq \text{FBQP}^{\mathcal{O}}/\text{qpoly}$ relative to a random oracle $\mathcal{O}$.

SODA Conference 2019 Conference Paper

Foundations of Differentially Oblivious Algorithms

• T. -H. Hubert Chan
• Kai-Min Chung
• Bruce M. Maggs
• Elaine Shi

It is well-known that a program's memory access pattern can leak information about its input. To thwart such leakage, most existing works adopt the technique of oblivious RAM (ORAM) simulation. Such an obliviousness notion has stimulated much debate. Although ORAM techniques have significantly improved over the past few years, the concrete overheads are arguably still undesirable for real-world systems — part of this overhead is in fact inherent due to a well-known logarithmic ORAM lower bound by Goldreich and Ostrovsky. To make matters worse, when the program's runtime or output length depend on secret inputs, it may be necessary to perform worst-case padding to achieve full obliviousness and thus incur possibly super-linear overheads. Inspired by the elegant notion of differential privacy, we initiate the study of a new notion of access pattern privacy, which we call “( ∊, δ )-differential obliviousness”. We separate the notion of ( ∊, δ )-differential obliviousness from classical obliviousness by considering several fundamental algorithmic abstractions including sorting small-length keys, merging two sorted lists, and range query data structures (akin to binary search trees). We show that by adopting differential obliviousness with reasonable choices of ∊ and δ, not only can one circumvent several impossibilities pertaining to full obliviousness, one can also, in several cases, obtain meaningful privacy with little overhead relative to the non-private baselines (i. e. , having privacy “almost for free”). On the other hand, we show that for very demanding choices of ∊ and δ, the same lower bounds for oblivious algorithms would be preserved for ( ∊, δ )-differential obliviousness.

FOCS Conference 2013 Conference Paper

Constant-Round Concurrent Zero Knowledge from P-Certificates

• Kai-Min Chung
• Huijia Lin
• Rafael Pass

We present a constant-round concurrent zero-knowledge protocol for NP. Our protocol relies on the existence of families of collision-resistant hash functions, and a new, but in our eyes, natural complexity-theoretic assumption: the existence of P-certificates-that is, "succinct" non-interactive proofs/arguments for P. As far as we know, our results yield the first constant-round concurrent zero-knowledge protocol for NP with an explicit zero-knowledge simulator based on any assumption.

FOCS Conference 2013 Conference Paper

Knowledge-Preserving Interactive Coding

• Kai-Min Chung
• Rafael Pass
• Sidharth Telang

How can we encode a communication protocol between two parties to become resilient to adversarial errors on the communication channel? If we encode each message in the communication protocol with a "good" error-correcting code (ECC), the error rate of the encoded protocol becomes poor (namely O(1/m) where m is the number of communication rounds). Towards addressing this issue, Schulman (FOCS'92, STOC'93) introduced the notion of interactive coding. We argue that whereas the method of separately encoding each message with an ECC ensures that the encoded protocol carries the same amount of information as the original protocol, this may no longer be the case if using interactive coding. In particular, the encoded protocol may completely leak a player's private input, even if it would remain secret in the original protocol. Towards addressing this problem, we introduce the notion of knowledge-preserving interactive coding, where the interactive coding protocol is required to preserve the "knowledge" transmitted in the original protocol. Our main results are as follows: The method of separately applying ECCs to each message has essentially optimal error rate: No knowledge-preserving interactive coding scheme can have an error rate of 1/m, where m is the number of rounds in the original protocol; If restricting to computationally-bounded (polynomial-time) adversaries, then assuming the existence of one-way functions (resp. sub exponentially-hard one-way functions), for every ϵ > 0, there exists a knowledge-preserving interactive coding schemes with constant error rate and information rate n -ϵ (resp. 1/polylog(n)) where n is the security parameter; additionally to achieve an error of even 1/m requires the existence of one-way functions; Finally, even if we restrict to computationally-bounded adversaries, knowledge-preserving interactive coding schemes with constant error rate can have an information rate of at most o(1 log n). This results applies even to non-constructive interactive coding schemes.

STOC Conference 2013 Conference Paper

Non-black-box simulation from one-way functions and applications to resettable security

• Kai-Min Chung
• Rafael Pass
• Karn Seth

The simulation paradigm, introduced by Goldwasser, Micali and Rackoff, is of fundamental importance to modern cryptography. In a breakthrough work from 2001, Barak (FOCS'01) introduced a novel non-black-box simulation technique. This technique enabled the construction of new cryptographic primitives, such as resettably-sound zero-knowledge arguments, that cannot be proven secure using just black-box simulation techniques. The work of Barak and its follow-ups, however, all require stronger cryptographic hardness assumptions than the minimal assumption of one-way functions. In this work, we show how to perform non-black-box simulation assuming just the existence of one-way functions. In particular, we demonstrate the existence of a constant-round resettably-sound zero-knowledge argument based only on the existence of one-way functions. Using this technique, we determine necessary and sufficient assumptions for several other notions of resettable security of zero-knowledge proofs. An additional benefit of our approach is that it seemingly makes practical implementations of non-black-box zero-knowledge viable.

FOCS Conference 2013 Conference Paper

Simultaneous Resettability from One-Way Functions

• Kai-Min Chung
• Rafail Ostrovsky
• Rafael Pass
• Ivan Visconti

Resettable-security, introduced by Canetti, Goldreich, Goldwasser and Micali (STOC'00), considers the security of cryptographic two-party protocols (in particular zero-knowledge arguments) in a setting where the attacker may “reset” or “rewind” one of the players. The strongest notion of resettable security, simultaneous resettability, introduced by Barak, Goldreich, Goldwasser and Lindell (FOCS'01), requires resettable security to hold for both parties: in the context of zero-knowledge, both the soundness and the zero-knowledge conditions remain robust to resetting attacks. To date, all known constructions of protocols satisfying simultaneous resettable security rely on the existence of ZAPs; constructions of ZAPs are only known based on the existence of trapdoor permutations or number-theoretic assumptions. In this paper, we provide a new method for constructing protocols satisfying simultaneous resettable security while relying only on the minimal assumption of one-way functions. Our key results establish, assuming only one-way functions: Every language in NP has an ω(1)-round simultaneously resettable witness indistinguishable argument system; Every language in NP has a (polynomial-round) simultaneously resettable zero-knowledge argument system. The key conceptual insight in our technique is relying on black-box impossibility results for concurrent zero-knowledge to achieve resettable-security.

FOCS Conference 2011 Conference Paper

The Randomness Complexity of Parallel Repetition

• Kai-Min Chung
• Rafael Pass

Consider a m-round interactive protocol with soundness error 1/2. How much extra randomness is required to decrease the soundness error to δ through parallel repetition? Previous work, initiated by Bell are, Goldreich and Goldwasser, shows that for public-coin interactive protocols with statistical soundness, m · O(log (1/δ)) bits of extra randomness suffices. In this work, we initiate a more general study of the above question. We establish the first derandomized parallel repetition theorem for public-coin interactive protocols with computational soundness (a. k. a. arguments). The parameters of our result essentially matches the earlier works in the information-theoretic setting. We show that obtaining even a sub-linear dependency on the number of rounds m (i. e. , o(m)·log(1/δ)) is impossible in the information-theoretic, and requires the existence of one-way functions in the computational setting. We show that non-trivial derandomized parallel repetition for private-coin protocols is impossible in the information-theoretic setting and requires the existence of one-way functions in the computational setting. These results are tight in the sense that parallel repetition theorems in the computational setting can trivially be derandomized using pseudorandom generators, which are implied by the existence of one-way functions.