Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2608.17629

Unclonable encryption from BB84 states: a simultaneous Goldreich-Levin reduction

Andrea Coladangelo, Qipeng Liu, Ziyi Xie

quant-phcs.CRSubmitted Aug 18, 2026• Announced Aug 19, 2026• 0 citations
v1 · Aug 18, 2026v2 · Oct 5, 2026
arXivHTMLPDF

Abstract

Goldreich-Levin reductions are ubiquitous in cryptography: they convert an algorithm capable of guessing $\langle r, m \rangle$ (mod $2$) for a hidden string $m$ and a random challenge $r$, to one that is capable of extracting the entirety of $m$. Here, we describe a "simultaneous" Goldreich-Levin reduction for two entangled parties who are capable of guessing $\langle r, m \rangle$ given uniformly random identical challenges $r$. This allows to upgrade any unclonable encryption scheme satisfying "search" security to one satisfying the gold standard of unclonable "indistinguishability". As a corollary, we show that the simplest candidate unclonable encryption scheme from BB84 states satisfies unclonable indistinguishability. This result was discovered by GPT-5.6 Ultra after a few interactions. Our prompts included recent results on unclonable encryption by Ananth and Sahai, and Ragavan.

Comments
33 pages

Related papers

Efficient Unclonable Encryption from Pauli Eigenstates

Seyoon Ragavan

We give, to our knowledge, the first plain-model, one-time information-theoretically secure, efficient unclonable encryption scheme for one classical bit. Previous work by Bhattacharyya and Culf (Nature Physics, 2026) and Bhattacharyya, Broadbent, and Culf either only showed $1/\mathsf{poly}(λ)$ security loss or required inefficient encryption/decryption operations. We avoid both of these caveats; in doing so, we obtain (to our knowledge) the first plain-model construction of many-time secure $1 \to 2$ unclonable encryption for arbitrary polynomial-length messages, assuming the existence of pseudorandom function-like states (Bartusek and Goldin). The key is a uniformly random non-identity phase-free Pauli on $n$ qubits, and bit $a$ is encrypted as a random $(-1)^a$ eigenstate of that Pauli. The scheme is exponentially secure; we prove that the probability that both receivers recover the bit is at most $\frac{1}{2}+\frac{1}{2}\sqrt{{2^n}/({4^n-1})} = \frac{1}{2} + O\left(2^{-n/2}\right).$ By a lower bound due to Broadbent, Culf, and Rochette, this is the best probability bound achievable with $n$-qubit ciphertexts (up to the constant hidden in the $O(\cdot)$). The main conceptual idea is to leverage, in a precise spectral sense, the balanced commutation-anticommutation structure of the Pauli group. The proof is intricate but completely elementary and makes use of standard spectral bound techniques. The main technical workhorse is a standalone linear-algebraic lemma that informally relates the positivity of two different operators, each capturing the intuition that if the two receivers can individually decrypt unusually often then they must also disagree often. GPT-5.6 Sol Ultra found this proof in an extended conversation with the author and drafted a preliminary version of this paper. The author is fully accountable for the correctness of this paper.

quant-pharXiv:2607.21811•Jul 27, 2026•0 citations

Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography

Prabhanjan Ananth, Fatih Kaleoglu, Henry Yuen

Unclonable cryptography is concerned with leveraging the no-cloning principle to build cryptographic primitives that are otherwise impossible to achieve classically. Understanding the feasibility of unclonable encryption, one of the key unclonable primitives, satisfying indistinguishability security in the plain model has been a major open question in the area. So far, the existing constructions of unclonable encryption are either in the quantum random oracle model or are based on new conjectures. We present a new approach to unclonable encryption via a reduction to a novel question about nonlocal quantum state discrimination: how well can non-communicating -- but entangled -- players distinguish between different distributions over quantum states? We call this task simultaneous state indistinguishability. Our main technical result is showing that the players cannot distinguish between each player receiving independently-chosen Haar random states versus all players receiving the same Haar random state. We leverage this result to present the first construction of unclonable encryption satisfying indistinguishability security, with quantum decryption keys, in the plain model. We also show other implications to single-decryptor encryption and leakage-resilient secret sharing.

arXiv:2405.10274•Leibniz international proceedings in informatics•May 16, 2024•0 citations

Pauli Encodings & Unclonable Encryption

Pierre Botteron, Sébastien Designolle, Omar Fawzi

