ProvACAna: Beweisbare Algebraische Kryptoanalyse

Das Internet lässt sich als ein großes Verkehrsnetz für digitale Kommunikation verstehen, in dem grundsätzlich jeder mit jedem sprechen kann. Da jedoch jeder Teilnehmer auch beliebige Behauptungen aufstellen kann, bietet das Internet per se keinen Schutz vor Betrug, Lauschangriffen oder aktiver Manipulation von Nachrichten. Um solchen Angriffen entgegenzuwirken und Authentizität, Integrität sowie Vertraulichkeit digitaler Kommunikation zu gewährleisten, müssen kryptografische Algorithmen auf Protokollebene eingesetzt werden. Tatsächlich wäre eine kommerzielle Nutzung des Internets ohne Kryptografie schlicht unvorstellbar. Klassische Kryptosysteme, die auf der Faktorisierung großer Zahlen oder auf elliptischen Kurven beruhen, haben bislang einen zuverlässigen Schutz geboten und finden darüber hinaus in zahlreichen weiteren Anwendungen Verwendung, etwa in Blockchains. Obwohl diese Systeme sehr effizient sind, können siezumindest theoretischvon Quantencomputern gebrochen werden. Auch wenn derzeit noch unklar ist, wann Quantencomputer im kommerziellen Maßstab verfügbar sein werden, ist es bereits heute notwendig, Algorithmen und Protokolle für ein quantensicheres Internet zu entwerfen und zu standardisieren. Die meisten quantensicheren Kryptosysteme basieren auf einer der folgenden vier mathematischen Theorien: der Gittertheorie, der Kodierungstheorie, der Theorie multivariater Gleichungssysteme sowie der Theorie der Isogenien elliptischer Kurven. Gitterbasierte Kryptosysteme sind gut untersucht und bieten starke Sicherheitsgarantien, büßen jedoch Effizienz ein, da sie große Signaturen, Chiffrate und Schlüssel erfordern. Isogeniebasierte Kryptosysteme hingegen sind äußerst kompakt und effizient, doch ist ihre Sicherheit noch Gegenstand aktueller Forschung und ihr Anwendungsspektrum scheint bislang begrenzt. Multivariate und codebasierte Kryptosysteme könnten im Vergleich einen guten Kompromiss zwischen Effizienz und Sicherheit zu bieten. Allerdings stellt sich die Frage: Wie sicher sind diese Systeme eigentlich? Zur Bewertung der Sicherheit eines Kryptosystems und zur Wahl geeigneter Parameter orientieren sich Kryptografen an der Laufzeit des jeweils schnellsten bekannten Angriffs. Für viele codebasierte sowie für alle multivariaten Kryptosysteme gelten algebraische Algorithmen als die aussichtsreichsten Angriffsmethoden. Obwohl die algebraische Kryptoanalyse schon lange bekannt ist, wurden ihre theoretischen Grundlagen bislang wenig erforscht. In der Praxis stützt sich die algebraische Kryptoanalyse auf Heuristiken und empirische Erfahrungswerte. Dies schränkt ihre Aussagekraft erheblich ein und stellt die langfristige Sicherheit quantenresistenter Kryptosysteme infrage. Ziel dieses Forschungsprojekts ist es daher, die algebraische Kryptoanalyse auf ein solides mathematisches Fundament zu stellen. Zu diesem Zweck wurden vier Kernprobleme identifiziert, die mithilfe einer rigorosen, formalen Methodik systematisch untersucht werden sollen.