Security of Cryptographic Primitives in Advanced Security Notions

The provable security paradigm is an important tool to show security of cryptographic primitives. Here, security follows from showing that an adversary cannot break a scheme with respect to some security notion. Standard security notions, however, often do not cover scenarios that might happen in practice. Examples are side-channel leakage as well as usage of keys and random coins that are somehow related. Another setting that often is not considered is security with respect to adversaries that have quantum computing power. In this thesis we study security of schemes in advanced security notions; these notions model more sophisticated attacks which can happen when using such schemes. We develop new advanced security notions, analyse existing primitives with respect to these, and construct primitives that achieve such advanced security notions. The first part of this thesis focuses on security outside the black-box model. Here, we develop a generic blueprint for a leakage-resilient authenticated encryption scheme from leakage-resilient functions. We then provide an instantiation entirely built from sponges. Furthermore, we provide security notions for related-key attacks against authenticated encryption schemes and analyse generic constructions with respect to these. Finally, we study the security of public key encryption schemes in case of reused random coins; we prove a simplification of the security notion which was already claimed yet backed up by a proof which was later identified as flawed. The second part focuses on security against the glooming threat of quantum computers. First, we provide positive results for the post-quantum security of several primitives. We develop a lifting theorem for public key encryption schemes from classical proofs in the random oracle model to post-quantum proofs in the quantum random oracle model. We further show post-quantum security of the sponge-based authenticated encryption scheme developed in the first part, a generic construction for deterministic wallets, and Yao's garbled circuits. Second, we develop a quantum security notion for public key encryption schemes which allows for a quantum challenge phase; we provide both positive and negative results with respect to this security notion.

Beweisbare Sicherheit ist ein wichtiges Werkzeug, um die Sicherheit von kryptographischen Verfahren zu zeigen. Man zeigt, dass ein Angreifer ein Verfahren im Hinblick auf einen konkreten Sicherheitsbegriff nicht brechen kann. Allerdings decken Standard-Sicherheitsbegriffe häufig nicht Szenarien ab, die in der Praxis auftreten. Ein Beispiel hierfür ist Seitenkanal Information ebenso wie die Verwendung von Schlüsseln bzw. Zufallswerten, welche voneinander abhängen. Ein anderes, häufig nicht beachtetes, Szenario ist Sicherheit im Hinblick auf Angreifer mit Quantencomputern. Die Arbeit analysiert Sicherheit von Verfahren hinsichtlich erweiterter Sicherheitsbegriffe; diese modellieren ausgeklügelte Angriffe, welche möglich sind, wenn kryptographische Verfahren genutzt werden. Es werden erweiterte Sicherheitsbegriffe entwickelt, existierende Primitive hinsichtlich dieser analysiert und neue Primitive konstruiert. Der erste Teil der Arbeit umfasst Sicherheit außerhalb des black-box models. Die Arbeit liefert eine generische Konstruktion für ein leakage-resilient authenticated encryption scheme von leakage-resilient pseudorandom functions. Außerdem wird eine Instanziierung basierend auf der sponge construction gegeben. Des Weiteren werden Sicherheitsbegriffe für related-key attacks gegen authenticated encryption schemes beschrieben und generische Verfahren bezüglich dieser Sicherheitsbegriffe analysiert. Schließlich wird die Sicherheit von public key encryption im Fall von wiederholten Zufallszahlen betrachten; die Arbeit zeigt eine Vereinfachung des Sicherheitsbegriffs, welche bereits behauptet wurde, deren entsprechender Beweis später jedoch als fehlerhaft identifiziert wurde. Der zweite Teil der Arbeit befasst sich mit der Bedrohung durch Quantencomputer. Zunächst wird Post-Quantum Sicherheit von mehreren Primitiven gezeigt. Es wird ein lifting theorem für public key encryption von klassischen Beweisen im random oracle model zu Post-Quantum Beweisen im quantum random oracle model entwickelt. Zusätzlich wird Post-Quantum Sicherheit des sponge-based authenticated encryption schemes aus dem ersten Teil, einer generischen Konstruktion für deterministic wallets sowie Yao's garbled circuits gezeigt. Anschließend wird ein Quantum-Sicherheitsbegriff für public key encryption entwickelt, welcher eine quantum challenge phase erlaubt; es werden positive sowie negative Ergebnisse bezüglich dieses Sicherheitsbegriffs gegeben.