Primitive-Root Determinant Densities over Prime Fields and Implications for PRIM-LWE

Diese Arbeit beweist unconditionally, dass die Dichte von Matrizen über endlichen Körpern mit Determinante als primitivem Wurzelwert von der Ordnung $1/\log\log x$ ist, und leitet daraus explizite, für kryptografische Anwendungen relevante Schranken für die Ablehnungsstichprobeneffizienz des PRIM-LWE-Problems ab.

Das Wesentliche

Hier ist eine einfache, bildhafte Erklärung der wissenschaftlichen Arbeit von Vipin Singh Sehrawat, die sich mit einem speziellen mathemischen Problem im Bereich der modernen Verschlüsselung befasst.

Das große Rätsel: Der „Primitive-Root"-Detektiv

Stellen Sie sich vor, Sie bauen einen extrem sicheren digitalen Tresor (eine Verschlüsselungsmethode namens PRIM-LWE). Um diesen Tresor zu öffnen, benötigen Sie einen geheimen Schlüssel. In der Welt dieser speziellen Verschlüsselung ist dieser Schlüssel nicht einfach eine Zahl, sondern eine riesige Tabelle von Zahlen (eine Matrix).

Es gibt eine besondere Regel für diesen Schlüssel: Wenn man die Zahlen in der Tabelle multipliziert und zusammenrechnet (man nennt das den Determinanten-Wert), muss das Ergebnis eine ganz bestimmte Eigenschaft haben. Es muss ein „Urzahl-Generator" sein.

Die Analogie des Uhrwerks:
Stellen Sie sich den mathematischen Raum als ein riesiges Uhrwerk vor, das von einer einzigen Zahl angetrieben wird. Ein „Urzahl-Generator" ist wie ein perfekter Zahnradmechanismus, der das gesamte Uhrwerk durchläuft, ohne jemals in einer Schleife stecken zu bleiben, bevor er wieder am Anfang ist. Nur sehr wenige Zahlen haben diese magische Eigenschaft.

Die Forscher wollten wissen: Wie oft kommt so ein perfekter Mechanismus zufällig vor?
Wenn Sie zufällig eine Tabelle von Zahlen wählen, wie hoch ist die Wahrscheinlichkeit, dass sie diesen perfekten Mechanismus enthält?

Die alte Sorge: „Was, wenn es gar keine gibt?"

Früher hatten Mathematiker eine große Sorge. Sie dachten: „Vielleicht gibt es bestimmte Arten von Tresoren (bestimmte Primzahlen), bei denen diese perfekten Mechanismen so selten sind, dass sie praktisch gar nicht vorkommen."

Wenn das wahr wäre, würde die Verschlüsselung zusammenbrechen. Denn wenn Sie keinen perfekten Schlüssel finden können, können Sie den Tresor nicht bauen. Ein früherer Forscher hatte vermutet, dass dies nur dann passiert, wenn es eine unendliche Anzahl von ganz speziellen, extrem seltenen Primzahlen gibt (die sogenannten Primorial-Primzahlen). Aber niemand konnte beweisen, ob diese speziellen Primzahlen wirklich existieren.

Die neue Entdeckung: Ein unbedingter Beweis

Der Autor dieses Papiers, Vipin Singh Sehrawat, hat dieses Problem gelöst – und zwar ohne auf die Existenz dieser seltenen Primzahlen zu warten. Er hat es mit zwei alten, bewährten mathematischen Werkzeugen bewiesen:

1. Dirichlets Theorem: Das ist wie ein Versprechen der Mathematik, dass man in bestimmten Zahlenreihen immer wieder neue Primzahlen findet.
2. Mertens' Formel: Eine Regel, die beschreibt, wie sich die Dichte dieser Zahlen verändert, je größer sie werden.

Das Ergebnis:
Ja, es gibt tatsächlich Primzahlen, bei denen die Chance, einen perfekten Schlüssel zu finden, extrem klein wird. Sie können so klein werden, dass sie fast gegen Null gehen.
Allerdings: Das passiert nur bei sehr, sehr speziellen, künstlich konstruierten Zahlen.

