Hidden Cosets and Applications to Unclonable Cryptography

Andrea Coladangelo, Jiahui Liu, Qipeng Liu, Mark Zhandry

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Proceedings
EditorsTal Malkin, Chris Peikert
PublisherSpringer Science and Business Media Deutschland GmbH
Pages556-584
Number of pages29
ISBN (Print)9783030842413
DOIs
StatePublished - 2021
Event41st Annual International Cryptology Conference, CRYPTO 2021 - Virtual, Online
Duration: Aug 16 2021Aug 20 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12825 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference41st Annual International Cryptology Conference, CRYPTO 2021
CityVirtual, Online
Period8/16/218/20/21

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Hidden Cosets and Applications to Unclonable Cryptography'. Together they form a unique fingerprint.

Cite this