💻 computer science

Rotation-Optimal Noncommutative Prefix Scans in Bit-Reversed Homomorphic Layouts

Diese Arbeit führt einen rotationsoptimalen Präfix-Scan-Algorithmus für bit-reversierte Layouts der homomorphen Verschlüsselung ein, der die Rotationskomplexität durch die Nutzung einer replizierten-aggregierten Invariante von $O(m^2)$ auf $O(m)$ reduziert und dadurch die Rechenlatenz, den Speicherverbrauch sowie die Speicherung von Evaluationsschlüsseln signifikant senkt und gleichzeitig tiefere nachgeschaltete Pipelines ermöglicht.

Ursprüngliche Autoren: Anis Bkakria, Madicke-Diadji Mbodj, Mawloud Omar, Reda Yaich

Veröffentlicht 2026-07-07

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Anis Bkakria, Madicke-Diadji Mbodj, Mawloud Omar, Reda Yaich

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 haben eine riesige, verschlüsselte Tabelle, in der jede Zelle eine geheime Zahl enthält. Sie möchten mit all diesen Zahlen gleichzeitig einen speziellen mathematischen Trick anwenden: Für jede Zelle müssen Sie die „laufende Summe“ aller Zahlen ermitteln, die vor ihr kamen. In der Welt der homomorphen Verschlüsselung (Berechnungen auf geheimen Daten, ohne diese jemals zu entschlüsseln) nennt man dies einen „Präfix-Scan“ (Prefix Scan).

Das Problem ist, dass die Daten nicht in einer ordentlichen Reihe wie 1, 2, 3, 4 gespeichert sind. Weil die Verschlüsselung so funktioniert, sind die Daten in einem speziellen Muster verschachtelt, das als „bit-invertierte Reihenfolge“ bezeichnet wird. Es ist wie ein Buch, bei dem die Seiten durcheinandergewürfelt sind: Seite 1 folgt auf Seite 8, dann Seite 4, dann Seite 12 und so weiter.

Die alte Methode: Das Problem des „exakten Nachbarn“

Um die laufende Summe zu berechnen, müssen Sie normalerweise Ihren Nachbarn nach dessen Zahl fragen. In einer normalen Reihe ist Ihr Nachbar nur einen Schritt entfernt. Aber in diesem verschachtelten „bit-invertierten“ Buch kann Ihr logischer Nachbar jedoch am anderen Ende des Raumes sitzen.

Die alte Methode versuchte, dies zu lösen, indem sie einen Boten (eine „Rotation“) schickte, um genau den spezifischen Nachbarn zu holen, den man brauchte.

Die Analogie: Stellen Sie sich vor, Sie sind in einer Bibliothek mit 8 Regalen. Sie müssen mit der Person sprechen, die direkt links von Ihnen im Regal steht. Aber weil die Regale verschachtelt sind, bedeutet „links“ für verschiedene Menschen unterschiedliche physische Entfernungen.
Die Kosten: Um jeden seinen korrekten Nachbarn zu besorgen, musste der Bibliothekar viele verschiedene Wege mit Boten schicken. Für ein kleines Buch mit 8 Seiten benötigte er 6 Boten. Für ein größeres Buch explodierte die Zahl der Boten (sie wuchs wie eine Dreieckszahl: 1+2+3+4...). Dies war langsam, teuer und erforderte eine riesige Bibliothek an „Schlüsseln“ (Genehmigungen), um Boten an all diese verschiedenen Stellen zu senden.

Die neue Methode: Die „Copycat“-Strategie

Die Autoren dieses Papers erkannten, dass sie viel zu wählerisch waren. Sie brauchten nicht den exakten Nachbarn; sie brauchten einfach irgendjemanden aus der Gruppe des Nachbarn, der über dieselbe Information verfügt.

Die Analogie: Anstatt nach der spezifischen Person links zu fragen, stellen Sie sich vor, dass jeder in einer „Gruppe“ (einem Block von Regalen) eine identische Kopie der Gesamtsumme der Gruppe hält.
Der magische Zug: Die Autoren fanden einen Weg, die gesamte Bibliothek pro Berechnungsebene nur ein einziges Mal zu rotieren. Diese einzige Rotation bewegt alle an einen Ort, an dem sie neben jemandem aus der benachbarten Gruppe stehen. Da jeder in dieser Gruppe eine Kopie der „Gruppensumme“ hält, spielt es keine Rolle, welche spezifische Person man bekommt; die Mathematik funktioniert trotzdem perfekt.
Das Ergebnis: Anstatt 6 Boten für 8 Seiten zu benötigen, benötigen Sie nur 1 Boten pro Ebene. Für das ganze Buch benötigen Sie also statt einer Dreieckszahl von Boten (wie 28) nur die Anzahl der Ebenen (wie 7).

