TY - GEN
T1 - Hidden Cosets and Applications to Unclonable Cryptography
AU - Coladangelo, Andrea
AU - Liu, Jiahui
AU - Liu, Qipeng
AU - Zhandry, Mark
N1 - Funding Information:
Acknowledgements. A.C. is supported by the Simons Institute for the Theory of Computing, through a Quantum Postdoctoral Fellowship. J. L., Q. L. and M. Z. are supported by the NSF. J. L. is also supported by Scott Aaronson’s Simons Investigator award. The authors are grateful for the support of the Simons Institute, where this collaboration was initiated.
Funding Information:
A.C. is supported by the Simons Institute for the Theory of Computing, through a Quantum Postdoctoral Fellowship. J. L., Q. L. and M. Z. are supported by the NSF. J. L. is also supported by Scott Aaronson?s Simons Investigator award. The authors are grateful for the support of the Simons Institute, where this collaboration was initiated.
Publisher Copyright:
© 2021, International Association for Cryptologic Research.
PY - 2021
Y1 - 2021
N2 - 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 (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. As potential evidence in support of the monogamy 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, 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.
AB - 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 (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. As potential evidence in support of the monogamy 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, 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.
UR - http://www.scopus.com/inward/record.url?scp=85115129881&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85115129881&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-84242-0_20
DO - 10.1007/978-3-030-84242-0_20
M3 - Conference contribution
AN - SCOPUS:85115129881
SN - 9783030842413
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 556
EP - 584
BT - Advances in Cryptology – CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Proceedings
A2 - Malkin, Tal
A2 - Peikert, Chris
PB - Springer Science and Business Media Deutschland GmbH
T2 - 41st Annual International Cryptology Conference, CRYPTO 2021
Y2 - 16 August 2021 through 20 August 2021
ER -