Ueli Maurer

Recent research in quantum cryptography has led to the development of schemes that encrypt and authenticate quantum messages with computational security. The security definitions used so far in the literature are asymptotic, game-based, and not known to be composable. We show how to define finite, composable, computational security for secure quantum message transmission. The new definitions do not involve any games or oracles, they are directly operational: a scheme is secure if it transforms an insecure channel and a shared key into an ideal secure channel from Alice to Bob, i.e., one which only allows Eve to block messages and learn their size, but not change them or read them. By modifying the ideal channel to provide Eve with more or less capabilities, one gets an array of different security notions. By design these transformations are composable, resulting in composable security. Crucially, the new definitions are finite. Security does not rely on the asymptotic hardness of a computational problem. Instead, one proves a finite reduction: if an adversary can distinguish the constructed (real) channel from the ideal one (for some fixed security parameters), then she can solve a finite instance of some computational problem. Such a finite statement is needed to make security claims about concrete implementations. We then prove that (slightly modified versions of) protocols proposed in the literature satisfy these composable definitions. And finally, we study the relations between some game-based definitions and our composable ones. In particular, we look at notions of quantum authenticated encryption and QCCA2, and show that they suffer from the same issues as their classical counterparts: they exclude certain protocols which are arguably secure.

A qubit can be used to implement a classical memory bit, but not vice versa. We address the question whether quantum memory can be more powerful than classical memory in a classical information context where some relevant information X (e.g. an n-bit string) must be stored in memory of insufficient size s (e.g. s We discuss an information-theoretic model of memory, which includes quantum memory, and show that in a quite general context, quantum memory is only marginally more powerful than classical memory. In particular, classical privacy amplification by universal hashing remains secure even against an adversary with (the same amount of) quantum rather than classical memory. It remains a general open problem to prove certain classical information-theoretic cryptosystems, for instance schemes secure in the bounded-storage model, secure in presence of a quantum adversary. This is joint work with Robert Koenig and Renato Renner.