Quantum no-cloning theorem gives rise to the intriguing possibility of quantum copy protection where we encode a program or functionality in a quantum state such that a user in possession of k copies cannot create \(k+1\) copies, for any k. Introduced by Aaronson (CCC’09) over a decade ago, copy protection has proven to be notoriously hard to achieve. Previous work has been able to achieve copy-protection for various functionalities only in restricted models: (i) in the bounded collusion setting where \(k \rightarrow k+1\) security is achieved for a-priori fixed collusion bound k (in the plain model with the same computational assumptions as ours, by Liu, Liu, Qian, Zhandry [QIP’23]), or, (ii) only \(k \rightarrow 2k\) security is achieved (relative to a structured quantum oracle, by Aaronson [CCC’09]). In this work, we give the first unbounded collusion-resistant (i.e. multiple-copy secure) copy-protection schemes, answering the long-standing open question of constructing such schemes, raised by multiple previous works starting with Aaronson (CCC’09). More specifically, we obtain the following results. We obtain our results through a novel technique which uses identity-based encryption to construct multiple copy secure copy-protection schemes from \(\mathsf {1-copy} \rightarrow \mathsf {2-copy}\) secure schemes. We believe our technique is of independent interest. Along the way, we also obtain the following results.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Unclonable Cryptography with Unbounded Collusions and Impossibility of Hyperefficient Shadow Tomography

  • Alper Çakan,
  • Vipul Goyal

摘要

Quantum no-cloning theorem gives rise to the intriguing possibility of quantum copy protection where we encode a program or functionality in a quantum state such that a user in possession of k copies cannot create \(k+1\) copies, for any k. Introduced by Aaronson (CCC’09) over a decade ago, copy protection has proven to be notoriously hard to achieve. Previous work has been able to achieve copy-protection for various functionalities only in restricted models: (i) in the bounded collusion setting where \(k \rightarrow k+1\) security is achieved for a-priori fixed collusion bound k (in the plain model with the same computational assumptions as ours, by Liu, Liu, Qian, Zhandry [QIP’23]), or, (ii) only \(k \rightarrow 2k\) security is achieved (relative to a structured quantum oracle, by Aaronson [CCC’09]). In this work, we give the first unbounded collusion-resistant (i.e. multiple-copy secure) copy-protection schemes, answering the long-standing open question of constructing such schemes, raised by multiple previous works starting with Aaronson (CCC’09). More specifically, we obtain the following results. We obtain our results through a novel technique which uses identity-based encryption to construct multiple copy secure copy-protection schemes from \(\mathsf {1-copy} \rightarrow \mathsf {2-copy}\) secure schemes. We believe our technique is of independent interest. Along the way, we also obtain the following results.