Paper 2023/1841

Unclonable Cryptography with Unbounded Collusions and Impossibility of Hyperefficient Shadow Tomography

Abstract

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 -> 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 [TCC'22]), or, (ii) only k -> 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 construct (i) public-key encryption, (ii) public-key functional encryption, (iii) signature and (iv) pseudorandom function schemes whose keys are copy-protected against unbounded collusions in the plain model (i.e. without any idealized oracles), assuming (post-quantum) subexponentially secure iO and LWE. - We show that any unlearnable functionality can be copy-protected against unbounded collusions, relative to a classical oracle. - As a corollary of our results, we rule out the existence of hyperefficient quantum shadow tomography, * even given non-black-box access to the measurements, assuming subexponentially secure iO and LWE, or, * unconditionally relative to a quantumly accessible classical oracle, and hence answer an open question by Aaronson (STOC'18). We obtain our results through a novel technique which uses identity-based encryption to construct multiple copy secure copy-protection schemes from 1-copy -> 2-copy secure schemes. We believe our technique is of independent interest. Along the way, we also obtain the following results. - We define and prove the security of new collusion-resistant monogamy-of-entanglement games for coset states. - We construct a classical puncturable functional encryption scheme whose master secret key can be punctured at all functions f such that f(m_0) != f(m_1). This might also be of independent interest.

Note: Full version with the proofs.