Jenseits von Key-Escrow: Gitterbasierte Registration-Based Encryption und der Paradigmenwechsel in der PKI

Die Debatte um die Ablösung klassischer Public-Key-Infrastrukturen ist so alt wie die PKI selbst. Zu komplex, zu fehleranfällig, zu abhängig von Zertifikatsketten, die im Ernstfall brechen – das sind keine neuen Kritikpunkte. Doch die Alternativen, die in den vergangenen Jahrzehnten entstanden sind, haben das Dilemma meist nur verlagert, nicht gelöst. Identity-Based Encryption (IBE) erkauft ihre elegante Einfachheit durch ein strukturelles Sicherheitsproblem, das in Hochsicherheitsszenarien inakzeptabel ist: Key-Escrow. Eine zentrale Instanz kennt jeden privaten Schlüssel im System – wer diese Instanz kompromittiert, kompromittiert alles.

Ein neues Paper von Zhang et al. (2026) macht nun ernst mit einem Ansatz, der diesen gordischen Knoten durchschlägt, ohne neue aufzuwerfen: Registration-Based Encryption (RBE). Was bislang als theoretisch vielversprechend, aber praktisch untauglich galt, wird durch eine Kombination aus Gitter-Kryptographie, homomorphen Encodings und einer neuartigen Kompressionstechnik erstmals in die Praxissphäre gehoben – und das mit Post-Quanten-Sicherheit. Wenn Sie sich fragen, wie das konkret aussieht und ob Sie das selbst im Browser ausprobieren können: Ja, können Sie. Auf der interaktiven RBE-Seite dieser Website ist RBE vollständig implementiert und Schritt für Schritt mit Erklärungen erlebbar – vom Schlüsselpaar bis zur Entschlüsselung.

Das Trilemma der Schlüsselverteilung

Um zu verstehen, warum RBE relevant ist, muss man das Spannungsfeld verstehen, in dem es entsteht. In der klassischen PKI verwalten Certificate Authorities (CAs) Zertifikatsketten, deren Komplexität in Enterprise-Umgebungen oft zu Fehlkonfigurationen, Zertifikatsabläufen und Revokationsproblemen führt. Wer je eine CA-Hierarchie auditiert hat, weiß: Die Angriffsfläche ist groß, der operative Aufwand erheblich.

IBE vereinfacht das radikal. Hier ist die Identität des Empfängers – etwa eine E-Mail-Adresse – bereits der öffentliche Schlüssel. Kein Zertifikat, kein Lookup, keine Kettenverwaltung. Der Private Key Generator (PKG) leitet den privaten Schlüssel eines Nutzers deterministisch aus dessen Identität ab. Das ist elegant – aber genau darin liegt das Problem: Der PKG kennt jeden privaten Schlüssel. Er muss dem System nicht nur vertrauen, sondern tatsächlich geheim gehalten werden. Kompromittierung des PKG bedeutet die vollständige Kompromittierung aller vergangenen und zukünftigen verschlüsselten Kommunikation.

RBE löst dieses Problem durch eine grundlegende Neuausrichtung der Rollen. Die zentrale Instanz, hier als Key Curator (KC) bezeichnet, hat keinerlei Zugang zu geheimen Informationen. Sie ist vollkommen transparent und deterministisch. Was sie tut, kann jeder prüfen – und genau das macht sie sicher.

RBE: Das Konzept im Detail

Das Kernprinzip von RBE lässt sich in vier Mechanismen beschreiben:

Eigenständige Schlüsselgenerierung: Jeder Nutzer erzeugt sein Schlüsselpaar (pk, sk) lokal. Der KC sieht zu keinem Zeitpunkt den privaten Schlüssel – er existiert ausschließlich beim Nutzer.

Transparente Registrierung: Der Nutzer registriert seinen öffentlichen Schlüssel beim KC. Dieser aggregiert daraufhin alle registrierten öffentlichen Schlüssel zu einem Master Public Key (mpk), der öffentlich einsehbar ist.

Helper Decryption Keys: Um eine für ihn verschlüsselte Nachricht zu entschlüsseln, benötigt der Empfänger neben seinem eigenen privaten Schlüssel ein kleines Stück Zusatzinformation vom KC – den sogenannten Helper Decryption Key (hsk). Entscheidend: Dieser hsk enthält keine geheimen Informationen des KC, er ist vielmehr eine aus öffentlichen Parametern ableitbare Hilfsgröße.

