International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Hidden Cosets and Applications to Unclonable Cryptography

Authors:
Andrea Coladangelo , University of California, Berkeley
Jiahui Liu , The University of Texas at Austin
Qipeng Liu , Princeton University
Mark Zhandry , Princeton University and NTT Research
Download:
DOI: 10.1007/978-3-030-84242-0_20 (login may be required)
Search ePrint
Search Google
Conference: CRYPTO 2021
Abstract: 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 propose a generalization of hidden subspace states to hidden coset states. We study different 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 monogamy-of-entanglement property. Assuming this conjecture is true, we remove the requirement for extractable witness encryption in our unclonable decryption construction. As potential evidence in support of the conjecture, we prove a weaker version of this monogamy property, which we believe will still be of independent interest. * Finally, we give the first construction of a copy-protection scheme for pseudorandom functions (PRFs) in the plain model. Our scheme is secure either assuming iO and extractable witness encryption, or iO, LWE 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.
Video from CRYPTO 2021
BibTeX
@inproceedings{crypto-2021-31207,
  title={Hidden Cosets and Applications to Unclonable Cryptography},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-84242-0_20},
  author={Andrea Coladangelo and Jiahui Liu and Qipeng Liu and Mark Zhandry},
  year=2021
}