💻 computer science

Multi-Input Ciphertext Multiplication for Homomorphic Encryption

Dieser Beitrag stellt eine optimierte Multiplikationsmethode für Multi-Input-Chiffretexte in der Homomorphen Verschlüsselung vor, die durch reformulierte Berechnungen, zusätzliche Bewertungsschlüssel und einen mehrstufigen Reskalierungsansatz über zwei Eingaben hinausgeht und zu Hardware-Architekturen führt, die im Vergleich zu früheren Entwürfen die Logikfläche und Latenz erheblich reduzieren.

Ursprüngliche Autoren: Sajjad Akherati, Xinmiao Zhang

Veröffentlicht 2026-05-19

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Sajjad Akherati, Xinmiao Zhang

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 sind ein Meisterkoch, der einen Kuchen backen möchte, aber es gibt einen Haken: Sie müssen das gesamte Mischen und Backen mit dicken, schweren Ofenhandschuhen durchführen, die es Ihnen unmöglich machen, die Zutaten zu fühlen oder die Schüssel zu sehen. Dies ist Homomorphe Verschlüsselung (HE). Sie ermöglicht Computern, Mathematik auf „verschlüsselten" Daten (dem Kuchenteig in den Handschuhen) durchzuführen, ohne sie jemals zu entschlüsseln (die Handschuhe auszuziehen). Dies hält Geheimnisse sicher, seien es Ihre medizinischen Unterlagen oder Ihr Bankguthaben.

Das Rechnen mit diesen „Handschuhen" ist jedoch unglaublich langsam und chaotisch. Der größte Engpass ist die Multiplikation. Bei der Standardverschlüsselung können Sie nur zwei Zutaten gleichzeitig multiplizieren. Viele moderne Aufgaben, wie das Trainieren einer KI zur Erkennung einer Krankheit oder die Analyse komplexer Finanztrends, erfordern jedoch, dass viele Zutaten (Chiffretexte) gleichzeitig miteinander multipliziert werden.

Dieser Artikel stellt eine neue, super-effiziente Methode vor, um diese verschlüsselten Zutaten zu multiplizieren, speziell für eine beliebte Verschlüsselungsmethode namens CKKS. Hier ist die Aufschlüsselung ihres Durchbruchs mit einfachen Analogien:

1. Das Problem: Die „unordentliche Küche"

Wenn Sie verschlüsselte Zahlen multiplizieren, wird das „Rauschen" (die Unordnung, die durch die Ofenhandschuhe entsteht) immer lauter. Wenn Sie zu viele Zahlen gleichzeitig multiplizieren, ohne aufzuräumen, übertönt das Rauschen die eigentlichen Daten, und das Ergebnis wird zu Müll.

Um dies zu beheben, muss das Verschlüsselungssystem nach jeder Multiplikation einen „Aufräum"-Schritt namens Reskalierung durchführen. Stellen Sie sich dies vor als Anhalten, um die Arbeitsfläche abzuwischen und die Zutaten wieder in Ordnung zu bringen.

Der alte Weg: Wenn Sie 10 Zutaten multiplizieren mussten, war die alte Methode wie ein Förderband, auf dem Sie zwei multiplizierten, anhielten, um aufzuräumen, zwei weitere multiplizierten, wieder anhielten, um aufzuräumen, und so weiter. Es war langsam und erforderte viele Reinigungsmittel (Hardware-Ressourcen).
Der vorherige „Drei-Zutaten"-Versuch: Die frühere Arbeit der Autoren zeigte, dass man drei Zutaten gleichzeitig multiplizieren konnte, was schneller war. Es gab jedoch immer noch viele unnötige Aufräumschritte.

2. Die Lösung: Die „intelligente Fließbandproduktion"

Die Autoren schlagen zwei wesentliche Verbesserungen vor, um diesen Prozess schneller und kompakter zu machen:

A. Die „Ein-Schritt-Aufräumaktion" (Verbesserte 3-Eingangs-Multiplikation)

Bei ihrem neuen Design zur Multiplikation von drei Zutaten stellten sie fest, dass sie das Aufräumen (Reskalierung) und das Neuordnen (Relinearisierung) auf eine ungeschickte, umständliche Weise durchführten.

