Cryptographic Applications of the Quantum No-Cloning Principle for Messages, Programs, and Advice

Abstract

The no-cloning principle tells us that it is impossible to perfectly replicate the state of an arbitrary quantum system. From its early beginnings with Wiesner, Bennett, and Brassard, quantum cryptography has often relied, either implicitly or explicitly, on this principle to achieve security properties beyond the reach of classical cryptography. We examine in this thesis various such cryptographic applications of quantum uncloneability from two broad perspectives: uncloneability for messages and uncloneability for functionalities.

Starting with uncloneability for messages, we study relations between tamper-evident encryption schemes - symmetric-key schemes for classical messages producing quantum encodings which allows the honest recipient to detect meaningful eavesdropping - and various other security notions. We show that tamper evidence implies encryption, that it can be used to construct revocation schemes (and vice-versa), and we formalize Gottesman's construction of quantum money from schemes satisfying this notion.

Moving on to uncloneability for functionalities, we begin by detailing our contributions to the study of quantum copy-protection and secure software leasing. These are two similar but distinct notions of uncloneability for families of functionalities. We show how to instantiate a scheme for point functions which is secure against honest-malicious adversaries in the quantum copy-protection setting and show that this is, generically, a sufficient condition to construct a secure software leasing scheme for the same functions.

We then complete this thesis by reporting work in which we initiate the formal study of uncloneable quantum complexity theory. We accomplish this by defining a novel complexity class denoted neglQP/upoly - the class of promise problems and languages which can be solved with bounded error by efficiently describable quantum circuits with the help of a quantum advice state exhibiting a type of functional uncloneability - and we show, unconditionally, that this class is non-empty. This relates to uncloneable functionalities as we also formalize how uncloneable advice can be seen as a form of quantum copy-protection for specific functions.