💻 computer science

The complexity of solving a system of equations of the same degree

Diese Arbeit legt obere Schranken für den Grad der Regularität und die Komplexität des Lösens von Gleichungssystemen mit einheitlichem Grad fest, die in der Kryptographie weit verbreitet sind, indem sie deren Abhängigkeit von der Anzahl der Variablen, Gleichungen und des Gleichungsgrades analysiert.

Ursprüngliche Autoren: Giulia Gaggero, Elisa Gorla

Veröffentlicht 2026-02-02

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Giulia Gaggero, Elisa Gorla

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, ein komplexes Schloss zu knacken. In der Welt der Kryptographie ist dieses Schloss oft ein riesiges, verworrenes Geflecht aus mathematischen Gleichungen. Um es zu öffnen, müssen Sie die spezifischen Zahlen (Variablen) finden, die alle Gleichungen gleichzeitig wahr machen.

In dieser Arbeit geht es darum, zu bestimmen, wie schwer es ist, diese Schlösser zu knacken, und eine garantierte „Worst-Case“-Schätzung des erforderlichen Aufwands zu liefern, ohne sich auf Glückstreffer verlassen zu müssen.

Hier ist eine Aufschlüsselung der Ideen dieser Arbeit unter Verwendung alltäglicher Analogien:

1. Das Problem: Der verknotete Knoten

Die Kryptographie beruht oft auf der Idee, dass das Lösen eines Systems von Polynomgleichungen (wie $x^2 + y = 5$ und $xy + z = 10$) unglaublich schwierig ist. Wenn man sie nicht schnell lösen kann, bleibt der geheime Schlüssel sicher.

Um diese Systeme zu knacken, nutzen Mathematiker ein mächtiges Werkzeug namens Gröbnerbasis. Betrachten Sie dieses Werkzeug als eine riesige, automatisierte Sortiermaschine. Sie nimmt Ihre ungeordneten Gleichungen und ordnet sie in eine ordentliche, lösbare Liste um. Diese Maschine muss jedoch viele „Runden“ des Sortierens durchlaufen. Je mehr Runden sie benötigt, desto mehr Zeit und Rechenleistung kostet es.

Die Arbeit konzentriert sich auf eine spezifische Metrik namens Regularitätsgrad (degree of regularity). Man kann sich dies als die „Höhe“ der Leiter der Sortiermaschine vorstellen.

Geringe Höhe: Die Maschine sortiert die Gleichungen schnell. Das Schloss ist schwach.
Hohe Höhe: Die Maschine muss sehr hoch klettern, um die Lösung zu finden. Das Schloss ist stark.

2. Der alte Weg: Die Höhe erraten

Früher versuchten Experten, diese „Höhe“ zu schätzen, indem sie annahmen, dass die Gleichungen zufällig und perfekt ausbalanciert sind (ein Konzept namens „semiregelär“). Es ist, als würde man davon ausgehen, dass jeder Knoten, den man vor sich hat, ein standardisierter, vorhersehbarer Wirrwarr ist.

Der Fehler: Das ist nur eine Vermutung. Manchmal ist der Knoten tatsächlich eine seltsame, tückische Form, die den Regeln nicht folgt. Wenn man falsch rät, glaubt man vielleicht, ein Schloss sei sicher, obwohl es leicht zu knacken ist, oder umgekehrt.

3. Der neue Weg: Eine garantierte Decke

Die Autoren dieser Arbeit sagen: „Hören wir auf zu raten. Lassen Sie uns eine harte Grenze festlegen.“

Sie konzentrieren sich auf Systeme, bei denen alle Gleichungen den gleichen Grad haben (z. B. sind sie alle quadratisch oder kubisch). Sie beweisen, dass es, egal wie die Gleichungen angeordnet sind, eine mathematische Decke (eine obere Schranke) gibt, bis zu der die Sortierleiter steigen muss.

Die Analogie der Bibliothek:
Stellen Sie sich vor, Sie haben eine Bibliothek mit $n$ Regalen und $m$ Büchern.

Der Grad der Gleichungen ist die Dicke der Bücher.
Die Anzahl der Variablen ist die Anzahl der Regale.
Die Anzahl der Gleichungen ist die Anzahl der Bücher.

