Ryo Nishimaki

Unclonable cryptography leverages the quantum no-cloning principle to achieve strong security guarantees that are impossible to achieve in a classical world. Most existing works in this area only consider the basic single-copy security, and there been only a few works that achieve the more realistic notion of \emph{collusion-resistance} (where adversary receives multiple keys), which is the gold standard in cryptography. Further, existing works that do consider collusion-resistance have convoluted non-black-box solutions, and are highly tailored to their own applications, with little hope to generalize, and they often re-invent the tools from both single-key quantum cryptography as well as collusion-resistant classical cryptography. Moreover, the question of \emph{multi-copy security}, where the adversary receives multiple copies of the same state (rather than merely getting multiple independently sampled keys) is almost completely open. In this work, we develop a large toolset of black-box compilers and technical lemmata for dealing with collusion-resistance and multi-copy security in quantum cryptography. Using our toolset, we obtain a large number of new feasibility results with black-box constructions, with proofs that are significantly \emph{simpler} than the existing proofs in literature. In particular, we introduce a generic compiler that upgrades single-key secure quantum protection (copy-protection/LOCC leakage-resilience/secure leasing) schemes for decryption keys to collusion-resistant secure schemes. Then, we also introduce a generic compiler that upgrades collusion-resistant primitives to achieve multi-copy security, assuming only one-way functions. Using our toolset, we obtain a large number of new feasibility results. We obtain the first multi-copy secure constructions of public-key quantum money (termed quantum coins), single-decryptor encryption (SDE), unclonable encryption, and more. We obtain the first collusion-resistant secure key-leasing scheme with a fully classical lessor. Finally, we obtain the first LOCC leakage-resilient PKE scheme with multi-copy security, thus making progress towards achieving \emph{quantum key-fire} in the plain model. Finally, as part of our toolset, we also show various technical results, such as the collusion-resistant analogue of the \emph{one-way-to-hiding (O2H) lemma}, a quantum-state analogue of the small-range-distributions lemma, a \emph{quantum pigeonhole lemma} for entangled adversaries and the first deterministic signature scheme with quantum-query security. We also show that independent-challenge security implies identical-challenge security in collusion-resistant copy-protection search games, and thus we obtain the first schemes with such security.

We show how to obfuscate pseudo-deterministic quantum circuits, assuming the quantum hardness of learning with errors (QLWE) and post-quantum virtual black-box (VBB) obfuscation for classical circuits. Given the classical description of a quantum circuit $Q$, our obfuscator outputs a quantum state $\ket{\widetilde{Q}}$ that can be used to evaluate $Q$ repeatedly on arbitrary inputs. Instantiating the VBB obfuscator for classical circuits with any candidate post-quantum indistinguishability obfuscator gives us the first candidate construction of indistinguishability obfuscation for all polynomial-size pseudo-deterministic quantum circuits. In particular, our scheme is the first candidate obfuscator for a class of circuits that is powerful enough to implement Shor's algorithm (SICOMP 1997). Our approach follows Bartusek and Malavolta (ITCS 2022), who obfuscate \emph{null} quantum circuits by obfuscating the verifier of an appropriate classical verification of quantum computation (CVQC) scheme. We go beyond null circuits by constructing a publicly-verifiable CVQC scheme for quantum \emph{partitioning} circuits, which can be used to verify the evaluation procedure of Mahadev's quantum fully-homomorphic encryption scheme (FOCS 2018). We achieve this by upgrading the one-time secure scheme of Bartusek (TCC 2021) to a fully reusable scheme, via a publicly-decodable \emph{Pauli functional commitment}, which we formally define and construct in this work. This commitment scheme, which satisfies a notion of binding against committers that can access the receiver's standard and Hadamard basis decoding functionalities, is constructed by building on techniques of Amos, Georgiou, Kiayias, and Zhandry (STOC 2020) introduced in the context of equivocal but collision-resistant hash functions.

Broadbent and Islam (TCC '20) proposed a quantum cryptographic primitive called quantum encryption with certified deletion. In this primitive, a receiver in possession of a quantum ciphertext can generate a classical certificate that the encrypted message is deleted. Although their construction is information-theoretically secure, it is limited to the setting of one-time symmetric key encryption (SKE), where a sender and receiver have to share a common key in advance and the key can be used only once. Moreover, the sender has to generate a quantum state and send it to the receiver over a quantum channel in their construction. Although deletion certificates are privately verifiable, which means a verification key for a certificate has to be kept secret, in the definition by Broadbent and Islam, we can also consider public verifiability. In this work, we present various constructions of encryption with certified deletion. - Quantum communication case: We achieve (reusable-key) public key encryption (PKE) and attribute-based encryption (ABE) with certified deletion. Our PKE scheme with certified deletion is constructed assuming the existence of IND-CPA secure PKE, and our ABE scheme with certified deletion is constructed assuming the existence of indistinguishability obfuscation and one-way function. These two schemes are privately verifiable. - Classical communication case: We also achieve PKE with certified deletion that uses only classical communication. We give two schemes, a privately verifiable one and a publicly verifiable one. The former is constructed assuming the LWE assumption in the quantum random oracle model. The latter is constructed assuming the existence of one-shot signatures and extractable witness encryption.