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 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.