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

Veröffentlicht auf der Konferenz „PQCrypto 2020: Post-Quantum Cryptography“

08.05.2020

In dieser Forschungsarbeit entwickeln Dr. Juliane Krämer und Patrick Struck eine Methode, mit dem für bestimmte Verschlüsselungsverfahren einfach bewiesen werden kann, dass sie auch gegen Quantum-Angreifer sicher sind, d.h. wenn das Verfahren mit einem Quantencomputer angegriffen wird.

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.

Weitere Informationen

3 Fragen an Patrick Struck, Co-Autor des Paper

Wie entstand die Idee zu diesem Paper?

Das initiale Ziel war ein Post-Quantum Beweis für das Verschlüsselungsverfahren LARA, welches von einem ehemaligen Cysec Mitarbeiter entwickelt wurde. Für dieses Verfahren existierte bis dahin lediglich ein klassischer Beweis. Dabei ist aufgefallen, dass sich die Ergebnisse abstrahieren lassen und somit potentiell auf andere Verfahren übertragen lassen.

Was war die größte Herausforderung beim Schreiben dieses Papers?

Zum einen mussten passende Kriterien erarbeitet werden, zum anderen mussten anschließend alle Kandidaten des NIST PQ-Standardisierungsprozesses individuell bzgl. dieser Kriterien analysiert werden um herauszufinden ob die vorgestellte Methode auf sie angewendet werden kann.

Wie können die Ergebnisse des Papers in der Praxis eingesetzt werden?

Häufig ist der Post-Quantum Sicherheitsbeweis sehr komplex. Es ist daher einfacher ein Verfahren zu entwickeln und es sicher im „klassischen“ Sinne zu beweisen. Die Post-Quantum Sicherheit folgt dann aus der Anwendung der vorgestellten Methode und es muss kein expliziter Post-Quantum Beweis geführt werden.