Omri Shmueli

One-shot signatures (OSS) were defined by Amos, Georgiou, Kiayias, and Zhandry (STOC'20). These allow for signing exactly one message, after which the signing key self-destructs, preventing a second message from ever being signed. While such an object is impossible classically, Amos et al observe that OSS may be possible using quantum signing keys by leveraging the no-cloning principle. OSS has since become an important conceptual tool with many applications in decentralized settings and for quantum cryptography with classical communication. OSS are also closely related to separations between classical-binding and collapse-binding for post-quantum hashing and commitments. Unfortunately, the only known OSS construction due to Amos et al. was only justified in a classical oracle model, and moreover their justification was ultimately found to contain a fatal bug. Thus, the existence of OSS, even in a classical idealized model, has remained open. We give the first standard-model OSS, with provable security assuming (sub-exponential) indistinguishability obfuscation (iO) and LWE. This also gives the first standard-model separation between classical and collapse-binding post-quantum commitments/hashing, solving a decade-old open problem. Along the way, we also give the first construction with unconditional security relative to a classical oracle. To achieve our standard-model construction, we develop a notion of permutable pseudorandom permutations (permutable PRPs), and show how they are useful for translating oracle proofs involving random permutations into obfuscation-based proofs. In particular, obfuscating permutable PRPs gives a trapdoor one-way permutation that is \emph{full-domain}, solving another decade-old-problem of constructing this object from (sub-exponential) iO and one-way functions.

Recent work of Bostanci, Nehoran, Zhandry (STOC'25, QIP'25) formalized the notion of quantum fire: A quantum state that can be cloned efficiently but cannot be converted to a classical string. Nehoran and Zhandry (QIP'23) gave a construction of quantum fire relative to an (inefficient) unitary quantum oracle, and proved its correctness and security. Bostanci et al (STOC'25, QIP'25) gave a candidate construction of quantum fire based on cryptographic group action assumptions, and proved its correctness. However, they do not have a proof of security, and the security is only conjectured without any justification at all. In this work, we give the first construction of (public-key) quantum fire relative to a classical oracle, and prove its correctness and security. This resolves the open question posed by Bostanci et al (STOC'25, QIP'25) and Nehoran and Zhandry (QIP'23). Further, assuming existence of one-way functions, our scheme can also be made efficient. We note that, even in the unitary quantum oracle setting, no efficient quantum fire scheme existed: Nehoran-Zhandry show that their unitary oracle cannot be made efficient. Implications to Physics: In quantum mechanics, various fundamental principles called no-go properties exist, such as no-cloning theorem, no-hiding theorem, no-deleting theorem, no-telegraphing theorem and so on. Most of these no-go properties have been shown to be equivalent to each other. However, our result gives the first (classical oracle) separation between no-go properties of quantum mechanics! Our result means that, relative to a classical oracle, no-telegraphing does not imply no-cloning. Note that, in the information-theoretic setting, no-cloning and no-telegraphing are equivalent. Our result means that the equivalency of the fundamental no-go principles of quantum mechanics that we take for granted might not hold in a computational world!

Two fundamental properties of quantum states that quantum information theory explores are pseudorandomness and provability of destruction. We introduce the notion of quantum pseudorandom states with proofs of destruction (PRSPD) that combines both these properties. Like standard pseudorandom states (PRS), these are efficiently generated quantum states that are indistinguishable from random, but they can also be measured to create a classical string. This string is verifiable (given the secret key) and certifies that the state has been destructed. We show that, similarly to PRS, PRSPD can be constructed from any post-quantum one-way function. As far as the authors are aware, this is the first construction of a family of states that satisfies both pseudorandomness and provability of destruction. We show that many cryptographic applications that were shown based on PRS variants using quantum communication can be based on (variants of) PRSPD using only classical communication. This includes symmetric encryption, message authentication, one-time signatures, commitments, and classically verifiable private quantum coins.

We study post-quantum zero-knowledge (classical) protocols that are sound against quantum resetting attacks. Our model is inspired by the classical model of resetting provers (Barak-Goldreich-Goldwasser-Lindell, FOCS `01), providing a malicious efficient prover with oracle access to the verifier's next-message-function, fixed to some initial random tape; thereby allowing it to effectively reset (or equivalently, rewind) the verifier. In our model, the prover has quantum access to the verifier's function, and in particular can query it in superposition. The motivation behind quantum resettable soundness is twofold: First, ensuring a strong security guarantee in scenarios where quantum resetting may be possible (e.g., smart cards, or virtual machines). Second, drawing intuition from the classical setting, we hope to improve our understanding of basic questions regarding post-quantum zero knowledge. We prove the following results: Black-Box Barriers: Quantum resetting exactly captures the power of black-box zero knowledge quantum simulators. Accordingly, resettable soundness cannot be achieved in conjunction with black-box zero knowledge, except for languages in \BQP. Leveraging this, we prove that constant-round public-coin, or three message, protocols cannot be black-box post-quantum zero-knowledge. For this, we show how to transform such protocols into quantumly resettably sound ones. The transformations are similar to classical ones, but their analysis is significantly more challenging due to the essential difference between classical and quantum resetting. A Resettably-Sound Non-Black-Box Zero-Knowledge Protocol: Under the (quantum) Learning with Errors assumption and quantum fully-homomorphic encryption, we construct a post-quantum resettably-sound zero knowledge protocol for \NP. We rely on non-black-box simulation techniques, thus overcoming the black-box barrier for such protocols. From Resettable Soundness to The Impossibility of Quantum Obfuscation: Assuming one-way functions, we prove that any quantumly-resettably-sound zero-knowledge protocol for \NP implies the impossibility of quantum obfuscation. Combined with the above result, this gives an alternative proof to several recent results on quantum unobfuscatability.

We construct the first constant-round zero-knowledge classical argument for NP secure against quantum attacks. We assume the existence of Quantum Fully Homomorphic Encryption and other standard primitives, known based on the Learning with Errors Assumption for quantum algorithms. As a corollary, we also obtain the first constant-round zero-knowledge quantum argument for QMA. At the heart of our protocol is a new no-cloning non-black-box simulation technique.

We construct the first constant-round zero-knowledge classical argument for NP secure against quantum attacks. We assume the existence of Quantum Fully Homomorphic Encryption and other standard primitives, known based on the Learning with Errors Assumption for quantum algorithms. As a corollary, we also obtain the first constant-round zero-knowledge quantum argument for QMA. At the heart of our protocol is a new no-cloning non-black-box simulation technique.

Efficiently sampling a quantum state that is hard to distinguish from a truly random quantum state is an elementary task in quantum information theory that has both computational and physical uses. This is often referred to as pseudorandom (quantum) state generator, or PRS generator for short. In existing constructions of PRS generators, security scales with the number of qubits in the states, i.e. the (statistical) security parameter for an n-qubit PRS is roughly n. Perhaps counter-intuitively, n-qubit PRS are not known to imply k-qubit PRS even for k<n. Therefore the question of \emph{scalability} for PRS was thus far open: is it possible to construct n-qubit PRS generators with security parameter m for all n, m. Indeed, we believe that PRS with tiny (even constant) n and large m can be quite useful. We resolve the problem in this work, showing that any quantum-secure one-way function implies scalable PRS. We follow the paradigm of first showing a \emph{statistically} secure construction when given oracle access to a random function, and then replacing the random function with a quantum-secure (classical) pseudorandom function to achieve computational security. However, our methods deviate significantly from prior works since scalable pseudorandom states require randomizing the amplitudes of the quantum state, and not just the phase as in all prior works. We show how to achieve this using Gaussian sampling.