Modification to Fully Homomorphic Modified Rivest Scheme

Diese Arbeit beschreibt das vollständig homomorphe modifizierte Rivest-Schema (FHMRS), identifiziert eine darin auftretende Sicherheitslücke und stellt eine modifizierte Version (mFHMRS) vor, die diese Schwachstelle behebt.

Das Wesentliche

🕵️‍♂️ Das Geheimnis der unsichtbaren Rechenkiste: Eine Geschichte über FHMRS und mFHMRS

Stellen Sie sich vor, Sie haben eine magische Rechenkiste. Sie können Dinge hineingeben, die Kiste rechnet damit (addiert oder multipliziert), aber sie zeigt Ihnen das Ergebnis nicht direkt an. Sie gibt Ihnen nur einen verschlüsselten, kryptischen Zettel zurück. Nur Sie, der Besitzer der Kiste, haben den Schlüssel, um den Zettel zu entschlüsseln und das wahre Ergebnis zu sehen.

Das ist das Grundprinzip von Fully Homomorphic Encryption (FHE). Das Paper beschreibt eine solche Kiste, die auf einer Idee von Rivest basiert, aber zwei Versionen davon vorstellt: die ursprüngliche (FHMRS) und eine verbesserte, sicherere Version (mFHMRS).

1. Die ursprüngliche Kiste (FHMRS): Wie funktioniert sie?

Stellen Sie sich vor, Sie wollen eine Nachricht (z. B. die Zahl 5) verschlüsseln.

• Der Trick: Die Kiste nimmt Ihre Zahl und mischt sie mit einem riesigen, zufälligen Haufen Sand (einer großen Primzahl $u$) und einem weiteren Geheimnis (einer anderen Primzahl $p$).
• Die Aufteilung: Um sicherzustellen, dass niemand die Nachricht stiehlt, wird die verschlüsselte Nachricht in zwei Hälften geschnitten und in zwei verschiedene, abgeschlossene Tresore gelegt (die Primzahlen $p$ und $q$).
• Das Rechnen: Wenn jemand im Tresor addieren oder multiplizieren will, darf er das nur mit den verschlüsselten Hälften machen. Er darf die Tresore nicht öffnen.
• Das Ergebnis: Am Ende werden die beiden Hälften wieder zusammengefügt (wie ein Puzzle), und der Sand wird herausgesiebt, um das echte Ergebnis zu erhalten.

Das Problem: In der ursprünglichen Version gab es einen Riss im Tresor. Wenn ein Hacker wusste, welche Zahl ursprünglich drin war (z. B. weil er die Nachricht vorher gesehen hatte), konnte er die beiden verschlüsselten Hälften vergleichen. Durch einfaches „Abzählen" (mathematisch: den größten gemeinsamen Teiler berechnen) konnte er den riesigen Sandhaufen ($u$) herausfinden. Und sobald er den Sandhaufen hatte, war das ganze System wie ein Kartenhaus, das zusammenbrach.

2. Der Einbruch (Der Angriff)

Stellen Sie sich vor, Sie haben zwei verschlossene Briefe. In einem steht „Hallo" (klar) und im anderen „Hallo" (verschlüsselt).

• Im alten System (FHMRS) war die Verschlüsselung so einfach: Verschlüsselt = Nachricht + (Geheimnis * Sand).
• Wenn der Hacker die Nachricht kennt, rechnet er einfach: Verschlüsselt - Nachricht = Geheimnis * Sand.
• Hat er zwei solche Paare, kann er den „Sand" (das Geheimnis $u$) leicht herausfinden. Das war der „Known-Plaintext-Angriff".

3. Die neue, stärkere Kiste (mFHMRS): Die Lösung

Die Autoren (Sona Alex und Bian Yang) haben die Kiste umgebaut, damit dieser Trick nicht mehr funktioniert. Hier ist die neue Strategie:

