Cryptography with Dispensable Backdoors
Backdooring cryptographic algorithms is an indisputable taboo in the cryptographic literature for a good reason: however noble the intentions, backdoors might fall in the wrong hands, in which case security is completely compromised. Nonetheless, more and more legislative pressure is being produced to enforce the use of such backdoors. In this work we introduce the concept of dispensable cryptographic backdoors which can be used only once and become useless after that. These exotic primitives are impossible in the classical digital world without stateful and secure trusted hardware support, but, as we show, are feasible assuming quantum computation and access to classical stateless hardware tokens. Concretely, we construct a dispensable (single-use) version of message authentication codes, and use them to derive a black-box construction of stateful hardware tokens in the above setting with quantum computation and classical stateless hardware tokens. This can be viewed as a generic transformation from stateful to stateless tokens and enables, among other things, one-time programs and memories. We then use the latter primitives to propose a resolution to the most prominent recent legislative push in favor of backdooring cryptography: the conflict between Apple and FBI last year. We show that it is possible for Apple to create a one-time backdoor which unlocks any single device, and no more than one, i.e., the backdoor becomes useless after it is used. We further describe how to use our ideas to derive a version of CCA-secure public key encryption, which is accompanied with a dispensable (i.e, single-use, as in the above scenario) backdoor.