⚡ electrical engineering

Secure Two-Party Matrix Multiplication from Lattices and Its Application to Encrypted Control

Diese Arbeit stellt ein sicherheitsbewiesenes Zwei-Parteien-Protokoll für die approximative Matrixmultiplikation auf Gitterbasis vor, das die verschlüsselte Implementierung linearer Regelgesetze ermöglicht und dabei sowohl die Privatsphäre der Steuerungsparameter wahrt als auch eine reduzierte Online-Rechenkomplexität für den Client bietet.

Ursprüngliche Autoren: Kaoru Teranishi

Veröffentlicht 2026-03-25

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Kaoru Teranishi

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 genialer Ingenieur, der eine hochkomplexe Maschine steuert. Diese Maschine reagiert auf Ihre Befehle, aber Sie haben ein großes Problem: Sie dürfen den geheimen Bauplan Ihrer Steuerung (die „Controller-Parameter") und die aktuellen Sensordaten der Maschine niemals einem Dritten zeigen. Wenn Sie diese Daten einfach so an einen Cloud-Server senden, könnte dieser sie ausspähen oder manipulieren.

Früher gab es zwei Möglichkeiten:

Alles selbst berechnen: Sicher, aber sehr langsam und teuer für Sie.
Die Berechnung auslagern: Schnell, aber Sie mussten Ihre Geheimnisse preisgeben.

Dieser Artikel von Kaoru Teranishi stellt nun eine dritte, brillante Lösung vor: Eine Art „magischer Tresor", in dem zwei fremde Helfer Ihre Berechnungen durchführen, ohne jemals zu wissen, was sie eigentlich tun.

Hier ist die einfache Erklärung, wie das funktioniert:

1. Das Grundproblem: Das Rätsel der Multiplikation

Stellen Sie sich vor, Sie wollen zwei große Zahlenblöcke (Matrizen) miteinander multiplizieren. In der normalen Welt ist das einfach. In der verschlüsselten Welt ist es wie ein Puzzle, bei dem die Teile nicht zusammenpassen, wenn man sie nicht entziffert.
Bisherige Methoden hatten zwei große Nachteile:

Zu viel Hin und Her: Die Parteien mussten sich oft hin und her Nachrichten schicken (wie ein langes Telefonat), bis das Ergebnis fertig war.
Zu viel Arbeit für Sie: Sie (der Client) mussten am Ende immer noch viel rechnen, was den Sinn der Auslagerung zunichte machte.

2. Die neue Lösung: Ein einmaliges „Blitz-Handshake"-Protokoll

Der Autor entwickelt ein neues Verfahren, das auf modernster „Gitter-Kryptografie" (Lattice-based cryptography) basiert. Das klingt kompliziert, aber stellen Sie es sich so vor:

Der Trick mit den zwei Helfern: Sie haben zwei Computer (Helfer), die sich nicht trauen, zusammenzuarbeiten (sie sind „nicht kollusiv").
Der einmalige Wurf: Sie senden Ihren verschlüsselten Datenblock einmal an beide Helfer.
Die Magie: Die Helfer führen ihre Berechnungen durch und schicken Ihnen ein einziges Mal das Ergebnis zurück. Es gibt kein langes Hin und Her.
Das Ergebnis: Sie erhalten das Ergebnis der Multiplikation, aber die Helfer haben nie gesehen, was in den Blöcken stand.

3. Die Analogie: Der verschlüsselte Koch

Stellen Sie sich vor, Sie wollen ein geheimes Rezept (die Steuerung) kochen, aber Sie können nicht selbst kochen.

Der alte Weg: Sie schicken das Rezept an einen Koch, der es liest und kocht. Oder Sie schicken es in eine verschlossene Box, aber der Koch muss die Box öffnen, um zu wissen, was drin ist.
Der neue Weg (dieser Artikel):
1. Sie nehmen Ihr Rezept und zerlegen es in zwei Teile.
2. Sie geben Teil A dem ersten Koch und Teil B dem zweiten Koch.
3. Beide Kochen haben auch eine „magische Schürze" (die mathematischen Gitter-Verfahren), die verhindert, dass sie den Inhalt der Teile verstehen.
4. Sie schicken ihnen nur eine kurze Anweisung: „Mischen Sie eure Teile!"
5. Die beiden mischen ihre Teile, ohne zu wissen, was sie mischen, und schicken Ihnen das fertige Gericht zurück.
6. Sie fügen die beiden Teile zusammen und haben Ihr perfektes Gericht – ohne dass die Köche je das Rezept gesehen haben.

4. Warum ist das wichtig für die Zukunft?

Dieses Verfahren wurde speziell für Cyber-Physische Systeme getestet, also für Dinge wie autonome Autos, Roboter oder Stromnetze, die ferngesteuert werden müssen.

Schneller für Sie: Der Artikel zeigt, dass Sie als Besitzer der Maschine jetzt weniger Rechenarbeit haben als wenn Sie alles selbst gemacht hätten. Das ist ein riesiger Vorteil, besonders für kleine Geräte wie Sensoren.
Präzise: Selbst wenn die Verschlüsselung kleine „Rausch"-Fehler einführt (wie ein leichtes Zittern beim Zeichnen), bleibt das Ergebnis so genau, dass die Maschine sicher funktioniert. Ein Test mit einem simulierten Roboterarm zeigte, dass die Fehler winzig klein blieben.
Sicher: Weder die Sensordaten (wo ist das Auto?) noch die Steuerungsgewinne (wie stark bremst es?) werden verraten.

Zusammenfassung

Der Autor hat einen Weg gefunden, wie zwei fremde Computer gemeinsam eine komplexe mathematische Aufgabe lösen können, ohne dass jemand (außer Ihnen) weiß, worum es geht. Und das passiert in einem einzigen Schritt, ohne langes Warten.

Es ist wie ein Einweg-Tresor, der sich automatisch öffnet, sobald die beiden Wächter ihre Teile des Schlüssels zusammengesteckt haben. Das macht die sichere Steuerung von Robotern und Maschinen in der Cloud endlich praktikabel und effizient.

1. Problemstellung

Das Paper adressiert die Herausforderungen der verschlüsselten Regelungstechnik (Encrypted Control) in Cyber-Physical Systems (CPS). Ziel ist es, Regelalgorithmen auf verschlüsselten Daten auszuführen, um die Privatsphäre von Sensordaten, Stellgrößen und Reglerparametern zu schützen, während die Berechnung an unbekannte Server ausgelagert wird.

Bisherige Ansätze stoßen auf folgende Grenzen:

Single-Server-Setting (Homomorphe Verschlüsselung): Der Rechenaufwand für den Client (Entschlüsselung/Verschlüsselung) ist oft höher als bei der unverschlüsselten Berechnung, was die Praktikabilität einschränkt.
Multi-Party-Setting (Geheimhaltungsteilung/Secret Sharing):
- Einfache Protokolle erfordern oft, dass einer der Werte öffentlich ist.
- Interaktive Protokolle benötigen mehrere Kommunikationsrunden.
- Effiziente Alternativen wie replizierte Geheimhaltung benötigen mindestens drei nicht kollabierende Parteien.
- Methoden mit Beaver-Triples erhöhen die Online-Komplexität des Clients oder erfordern Mehr-Runden-Kommunikation.

Das Kernproblem: Es fehlt ein Protokoll für die zwei-Parteien-Berechnung (Two-Party Computation, 2PC), das gleichzeitig eine einzige Kommunikationsrunde erfordert, geringe Online-Komplexität für den Client bietet und die Privatsphäre aller Eingaben und Parameter garantiert.

2. Methodik

Der Autor schlägt ein neues Protokoll für die approximative Matrixmultiplikation von Fixpunktzahlen vor. Die Methode kombiniert additive Geheimhaltungsteilung (Secret Sharing) mit gitterbasierten kryptografischen Primitive (LWE und SIS).

A. Kryptografische Grundlagen

LWE (Learning With Errors): Dient zur Verschlüsselung von Daten. Ein Geheimnis $s$ und ein Fehlervektor $e$ werden genutzt, um eine Nachricht $x$ in einem Chiffretext $c = A^Ts + x + e \mod q$ zu verbergen.
SIS (Short Integer Solution): Dient zur Erstellung von Commitments. Ein Commitment $h = Ay + Br \mod q$ garantiert, dass die Eingabe $y$ nicht verändert werden kann (Binding) und vor dem Öffnen verborgen bleibt (Hiding).

B. Das Kernprinzip: Approximatives Skalarprodukt

Das Protokoll nutzt eine algebraische Eigenschaft, um das Skalarprodukt zweier geheimer Vektoren $x$ und $y$ zu berechnen, ohne sie zu entschlüsseln.
Gegeben sind:

LWE-Chiffretexte für $x$ : $c = A^Ts + x + e$ und $c' = B^Ts + e'$ .
SIS-Commitment für $y$ : $h = Ay + Br$.

Durch die Kombination $c^Ty + (c')^Tr - s^Th \mod q$ heben sich die geheimen Terme $s^TAy$ und $s^TBr$ auf. Das Ergebnis ist näherungsweise $x^Ty$ plus einem kleinen Rauschterm.

C. Das Zwei-Parteien-Protokoll (Mult)

Das Protokoll besteht aus drei Phasen:

Setup (Offline): Der Client generiert öffentliche Parameter ( $A, B$ ) und veröffentlicht sie.
Offline (Client): Der Client berechnet LWE-Chiffretexte für seine Eingabematrix $X$ (inkl. Geheimnis $S$ ) und teilt $S$ mit den beiden Parteien ( $P_0, P_1$ ).
Online (Interaktion):
- Der Client teilt die zweite Eingabematrix $Y$ mit den Parteien.
- Die Parteien generieren lokale Zufallsteile für den SIS-Random-Vektor $R$ .
- Die Parteien berechnen lokal Commitments und führen die oben genannte lineare Kombination durch, um Shares des Ergebnisses $Z$ zu erhalten.
- Die Parteien senden die Shares an den Client, der das Ergebnis rekonstruiert.

Wichtig: Die Berechnung erfolgt über Fixpunktzahlen. Die Matrixmultiplikation wird als ganzzahlige Operation auf skalierten Werten ( $2^\ell \cdot X$ ) durchgeführt, um die Genauigkeit zu kontrollieren.

3. Wichtige Beiträge

Ein-Runden-Protokoll: Entwicklung eines 2PC-Protokolls für Matrixmultiplikation, das nur eine einzige Kommunikationsrunde zwischen den Parteien erfordert.
Geringe Client-Komplexität: Die Online-Aufgaben des Clients beschränken sich auf das Generieren und Rekonstruieren von Shares. Die Komplexität ist $O(n_x + n_u)$ , was niedriger ist als die direkte Berechnung der Regelgesetze ( $O(n_x n_u)$ ).
Theoretische Fehleranalyse: Herleitung sufficient conditions (ausreichender Bedingungen) für die Bit-Längen der Fixpunktzahlen ( $k$ $k$ für Ganzzahlteil, $\ell$ $ℓ$ für Nachkommastellen), um sicherzustellen, dass:
- Keine Modular-Überläufe (Wrap-around) auftreten.
- Der Approximationsfehler unter einem definierten Schwellenwert $\epsilon$ bleibt.
Sicherheitsbeweis: Der Nachweis der Sicherheit unter den Standardannahmen LWE und SIS im semi-honesten Modell (die Parteien folgen dem Protokoll, versuchen aber, Informationen abzuleiten).

4. Ergebnisse und Evaluation

Anwendung auf lineare Regelgesetze: Das Protokoll wurde auf ein lineares Regelgesetz $u(\tau) = Kx(\tau) + v(\tau)$ angewendet.
Numerisches Beispiel:
- Ein lineares zeitinvariantes System wurde mit einem Feedback-Gain $K$ simuliert.
- Parameter: LWE-Parameter $(n=212, q=2^{108}, \sigma=3.2)$ für 128-Bit-Sicherheit.
- Fixpunkt-Parameter: $k=53, \ell=44$ .
Genauigkeit: Die Simulation zeigte, dass der Fehler zwischen dem verschlüsselten berechneten Stellgrößenvektor und dem idealen Wert theoretisch unter $2^{-10}$ liegt.
Leistung: Der Client erreicht eine niedrigere Online-Rechenkomplexität im Vergleich zur unverschlüsselten Berechnung, während die Privatsphäre von $K$ , $x$ , $u$ und $v$ gewahrt bleibt.

5. Bedeutung und Fazit

Dieses Paper stellt einen bedeutenden Fortschritt im Bereich der verschlüsselten Regelungstechnik dar. Es löst das Dilemma zwischen Sicherheit, Effizienz und Kommunikationsaufwand in Zwei-Parteien-Szenarien.

Praktische Relevanz: Es ermöglicht erstmals die Auslagerung von Regelungsrechnungen an zwei unsichere Server, ohne dass der Client einen hohen Rechenaufwand trägt oder die Kommunikation mehrstufig wird.
Innovation: Die Kombination von Secret Sharing mit LWE/SIS für Matrixoperationen ist neuartig und umgeht die Notwendigkeit von Beaver-Triples oder Mehr-Parteien-Setups.
Zukunftsausblick: Der Autor plant, den Rahmen auf dynamische Regler zu erweitern und die Rechenkosten für die Server weiter zu optimieren.

Zusammenfassend bietet das vorgestellte Protokoll einen praktikablen Weg, um Cyber-Physical Systems gegen Angriffe auf die Integrität und Vertraulichkeit der Regelungsdaten abzusichern, ohne die Echtzeitfähigkeit zu beeinträchtigen.