A. Mehr Tresore statt nur zwei
Statt die Nachricht nur in zwei Tresore ($p$ und $q$) zu legen, teilen wir sie jetzt in viele kleine Tresore auf (z. B. $p_1, p_2, p_3, \dots$).

• Analogie: Statt einen riesigen Diamanten in einen einzigen Safe zu legen, zerlegen wir ihn in 100 kleine Splitter und verteilen sie in 100 verschiedene, winzige Schließfächer. Selbst wenn ein Hacker einen oder zwei Fächer knackt, hat er immer noch nicht das ganze Bild.

B. Der Sandhaufen wird größer und unvorhersehbarer
Die Größe des „Sandhaufens" ($u$) und die Größe der Tresore ($p$) werden so gewählt, dass sie viel größer sind als die Nachricht selbst.

• Analogie: Stellen Sie sich vor, Sie werfen Ihre Nachricht in einen Ozean (den Sandhaufen). Im alten System war der Ozean so klein, dass man die Nachricht noch als Umriss erkennen konnte. Im neuen System ist der Ozean so riesig und die Wellen so hoch, dass die Nachricht völlig untergeht. Selbst wenn man weiß, was man hineingeworfen hat, kann man den Ozean nicht mehr analysieren, um das Geheimnis zu erraten.

C. Die Mathematik im Hintergrund (Gitter-Attacken)
Hacker versuchen oft, durch komplexe Mustererkennung (Gitter-Attacken) die Geheimnisse zu erraten. Die Autoren haben die Größe der Tresore und des Sandes so berechnet, dass diese Mustererkennung mathematisch unmöglich wird.

• Vergleich: Es ist wie ein Labyrinth. Im alten System gab es einen klaren Weg zum Ausgang. Im neuen System wurde das Labyrinth so vergrößert und mit so vielen Sackgassen versehen, dass selbst der schnellste Computer (der LLL-Algorithmus) nie den Weg findet.

4. Warum ist das wichtig?

Dieses Papier zeigt, wie man eine mathematische Kiste baut, die:

1. Rechenvorgänge erlaubt: Man kann Daten in der Cloud verarbeiten lassen, ohne dass der Cloud-Anbieter je sieht, was darin steht (Datenschutz).
2. Sicher ist: Selbst wenn ein Hacker weiß, welche Daten verschlüsselt wurden, kann er nicht auf das Geheimnis schließen.
3. Skalierbar ist: Egal ob man 1 oder 14 Multiplikationen hintereinander macht, die Kiste bleibt sicher, solange man die Größe der Tresore (die Parameter) richtig wählt.

Zusammenfassung in einem Satz

Die Autoren haben eine unsichere mathematische „Rechenkiste" (FHMRS), die von Hackern leicht geknackt werden konnte, in eine extrem robuste, mehrstufige Festung (mFHMRS) verwandelt, indem sie die Geheimnisse in viele kleine Teile zerlegten und die mathematischen Abstände so vergrößerten, dass kein Angriff mehr möglich ist.

Das Ergebnis: Wir können jetzt Daten sicher in der Cloud verarbeiten lassen, ohne Angst haben zu müssen, dass unsere Geheimnisse durchschaut werden.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des vorliegenden Papiers auf Deutsch, die das Problem, die Methodik, die wichtigsten Beiträge, die Ergebnisse und die Bedeutung der Arbeit abdeckt.

Titel: Modifikation des vollständig homomorphen modifizierten Rivest-Schemas (FHMRS)

Autoren: Sona Alex und Bian Yang (NTNU, Norwegen)

---

1. Problemstellung

Das Papier adressiert eine kritische Sicherheitslücke im ursprünglichen Fully Homomorphic Modified Rivest Scheme (FHMRS). FHMRS ist ein symmetrisches Verschlüsselungsschema, das homomorphe Operationen (Addition und Multiplikation) auf verschlüsselten Daten ermöglicht.

