International Association
for Cryptologic Research

We introduce a new notion called $\mathcal{Q}$-secure pseudorandom isometries (PRI). A pseudorandom isometry is an efficient quantum circuit that maps an $n$-qubit state to an $(n+m)$-qubit state in an isometric manner. In terms of security, we require that the output of a $q$-fold PRI on $\rho$, for $ \rho \in \mathcal{Q}$, for any polynomial $q$, should be computationally indistinguishable from the output of a $q$-fold Haar isometry on $\rho$. By fine-tuning $\mathcal{Q}$, we recover many existing notions of pseudorandomness. We present a construction of PRIs and assuming post-quantum one-way functions, we prove the security of $\mathcal{Q}$-secure pseudorandom isometries (PRI) for different interesting settings of $\mathcal{Q}$. We also demonstrate many cryptographic applications of PRIs, including, length extension theorems for quantum pseudorandomness notions, MACs for quantum states, multi-copy secure public and private encryption schemes, and succinct quantum commitments.

The powerful no-cloning principle of quantum mechanics can be leveraged to achieve interesting primitives, referred to as unclonable primitives, that are impossible to achieve classically. In the past few years, we have witnessed a surge of new unclonable primitives. While prior works have mainly focused on establishing feasibility results, another equally important direction, that of understanding the relationship between different unclonable primitives is still in its nascent stages. Moving forward, we need a more systematic study of unclonable primitives. \par To this end, we introduce a new framework called {\em cloning games}. This framework captures many fundamental unclonable primitives such as quantum money, copy-protection, unclonable encryption, single-decryptor encryption, and many more. By reasoning about different types of cloning games, we obtain many interesting implications to unclonable cryptography, including the following: 1. We obtain the first construction of information-theoretically secure single-decryptor encryption in the one-time setting. 2. We construct unclonable encryption in the quantum random oracle model based on BB84 states, improving upon the previous work, which used coset states. Our work also provides a simpler security proof for the previous work. 3. We construct copy-protection for single-bit point functions in the quantum random oracle model based on BB84 states, improving upon the previous work, which used coset states, and additionally, providing a simpler proof. 4. We establish a relationship between different challenge distributions of copy-protection schemes and single-decryptor encryption schemes. 5. Finally, we present a new construction of one-time encryption with certified deletion.

Unclonable encryption, first introduced by Broadbent and Lord (TQC'20), is a one-time encryption scheme with the following security guarantee: any non-local adversary (A, B, C) cannot simultaneously distinguish encryptions of two equal length messages. This notion is termed as unclonable indistinguishability. Prior works focused on achieving a weaker notion of unclonable encryption, where we required that any non-local adversary (A, B, C) cannot simultaneously recover the entire message m. Seemingly innocuous, understanding the feasibility of encryption schemes satisfying unclonable indistinguishability (even for 1-bit messages) has remained elusive. We make progress towards establishing the feasibility of unclonable encryption. (*) We show that encryption schemes satisfying unclonable indistinguishability exist unconditionally in the quantum random oracle model. (*) Towards understanding the necessity of oracles, we present a negative result stipulating that a large class of encryption schemes cannot satisfy unclonable indistinguishability. (*) Finally, we also establish the feasibility of another closely related primitive: copy-protection for single-bit output point functions. Prior works only established the feasibility of copy-protection for multi-bit output point functions or they achieved constant security error for single-bit output point functions.

Unclonable encryption, introduced by Broadbent and Lord (TQC'20), is an encryption scheme with the following attractive feature: given a ciphertext, an adversary cannot create two ciphertexts both of which decrypt to the same message as the original ciphertext. We revisit this notion and show the following: -Reusability: The constructions proposed by Broadbent and Lord have the disadvantage that they either guarantee one-time security (that is, the encryption key can only be used once to encrypt the message) in the plain model or they guaranteed security in the random oracle model. We construct unclonable encryption schemes with semantic security. We present two constructions from minimal cryptographic assumptions: (i) a private-key unclonable encryption scheme assuming post-quantum one-way functions and, (ii) a public-key unclonable encryption scheme assuming a post-quantum public-key encryption scheme. -Lower Bound and Generalized Construction: We revisit the information-theoretic one-time secure construction of Broadbent and Lord. The success probability of the adversary in their construction was guaranteed to be $0.85^n$, where $n$ is the length of the message. It was interesting to understand whether the ideal success probability of (negligibly close to) $0.5^n$ was unattainable. We generalize their construction to be based on a broader class of monogamy of entanglement games (while their construction was based on BB84 game). We demonstrate a simple cloning attack that succeeds with probability $0.71^n$ against a class of schemes including that of Broadbent and Lord. We also present a $0.75^n$ cloning attack exclusively against their scheme. -Implication to Copy-Protection: We show that unclonable encryption, satisfying a stronger property, called unclonable-indistinguishability (defined by Broadbent and Lord), implies copy-protection for a simple class of unlearnable functions. While we currently don't have encryption schemes satisfying this stronger property, this implication demonstrates a new path to construct copy-protection.