Paper verständlich erklärt: Encryption Schemes Using Random Oracles: From Classical to Post-Quantum Security

Sicherheitsbeweise für Verschlüsselungsverfahren beruhen darauf, dass den Verfahren ein schwer zu lösendes Problem zugrunde liegt, das auch ein potentieller Angreifer nicht lösen kann. Die Geheimnisse sind also beweisbar sicher verschlüsselt. Mit der Entwicklung von Quantencomputern müssen nun aber „klassische“ und Post-Quantum-Verfahren unterschieden werden: Denn ein Quantencomputer kann die meisten rechnerischen Probleme, die in klassischen Verfahren genutzt werden, lösen. Es müssen also Probleme gefunden werden, die auch mit einem Quantencomputer nicht zu lösen sind, und daher auch gegen einen Angreifer sicher sind, dem ein Quantencomputer zur Verfügung steht. Diese Verfahren sind dann „post-quantum-sicher“.

Post-Quantum Sicherheitsbeweise sind allerdings deutlich komplizierter durchzuführen als die Beweise für klassische Verfahren. Einige neu-entwickelte kryptographische Verfahren nutzen daher bereits Post-Quantum-Probleme, die Autoren führen aber weiterhin nur einen klassischen Sicherheitsbeweis durch. Mit ihrer Methode sind Krämer und Struck in der Lage, für solche Verfahren die Post-Quantum-Sicherheit zu beweisen, wenn die Verschlüsselungsverfahren bestimmte Kriterien aufweisen.

Zum einen muss das Verfahren eine Hash Funktion zur Erzeugung von Zufallszahlen verwenden. Diese Hash Funktion wird im mathematischen Beweis durch ein „random oracle“ modelliert. Die erste Bedingung ist, dass die Berechnung der Hash Funktion unabhängig von der zu verschlüsselnden Nachricht ist.

Zum anderen muss der „klassische“ Beweis auf eine bestimmte Art und Weise aufgebaut sein. Typischerweise sind die Beweise in mehrere Einzelschritte aufgeteilt welche dann separat bewiesen werden. Im Paper werden die entsprechenden Einzelschritte klassifiziert und im Hinblick auf Angriffe mit Quantencomputern analysiert.

Im Paper beweisen Krämer und Struck: Erfüllt das getestete Verschlüsselungsverfahren die definierten Kriterien, ist das Verfahren automatisch post-quantum-sicher, auch wenn ursprünglich nur ein klassischer Sicherheitsbeweis durchgeführt wurde. Sie zeigen das an zwei Beispielen für Verschlüsselungsverfahren, „LARA“ und „ROLLO II“. Diese Verfahren wurden beide im weltweiten wissenschaftlichen Wettbewerb für die erste Zertifizierung eines Post-Quantum Verfahrens eingereicht (die NIST PQ-Challenge).

Dr. Juliane Krämer ist Athene Young Investigator und leitet seit 2017 die Nachwuchsforschungsgruppe „Quantum and Physical attack resistant Cryptography (QPC)“ an der TU Darmstadt. Patrick Struck ist wissenschaftlicher Mitarbeiter an der TU Darmstadt und promoviert seit 2018 in der QPC-Gruppe.