Der gefeierte Kryptographie-Algorithmus erhält ein Upgrade | Quanta-Magazin

In unserem zunehmend digitalen Leben hängt die Sicherheit von der Kryptografie ab. Wenn Sie eine private Nachricht senden oder eine Rechnung online bezahlen, verlassen Sie sich auf Algorithmen, die Ihre Daten geheim halten. Natürlich wollen einige Leute diese Geheimnisse aufdecken – deshalb testen Forscher die Stärke dieser Systeme, um sicherzustellen, dass sie nicht durch die Hände eines cleveren Angreifers zusammenbrechen.

Ein wichtiges Werkzeug in dieser Arbeit ist der LLL-Algorithmus, benannt nach den Forschern veröffentlichte es 1982 – Arjen Lenstra, Hendrik Lenstra Jr. und László Lovász. LLL kann zusammen mit seinen vielen Nachkommen in einigen Fällen kryptografische Schemata brechen; Durch die Untersuchung ihres Verhaltens können Forscher Systeme entwerfen, die weniger anfällig für Angriffe sind. Und die Talente des Algorithmus gehen über die Kryptographie hinaus: Er ist auch ein nützliches Werkzeug in fortgeschrittenen mathematischen Bereichen wie der rechnerischen Zahlentheorie.

Im Laufe der Jahre haben Forscher Varianten des lebenslangen Lernens verfeinert, um den Ansatz praktischer zu machen – allerdings nur bis zu einem gewissen Punkt. Jetzt haben zwei Kryptografen einen neuen Algorithmus im LLL-Stil entwickelt, der die Effizienz erheblich steigert. Die neue Technik, die gewonnen hat Auszeichnung für das beste Papier im 2023 Internationale Kryptologiekonferenzerweitert das Spektrum an Szenarien, in denen Informatiker und Mathematiker LLL-ähnliche Ansätze sinnvoll nutzen können.

„Es war wirklich aufregend“, sagte er Chris Peikert, ein Kryptograph an der University of Michigan, der nicht an der Arbeit beteiligt war. Das Tool stehe seit Jahrzehnten im Mittelpunkt der Forschung, sagte er. „Es ist immer schön, wenn ein Ziel, an dem so lange gearbeitet wurde … zeigt, dass es immer noch Überraschungen gibt.“

LLL-Algorithmen arbeiten in der Welt der Gitter: unendliche Ansammlungen regelmäßig beabstandeter Punkte. Stellen Sie sich zum Beispiel vor, Sie würden einen Boden fliesen. Sie könnten es mit quadratischen Fliesen bedecken, und die Ecken dieser Fliesen würden ein einziges Gitter bilden. Alternativ könnten Sie eine andere Kachelform wählen – beispielsweise ein langes Parallelogramm –, um ein anderes Gitter zu erstellen.

Ein Gitter kann anhand seiner „Basis“ beschrieben werden. Dabei handelt es sich um eine Reihe von Vektoren (im Wesentlichen Zahlenlisten), die Sie auf unterschiedliche Weise kombinieren können, um jeden Punkt im Gitter zu erhalten. Stellen wir uns ein Gitter vor, dessen Basis aus zwei Vektoren besteht: [3, 2] und [1, 4]. Das Gitter besteht einfach aus allen Punkten, die Sie erreichen können, indem Sie Kopien dieser Vektoren addieren und subtrahieren.

Dieses Vektorpaar ist nicht die einzige Basis des Gitters. Jedes Gitter mit mindestens zwei Dimensionen hat unendlich viele mögliche Basen. Aber nicht alle Grundlagen sind gleich. Eine Basis, deren Vektoren kürzer und näher an einem rechten Winkel zueinander sind, ist in der Regel einfacher zu handhaben und für die Lösung mancher Rechenprobleme nützlicher, weshalb Forscher diese Basen als „gut“ bezeichnen. Ein Beispiel hierfür ist das Paar blauer Vektoren in der Abbildung unten. Basen, die aus längeren und weniger orthogonalen Vektoren bestehen – wie die roten Vektoren – können als „schlecht“ angesehen werden.

Dies ist eine Aufgabe für LLL: Geben Sie ihm (oder seinen Brüdern) eine Basis eines mehrdimensionalen Gitters, und es wird ein besseres ausspucken. Dieser Vorgang wird als Gitterbasisreduktion bezeichnet.