Die Autoren beweisen, dass, wenn Sie eine bestimmte Anzahl an Büchern derselben Dicke haben, Sie mathematisch garantieren können, dass Sie niemals höher als ein bestimmtes Regal klettern müssen, um die richtige Ordnung zu finden. Sie berechnen diese maximale Regalnummer strikt basierend auf:

Wie viele Bücher Sie haben ( $m$ ).
Wie viele Regale es gibt ( $n$ ).
Wie dick die Bücher sind (der Grad).

4. Der „Feldgleichungen“-Twist

In der Kryptographie gibt es eine spezielle Regel: Zahlen kreisen normalerweise (wie bei einer Uhr). Wenn man mit Zahlen von 0 bis 9 arbeitet, wird aus $10$ eine $0$. In der Mathematik ist dies das Hinzufügen von „Feldgleichungen“.

Die Arbeit untersucht auch, was passiert, wenn man diese „Kreis-Regeln“ in die Mischung bringt.

Ohne Kreis-Regeln: Die Sortiermaschine muss vielleicht eine gewisse Höhe erklimmen.
Mit Kreis-Regeln: Die Maschine findet die Lösung vielleicht schneller, weil die Regeln strenger sind.

Die Autoren liefern auch für dieses Szenario eine neue, garantierte Decke. Sie zeigen, dass es selbst mit diesen zusätzlichen Regeln eine Grenze dafür gibt, wie schwer das Problem werden kann, und sie berechnen genau, was dieses Limit ist.

5. Warum das wichtig ist (Der „bewiesene“ Vorteil)

Die Arbeit räumt ein, dass ihre berechnete „Decke“ etwas höher sein könnte als die tatsächliche Höhe, die für einen spezifischen, glücklichen Satz von Gleichungen nötig ist.

Die Heuristik (Alter Weg): „Ich wette, dieser Knoten ist leicht zu entwirren, weil er zufällig aussieht.“ (Schnell, aber riskant).
Der Beweis (Diese Arbeit): „Ich kann nicht beweisen, dass dieser Knoten leicht zu entwirren ist, aber ich kann beweisen, dass es niemals mehr als 100 Schritte dauern wird, ihn zu entwirren.“ (Langsamere Schätzung, aber 100 % sicher).

Dies ist entscheidend für die Sicherheit. Wenn ein Kryptograph ein Schloss entwerfen möchte, das für die nächsten 50 Jahre sicher ist, muss er das Worst-Case-Szenario kennen. Er möchte sich nicht auf die Hoffnung verlassen, dass die Gleichungen „angenehm“ sind. Er möchte die Gewissheit haben, dass die „Sortiermaschine“ niemals höher klettern muss als eine sichere Höhe.

Zusammenfassung

Diese Arbeit liefert ein mathematisches Sicherheitsnetz. Sie sagt uns: „Wenn Sie ein System von Gleichungen mit diesen spezifischen Zahlen an Variablen und Gleichungen haben, können Sie zu 100 % sicher sein, dass das Lösen nicht mehr als den Rechenaufwand X erfordern wird.“

Sie ersetzt das Raten nach dem Motto „Es sieht wahrscheinlich zufällig aus, also ist es schwer“ durch die Gewissheit: „Wir haben bewiesen, dass es nicht schwerer als dies sein kann.“ Dies ermöglicht es Kryptographen, Systeme mit einem bekannten, garantierten Sicherheitsniveau gegen mathematische Angriffe zu entwerfen.

Technisches Resümee: Komplexität des Lösens von Gleichungssystemen desselben Grades

Problemstellung

Die Sicherheit zahlreicher kryptographischer Verfahren, insbesondere in der multivariaten Kryptographie und im Post-Quanten-Kontext, beruht auf der rechnerischen Härte des Lösens von Systemen multivariater Polynomgleichungen über endlichen Körpern. Die Komplexität des Lösens solcher Systeme mittels Gröbner-Basis-Methoden wird primär durch den Reguläritätsgrad ( $d_{reg}$ ) und den Lösungsgrad bestimmt. Während der Reguläritätsgrad eine obere Schranke für die Komplexität von Gröbner-Basis-Berechnungen liefert, ist es oft schwierig, diesen für Systeme kryptographischer Größe zu berechnen oder abzuschätzen.

