A Note on Boosting Uncloneable Encryption in Microcrypt

James Bartusek, Eli Goldin · 2026

Read A Note on Boosting Uncloneable Encryption in Microcrypt by James Bartusek, Eli Goldin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-27647.txt.

Introduction

James Bartusek and Eli Goldin ask how little uncloneable encryption needs, starting from a single uncloneable bit. They show that if a t-to-t-prime uncloneable bit exists, many-time secure symmetric key encryption yields many-time secure uncloneable encryption for messages of any length. With pseudorandom unitaries instead, the same build gives identical copy security, proving the result tight.

Catalog record

CREATORJames Bartusek, Eli Goldin
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58724
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.27647

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Note on Boosting Uncloneable Encryption in Microcrypt James Bartusek, Eli Goldin Abstract In this note, we consider the setting of uncloneable encryption satisfying uncloneable indistinguishability, a form of symmetric key encryption that prevents the cloning of ciphertexts in a very strong sense. Our goal is to minimize the assumptions under which (many-time secure) uncloneable encryption is known to exist, assuming the existence of an information-theoretic “uncloneable bit”, i.e. a one-time secure uncloneable encryption scheme for one-bit messages. We observe that if a t → t ′ t\to t^{\prime} uncloneable bit exists, then the following implications hold. 1. If many-time secure symmetric key encryption exists, then many-time secure t → t ′ t\to t^{\prime} uncloneable encryption for arbitrary-length messages exists. Since many-time secure uncloneable encryption implies many-time secure symmetric key encryption, this result is tight. 2. If pseudorandom unitaries exist, then many-time secure t → t ′ t\to t^{\prime} uncloneable encryption for arbitrary-length messages with identical copy security exists. These results together show that many-time secure uncloneable encryption may follow from concrete assumptions in “microcrypt”, the world of unstructured quantum cryptography that plausibly exists even if P = N ​ P P=NP . 1 Introduction Uncloneable encryption (UE) is a fundamental primitive in quantum cryptography that leverages both the uncloneability of quantum information and the privacy of semantically-secure encryption to yield exciting new applications. Originally introduced by [ 11 ] , UE has since been studied in several works (e.g. [ 4 , 2 , 3 , 9 , 8 , 16 , 12 , 1 , 7 , 6 ] ) proposing constructions that satisfy different security notions under various assumptions and/or idealized models. In this note, we focus our attention on secret-key UE with standard semantic security, often referred to as uncloneable indistinguishability . Analogously to plain secret-key encryption (SKE), UE with one-time security plausibly exists information-theoretically. This question has a long history of study, and has come to be known as the question of whether an “uncloneable bit” exists. In fact, a recent preprint [ 7 ] has claimed to solve the problem with an approach based on a random 2-design. On the other hand, if we require many-time (reusable) security, where a single secret key can be used to encrypt several messages, 1 1 1 In particular, more bits than the size of the secret key. then UE provably requires cryptographic assumptions. A recent work [ 6 ] has established that reusable UE lives in “microcrypt”, a world of very unstructured cryptography that plausibly remains secure even in the event that P = NP. Importantly, this result does not rely on the existence of an information-theoretic uncloneable bit. However, security is argued in an idealized model, namely the Haar random oracle model, and does not say anything about the existence of (reusable) UE from concrete microcrypt assumptions. In this note, we seek to minimize the concrete assumptions under which reusable UE exists, assuming the existence of an information-theoretic uncloneable bit. While some previous works have studied similar questions, e.g. [ 4 , 14 ] , we systematize and generalize existing results, establishing a clearer picture of reusable UE and the assumptions on which it relies. 1.1 Results First, we show that if an uncloneable bit exists, then reusable UE is equivalent to reusable (plain) SKE. In fact, we consider a generalization of the typical 1-to-2 UE security game to any t<t^{\prime} , and show the equivalence between reusable t\to t^{\prime} UE and reusable SKE, assuming the existence of a t\to t^{\prime} uncloneable bit. Theorem 1.1 (Informal) . For any t^{\prime}>t , assuming the existence of a t\to t^{\prime} uncloneable bit and reusable SKE, there exists reusable t\to t^{\prime} UE. Next, we consider variants of the definition of uncloneable encryption. In particular, the flavor of UE that results from the above theorem statement comes with the following caveats. • The encryption and decryption key are different. That is, one needs “more” information to encrypt than decrypt, and the cloning game adversaries are only given what is necessary to decrypt. A stronger notion of UE is one in which the encryption and decryption key are identical, which we refer to as “normal form” UE. • The t challenge ciphertexts given to the cloning adversary are mixed states , sampled independently as encryptions of the same message m . One could alternatively consider a notion where a single encryption of m is sampled and the adversary is given t identical copies of this state, which we refer to as UE with “identical copy” security. We next show how to obtain normal form UE as well as UE with identical copy security, though we do not know how to do so from the generic assumption of reusable SKE. Instead, we assume the existence of pseudorandom unitaries , which is nevertheless a standard microcrypt assumption. Theorem 1.2 (Informal) . For any t^{\prime}>t , assuming the existence of a t\to t^{\prime} uncloneable bit and pseudorandom unitaries, there exists reusable normal form t\to t^{\prime} UE with identical copy security . 1.2 Techniques These results follow from two main compilers, which we first introduce below and then describe in some more detail. While each has appeared in some form in the literature previously, we adapt and generalize the techniques in order to establish the theorems stated above. Plaintext expansion via DQRE. [ 14 ] introduced a compiler that bootstraps one-time UE for bits to one-time UE for any length of message, assuming a type of quantum garbling scheme called decomposable quantum randomized encoding (DQRE). In this work, we propose a variant of the compiler that works in the more general t\to t^{\prime} setting, and observe that the notion of DQRE required to instantiate the compiler exists from any reusable SKE scheme. We further establish that our modified compiler directly achieves reusable t\to t^{\prime} security, yielding our first main theorem ( Theorem 1.1 ). The most straightforward application of this compiler yields a scheme that is not normal form. We show how to further tweak the compiler to obtain a normal form reusable t\to t^{\prime} UE scheme, additionally assuming the existence of reusable SKE with pseudorandom ciphertexts , which follows from pseudorandom unitaries (PRUs), or even pseudorandom function-like states [ 5 ] . These results are presented in Section 3 . Identical copy security via the purification channel. Finally, we consider recent results establishing the feasibility of identical copy security [ 1 , 12 ] that are based on the existence of one-way functions. Building on recent results in quantum learning theory [ 17 , 15 , 13 ] , we show that the assumption underlying these approaches can be weakened to the existence of PRUs. This allows us to obtain reusable UE with identical copy security (that is still normal form) assuming an uncloneable bit and PRUs, establishing our second main theorem ( Theorem 1.2 ). This is detailed in Section 4 . 1.2.1 Sketch of plaintext expansion As mentioned above, [ 14 ] shows how to construct 1\to 2 encryption for \lambda -bit messages from a 1\to 2 uncloneable bit using a tool known as a decomposable quantum randomized encoding (DQRE). Essentially, DQRE is a procedure that takes a circuit C and (potentially

Read the complete text