Die gute Nachricht für die Praxis: „Der Worst-Case ist harmlos"

Hier kommt die wichtigste Erkenntnis für die Sicherheitstheorie:

Stellen Sie sich vor, Sie suchen nach einem Nadel im Heuhaufen.

• In einem schlechten Heuhaufen (den speziellen, künstlichen Zahlen) ist die Nadel so selten, dass Sie theoretisch unendlich lange suchen müssten (die Wahrscheinlichkeit geht gegen Null).
• Aber in den Heuhaufen, die wir tatsächlich benutzen (die Standard-Zahlen in unserer Computer-Verschlüsselung, wie sie von NIST für ML-KEM und ML-DSA festgelegt wurden), ist die Nadel gar nicht so selten.

Die Metapher vom Heuhaufen:
Die Forscher haben gezeigt, dass für die Zahlen, die wir in der echten Welt verwenden (z. B. für sichere Internetverbindungen), die Wahrscheinlichkeit, einen perfekten Schlüssel zu finden, immer noch sehr gut ist.

• Für den Standard-Tresor (Modul 3329) finden Sie den Schlüssel im Durchschnitt nach 2,17 Versuchen.
• Für den großen Tresor (Modul 8.380.417) brauchen Sie im Durchschnitt nur 3,42 Versuche.

Das ist wie wenn Sie in einem normalen Heuhaufen nach einer Nadel suchen und sie nach ein paar Händevoll Heu finden. Das ist absolut machbar und sicher.

Was bedeutet das für die Zukunft?

1. Kein Kollaps: Die Verschlüsselungsmethode (PRIM-LWE) ist sicher. Die Tatsache, dass es theoretische Zahlen gibt, bei denen es fast unmöglich ist, einen Schlüssel zu finden, ist kein praktisches Problem, weil wir diese Zahlen nicht verwenden.
2. Wahl des Schlüssels ist wichtig: Es kommt darauf an, welche Zahl man als Basis wählt. Wenn man eine Zahl wählt, die viele kleine Teiler hat (wie ein Heuhaufen voller Strohhalme, die die Nadel verstecken), wird es schwieriger. Aber die Standard-Wahlen in der Kryptografie sind so gewählt, dass sie „freundlich" sind und die Nadel gut sichtbar bleibt.
3. Die langsame Abnahme: Die Forscher haben auch gezeigt, dass die Wahrscheinlichkeit, einen Schlüssel zu finden, nur extrem langsam abnimmt, je größer die Zahlen werden. Sie fällt nicht wie ein Stein, sondern eher wie ein Blatt, das langsam zu Boden schwebt.

Zusammenfassung in einem Satz

Die Mathematiker haben bewiesen, dass es zwar theoretische Szenarien gibt, in denen die Suche nach dem perfekten Verschlüsselungsschlüssel fast aussichtslos ist, aber für alle praktisch genutzten Standards ist die Suche immer noch schnell und erfolgreich – wir müssen uns also keine Sorgen machen, dass unsere digitalen Tresoren unbrauchbar werden.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Primitive-Root Determinant Densities over Prime Fields and Implications for PRIM-LWE" von Vipin Singh Sehrawat auf Deutsch.

1. Problemstellung

Das Paper befasst sich mit dem PRIM-LWE-Problem (Learning with Errors mit primitivem Wurzeldeterminanten), einer Variante des LWE-Problems, die von Sehrawat, Yeo und Desmedt (2021) eingeführt wurde. Beim PRIM-LWE wird gefordert, dass die geheime Matrix $S$ einen Determinantenwert besitzt, der eine primitive Wurzel des multiplikativen Körpers $\mathbb{F}_p^*$ ist.