Die gängige Praxis stützt sich auf die heuristische Annahme, dass Systeme semiregelmäßig (oder kryptographisch semiregelmäßig) sind, was explizite Formeln für den Reguläritätsgrad liefert. Diese Annahme ist jedoch nicht immer gültig; es existieren Parameterwahlmöglichkeiten und Körper, in denen keine semiregelmäßige Sequenz existiert. Folglich besteht ein Bedarf an bewiesenen, nicht-heuristischen oberen Schranken für den Reguläritätsgrad und den Lösungsgrad, die für Systeme gelten, bei denen der Reguläritätsgrad endlich ist, ohne sich auf die Semiregelmäßigkeit-Annahme zu verlassen.

Methodik

Die Autoren nähern sich dem Problem mit Werkzeugen der kommutativen Algebra, wobei sie sich speziell auf Systeme konzentrieren, bei denen das von den Top-Grad-Teilen der Polynome erzeugte Ideal eine Reguläre Sequenz von $n$ Polynomen in einem gegebenen Grad $D$ enthält.

Rahmenbedingungen: Das Paper betrachtet ein System $F = \{f_1, \dots, f_m\}$ aus $m$ Polynomen in $n$ Variablen über einem Körper $F$ . Die Analyse setzt voraus, dass die Top-Grad-Teile $f_1^{top}, \dots, f_m^{top}$ linear unabhängig sind und dass das System regulär in Grad $D$ ist (das heißt, das von den Top-Grad-Teilen erzeugte Ideal enthält eine reguläre Sequenz von $n$ Polynomen des Grades $D$ ).
Reduktion auf LPP-Ideale: Um die Castelnuovo-Mumford-Regulariät zu begrenzen (welche dem Reguläritätsgrad entspricht, wenn dieser endlich ist), nutzen die Autoren die Eisenbud-Green-Harris (EGH)-Vermutung. Diese Vermutung postuliert, dass unter allen homogenen Idealen, die eine reguläre Sequenz spezifischer Grade enthalten, das Lex-Plus-Powers (LPP)-Ideal die maximale Regulariät besitzt.
Kombinatorische Analyse: Die Autoren konstruieren spezifische LPP-Ideale, die mit den gegebenen Parametern ( $n, m, D$ ) assoziiert sind. Durch die Analyse der Struktur dieser Ideale unter der lexikographischen Ordnung bestimmen sie die Regulariät des LPP-Ideals, welches als obere Schranke für die Regulariät des ursprünglichen Systems dient (unter der Bedingung der EGH-Vermutung).
Feldgleichungen: Die Methodik wird auf Systeme erweitert, die mit Feldgleichungen ( $x_i^q - x_i$ ) ergänzt werden, was entscheidend für Systeme über endlichen Körpern $\mathbb{F}_q$ ist, insbesondere wenn der Grad der Gleichungen $D$ größer als oder gleich der Körpergröße $q$ ist.

Zentrale Beiträge und Ergebnisse

1. Obere Schranken für Systeme, die in Grad $D$ regulär sind (ohne Feldgleichungen)

Theorem 23 liefert eine scharfe obere Schranke für den Reguläritätsgrad eines Systems von $m$ Gleichungen des Grades $D$ in $n$ Variablen, unter der Annahme, dass das System in Grad $D$ regulär ist.

Die Schranke hängt von der Anzahl der Gleichungen ( $m$ ), der Variablen ( $n$ ) und dem Grad ( $D$ ) ab.
Die Formel beinhaltet die Identifizierung eindeutiger Ganzzahlen $k$ und $t$ , sodass $m-n$ in ein spezifisches Intervall fällt, das durch kombinatorische Summen ( $\sigma_{k,t}$ ) definiert ist.
Die resultierende Schranke lautet: $d_{reg}(F) \le (D - t) + (n - k)(D - 1)$ .
Diese Schranke ist für alle Werte von $m, n, D$ scharf und wird von Systemen erreicht, deren Top-Grad-Teile ein spezifisches LPP-Ideal bilden.