Was sie tatsächlich bewiesen haben

Das Paper sagt nicht nur „das ist schneller“. Sie haben drei harte mathematische Fakten bewiesen:

Man kann es nicht besser machen: Sie haben bewiesen, dass man, egal wie clever man ist, mindestens so viele Rotationen wie es Ebenen in der Berechnung gibt, verwenden muss. Man kann die Boten nicht ganz weglassen.
Die „perfekte“ Route: Sie zeigten, dass die Boten, wenn man die minimale Anzahl an Boten verwendet, einem sehr spezifischen, starren Muster folgen müssen (bezogen auf Zweierpotenzen). Es gibt keinen Spielraum; die Mathematik erzwingt diesen spezifischen Pfad.
Der Kompromiss: Um Boten einzusparen, muss man lokal etwas mehr mathematische Arbeit leisten (zwei Sätze von Zahlen statt einem). Aber in ihren Tests war das Einsparen der Boten die Arbeit wert.

Der Praxistest (Das „Übertrag“-Problem)

Sie haben dies an einem sehr verbreiteten mathematischen Problem getestet: dem Übertrag (wie wenn man 9 + 3 rechnet und 12 erhält – man muss die 1 zur nächsten Spalte „übertragen“).

Das Setup: Sie haben eine Liste von Ziffern verschlüsselt und versucht, die Überträge zu korrigieren, ohne die Reihenfolge zu entwirren.
Das Ergebnis:
- Geschwindigkeit: Ihre neue Methode war bei mittleren Problemen etwa 20 % schneller als die alte „exakte Nachbar“-Methode.
- Speicher: Sie verbrauchte 64 % weniger Speicher, da sie nicht so viele Genehmigungsschlüssel speichern mussten.
- Der große Sieg: In einer längeren Kette von Berechnungen sparte ihre Methode so viel „Verschlüsselungsleistung“, dass sie ein massives, langsames Reset-Verfahren (genannt „Bootstrapping“) vermeiden konnte. Dies machte den gesamten Prozess 4,3-mal schneller am Ende.

Zusammenfassung

Denken Sie an einen Staffellauf.

Alte Methode: Jeder Läufer musste einen einzigartigen, langen, gewundenen Pfad laufen, um seinen spezifischen Teamkollegen zu finden. Das kostete viel Energie und Zeit.
Neue Methode: Das Team erkannte, dass wenn sie einfach eine kurze, standardisierte Runde laufen, jeder neben einem Teamkollegen landen würde, der denselben Staffelstab hält. Es brauchte weniger Schritte, weniger Energie und erledigte den Job schneller, obwohl die Läufer dabei ein paar zusätzliche Staffelstäbe halten mussten.

Das Paper beweist, dass diese Abkürzung der absolut schnellste Weg ist, diese spezifische Art von Mathematik auf verschachtelten, verschlüsselten Daten durchzuführen.

Technisches Resümee: Rotationsoptimale nichtkommutative Präfix-Scans in bit-invertierten homomorphen Layouts

Problemstellung

In der gepackten homomorphen Verschlüsselung (HE), speziell beim CKKS-Schema, ermöglichen SIMD-Operationen die parallele Berechnung auf verschlüsselten Vektoren. Die Kommunikation zwischen Slots erfordert jedoch zyklische Rotationen (Galois-Automorphismen), welche kostspielige Operationen sind, die Key-Switching beinhalten. Die Kosten einer Rotation hängen von der physischen Anordnung der Daten ab.

Das Paper adressiert das Problem der Durchführung von geordneten Präfix-Berechnungen (Scans) auf $n = 2^m$ Elementen eines assoziativen, möglicherweise nichtkommutativen Monoids, wenn die Daten in einer bit-invertierten Reihenfolge gespeichert sind. Dieses Layout ist üblich bei schnellen Transformationen und Packing-Konversionen.