Ein zentrales Hindernis für die Sicherheitsreduktion von Decision-LWE auf Decision-PRIM-LWE ist die Dichte $c(p)$ solcher Matrizen. Diese Dichte ist definiert als der Grenzwert der Wahrscheinlichkeit, dass eine zufällige $n \times n$-Matrix über $\mathbb{F}_p$ einen primitiv-wurzel-Determinanten hat, wenn $n \to \infty$:
$$c(p) = \frac{\phi(p-1)}{p-1} \prod_{j=1}^{\infty} \left(1 - \frac{1}{p^j}\right)$$
Dabei ist $\phi$ die Eulersche Phi-Funktion.

Die offene Frage:
In der vorherigen Arbeit wurde die Vermutung aufgestellt, dass $\inf_{p \text{ prim}} c(p) = 0$ gilt. Dies würde folgen, wenn es unendlich viele Primorial-Primzahlen ($p = p_1 \cdot p_2 \cdots p_k + 1$) gäbe. Da die Existenz unendlich vieler solcher Primzahlen jedoch ein offenes Problem der Zahlentheorie ist, blieb die Frage, ob $\inf c(p) = 0$ unbedingt (ohne Vermutungen) bewiesen werden kann, offen. Ein Ergebnis von 0 würde bedeuten, dass die Reduktion für bestimmte Moduli extrem ineffizient wird (hoher Overhead beim Rejection Sampling).

2. Methodik

Der Autor löst das Problem durch eine Kombination klassischer zahlentheoretischer Sätze, ohne auf die Hypothese der Primorial-Primzahlen zurückzugreifen:

1. Dirichletscher Primzahlsatz: Dieser garantiert die Existenz unendlich vieler Primzahlen in arithmetischen Progressionen. Der Autor nutzt dies, um für jedes Primorial $N_k = \prod_{i=1}^k p_i$ unendlich viele Primzahlen $p \equiv 1 \pmod{N_k}$ zu finden.
2. Mertens' dritter Satz: Dieser liefert das asymptotische Verhalten des Produkts über Primzahlen: $\prod_{q \le x} (1 - 1/q) \sim e^{-\gamma} / \log x$.
3. Linniks Theorem: Wird verwendet, um quantitative Abschätzungen für die kleinste Primzahl in einer arithmetischen Progression zu erhalten, um die Wachstumsrate des Minimums von $c(p)$ zu bestimmen.
4. Erdős–Wintner-Theorie für additive Funktionen: Für die Analyse der Verteilung von $c(p)$ über die Primzahlen hinweg wird die Theorie der additiven Funktionen auf verschobenen Primzahlen ($p-1$) herangezogen.

3. Hauptergebnisse und Beiträge

A. Unbedingtes Verschwinden des Infimums (Theorem 3)

Der Autor beweist unbedingt (unconditional), dass:
$$\inf_{p \text{ prim}} c(p) = 0 \quad \text{und} \quad \liminf_{p \to \infty} c(p) = 0.$$
Beweisidee: Für jedes $k$ wählt man eine Primzahl $p \equiv 1 \pmod{N_k}$. Dann teilt jedes $p_i$ für $i \le k$ den Wert $p-1$. Daraus folgt:
$$\frac{\phi(p-1)}{p-1} \le \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right).$$
Nach Mertens' Theorem geht dieses Produkt gegen 0, wenn $k \to \infty$. Da Dirichlets Theorem sicherstellt, dass solche Primzahlen $p$ existieren, muss das Infimum von $c(p)$ 0 sein. Dies umgeht die Notwendigkeit der Existenz von Primorial-Primzahlen.

B. Scharfe Ordnung des Minimums (Proposition 1, Corollary 6)

Die Arbeit etabliert die genaue asymptotische Rate, mit der das Minimum von $c(p)$ gegen 0 konvergiert:
$$\min_{p \le x} c(p) \asymp \frac{1}{\log \log x} \quad (x \to \infty).$$
Dies zeigt, dass der Abfall extrem langsam ist. Für kryptografisch relevante Größenordnungen (z.B. $2^{128}$) ist$\log \log x$sehr klein, was bedeutet, dass$c(p)$in praktischen Bereichen nicht beliebig klein wird, solange die Faktorisierung von$p-1$ kontrolliert ist.

C. Limitierende Verteilung (Theoreme 6 & 7)