Sublineare Skalierung: Das fundamentale Ziel von RBE ist es, dass Verschlüsselung und Entschlüsselung sublinear zur Anzahl der registrierten Nutzer skalieren. Dies ist keine Selbstverständlichkeit – naive Konstruktionen würden mit jeder weiteren Registrierung teurer.

Der Kontrast zu IBE ist strukturell: Während dort eine Instanz alle privaten Schlüssel kennt und ableiten kann, kennt der KC bei RBE ausschließlich öffentliche Schlüssel. Wer den KC kompromittiert, erhält – nichts Verwendbares.

Die mathematische Mechanik: Homomorphe Encodings über Gittern

Das Herzstück der Konstruktion von Zhang et al. ist die Nutzung homomorpher Encodings im Gitter-Kontext, aufbauend auf einer dualen Version des Regev-Kryptosystems. Diese Wahl ist kein Zufall: Das Regev-System ist eines der am besten analysierten und verstandenen Post-Quanten-Schemata, seine Sicherheit reduziert auf das Learning-With-Errors (LWE)-Problem, dessen Härte unter Quantenangriffen als etabliert gilt.

Der öffentliche Schlüssel als Gitterproblem

Ein öffentlicher Schlüssel wird im verwendeten Schema als Matrix B interpretiert, für die der Nutzer einen kurzen Vektor s – seinen privaten Schlüssel – besitzt, sodass gilt:

Bs ≈ 0

Das „≈ 0" ist das entscheidende Detail: Es handelt sich nicht um exakte Gleichheit, sondern um eine Näherung mit kleinem Fehlerterm. Genau dieses Rauschen ist es, das das LWE-Problem schwer macht – und damit die Sicherheit des gesamten Systems trägt.

Master Public Key durch homomorphe Aggregation

Die Innovation besteht darin, die Registrierung als eine Form von Hashing über einen Baum zu betrachten. Mithilfe homomorpher Operationen werden die öffentlichen Schlüssel aller Nutzer in den mpk aggregiert. Technisch geschieht dies über Kronecker-Delta-Funktionen δᵢ(j):

• δᵢ(j) = 1, wenn i = j
• δᵢ(j) = 0, sonst

Der mpk ergibt sich als:

mpk := Σᵢ₌₀ᴺ⁻¹ A^(δᵢ) · G⁻¹(pkᵢ)

Hierbei ist A^(δᵢ) eine Matrix, die durch den EvalPKDelta-Algorithmus aus den öffentlichen Parametern abgeleitet wird. Die Aggregation ist vollständig transparent und ohne geheime Information des KC durchführbar.

Verschlüsselung und der Entschlüsselungsweg

Alice möchte eine Nachricht an Bob (Nutzer-ID i) verschlüsseln. Sie tut dies unter Verwendung des mpk und der Identität i – kein Zertifikat, keine Kettenverwaltung. Bob erhält vom KC seinen hskᵢ.

Der technisch elegante Clou liegt im Entschlüsselungsvorgang: Die Multiplikation des RBE-Chiffretexts mit hskᵢ transformiert diesen in einen Standard-Regev-Chiffretext, der unter Bobs eigenem öffentlichen Schlüssel pkᵢ verschlüsselt ist. Bob entschlüsselt diesen anschließend mit seinem privaten Schlüssel skᵢ – einem Verfahren, das er vollständig in seiner eigenen Sphäre kontrolliert.

Diese zweistufige Transformation ist der mathematische Kern dessen, warum RBE kein Key-Escrow benötigt: Der KC ermöglicht die Entschlüsselung, ohne jemals Zugang zum Inhalt oder zu einem Nutzerschlüssel zu haben.

Der eigentliche Durchbruch: ℓ-succinct LWE und Chiffretext-Kompression

Bisherige gitterbasierte RBE-Konstruktionen waren praktisch nicht einsetzbar. Der entscheidende Flaschenhals waren die Chiffretext-Größen: bis zu 49 MB für realistische Nutzeranzahlen. Kein System, das in der Praxis Tausende von Nutzern verwaltet, kann mit solchen Datenmengen arbeiten.

Zhang et al. führen eine Kompressionstechnik ein, die auf der ℓ-succinct LWE-Annahme basiert. Durch die Verwendung spezieller Gadget-Matrizen und Trapdoor-Sampling-Verfahren (konkret: TrapGen und SamplePre) gelingt eine drastische Reduktion:

Konfiguration	Chiffretext-Größe (bisheriger SotA)	Chiffretext-Größe (Zhang et al. 2026)
1.000 Nutzer	~9 MB	0,148 MB
Geschwindigkeitsfaktor (Enc)	–	~18× schneller
Geschwindigkeitsfaktor (Dec)	–	~12× schneller