Das Hauptproblem liegt in einer Known-Plaintext-Attacke (KPA), die erfolgreich gegen das ursprüngliche FHMRS durchgeführt werden kann, wenn es Multiplikationen unterstützt:

• Der Angriff: Wenn ein Angreifer Paare aus Klartext ($m$) und zugehörigem Chiffretext ($c$) besitzt, kann er die Differenz $c - m$ berechnen. Da die Verschlüsselung im ursprünglichen Schema als $c = (m + g \cdot u) \pmod p$ definiert ist (wobei $g$ eine Zufallszahl und $u$ ein geheimer Primfaktor ist), ergibt die Differenz $c - m = g \cdot u$.
• Die Folge: Durch Berechnung des größten gemeinsamen Teilers (GCD) mehrerer solcher Differenzen ($g_1 \cdot u$ und $g_2 \cdot u$) kann der Angreifer den geheimen Parameter $u$ effizient ableiten.
• Ursache: Die ursprüngliche Parameterwahl führte dazu, dass bei Multiplikationen die Modulo-Reduktion durch die Primzahlen $p$ und $q$ nicht effektiv griff (da der Wert $(m + g \cdot u)$ kleiner als $p$ und $q$ blieb), wodurch die Struktur der Geheimnisse direkt im Chiffretext sichtbar wurde.

2. Methodik: Das modifizierte Schema (mFHMRS)

Um diese Schwachstelle zu beheben, schlagen die Autoren das Modified FHMRS (mFHMRS) vor. Die Kernidee besteht in einer Erweiterung des Schemas von zwei auf mehrere Primzahlen und einer strikteren Parametrisierung.

Hauptmerkmale der Modifikation:

1. Erweiterung auf $N+S$ Primzahlen:
   • Statt nur zwei Primzahlen ($p, q$) werden $N+S$ Primzahlen ($p_1, p_2, \dots, p_{N+S}$) generiert.
   • Der Chiffretext besteht nun aus $N+S$ Komponenten (Shares), berechnet mittels des Chinesischen Restsatzes (CRT).
2. Neue Verschlüsselungsfunktion:
   • $c_i = ([(m_i + g_i \cdot u)]_{p_1}, \dots, [(m_i + g_i \cdot u)]_{p_{N+S}})$.
   • Durch die Verwendung mehrerer Primzahlen wird sichergestellt, dass die Summe $m + g \cdot u$ nicht mehr trivialerweise kleiner als jede einzelne Primzahl ist, was die direkte GCD-Analyse verhindert.
3. Homomorphe Operationen:
   • Addition und Multiplikation werden komponentenweise auf den Shares durchgeführt (z. B. $c_{add} = (c_{11}+c_{21}, \dots)$).
   • Die Entschlüsselung rekonstruiert den Wert mittels CRT und führt dann eine Modulo-$u$-Operation durch, um das Ergebnis zu erhalten.

Sicherheitsparameter und Constraints:
Die Autoren leiten strenge mathematische Bedingungen für die Bit-Längen der Parameter her, um Angriffe zu verhindern:

• $l_{p_i}$ (Länge der Primzahlen): Muss groß genug sein, um Raten zu verhindern, aber klein genug, um Gitterangriffe (Lattice Attacks) zu erschweren.
• $l_u$ (Länge von $u$): Muss größer sein als die maximale Größe des Ergebnisses nach homomorphen Operationen ($l_M$), damit die Modulo-$u$-Reduktion bei der Entschlüsselung korrekt funktioniert.
• $l_g$ (Länge der Zufallszahl): Muss groß genug sein ($\ge \lambda/4$), um Angriffe durch Lösen linearer Gleichungssysteme zu verhindern.
• Bedingung $u > p_i$: Dies ist entscheidend, um zu verhindern, dass Differenzen von Chiffretexten (bei gleichen Klartexten) den Wert von $u$ durch GCD offenbaren.

3. Wichtige Beiträge