Korollar 27 überträgt dies auf eine obere Schranke für den Lösungsgrad für Mutanten-Algorithmen:
$\text{solv. deg}_m(F) \le D - t + 1 + (n - k)(D - 1)$

2. Obere Schranken für Systeme mit Feldgleichungen

Das Paper behandelt den Fall, in dem Feldgleichungen zum System hinzugefügt werden, was essenziell ist, wenn $D \ge q$ .

Proposition 31: Für sehr überbestimmte Systeme (bei denen $m$ die Dimension des Polynomraums modulo Feldgleichungen überschreitet) ist der Reguläritätsgrad exakt $D$ .
Theorem 33: Für Systeme, bei denen $q \le D \le n(q-1)$ $q \leq D \leq n (q - 1)$ gilt und die Top-Grad-Teile modulo die Feldgleichungen linear unabhängig sind, liefern die Autoren eine obere Schranke für den Reguläritätsgrad.
- Die Schranke wird durch die Analyse der Position des $m$ -ten Monoms in der lexikographischen Ordnung der Monome des Grades $D$ modulo $(x_1^q, \dots, x_n^q)$ abgeleitet.
- Die Schranke wird in Abhängigkeit von $B = q - t + (n - k)(q - 1)$ ausgedrückt, wobei $k$ und $t$ durch das Intervall bestimmt werden, in dem $m$ liegt.
- Je nach spezifischen Bedingungen bezüglich $m, D$ und $t$ ist die Schranke entweder $B$ oder $B-1$ .

Korollar 34 spezialisiert diese Ergebnisse für Binärsysteme ( $q=2$ ) und liefert vereinfachte Formeln für den Reguläritätsgrad und den Lösungsgrad für Systeme des Grades $D$ über $\mathbb{F}_2$ .

3. Anwendung auf spezifische Schemata

Die Autoren wenden ihre Schranken auf konkrete kryptographische Schemata an:

Cubic Simple Matrix: Sie leiten eine bewiesene Schranke $d_{reg} \le 2n - 1$ ab, was die erste bewiesene Schranke für dieses System darstellt und im Gegensatz zu früheren heuristischen Schätzungen steht.
Unbalanced Oil and Vinegar (UOV): Die Schranken werden auf UOV-Systeme über $\mathbb{F}_2$ angewendet, um zu demonstrieren, wie sich der Reguläritätsgrad verhält, wenn Feldgleichungen einbezogen werden.

Bedeutung und Ansprüche

Das Paper beansprucht seine Bedeutung primär dadurch, dass es bewiesene, nicht-heuristische Schranken für die Komplexität des Lösens von Polynomsystemen liefert.

Zuverlässigkeit: Im Gegensatz zu Schätzungen, die auf der Semiregelmäßigkeit-Annahme basieren (welche für bestimmte Parameter versagen können), gelten diese Schranken für jedes System, bei dem der Reguläritätsgrad endlich ist und das System in einem gegebenen Grad regulär ist.
Generalität: Die Ergebnisse gelten für Systeme über beliebige Körper und decken sowohl Fälle mit als auch ohne Feldgleichungen ab.
Schärfe: Die Schranken werden als „scharf“ beschrieben, was bedeutet, dass sie durch spezifische Systeme (LPP-Ideale) erreicht werden, was eine realistische Worst-Case-Abschätzung für die Sicherheitsanalyse bietet.
Limitierungen: Die Autoren räumen explizit ein, dass ihre Schranken im Allgemeinen weniger eng (d. h. höher) sind als jene, die unter der Semiregelmäßigkeit-Heuristik gewonnen werden. Sie argumentieren jedoch, dass dieser Kompromiss notwendig ist, um unbewiesene Annahmen zu vermeiden, insbesondere in Szenarien, in denen keine semiregelmäßigen Sequenzen existieren.

Die Arbeit schlägt keine neuen Algorithmen oder experimentellen Implementierungen vor, sondern etabliert vielmehr theoretische Grenzen für die Komplexität bestehender Gröbner-Basis-Methoden (sowohl Standard- als auch Mutanten-Algorithmen) für eine breite Klasse von Polynomsystemen, die für die Kryptographie relevant sind.