Die Größe $c(p)$ besitzt eine stetige, rein singuläre Grenzverteilung über die Primzahlen.

• Träger (Support): Exakt das Intervall $[0, 1/2]$.
• Verteilungsfunktion: Ist auf $[0, 1/2]$ strikt monoton steigend.
• Dies bedeutet, dass für jedes $\tau \in (0, 1/2)$ sowohl die Menge der Primzahlen mit $c(p) \le \tau$ als auch die mit $c(p) > \tau$ eine positive relative Dichte haben.

D. Explizite untere Schranken für kryptografische Moduli (Theorem 8, Tabelle 1)

Ein praktischer Beitrag ist die Herleitung expliziter unterer Schranken für $c(q)$, die nur von der Anzahl der verschiedenen Primfaktoren von $q-1$, bezeichnet als $\omega(q-1)$, abhängen:
$$c(q) \ge P_3 \prod_{i=1}^{\omega(q-1)} \left(1 - \frac{1}{p_i}\right),$$
wobei $P_3 \approx 0.5601$.

Anwendung auf NIST-Standards:
Für die in ML-KEM und ML-DSA verwendeten Moduli wurden die genauen Werte berechnet:

• ML-KEM ($q = 3329$): $c(3329) \approx 0.4614$. Der erwartete Overhead beim Rejection Sampling beträgt höchstens 2.17.
• ML-DSA ($q = 8380417$): $c(8380417) \approx 0.2933$. Der Overhead beträgt höchstens 3.42.

Diese Werte zeigen, dass für gängige kryptografische Parameter der Overhead konstant und klein bleibt, obwohl das theoretische Infimum 0 ist.

4. Bedeutung und Implikationen für PRIM-LWE

1. Sicherheitsreduktion: Die Reduktion von Decision-LWE zu Decision-PRIM-LWE bleibt für jeden festen Primmodul $p$ gültig, da $c(p) > 0$. Der Faktor $1/c(p)$ stellt einen konstanten Overhead dar.
2. Modulwahl ist kritisch: Während die Reduktion theoretisch funktioniert, hängt die Effizienz stark von der Wahl des Moduls ab.
   • Moduli, bei denen $p-1$ viele kleine Primfaktoren hat (hoher $\omega(p-1)$), führen zu einem kleinen $c(p)$ und damit zu einem hohen Sampling-Overhead (bis zu $\Omega(\log \log p)$ im Worst-Case).
   • NTT-Freundlichkeit allein reicht nicht aus: Die Bedingung $q \equiv 1 \pmod{2^t}$ (wichtig für NTT) kontrolliert nur den 2-Teil von $q-1$. Sie garantiert nicht automatisch eine gute untere Schranke für $c(q)$, wenn $q-1$ viele ungerade Primfaktoren hat.
   • Praktische Sicherheit: Die in der Praxis verwendeten NIST-Moduli haben eine kontrollierte Faktorisierung von $q-1$ (wenige kleine Primfaktoren), was zu akzeptablen Overhead-Faktoren führt.
3. Theoretische Klärung: Das Paper schließt eine Lücke in der Literatur, indem es zeigt, dass das Verschwinden der Dichte nicht auf die (unbewiesene) Existenz unendlich vieler Primorial-Primzahlen angewiesen ist, sondern ein direktes Ergebnis klassischer Primzahlsätze ist.

Fazit

Das Paper liefert eine vollständige Analyse der Dichte primitiver Wurzeldeterminanten. Es beweist, dass diese Dichte zwar theoretisch gegen 0 gehen kann (mit einer sehr langsamen Rate von $1/\log \log x$), aber für alle praktisch relevanten kryptografischen Moduli (insbesondere die NIST-Standards) durch explizite, positive Konstanten nach unten beschränkt ist. Die Ergebnisse quantifizieren den Overhead beim Rejection Sampling präzise und bestätigen, dass PRIM-LWE unter Verwendung standardisierter Parameter eine praktikable und sichere Alternative zu normalem LWE darstellt, solange die Faktorisierungsstruktur von$q-1$ beachtet wird.