Das ist keine marginale Optimierung. Eine Reduktion der Chiffretext-Größe um den Faktor ~60, kombiniert mit einem Geschwindigkeitsgewinn von einer Größenordnung, bedeutet den Übergang von akademisch interessant zu praktisch einsetzbar.

Die ℓ-succinct LWE-Annahme, auf der diese Kompression beruht, ist eine Verstärkung der klassischen LWE-Annahme. Sie postuliert, dass bestimmte strukturierte Matrizen im Gitterkontext nicht von zufälligen unterscheidbar sind – auch dann nicht, wenn der Angreifer einen Quantencomputer besitzt.

d-ary Decomposition: Warum d=64 kein Zufall ist

Ein Detail, das in der Implementierung eine zentrale Rolle spielt und Kryptographie-Entwickler besonders interessieren dürfte: die Wahl des Parameters d in der sogenannten d-ary Decomposition. Diese Zerlegung beschreibt, wie Vektoren und Matrizen in der Gadget-Matrix-Arithmetik in Basisdarstellungen zerlegt werden – vergleichbar mit einer Stellenwertdarstellung, aber über Gitter-Elemente.

Die naheliegende Wahl wäre eine binäre Zerlegung mit d=2, wie sie in vielen Lehrbuchkonstruktionen verwendet wird. Zhang et al. entscheiden sich in ihrer Implementierung jedoch für d=64. Der Grund liegt in einem fundamentalen Trade-off: Ein kleineres d erzeugt feinere Zerlegungen mit vielen Koeffizienten – das reduziert zwar das Rauschwachstum (Noise Growth) pro Operation, produziert aber längere Vektoren und damit größere Chiffretexte. Ein größeres d kehrt dieses Verhältnis um: weniger, dafür größere Koeffizienten, kürzere Zerlegungen, kompaktere Chiffretexte – aber mehr akkumuliertes Rauschen.

Bei d=64 liegt der Sweet Spot, den die Autoren empirisch und analytisch als optimal für das angestrebte Verhältnis aus Chiffretext-Kompaktheit und korrekter Entschlüsselbarkeit identifiziert haben. Wer die Implementierung auf der RBE-Seite studiert, wird diesen Parameter direkt im Code wiederfinden – und damit nachvollziehen können, wie eine theoretische Designentscheidung sich in konkreten Zahlen und Strukturen niederschlägt.

Key-Independent Pre-Processing

Ein weiterer technisch bedeutsamer Beitrag des Papers ist die Unterstützung von Key-Independent Pre-Processing. Die rechenintensiven Matrizen A^(δᵢ) und H^(δᵢ,ⱼ), die für Registrierung und Helper-Key-Generierung benötigt werden, hängen ausschließlich von öffentlichen Parametern ab – nicht von den tatsächlichen öffentlichen Schlüsseln der Nutzer.

Das hat eine wichtige praktische Konsequenz: Der Key Curator kann diese Berechnungen vollständig offline und im Voraus durchführen, bevor überhaupt ein Nutzer registriert wird. Die Online-Phase – der eigentliche Registrierungsvorgang – wird damit auf günstige Operationen reduziert.

Für den Betrieb eines RBE-Systems bedeutet das eine klare Architekturperspektive: Rechenintensive Vorberechnungen lassen sich in Schwachlastzeiten auslagern, der laufende Betrieb bleibt schlank.

Homomorphic RBE: Der Ausblick auf verarbeitbare Chiffretexte

Das Paper geht konzeptuell noch einen Schritt weiter und definiert erstmals eine Fully Homomorphic RBE (FHRBE). Durch eine Modifikation, die Anleihen beim GSW-Kryptosystem nimmt, lassen sich homomorphe Operationen direkt auf RBE-Chiffretexten ausführen – ohne dass der Server Zugang zu den Helper-Schlüsseln der Nutzer benötigt.

Was bedeutet das in der Praxis? Ein Cloud-Dienst könnte verschlüsselte Daten verarbeiten, ohne sie je zu entschlüsseln. Die Kombination aus Key-Escrow-freier Infrastruktur und voll homomorpher Verarbeitbarkeit ist eine der offenen Traumvorstellungen in der angewandten Kryptographie. FHRBE ist noch kein fertiges Deployment-Schema – aber die theoretische Fundierung, die Zhang et al. legen, ist ein konkreter Schritt in diese Richtung.

Einordnung: Was RBE ist – und was nicht

