CryptoDB
Unclonable Cryptography with Unbounded Collusions and Impossibility of Hyperefficient Shadow Tomography
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | TCC 2024 |
| 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-keyencryption,(ii) public-keyfunctionalencryption,(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 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(m0) ̸= f(m1). This might also be of independent interest. |
BibTeX
@inproceedings{tcc-2024-34792,
title={Unclonable Cryptography with Unbounded Collusions and Impossibility of Hyperefficient Shadow Tomography},
publisher={Springer-Verlag},
author={Alper Cakan and Vipul Goyal},
year=2024
}