CS Paper Radar

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

Andrea Coladangelo, Qipeng Liu, Ziyi Xie

cs.CR quant-ph ·submitted 2026-08-18 10:46 UTC · v2

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.

Comment
34 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Decisional Monogamy-of-Entanglement for Coset States and Applications to Unclonable Cryptography with Correlated Challenges

cs.CR quant-ph ·2026-08-19 ·Amit Behera, Alper Cakan, Vipul Goyal
hot direction similarity 0.64
Abstract

A main application of quantum information in cryptography is copy-protection, where we encode a functionality (such as a decryption key or software) into a reusable quantum state so that it cannot be split into two adversaries (called freeloaders) that both remain useful. Previous works have only shown security for independently sampled challenges for the two adversaries. A competing natural security notion is identical-challenge security where the adversaries receive the same challenge. This notion has many real-life applications and connections to other fundamental primitives such as unclonable bits (i.e. unclonable encryption) and unclonable lockboxes (i.e. copy-protection of point functions). Despite its importance and numerous attempts, achieving identical-challenge security in the plain model has remained open. We first make progress on the definitional foundations of copy-protection by introducing natural copy-protection security definitions that imply the previous ones (including identical-challenge security) and better capture the security intuitions and real-life use cases; and we also characterize the relationship between the previous definitions. Then, we show how to achieve in the plain model our new stronger definitions for copy-protection of general classes of functionalities. In particular, we resolve the long-standing open questions of copy-protection of point functions, copy-protection of compute-and-compare programs, and identical-challenge secure copy-protection of decryption keys and all puncturable functionalities. Our technical core is a new decisional monogamy-of-entanglement result for coset states, which both allows us to achieve our new results, and also significantly simplifies and unifies unclonable cryptography proofs. We believe this will have further applications and may be of independent interest.

0.25

Indistinguishability Lifting for Keyed Oracles, Compressed Ideal Cipher, and More Applications

cs.CR quant-ph ·2026-10-03 ·Ritam Bhaumik, Yu-Hsuan Huang
theoryhot direction similarity 0.63
Abstract

Cryptographic security proofs often involve an adversary interacting with a larger, keyed oracle that consists of (potentially exponentially) many independent instances of a smaller, base oracle. However, showing quantum indistinguishability between two such keyed oracles can be tricky, since a single query made by an adversary may involve a superposition that covers all instances of the base oracles simultaneously. In this paper, we establish a generic indistinguishability lifting theorem of the following form: if the two base oracles are indistinguishable under quantum queries, then their corresponding keyed oracles are too, up to an O(q^2) multiplicative loss in distinguishing advantage, where q is the number of queries made by the adversary. Our lifting theorem applies to both statistical and computational settings, and to oracles that are stateful as well. It is also optimal in that it matches the obvious Grover search attack for a certain (contrived) choice of oracles. As an immediate application, we extend Carolan's compressed permutation oracle to an efficiently implementable compressed ideal cipher, and use it to prove preimage resistance of the Davies-Meyer compression function in the quantum ideal cipher model. Thanks to our lifting theorem, the soundness of our compressed ideal cipher reduces to that of Carolan's oracle, and any further improvement on the latter would automatically carry over to the former. As our second application, we give a modular construction that doubles the message length of any quantum-secure strong pseudorandom permutation. Along the way, we show that an existing two-round tweakable Feistel construction is indistinguishable from a random permutation under quantum bidirectional queries. This is done via a dedicated polynomial-method argument, which may be of independent interest.

0.23

Constant-Rate Certified Deletion

cs.CR quant-ph ·2026-10-02 ·Kai-Min Chung, Tzu-Hsiang Huang, Wei-Hsiang Hung, Shota Yamada
top venue similarity 0.61
Abstract

We present a unified framework for upgrading a broad class of cryptographic primitives to support constant-rate certified deletion. Previous constructions require a linear number of qubits per encrypted bit of certified-deletable plaintext. In contrast, we obtain the first constant-rate constructions in the plain model that achieve certified deletion while preserving everlasting security. Our approach applies to a wide range of "all-or-nothing"-type primitives based on BB84-style encodings, including commitment schemes, public-key encryption, attribute-based encryption, and fully homomorphic encryption. Beyond this class, we also obtain constant-rate certified deletion for primitives built from subspace coset states, such as blind delegation, secure software leasing, functional encryption, and differing-inputs iO, and CCA-PKE. Importantly, our framework does not introduce any additional assumptions beyond those required by the underlying certified deletion primitives. Finally, under the hardness of SIS, we show that public verifiability can be incorporated into BB84- and coset-based certified deletion. In combination with our constant-rate constructions, this yields publicly verifiable certified deletion schemes with constant rate.

0.38

Computational Cryptography from Pseudoentanglement

cs.CR quant-ph ·2026-09-24 ·Ilia Ryzov, Manuel Goulão, Faedi Loulidi, David Elkouss
similarity 0.60
Abstract