Eine realistische Bewertung gehört dazu. RBE ist kein Drop-in-Ersatz für PKI, der sich morgen in bestehende TLS-Stacks integrieren lässt. Die Frage der Standardisierung, der Interoperabilität mit bestehenden Protokollen und der Auditierbarkeit von KC-Implementierungen ist noch offen. Einige Punkte, die eine seriöse Beurteilung erfordert:

Vertrauensmodell des Key Curators: Auch wenn der KC keine geheimen Schlüssel kennt, bleibt er eine Instanz, der Nutzer ihren öffentlichen Schlüssel melden müssen. Die Verfügbarkeit des KC (insbesondere für hsk-Abrufe) und die Integrität des mpk sind systemkritisch. Wie diese Instanz dezentralisiert oder durch Konsensverfahren abgesichert werden kann, ist ein offenes Forschungsfeld.

Performance-Realität: Die im Paper berichteten Zahlen sind beeindruckend – aber sie beziehen sich auf spezifische Konfigurationen mit 1.000 Nutzern. Wie skaliert das System mit 100.000 oder 10 Millionen Registrierungen? Die sublineare Skalierungsgarantie ist theoretisch gegeben, die praktische Benchmark-Arbeit für große Deployments steht noch aus.

Krypto-Agilität: Für Unternehmen, die heute ihre Kryptographiearchitektur planen, ist RBE noch kein Entscheidungskandidat für produktive Systeme. Es ist jedoch ein Kandidat für die strategische Roadmap und für die Beobachtungsliste jedes CISOs, der IBE-ähnliche Deployment-Szenarien ohne Key-Escrow evaluiert.

Handlungsempfehlungen für die Zielgruppen

Für Entwicklerinnen und Entwickler

• Machen Sie sich mit den Grundlagen des dualen Regev-Systems vertraut – es ist die mathematische Basis nicht nur von RBE, sondern eines wachsenden Ökosystems gitterbasierter Schemata.
• Verfolgen Sie die Entwicklung der ℓ-succinct LWE-Annahme. Sollte diese sich als robust gegenüber weiterer kryptoanalytischer Arbeit erweisen, wird die auf ihr basierende Kompressionstechnik zunehmend relevant.
• Beobachten Sie mögliche Einreichungen zur NIST Post-Quantum Cryptography Standardization – RBE-Schemata könnten in einem zukünftigen Call relevant werden.

Für CISOs, ISBs und Consultants

• RBE ist kein akuter Handlungsbedarf, aber ein strategisches Beobachtungsthema: Unternehmen, die IBE evaluieren oder einsetzen, sollten RBE aktiv in den Vergleich einbeziehen – das Key-Escrow-Problem ist ein handfestes Compliance- und Haftungsrisiko.
• Nutzen Sie das Paper als Grundlage für interne Awareness: Die Botschaft, dass PKI-Alternativen mit Post-Quanten-Sicherheit und ohne zentrale Schlüsselverwaltung machbar sind, verändert die Debatte über langfristige Kryptographiearchitekturen.
• Halten Sie Ihre Krypto-Inventur aktuell: Systeme, die heute auf IBE oder klassischer PKI aufbauen, werden in den nächsten Jahren Migrationsentscheidungen erfordern. Wer seinen Ist-Zustand nicht kennt, kann keine fundierte Migrationsstrategie entwickeln.

Fazit: RBE verlässt das Labor

Mit dem Paper von Zhang et al. verlässt Registration-Based Encryption das Stadium der theoretischen Machbarkeit. Die Chiffretext-Größen, die bislang jeden Praxiseinsatz verhindert haben, sind durch ℓ-succinct LWE auf ein realistisches Niveau gesunken. Die Performance-Gewinne von einer Größenordnung gegenüber dem bisherigen Stand der Technik sind keine Randnotiz – sie sind die Bedingung, unter der eine Technologie überhaupt in echten Systemen erprobt werden kann.

Das Key-Escrow-Problem, das IBE seit Jahrzehnten in Hochsicherheitsszenarien disqualifiziert, ist bei RBE strukturell gelöst – nicht durch Vertrauen in Institutionen, sondern durch mathematische Konstruktion. Dass dies auf Basis von Gittern geschieht, macht RBE zugleich zu einem Post-Quanten-nativen Paradigma: keine nachträgliche Migration, keine hybride Übergangslösung, sondern von Grund auf quantensicher.

Ob RBE die PKI ablösen wird, ist offen. Dass es die Debatte über Schlüsselverwaltungsarchitekturen fundamental verändern wird, ist es nicht.