Was hat das alles mit Kryptographie zu tun? Es stellt sich heraus, dass die Aufgabe, ein kryptografisches System zu knacken, in manchen Fällen als ein anderes Problem umgestaltet werden kann: das Finden eines relativ kurzen Vektors in einem Gitter. Und manchmal kann dieser Vektor aus der reduzierten Basis entnommen werden, die von einem Algorithmus im LLL-Stil generiert wird. Diese Strategie hat Forschern geholfen, Systeme zu stürzen, die oberflächlich betrachtet wenig mit Gittern zu tun zu haben scheinen.

Im theoretischen Sinne läuft der ursprüngliche LLL-Algorithmus schnell: Die Zeit, die für die Ausführung benötigt wird, skaliert nicht exponentiell mit der Größe der Eingabe – also der Dimension des Gitters und der Größe (in Bits) der Zahlen im Basisvektoren. Aber es nimmt als Polynomfunktion zu, und „wenn man es tatsächlich machen will, ist die Polynomzeit nicht immer so machbar“, sagte er Léo Ducas, Kryptograf am nationalen Forschungsinstitut CWI in den Niederlanden.

In der Praxis bedeutet dies, dass der ursprüngliche LLL-Algorithmus keine zu großen Eingaben verarbeiten kann. „Mathematiker und Kryptographen wollten die Möglichkeit haben, mehr zu tun“, sagte er Keegan Ryan, Doktorand an der University of California, San Diego. Die Forscher arbeiteten daran, Algorithmen im LLL-Stil zu optimieren, um größere Eingaben zu bewältigen und dabei häufig eine gute Leistung zu erzielen. Dennoch blieben einige Aufgaben hartnäckig außer Reichweite.

Das neue Papier, verfasst von Ryan und seinem Berater, Nadia Heninger, kombiniert mehrere Strategien, um die Effizienz seines LLL-Algorithmus zu verbessern. Zum einen verwendet die Technik eine rekursive Struktur, die die Aufgabe in kleinere Teile zerlegt. Zum anderen verwaltet der Algorithmus sorgfältig die Präzision der beteiligten Zahlen und findet ein Gleichgewicht zwischen Geschwindigkeit und einem korrekten Ergebnis. Die neue Arbeit ermöglicht es Forschern, die Basis von Gittern mit Tausenden von Dimensionen zu reduzieren.

Frühere Arbeiten verfolgten einen ähnlichen Ansatz: A 2021 Papier kombiniert auch Rekursion und Präzisionsmanagement, um große Gitter schnell bearbeiten zu können, funktionierte jedoch nur für bestimmte Arten von Gittern und nicht für alle, die in der Kryptographie wichtig sind. Der neue Algorithmus verhält sich in einem viel größeren Bereich gut. „Ich bin wirklich froh, dass es jemand getan hat“, sagte er Thomas Espitau, ein Kryptographieforscher bei der Firma PQShield und Autor der Version 2021. Die Arbeit seines Teams biete einen „Proof of Concept“, sagte er; Das neue Ergebnis zeigt, dass „man eine sehr schnelle Gitterreduktion auf solide Weise durchführen kann.“

Die neue Technik hat bereits begonnen, sich als nützlich zu erweisen. Aurel Seite, ein Mathematiker am französischen nationalen Forschungsinstitut Inria, sagte, dass er und sein Team eine Anpassung des Algorithmus vorgenommen hätten, um an einigen rechnerischen Aufgaben der Zahlentheorie zu arbeiten.

Algorithmen im LLL-Stil können auch in der Forschung im Zusammenhang mit gitterbasierten Kryptografiesystemen, die darauf ausgelegt sind, eine Rolle spielen bleib sicher selbst in einer Zukunft mit leistungsstarken Quantencomputern. Sie stellen keine Bedrohung für solche Systeme dar, da für deren Beseitigung kürzere Vektoren gefunden werden müssen, als diese Algorithmen erreichen können. Aber die besten Angriffsforscher, die sie kennen, verwenden einen LLL-ähnlichen Algorithmus als „Grundbaustein“, sagte er Wessel van Woerden, Kryptograf an der Universität Bordeaux. In praktischen Experimenten zur Untersuchung dieser Angriffe kann dieser Baustein alles verlangsamen. Mit dem neuen Tool können Forscher möglicherweise die Palette der Experimente erweitern, die sie mit den Angriffsalgorithmen durchführen können, und so ein klareres Bild ihrer Leistung liefern.

Wie viel führt eine Reihe von Umfragen durch, um unser Publikum besser zu bedienen. Nimm unser Leserbefragung Informatik und Sie nehmen an der kostenlosen Verlosung teil Wie viel Waren.