The advent of pseudoentanglement and computational entanglement theory bootstrapped a wave of research at the intersection of computer science and information theory. In parallel, computational cryptography has undergone substantial development, prompted by the introduction of pseudorandom states and followed by the establishment of a baseline for the computational hardness required for quantum cryptography, from which EFI pairs emerge as a central primitive. We study the connection between pseudoentanglement and computational cryptography through EFI pairs. Our goal is to enable the use of resources arising from computational entanglement theory in the field of cryptography. For this, we establish the relation between operational instances of pseudoentanglement and the hierarchy of minimal assumptions for computational cryptography. We show that the existence of pseudoentanglement under two different operational definitions, with efficient state generation, is a sufficient condition for the existence of EFI pairs. Combined with a previously established result that the converse also holds under the second definition, this allows us to also demonstrate their equivalence. This places pseudoentanglement alongside other minimal assumptions in cryptography, not only offering an alternative perspective on this fundamental problem, but also building a bridge that allows insights from either area to inform the other. While proving these theorems, we introduce and demonstrate technical lemmas in quantum information and computational entanglement theory, relating the computational entanglement measures to the distance between states, establishing distinguishing conditions for mixtures of two families given pairwise distances between their states, and demonstrating the first continuity relation for a computational entanglement measure.

0.26

A Broadcast Authenticated Encryption with Keyword Search in the Standard Model: Tightly Secure in Multi-User, Multi-Challenge Settings

cs.CR ·2026-08-29 ·Sayantan Mukherjee
theory similarity 0.60
Abstract

However, no known work considered the functionality requirement in its most realistic setting. We propose a new security definition of BAEKS in the multi-user (with adaptive corruptions) and multi-challenge (both in terms of ciphertext and trapdoor in an interleaved manner) settings. We also study the question of the unforgeability of BAEKS. In fact, our strong hiding requirement already implies a significant amount of unforgeability. We then propose a new BAEKS construction in the bilinear pairing groups. We prove this scheme achieves adaptive tight full-hiding security under (almost) standard MDDH assumptions. Restricting our BAEKS construction for a single receiver also gives an efficient and tightly secure PAEKS construction. We further run experiments to implement and evaluate our scheme.

0.22

Succinct Arguments for QMA from Collapsing Hash Functions

cs.CR quant-ph ·2026-09-28 ·James Bartusek, Giulio Malavolta
theoryhot direction similarity 0.60
Abstract

We prove the existence of succinct arguments for QMA, assuming only the existence of collapsing hash functions. This is the first scheme that relies only on unstructured ``Minicrypt'' assumptions, which are not known to imply public-key encryption. Our main technical contribution is a quantum-succinct \emph{claw-state generation} protocol that allows us to bootstrap a small number of quantum correlations into an arbitrarily large number of claw-state correlations, using classical communication only. This improves upon the work of [Zhang, STOC 2021], having better round complexity, a proof in the standard model, and being overall much simpler. This yields a quantum-succinct blind delegation of quantum computation protocol from one-way functions, which we plug into the communication-compression compiler of [Bartusek, Liu, and Malavolta, EUROCRYPT 2026] to obtain succinct arguments for QMA.

0.24

Semi-Quantum Cryptography with Certified Deletion

cs.CR quant-ph ·2026-09-30 ·Yael Tauman Kalai, Justin Raizes
similarity 0.59
Abstract

Certified deletion allows a client to upload encrypted data to a server as a quantum state, then later request that the server delete their data and detect whether the server complies. If verification passes, then the data on the server will remain hidden even if the decryption key is later leaked. In publicly verifiable certified deletion, the verification key is published so that anyone may check for deletion compliance. In this work, we give a general compiler to publicly verifiable certified deletion that allows the client to initially upload the *quantum* ciphertext using purely *classical* communication, assuming the post-quantum hardness of LWE in the plain model. Our approach can be applied to a wide variety of primitives, including commitments and public-key, attribute-based, identity-based, and fully-homomorphic encryption. Moreover, our constructions allow the client to classically manage the encrypted data beyond just verifying its deletion. The classical client may non-destructively audit the ciphertext via a Proof of No Intrusion to check whether it has been leaked to a third party. The classical client may also retrieve the data while simultaneously verifying its deletion from the server. Thus, they do not have to choose between retrieving the data and protecting it against future key leakage. As our core technical contribution, we give a classical-communication protocol and simulation technique that allows adapting purification-based security arguments for BB84-style states which are prepared through classical interaction. It makes the required purification available in a hybrid experiment, despite the classical transcript uniquely determining the prepared state in a real execution.

0.25

Rate 1/5 Non-Malleable Codes against Entangled Split-State Tampering

cs.CR quant-ph ·2026-09-30 ·Naresh Goud Boddu
similarity 0.59
Abstract

We construct efficient information-theoretic non-malleable codes for classical messages that are secure against two noncommunicating local quantum tampering operations with arbitrary pre-shared entanglement. For every sufficiently small fixed $ξ>0$ and all sufficiently large first-share lengths $n$, the codes have rate at least $1/5-ξ$, perfect correctness, and error $2^{-n^{Ω(1)}}$. Security holds for every message, with a single message-independent simulator for each attack. This resolves the constant-rate question for worst-case classical messages in the entangled two-split-state model. Our construction builds on the permutation-based two-split construction of Batra, Boddu, and Jain, which achieves rate approaching $1/5$ for uniformly random messages. We retain their architecture but replace the uniform message input to the permutation with a prescribed message concatenated with fresh uniform padding. Our main contribution is a worst-case security reduction for this modification.

0.35