### Hidden Cosets and Applications to Unclonable Cryptography

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

##### 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 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)
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2021
Keywords
quantum cryptographycopy-protectioncoset state
Contact author(s)
jiahui @ utexas edu
qipengl @ cs princeton edu
History
2022-01-09: revised
See all versions
Short URL
https://ia.cr/2021/946

CC BY

BibTeX

@misc{cryptoeprint:2021/946,
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{https://eprint.iacr.org/2021/946}},
url = {https://eprint.iacr.org/2021/946}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.