Paper 2023/1841
Unclonable Cryptography with Unbounded Collusions
Abstract
Quantum no-cloning theorem gives rise to the intriguing possibility of quantum copy protection where we encode a program in a quantum state such that a user in possession of $k$ such states cannot create $k+1$ working copies. Introduced by Aaronson (CCC'09) over a decade ago, copy protection has proven to be notoriously hard to achieve. In this work, we construct public-key encryption and functional encryption schemes whose secret keys are copy-protected against unbounded collusions in the plain model (i.e. without any idealized oracles), assuming (post-quantum) subexponentially secure $\mathcal{iO}$, one-way functions and LWE. This resolves a long-standing open question of constructing fully collusion-resistant copy-protected functionalities raised by multiple previous works. Prior to our work, copy-protected functionalities were known only in restricted collusion models where either an a-priori bound on the collusion size was needed, in the plain model with the same assumptions as ours (Liu, Liu, Qian, Zhandry [TCC'22]), or adversary was only prevented from doubling their number of working programs, in a structured quantum oracle model (Aaronson [CCC'09]). We obtain our results through a novel technique which uses identity-based encryption to construct unbounded collusion resistant copy-protection schemes from $1\to2$ secure schemes. This is analogous to the technique of using digital signatures to construct full-fledged quantum money from single banknote schemes (Lutomirski et al. [ICS'09], Farhi et al. [ITCS'12], Aaronson and Christiano [STOC'12]). We believe our technique is of independent interest. Along the way, we also construct a puncturable functional encryption scheme whose master secret key can be punctured at all functions $f$ such that $f(m_0) \neq f(m_1)$. This might also be of independent interest.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- quantum cryptographycopy-protection
- Contact author(s)
-
acakan @ andrew cmu edu
vipul @ cmu edu - History
- 2023-12-01: approved
- 2023-11-30: received
- See all versions
- Short URL
- https://ia.cr/2023/1841
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1841, author = {Alper Çakan and Vipul Goyal}, title = {Unclonable Cryptography with Unbounded Collusions}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1841}, year = {2023}, url = {https://eprint.iacr.org/2023/1841} }