The unclonable bit question asks whether quantum encryption can prevent an adversary from producing two systems that both reveal the plaintext once the key is disclosed. We introduce and study Pauli Encodings, a simple class of one-bit encryption schemes whose ciphertexts are normalized eigenspace projectors of Pauli strings. For every Pauli Encoding with K Pauli strings, we prove a universal lower bound $1/2+1/(2\sqrt{K})$ on the optimal monogamy-of-entanglement winning probability, together with sharper bounds for several structured families. We then establish two limitations of natural approaches to unclonable security. First, if the Pauli strings are restricted to strings of X and Z of length n, the encoding is not secure. Second, we identify a universal 3/4 obstruction showing that arguments based only on pairwise guessing marginals cannot establish unclonable-indistinguishable security. When the Pauli strings all pairwise anticommute, the protocol becomes the one studied in [Quantum 10, 2157 (2026)]. We exploit the symmetry of this protocol to solve the third level of the natural semidefinite programming relaxation obtaining an asymptotic upper bound of approximately 0.5556 on the winning probability. Finally, we prove strong unclonable-indistinguishable security against bounded-local-dimension adversaries and strong indistinguishability security for several efficient Pauli families. First-level NPA computations provide additional numerical evidence towards the strong unclonable-indistinguishable security.

quant-pharXiv:2607.28602•Jul 31, 2026•0 citations

Unconditional Unclonable Encryption

Prabhanjan Ananth, Seyoon Ragavan, Amit Sahai

We give an unconditional construction of information-theoretically secure one-time private-key unclonable encryption for one-bit messages, with efficient encryption and decryption and exponentially small unclonable-indistinguishability advantage. Previous work by Bhattacharyya and Culf (Nature Physics, 2026) and Bhattacharyya, Broadbent, and Culf (arXiv:2603.08916) either only showed inverse-polynomial security loss or required inefficient encryption/decryption operations; we avoid both of these caveats. Our scheme's key is a uniformly random non-identity phase-free Pauli on $n$ qubits, and bit $a$ is encrypted as a random $(-1)^a$ eigenstate of that Pauli. We prove that the probability that both receivers recover the bit is at most $1/2 + O\left(2^{-n/2}\right).$ By a lower bound due to Broadbent, Culf, and Rochette (arXiv:2510.00903), this is the best probability bound achievable with $n$-qubit ciphertexts while ensuring perfect correctness (up to the constant hidden in the $O(\cdot)$).

quant-pharXiv:2607.21551•Jul 24, 2026•0 citations

Unclonable Encryption in the Haar Random Oracle Model

James Bartusek, Eli Goldin

We construct unclonable encryption (UE) in the Haar random oracle model, where all parties have query access to $U,U^\dagger,U^*,U^T$ for a Haar random unitary $U$. Our scheme satisfies the standard notion of unclonable indistinguishability security, supports reuse of the secret key, and can encrypt arbitrary-length messages. That is, we give the first evidence that (reusable) UE, which requires computational assumptions, exists in "microcrypt", a world where one-way functions may not exist. As one of our central technical contributions, we build on the recently introduced path recording framework to prove a natural ``unitary reprogramming lemma'', which may be of independent interest.

cs.CRCross-listedarXiv:2603.11437•Mar 13, 2026•0 citations

A Note on Boosting Uncloneable Encryption in Microcrypt

James Bartusek, Eli Goldin

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' uncloneable bit exists, then the following implications hold. 1. If many-time secure symmetric key encryption exists, then many-time secure t -> t' 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' 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 = NP.