• Identifikation der KPA-Schwachstelle: Detaillierte Analyse, warum das ursprüngliche FHMRS bei Unterstützung von Multiplikationen anfällig für Known-Plaintext-Angriffe ist.
• Entwurf von mFHMRS: Ein neues Schema, das die Anzahl der CRT-Teile erhöht und die Parameterbeziehungen so anpasst, dass die Geheimnisse ($p_i, u$) nicht mehr durch einfache GCD-Berechnungen oder lineare Gleichungssysteme abgeleitet werden können.
• Umfassende Sicherheitsanalyse: Das Papier bietet eine formale Analyse gegen verschiedene Angriffsvektoren:
  • Brute-Force: Die Schlüsselraumgröße wird durch die Anzahl der Primzahlen und deren Länge exponentiell erhöht.
  • Gitterbasierte Angriffe (Lattice Attacks): Es wird gezeigt, dass der LLL-Algorithmus (Lenstra-Lenstra-Lovász) aufgrund der gewählten Parametergrößen (Fehlerterme und Vektorlängen) keine kurzen Vektoren findet, die die Geheimnisse verraten.
  • Lineare Gleichungssysteme: Die Analyse zeigt, dass die Unvorhersehbarkeit der Zufallszahlen $g_i$ und die Größe von $u$ gegenüber $p_i$ das Lösen von Gleichungssystemen für $u$ und $p_i$ unmöglich macht.
• Korrektur der Entschlüsselung: Herleitung der notwendigen Bedingungen für die Bit-Längen, um sicherzustellen, dass nach $N$ Multiplikationen und $A$ Additionen das Ergebnis noch innerhalb des zulässigen Bereichs liegt, um korrekt entschlüsselt zu werden.

4. Ergebnisse

• Sicherheitsgewinn: Das modifizierte Schema (mFHMRS) widersteht den im ursprünglichen Schema erfolgreichen Known-Plaintext-Angriffen.
• Komplexität:
  • Ein Brute-Force-Angriff auf ein Szenario mit einer Multiplikation ($N=1$) und 128-Bit-Primzahlen hat eine Komplexität von ca. $2^{490}$, was als sicher gilt.
  • Auch bei Known-Plaintext-Angriffen steigt die Komplexität auf ca. $2^{489}$, was weit über den Grenzen aktueller Rechenleistung liegt.
• Effizienz: Der Chiffretext wird größer (da er aus $N+S$ Teilen besteht), was ein notwendiger Kompromiss für die erhöhte Sicherheit ist. Für $N=14$ und $S=5$ beträgt die maximale Chiffretextgröße ca. 3420 Bit.
• Funktionalität: Das Schema behält die volle Funktionalität der homomorphen Addition und Multiplikation bei, erfüllt jedoch die mathematischen Korrektheitsbedingungen für die Entschlüsselung.

5. Bedeutung und Fazit

Die Arbeit ist signifikant für das Feld der Fully Homomorphic Encryption (FHE), da sie zeigt, dass selbst scheinbar sichere symmetrische Schemata durch subtile Parameterwahlfehler (hier das Fehlen einer effektiven Modulo-Reduktion bei Multiplikation) kompromittiert werden können.

• Praktische Relevanz: Die vorgeschlagenen Parameterkonfigurationen und die mathematischen Grenzen bieten einen Leitfaden für die sichere Implementierung von symmetrischen FHE-Schemata.
• Theoretischer Beitrag: Die Analyse der Interaktion zwischen CRT, Gitterangriffen und Known-Plaintext-Szenarien vertieft das Verständnis der Sicherheitsgrenzen von modifizierten Rivest-ähnlichen Schemata.
• Schlussfolgerung: Durch die Einführung mehrerer Primzahlen und die strikte Einhaltung der Relation $u > p_i$ sowie der Bit-Längen-Beschränkungen wird mFHMRS zu einem robusten, sichereren Nachfolger des ursprünglichen FHMRS, der gegen bekannte algebraische Angriffe resistent ist.