Die zentrale Herausforderung besteht darin, dass ein Standard-"Transported-Predecessor"-Scan, der den Abstand zu logischen Vorgängern rekursiv verdoppelt, in einem bit-invertierten Layout einen hohen Routing-Aufwand verursacht. Da die Bit-Invertierung die logischen Indizes permutiert, zerfällt ein einzelner logischer Shift um $2^t$ in mehrere distinkte zyklische Verschiebungsklassen. Folglich erfordert eine direkte Implementierung $R_{direct} = \sum_{t=0}^{m-1} (m-t) = \frac{m(m+1)}{2}$ Rotationen. Die Autoren untersuchen, ob dieser quadratische Kostenfaktor eine inhärente Eigenschaft der Präfix-Berechnung in bit-invertierten Layouts ist oder ein Artefakt der spezifischen Routing-Topologie.

Methodik und Konstruktion

Das Paper führt ein replicated-aggregate invariant ein, um die Anzahl der Rotationen von quadratisch auf linear zu reduzieren.

Semantische Replikation: Anstatt jeden Slot exakt zu seinem logischen Vorgänger zu routen, hält die Konstruktion einen Zustand aufrecht, in dem jeder Slot innerhalb eines ausgerichteten logischen Blocks das vollständige Aggregat dieses Blocks speichert.
Sibling-Block-Austausch: Auf jeder Ebene $d$ $d$ des Scans (Kombination von Blöcken der Größe $2^d$ $2^{d}$ ) rotiert der Algorithmus den Aggregatzustand um einen spezifischen Offset $s_d = 2^{m-d-1}$ $s_{d} = 2^{m - d - 1}$ .
- Unter Bit-Invertierung besetzen die beiden Kinder eines Eltern-Blocks physische Kosets, die exakt durch $s_d$ getrennt sind.
- Eine Rotation um $s_d$ bildet einen Slot auf eine Position im Geschwister-Block ab. Da das Aggregat des Geschwister-Blocks über alle seine Slots repliziert ist, liefert jede Position im Geschwister-Block den korrekten semantischen Wert.
- Dies ermöglicht eine einzige gerichtete zyklische Rotation, um gültige Aggregate für beide Kind-Orientierungen gleichzeitig bereitzustellen, wobei die Korrektheit für nichtkommutative Monoide durch öffentliche Masken gewahrt bleibt, die die Operandenreihenfolge auswählen.
Exklusiver Scan-Ansatz: Die Autoren implementieren einen exklusiven Scan (der das Präfix vor dem aktuellen Element ausgibt). Dies vermeidet die Notwendigkeit eines abschließenden logischen-Vorgänger-Shifts, um den eingehenden Übertrag zur Korrektur der Ziffer zu erhalten – eine Anforderung, die andernfalls die layoutsensitive Routung reintroduzieren würde.
Untere Schranken-Beweise: Das Paper etabliert $m$ Rotationen als globale untere Schranke für jeden Schaltkreis, der eine Ausgabe berechnet, die von allen $2^m$ Eingängen abhängt, in diesem Modell. Der Beweis stützt sich auf ein Teilsummen-Argument: Wenn $R$ Rotationen verwendet werden, können maximal $2^R$ distinkte Eingangs-Displacements einen festen Ausgang erreichen. Um alle $2^m$ Eingänge abzudecken, ist $R \ge m$ notwendig. Des Weiteren beweist das Paper, dass das Erreichen dieser Schranke erfordert, dass die Rotations-Offsets eine vollständige 2-adische Basis (ein Offset für jede Valuierung $0, \dots, m-1$ ) bilden.

Kernbeiträge

