Towards Unclonable Cryptography in the Plain Model

Congratulations Dr.Hermouet !

Abstract

Although it is well known that quantum mechanics enables new threats to cryptography, it also provides new tools to construct cryptographic primitives that cannot be achieved in the classical world. Among these primitives are the unclonable primitives, who harness the non-cloning theorem of quantum states: the surprising fact that they cannot be copied. In the first part of this thesis, we give an extensive overview of unclonable primitives, and in particular of three main primitives: quantum money, providing unclonable verifiable tokens; unclonable encryption, an encryption scheme with unclonable ciphertexts; and finally copy-protection, in which a vendor sends unclonable programs to clients. For each of these primitives, we define them, discuss their history, and give example constructions.

In the second part, we focus on copy-protection and unclonable encryption. Despite receiving a lot of attention in the past years, these primitives are not yet fully understood. In particular, deciding whether they exist in the plain model (in which we cannot use any (quantum) random oracles) is still an open question. We progress towards this goal, by presenting new constructions for these primitives, with security in the plain model, assuming new conjectures. In order to prove the security of our constructions, we define and prove a new monogamy-of-entanglement property for coset states - arguably the most useful quantum states when it comes to constructing unclonable primitives - which we think is of independent interest. As independent contributions, we define two new security properties for another unclonable primitive, tokenized signature schemes, and present a construction satisfying these new properties. The security proofs follow from our new monogamy-of-entanglement property, as well as a variant of the direct product hardness property for coset states, that we define and prove.

Unclonable cryptographic protocols often require a significant amount of quantum power for all involved parties. As such a model is unlikely to be realizable in the near future, we investigate in a third part semi-quantum unclonable cryptography, in which classical parties interact with a powerful quantum server. As most of the unclonable primitives are based on coset states, we construct a remote coset states preparation protocol, that enables a classical party to instruct the quantum server on how to construct coset states. Furthermore, this preparation is done in a blind way, in the sense that the server does not learn which coset states they prepared. This allows us to leverage this protocol to construct unclonable primitives in a semi-quantum way.