Deniability, Plaintext-Awareness, and Non-Malleability in the Quantum and Post-Quantum Setting

Secure communication plays an important role in our everyday life, from the
messages we send our friends to online access to our banking. In fact, we can hardly
imagine a world without it. With quantum computers on the rise, it is critical for us
to consider what security might look like in the future. Can we rely on the principles
we use today? Or should we adapt them? This thesis asks exactly those questions.
We will look at both the quantum setting, where we consider communication
between quantum computers, and the post-quantum setting, where we consider communication
between classical computers in the presence of adversaries with quantum
computers. In this thesis, we will consider security questions centred around misleading
others, by considering to what extent the exchange of secrets can be denied,
misconstructed, or modified. We do this by exploring three security principles.
Firstly, we consider deniability for quantum key exchange, which describes the
ability to generate secure keys without leaving evidence. As quantum key exchange
can be performed without a fully-fledged quantum computer, using basic quantumcapable
machines, this concept is already close to becoming a reality. We explore the
setting of public-key authenticated quantum key exchange, and define a simulationbased
notion of deniability. We show how this notion can be achieved through an
adapted form of BB84, using post-quantum secure strong designated-verifier signature
schemes.
Secondly, we consider plaintext-awareness, which addresses the security of a
scheme by looking at the ability of an adversary to generate ciphertexts without
knowing the plaintext. Here two settings are considered. Firstly, the post-quantum
setting, in which we formalize three different plaintext-awareness notions in the superposition
access model, show their achievability and the relations between them,
as well as in which settings they can imply ciphertext indistinguishability. Next, the
quantum setting, in which we adapt the same three plaintext-awareness notions to a
setting where quantum computers are communicating with each other, and we again
show achievability and relations with ciphertext indistinguishability.
Lastly, we consider non-malleability, which protects a message from attacks that
alter the underlying plaintext. Overcoming the notorious “recording barrier” known
from generalizing other integrity-like security notions to quantum encryption, we generalize
one of the equivalent classical definitions, comparison-based non-malleability,
to the quantum setting and show how this new definition can be fulfilled. We also
show its equivalence to the classical definition when restricted to a post-quantum
setting.