Paper 2021/946

Hidden Cosets and Applications to Unclonable Cryptography

Andrea Coladangelo, Jiahui Liu, Qipeng Liu, and Mark Zhandry


In 2012, Aaronson and Christiano introduced the idea of hidden subspace states to build public-key quantum money [STOC '12]. Since then, this idea has been applied to realize several other cryptographic primitives which enjoy some form of unclonability. In this work, we study a generalization of hidden subspace states to hidden coset states. This notion was considered independently by Vidick and Zhang [Eurocrypt '21], in the context of proofs of quantum knowledge from quantum money schemes. We explore unclonable properties of coset states and several applications: * We show that, assuming indistinguishability obfuscation (iO), hidden coset states possess a certain direct product hardness property, which immediately implies a tokenized signature scheme in the plain model. Previously, a tokenized signature scheme was known only relative to an oracle, from a work of Ben-David and Sattath [QCrypt '17]. * Combining a tokenized signature scheme with extractable witness encryption, we give a construction of an unclonable decryption scheme in the plain model. The latter primitive was recently proposed by Georgiou and Zhandry [ePrint '20], who gave a construction relative to a classical oracle. * We conjecture that coset states satisfy a certain natural (information-theoretic) monogamy-of-entanglement property. Assuming this conjecture is true, we remove the requirement for extractable witness encryption in our unclonable decryption construction, by relying instead on compute-and-compare obfuscation for the class of unpredictable distributions. This conjecture was later proved by Culf and Vidick in a follow-up work. * Finally, we give a construction of a copy-protection scheme for pseudorandom functions (PRFs) in the plain model. Our scheme is secure either assuming iO, OWF and extractable witness encryption, or assuming iO, OWF, compute-and-compare obfuscation for the class of unpredictable distributions, and the conjectured monogamy property mentioned above. This is the first example of a copy-protection scheme with provable security in the plain model for a class of functions that is not evasive.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2021
quantum cryptographycopy-protectioncoset state
Contact author(s)
andrea coladangelo @ gmail com
jiahui @ utexas edu
qipengl @ cs princeton edu
2022-01-09: revised
2021-07-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Andrea Coladangelo and Jiahui Liu and Qipeng Liu and Mark Zhandry},
      title = {Hidden Cosets and Applications to Unclonable Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2021/946},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.