Optimaler Scan-Konstruktion: Ein inklusiver und exklusiver Scan-Algorithmus, der $R = m$ Rotationen und $D = m$ Monoid-Tiefe für bit-invertierte Layouts erreicht. Dies reduziert die Rotationsanzahl von der direkten Topologie ( $O(m^2)$ ) auf $O(m)$ .
Rigidität der Optimalität: Eine Charakterisierung aller optimalen Schaltkreise. Wenn ein Schaltkreis exakt $m$ Rotationen verwendet, müssen die Offsets eine vollständige 2-adische Basis bilden. Dies beweist, dass das Rotationsprofil starr (rigid) ist, selbst wenn sich die Schaltkreis-Topologie ändert.
Rotation-Key-Frontier: Eine Analyse des Trade-offs zwischen der Anzahl der direkt genutzten Schlüssel-Offsets ( $K$ $K$ ) und der Anzahl der Online-Rotationsaufrufe ( $R$ $R$ ).
- Das Paper leitet eine Produkt-Untergrenze ab: $\prod (c_j + 1) \ge 2^m$ , wobei $c_j$ die Anzahl der Nutzungen des Schlüssels $j$ ist.
- Wenn $K$ ein Teiler von $m$ ist, wird die exakte Frontier als $R^* = K \cdot (2^{m/K} - 1)$ bewiesen.
Radix-CKKS-Instanziierung: Anwendung des exklusiven Scans auf die exakte Übertrag- und Borrows-Propagation in radix-basiertem CKKS. Dies ermöglicht Ganzzahlvergleiche und modulare Arithmetik, ohne die natürliche Ordnung wiederherzustellen oder einen finalen Shift durchzuführen.
Batching-Effizienz: Demonstration, dass die Rotationsersparnis auch für vollständig besetzte Digit-Major-Interleavings gilt, bei denen $g$ unabhängige Ganzzahlen in ein einziges Ciphertext gepackt werden, ohne die Anzahl der Rotationen zu vervielfachen.

Ergebnisse und Evaluierung

Die Autoren implementierten den Algorithmus in Lattigo (Go) und verglichen ihn mit zwei Baselines:

Direkter Bit-Invertierter Predecessor: Der naive $O(m^2)$ Rotationsansatz.
Normalize–Scan–Restore: Eine Baseline, die Daten in die natürliche Ordnung konvertiert, scannt und wieder zurückkonvertiert.

Wesentliche Erkenntnisse bei $m=7$ (128 Slots):

Rotationen: Reduziert von 28 (direkt) auf 7 (repliziert).
Evaluations-Keys: Speichereffizienz um 70,0 % gesteigert (908,6 MB $\to$ 272,6 MB).
Speicher: Peak-Heap-Nutzung um 63,9 % reduziert (2,30 GB $\to$ 830,5 MB).
Latenz: Der replizierte Scan verbesserte die isolierte Scan-Latenz um 19,9 % gegenüber der direkten Predecessor-Methode.
End-to-End Pipeline: In einer Downstream-Pipeline mit Tiefe 5 vermied der replizierte Scan eine vollständige Bootstrapping-Operation, die für die Normalize-Restore-Baseline erforderlich gewesen wäre. Dies ergab eine mittlere Paar-Beschleunigung von 4,31 $\times$ (95 % KI [3,69, 4,92]).

Das Paper merkt an, dass während "Normalize–Scan–Restore" bei kleinem $m$ eine geringere isolierte Latenz aufweist (aufgrund weniger Monoid-Kompositionen), der replizierte Scan bei $m \ge 5$ schneller wird und eine überlegene Ressourceneffizienz (Keys, Speicher, Modulus-Level) bietet.

Bedeutung und Ansprüche

Das Paper behauptet, dass die Beibehaltung einer bit-invertierten SIMD-Repräsentation keine unvermeidbare Rotations-Overhead für geordnete Präfix-Berechnungen erzwingt. Die Bedeutung liegt in:

Durchbrechen der quadratischen Barriere: Der Beweis, dass die $O(m^2)$ -Kosten des direkten Routings in bit-invertierten Layouts nicht inhärent sind, sondern durch semantische Replikation auf die theoretische Untergrenze von $O(m)$ gesenkt werden können.
Ressourcen-Trade-offs: Die Feststellung, dass die Reduktion der Routing-Kosten (Rotationen) und des Key-Speichers zu Lasten der erhöhten gepackten Monoid-Arbeit ( $2m-1$ Kompositionen vs. $m$ ) und eines zweiten Live-State-Vektors geht. Das Paper argumentiert, dass dieser Trade-off vorteilhaft für tiefe Pipelines ist, in denen Modulus-Level und Bootstrapping Engpässe darstellen.
Exaktheit: Bereitstellung exakter Untergrenzen und Frontier-Charakterisierungen für das Rotations-Key-Management, was über heuristische Optimierungen hinausgeht und beweisbare Limits für spezifische Abhängigkeitsmuster liefert.

Die Arbeit ist als spezifische Optimierung für die Beschränkung des bit-invertierten Layouts konzipiert, unterscheidet sich von allgemeiner Präfix-Netzwerktheorie und wird durch rigorose kombinatorische Beweise sowie empirische Evaluierung in einer Standard-CKKS-Implementierung validiert.