Die Analogie: Stellen Sie sich vor, Sie haben drei Schüsseln mit Teig. Die alte Methode bestand darin, sie zu mischen, die Mischung in eine neue Schüssel zu gießen, die alten Schüsseln zu reinigen, die Mischung erneut zu gießen und erneut zu reinigen.
Die Lösung: Sie haben den Prozess so neu gestaltet, dass Sie mischen und aufräumen in einer einzigen flüssigen Bewegung können. Sie haben herausgefunden, wie man die Reinigungsschritte kombiniert, sodass Sie nicht so oft anhalten und die Arbeitsfläche abwischen müssen.
Das Ergebnis: Ihr neuer „Drei-Schüsseln-Mischer" ist 50 % schneller (Latenz) und belegt 15 % weniger Platz auf dem Chip (Fläche) im Vergleich zu ihrem vorherigen besten Design.

B. Die „Gruppenreinigung" (Multi-Eingangs-Multiplikation)

Was ist, wenn Sie vier, fünf oder sogar zwölf Zutaten gleichzeitig multiplizieren müssen?

Der alte Weg: Sie würden eine lange Kette von „Zwei-Schüsseln-Mischern" aufbauen. Sie mischen zwei, reinigen, mischen zwei weitere, reinigen, mischen dann die Ergebnisse, reinigen erneut. Dies erzeugt eine sehr lange Kette (hohe „multiplikative Tiefe"), was bedeutet, dass sich das Rauschen zu schnell aufbaut.
Die neue Strategie: Die Autoren stellten fest, dass man, wenn man die Zutaten anders gruppiert, eine „Gruppenreinigung" durchführen kann.
- Anstatt nach jedem einzelnen Schritt zu reinigen, entwickelten sie einen mathematischen Trick (genannt Multi-Reskalierung), der es ermöglicht, mehrere Schichten von Unordnung gleichzeitig zu warten und zu reinigen.
- Die Analogie: Stellen Sie sich vor, Sie spülen Geschirr. Anstatt einen Teller zu waschen, ihn zu trocknen und wegzustellen, dann eine Tasse zu waschen, sie zu trocknen und wegzustellen, waschen Sie einen ganzen Stapel Geschirr, trocknen dann den ganzen Stapel und stellen ihn alle weg. Sie führen das „Trocknen" (den teuren, langsamen Teil) nur einmal für die gesamte Gruppe durch.
Das Ergebnis: Durch die Neuordnung der Gruppierung der Zutaten (die „Partitionierung") können sie diese Reinigungsschritte kombinieren. Für die Multiplikation von 4 bis 12 Zutaten spart ihre neue Methode 32 % des Platzes und halbiert die Zeit (45 % schneller) im Vergleich zur alten „Zwei-für-Zwei"-Kette.

3. Warum dies wichtig ist (laut dem Artikel)

Der Artikel konzentriert sich strikt auf die Hardware-Architektur – das physische Design des Computerchips, der diese Mathematik durchführt.

Sie bewiesen, dass man, indem man ändert, wie die Mathematik organisiert ist (der Algorithmus) und wie der Chip gebaut ist (die Architektur), komplexe verschlüsselte Mathematik viel schneller durchführen kann.
Sie erwähnen speziell, dass dies Anwendungen wie maschinelles Lernen, medizinische Diagnose und Finanzanalyse unterstützt, da diese Bereiche oft die Multiplikation vieler verschlüsselter Datenpunkte erfordern.

Zusammenfassung

Stellen Sie sich diesen Artikel als die Erfindung einer neuen, super-effizienten Küche für einen Koch vor, der seine Ofenhandschuhe nicht ausziehen kann.

Sie haben herausgefunden, wie man drei Zutaten gleichzeitig mischt, ohne Unordnung zu verursachen.
Sie haben eine Methode erfunden, um mehrere Schichten von Unordnung gleichzeitig aufzuräumen, anstatt eine nach der anderen.
Das Ergebnis ist eine Küche, die kleiner, schneller und energieeffizienter ist, um Geheimnisse sicher zu halten, während komplexe Mathematik durchgeführt wird.

Die Autoren haben dies in diesem Artikel nicht an echten Patienten oder echten Bankkonten getestet; sie haben lediglich bewiesen, dass die Maschine, die für diese Arbeit entwickelt wurde, signifikant besser ist als die Maschinen, die wir vorher hatten.

Technische Zusammenfassung: Multiplikation von Mehrfacheingangs-Chiffretexten für Homomorphe Verschlüsselung

Problemstellung
Homomorphe Verschlüsselung (HE), insbesondere das RNS-CKKS-Schema, ermöglicht arithmetische Operationen auf verschlüsselten Daten, was für datenschutzkonforme Anwendungen wie maschinelles Lernen und medizinische Diagnostik entscheidend ist. Standard-HE-Schemata definieren die Chiffretextmultiplikation jedoch nur für zwei Eingänge. Viele praktische Anwendungen, wie hochordentliche Polynomapproximationen für Aktivierungsfunktionen neuronaler Netze (z. B. ReLU), Entscheidungsbäume und Genomsequenzierung, erfordern die Multiplikation mehrerer Chiffretexte ( $n > 2$ ).

Bestehende Ansätze zur Handhabung der Mehrfacheingangsmultiplikation verketten typischerweise mehrere Zweieingangsmultiplikatoren in einer binären Baumstruktur. Diese Methode leidet unter zwei primären Ineffizienzen:

Hohe Latenz und Flächenbedarf: Das sequenzielle Multiplizieren von $n$ Chiffretexten unter Verwendung von Zweieingangseinheiten führt zu erheblichem Hardware-Overhead und Latenz.
Rauschwachstum und Rescaling-Overhead: Jede Multiplikation erhöht das Rauschniveau, was eine Rescaling-Operation zur Wiederherstellung der Nachrichtenskala erforderlich macht. In einem standardmäßigen binären Baum muss nach jedem Multiplikationsschritt ein Rescaling erfolgen, um ein exponentielles Rauschwachstum zu verhindern. Dies führt zu einer großen Anzahl von Rescaling-Einheiten, die jeweils teure Number Theoretic Transform (NTT)- und Inverse NTT (INTT)-Operationen erfordern, was die rechnerische Komplexität und die Nutzung von Hardware-Ressourcen erheblich erhöht.

Methodik
Der Artikel schlägt einen Rahmen für die direkte $n$ -Eingang-Chiffretextmultiplikation vor, der die multiplikative Tiefe und die Hardware-Komplexität minimiert. Die Methodik gliedert sich in zwei Hauptbeiträge:

Verbesserter Dreieingangsmultiplikator:
Die Autoren reformulieren zunächst den Prozess der Dreieingangsmultiplikation. In der Vorarbeit [26] wurden Relinearisierung und Rescaling separat durchgeführt, was mehrere ModUp/ModDown-Operationen und zahlreiche (I)NTT-Blöcke erforderte. Das neue Design:
- Reformuliert die Relinearisierung: Durch das Verschieben des $P^{-1}$ -Skalierungsfaktors in die Basisumwandlung (BConv) und die Multiplikation mit dem Evaluierungsschlüssel werden separate Skalierungsschritte eliminiert.
- Optimiert das Rescaling: Die Autoren strukturieren den Datenpfad so um, dass das Rescaling im ursprünglichen Bereich vor der finalen NTT durchgeführt wird, anstatt im NTT-Bereich. Dies ermöglicht die Eliminierung redundanter (I)NTT-Operationen.
- Ergebnis: Diese Änderungen reduzieren die Anzahl der (I)NTT-Blöcke im Datenpfad von acht auf vier und halbieren effektiv die Länge des Datenpfads.
Mehrereingangserweiterung mit kombiniertem Rescaling:
Um die Multiplikation auf $n > 3$ Eingänge zu erweitern, ohne die multiplikative Tiefe zu erhöhen, führt der Artikel ein:
- Generalisierte Evaluierungsschlüssel: Neue Evaluierungsschlüssel ( $ek_t$ ) werden eingeführt, um die durch die Multiplikation von $n$ Chiffretexten erzeugten Polynomterme höheren Grades ( $d_t s^t$ ) zu relinearisieren und das Ergebnis zurück in ein Zwei-Polynom-Format zu überführen.
- Multi-Rescaling-Algorithmus (Multi-RS): Eine theoretische Analyse identifiziert Bedingungen, unter denen mehrere Rescaling-Operationen verzögert und kombiniert werden können. Die Autoren schlagen einen Algorithmus vor, der $\mu$ verkettete Rescaling-Operationen unter Verwendung derselben Anzahl von (I)NTT-Operationen wie eine einzelne Rescaling durchführt. Dies wird erreicht, indem der Eingang in den INTT-Bereich transformiert, im Koeffizientenbereich eine iterative Rescaling durchgeführt und zurücktransformiert wird, wobei vorkalkulierte Konstanten zur Verschmelzung der Operationen genutzt werden.
- Leitlinien zur Eingangspartitionierung: Der Artikel liefert Leitlinien zur Partitionierung von $n$ Eingängen in Gruppen (z. B. $(n_1, n_2, \dots, n_m)$ ), um die Anzahl der kombinierten Rescaling-Operationen zu maximieren und gleichzeitig die optimale multiplikative Tiefe von $\lceil \log_2 n \rceil$ beizubehalten. Dies beinhaltet die Schaffung von unausgewogenen Baumstrukturen, wo möglich, um mehr Eingänge vor einem Rescaling-Schritt zu gruppieren.

Hauptbeiträge

Algorithmische Reformulierung: Eine neue Formulierung für die Dreieingangsmultiplikation, die Zwischenergebnisse kombiniert, die Anzahl der (I)NTT-Operationen reduziert und den Datenpfad verkürzt.
Mehrereingangs-Rahmen: Eine Erweiterung der Chiffretextmultiplikation auf beliebige $n$ Eingänge unter Verwendung generalisierter Evaluierungsschlüssel und eines baumstrukturierten Multiplikators.
Kombiniertes Rescaling: Ein neuartiger Multi-Rescaling-Algorithmus, der die Komplexität der Durchführung mehrerer Rescalings auf die einer einzelnen Rescaling reduziert, unabhängig von der Anzahl der kombinierten Schritte ( $\mu$ ).
Hardware-Architektur: Entwurf vollständig gepipelinerter Hardware-Architekturen für die vorgeschlagenen Multiplikatoren, einschließlich optimierter ModUp-, ModDown- und Rescaling-Einheiten.

Ergebnisse
Die vorgeschlagenen Designs wurden mit dem GlobalFoundries 22FDX-Prozess unter den Parametern $N=2^{16}$ , $L=K=24$ und $w=64$ synthetisiert.

Dreieingangsmultiplikator: Im Vergleich zur vorherigen Arbeit [26] erreicht der verbesserte Dreieingangsmultiplikator eine Reduktion des Logikflächenbedarfs um 15 % und eine Reduktion der Latenz um 50 %. Aufgrund weniger (I)NTT-Einheiten reduziert er zudem den Speicherbedarf um etwa 20 %.
Mehrereingangsmultiplikatoren ( $n=4$ bis $12$): Im Vergleich zu einer Baseline-Implementierung unter Verwendung eines binären Baums aus Zweieingangsmultiplikatoren erreicht die vorgeschlagene Methode eine durchschnittliche Reduktion der Gesamtfläche um 32 % und eine Reduktion der Latenz um 45 %.
Rescaling-Effizienz: Für Nicht-Potenz-von-zwei-Eingänge (z. B. $n=17$ ) reduziert die optimierte Partitionierung in Kombination mit Multi-Rescaling die Gesamtzahl der Rescaling-Einheiten (und der damit verbundenen (I)NTT-Operationen) im Vergleich zum Standardansatz mit binärem Baum um etwa 47 %.

Bedeutung
Der Artikel behauptet, dass diese Verbesserungen den Engpass der Mehrfacheingangsmultiplikation in der HE adressieren, der für komplexe datenschutzkonforme Anwendungen unerlässlich ist. Durch die Reduzierung der Hardware-Komplexität und der Latenz der Chiffretextmultiplikation macht die vorgeschlagene Architektur den Einsatz von HE in ressourcenbeschränkten oder hochdurchsatzfähigen Umgebungen praktikabler. Die Arbeit zeigt, dass durch algorithmische Reformulierung und sorgfältige Eingangspartitionierung der Overhead des Rauschmanagements (Rescaling) erheblich minimiert werden kann, ohne die Sicherheit oder Korrektheit des Verschlüsselungsschemas zu beeinträchtigen. Die Autoren weisen darauf hin, dass sich zukünftige Arbeiten auf die weitere Vereinfachung von Multiplikatoren für noch größere Anzahlen von Eingängen konzentrieren werden.