cs.CRCross-listedarXiv:2605.27647•May 28, 2026•0 citations
Goldreich-Levin reductions are ubiquitous in cryptography: they convert an algorithm capable of guessing ⟨r,m⟩\langle r, m \rangle⟨r,m⟩ (mod 222) for a hidden string mmm and a random challenge rrr, to one that is capable of extracting the entirety of mmm. Here, we describe a "simultaneous" Goldreich-Levin reduction for two entangled parties who are capable of guessing ⟨r,m⟩\langle r, m \rangle⟨r,m⟩ given uniformly random identical challenges rrr. This allows to upgrade any unclonable encryption scheme satisfying "search" security to one satisfying the gold standard of unclonable "indistinguishability". As a corollary, we show that the simplest candidate unclonable encryption scheme from BB84 states satisfies unclonable indistinguishability.
This result was discovered by GPT-5.6 Ultra after a few interactions. Our prompts included recent results on unclonable encryption by Ananth and Sahai, and Ragavan.
We give, to our knowledge, the first plain-model, one-time information-theoretically secure, efficient unclonable encryption scheme for one classical bit. Previous work by Bhattacharyya and Culf (Nature Physics, 2026) and Bhattacharyya, Broadbent, and Culf either only showed 1/poly(λ)1/\mathsf{poly}(λ)1/poly(λ) security loss or required inefficient encryption/decryption operations. We avoid both of these caveats; in doing so, we obtain (to our knowledge) the first plain-model construction of many-time secure 1→21 \to 21→2 unclonable encryption for arbitrary polynomial-length messages, assuming the existence of pseudorandom function-like states (Bartusek and Goldin). The key is a uniformly random non-identity phase-free Pauli on nnn qubits, and bit aaa is encrypted as a random (−1)a(-1)^a(−1)a eigenstate of that Pauli. The scheme is exponentially secure; we prove that the probability that both receivers recover the bit is at most 12+122n/(4n−1)=12+O(2−n/2).\frac{1}{2}+\frac{1}{2}\sqrt{{2^n}/({4^n-1})} = \frac{1}{2} + O\left(2^{-n/2}\right).21​+21​2n/(4n−1)​=21​+O(2−n/2). By a lower bound due to Broadbent, Culf, and Rochette, this is the best probability bound achievable with nnn-qubit ciphertexts (up to the constant hidden in the O(⋅)O(\cdot)O(⋅)). The main conceptual idea is to leverage, in a precise spectral sense, the balanced commutation-anticommutation structure of the Pauli group. The proof is intricate but completely elementary and makes use of standard spectral bound techniques. The main technical workhorse is a standalone linear-algebraic lemma that informally relates the positivity of two different operators, each capturing the intuition that if the two receivers can individually decrypt unusually often then they must also disagree often. GPT-5.6 Sol Ultra found this proof in an extended conversation with the author and drafted a preliminary version of this paper. The author is fully accountable for the correctness of this paper.
Unclonable cryptography is concerned with leveraging the no-cloning principle to build cryptographic primitives that are otherwise impossible to achieve classically. Understanding the feasibility of unclonable encryption, one of the key unclonable primitives, satisfying indistinguishability security in the plain model has been a major open question in the area. So far, the existing constructions of unclonable encryption are either in the quantum random oracle model or are based on new conjectures. We present a new approach to unclonable encryption via a reduction to a novel question about nonlocal quantum state discrimination: how well can non-communicating -- but entangled -- players distinguish between different distributions over quantum states? We call this task simultaneous state indistinguishability. Our main technical result is showing that the players cannot distinguish between each player receiving independently-chosen Haar random states versus all players receiving the same Haar random state. We leverage this result to present the first construction of unclonable encryption satisfying indistinguishability security, with quantum decryption keys, in the plain model. We also show other implications to single-decryptor encryption and leakage-resilient secret sharing.
The unclonable bit question asks whether quantum encryption can prevent an adversary from producing two systems that both reveal the plaintext once the key is disclosed. We introduce and study Pauli Encodings, a simple class of one-bit encryption schemes whose ciphertexts are normalized eigenspace projectors of Pauli strings. For every Pauli Encoding with K Pauli strings, we prove a universal lower bound 1/2+1/(2K)1/2+1/(2\sqrt{K})1/2+1/(2K​) on the optimal monogamy-of-entanglement winning probability, together with sharper bounds for several structured families. We then establish two limitations of natural approaches to unclonable security. First, if the Pauli strings are restricted to strings of X and Z of length n, the encoding is not secure. Second, we identify a universal 3/4 obstruction showing that arguments based only on pairwise guessing marginals cannot establish unclonable-indistinguishable security. When the Pauli strings all pairwise anticommute, the protocol becomes the one studied in [Quantum 10, 2157 (2026)]. We exploit the symmetry of this protocol to solve the third level of the natural semidefinite programming relaxation obtaining an asymptotic upper bound of approximately 0.5556 on the winning probability. Finally, we prove strong unclonable-indistinguishable security against bounded-local-dimension adversaries and strong indistinguishability security for several efficient Pauli families. First-level NPA computations provide additional numerical evidence towards the strong unclonable-indistinguishable security.
We give an unconditional construction of information-theoretically secure one-time private-key unclonable encryption for one-bit messages, with efficient encryption and decryption and exponentially small unclonable-indistinguishability advantage. Previous work by Bhattacharyya and Culf (Nature Physics, 2026) and Bhattacharyya, Broadbent, and Culf (arXiv:2603.08916) either only showed inverse-polynomial security loss or required inefficient encryption/decryption operations; we avoid both of these caveats. Our scheme's key is a uniformly random non-identity phase-free Pauli on nnn qubits, and bit aaa is encrypted as a random (−1)a(-1)^a(−1)a eigenstate of that Pauli. We prove that the probability that both receivers recover the bit is at most 1/2+O(2−n/2).1/2 + O\left(2^{-n/2}\right).1/2+O(2−n/2). By a lower bound due to Broadbent, Culf, and Rochette (arXiv:2510.00903), this is the best probability bound achievable with nnn-qubit ciphertexts while ensuring perfect correctness (up to the constant hidden in the O(⋅)O(\cdot)O(⋅)).
We construct unclonable encryption (UE) in the Haar random oracle model, where all parties have query access to U,U†,U∗,UTU,U^\dagger,U^*,U^TU,U†,U∗,UT for a Haar random unitary UUU. Our scheme satisfies the standard notion of unclonable indistinguishability security, supports reuse of the secret key, and can encrypt arbitrary-length messages. That is, we give the first evidence that (reusable) UE, which requires computational assumptions, exists in "microcrypt", a world where one-way functions may not exist. As one of our central technical contributions, we build on the recently introduced path recording framework to prove a natural ``unitary reprogramming lemma'', which may be of independent interest.
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' uncloneable bit exists, then the following implications hold. 1. If many-time secure symmetric key encryption exists, then many-time secure t -> t' 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' 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 = NP.