Research Interest

My research has mostly focused on understanding quantum information and quantum computation, through the lens of cryptography. 

Overview

Since cryptography plays an irreplaceable role in data and privacy protection on the Internet and blockchains, upgrading the security of cryptographic protocols becomes a question of "not when but how." Therefore, the first part of my research is to understand quantum algorithms, improve security of existing cryptographic protocols in the presence of quantum attacks; and eventually provide a smooth transition to a quantum world where communication and secure Internet are reliable, personal data and privacy remains intact.

On the flip side, quantum computers also raise the possibility of using quantum mechanical phenomena to achieve never-before-possible functionalities. One famous example is the no-cloning principle of quantum information, which states that quantum information cannot be cloned in general. The no-cloning principle raises the idea of using unclonable quantum states to build physically unclonable quantum money or copy-protected programs. The second part of my research is to combine modern cryptography with quantum information into fascinating protocols, that no one could imagine in a classical world. Along the way, I also discover various properties of quantum information.

Finally, since almost all Noisy Intermediate Scale Quantum technology (NISQ) faces extreme difficulties from quantum noise correction, a large-scale noise-tolerant quantum computer may not be realized in the short term. Consequently, quantum computers pose fewer threats, since they are still in their imperfect forms. In the meantime, all applications involving quantum information, like quantum money and copy-protected programs, are difficult to implement. Thus, the final part of my research is to re-think the first and second part of my research in the presence of imperfect quantum computers.

Quantum Query Complexity

I developed tools for analyzing query complexity of quantum algorithms, especially when they have access to a hash function or a random function. Proofs in the classical setting do not carry out in the quantum world because a quantum algorithm can query a function in superposition. Loosely speaking, a quantum algorithm can view multiple input-output pairs of a function via a single interaction with the function, but all information is stored in a short piece of quantum information. Since the introduction of quantum-accessible hash functions in 2011, few techniques and proofs have been established in the model due to the ability of quantum access.

In my work [Revisiting Post-Quantum Fiat-Shamir, CRYPTO'19] with Zhandry, I showed a general way of leveraging classical proofs and proving the security of different hash function applications. My other works leverage the tool and show matching upper and lower bounds for finding multiple collisions in the quantum world [On Finding Quantum Multi-collisions , EUROCRYPT'19], which gives guidelines for how to choose parameters of practical hash functions like SHA-3 256, against quantum computers; generalize the impossibility of zero-knowledge to the quantum setting [On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds, FOCS'21]; establish post-quantum security against preprocessing quantum attacks [Tight Quantum Time-Space Tradeoffs for Function Inversion, FOCS'20], [Non-uniformity, Quantum Advice in the Quantum Random Oracle Model, EUROCRYPT'23], ...

Cryptography Using QI

One fascinating nature of quantum information is the no-cloning principle. Based on it, people have constructed quantum banknotes and programs that cannot be duplicated. Starting from my work on copy-protected programs [New Approaches for Quantum Copy-Protection, CRYPTO'21], it has gained widespread attention to combine modern cryptography and quantum information into classically impossible primitives. My research in this direction covers cryptographic protocols that cannot be cloned [Hidden Cosets and Applications to Unclonable Cryptography, CRYPTO'21], [On the Feasibility of Unclonable Encryption, and More, CRYPTO'22], [Collusion-Resistant Copy-Protection for Watermarkable Functionalities, TCC'22], positioning systems without trusting hardware [Beating Classical Impossibility of Position Verification, ITCS'22] (loosely speaking, improved GPS based on quantum information). These results perfectly complement quantum-safe classical cryptography and enlarge applications of quantum technologies.

Quantum copy-protection compiles a classical program into a quantum program. It leverages the unclonability of quantum states to construct programs that cannot be copied. Copy-protection has numerous applications in intellectual property management and cryptography generally. One interesting case is to prevent decryption keys from being maliciously spread. In the example of online streaming, service providers can provide different decryption keys (for decrypting the streaming content) to different subscribers. Classical solutions will allow the provider to trace the source of leaks. However, these classical notions do not prevent a leak from happening in the first place. I show how to achieve unclonable decryption keys and unclonable functions with quantum power. In my work with Aaronson, Liu, Zhandry, and Zhang, I improve the previous result of Aaronson by constructing general quantum copy-protection with weaker assumptions. In my other work with Coladangelo, Liu, and Zhandry, I show that many functions can be copy-protected with even more standard assumptions.

Understanding Near-Term Quantum

Despite the great success in the theoretical study of the above quantum attacks and protocols, almost all applications face extreme difficulties with state-of-the-art quantum technology. Though the difficulties are considered just an engineering challenge by the community, these problems fundamentally limit quantum attacks and applications in the near term: most notably, the barrier to maintaining a quantum state for a long time and computing coherently over a large depth. I work on another line of research on limitations and potentials of imperfect quantum devices. These researches consist of (1) understanding the boundary of quantum learning algorithms in the presence of limited quantum memory [Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory, STOC'23], (2) analyzing the restrictions of quantum algorithms on imperfect devices [Quantum-Classical Tradeoffs in the Random Oracle Model], and (3) utilizing noisy quantum devices to build one-time programs [Depth-Bounded Quantum Cryptography with Applications to One-Time Memory and More, ITCS'23].