💻 computer science

Ciphertext-Policy ABE for $\mathsf{NC}^1$ Circuits with Constant-Size Ciphertexts from Succinct LWE

Die Autoren stellen ein gitterbasiertes ciphertext-policy attribute-based encryption (CP-ABE)-Schema für $\mathsf{NC}^1$ -Schaltungen vor, das konstante Chiffratgrößen bietet und auf der poly( $\lambda$ )-succinct LWE-Annahme von Wee basiert.

Ursprüngliche Autoren: Jiaqi Liu, Yuanyi Zhang, Fang-Wei Fu

Veröffentlicht 2026-03-18

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Jiaqi Liu, Yuanyi Zhang, Fang-Wei Fu

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

Das große Ziel: Der „intelligente" Briefkasten

Stellen Sie sich vor, Sie sind ein Geheimdienst oder ein großes Unternehmen. Sie haben viele vertrauliche Dokumente (die Nachrichten). In der normalen Welt geben Sie jedem Mitarbeiter einen Schlüssel, und jeder kann alles öffnen, was mit diesem Schlüssel verschlüsselt ist. Das ist wie ein großer Haufen Schlüssel, den jeder hat – unsicher und unübersichtlich.

Attribute-Based Encryption (ABE) ist wie ein intelligenter Briefkasten.

Bei der alten Methode: Der Schlüssel passt nur zu einem bestimmten Schloss.
Bei dieser neuen Methode: Der Briefkasten hat eine Regel (eine Richtlinie). Zum Beispiel: „Nur Mitarbeiter aus der Abteilung Finanzen, die auch Senior sind, dürfen öffnen."
- Wenn Sie einen Schlüssel für „Finanzen" haben, aber nicht „Senior", geht er nicht auf.
- Wenn Sie „Senior" sind, aber in der IT, geht er auch nicht auf.
- Nur wer beide Eigenschaften hat, bekommt den Brief.

Das Problem bisher war: Je komplexer die Regel (z. B. „Finanzen ODER IT, ABER NICHT Praktikant"), desto riesiger und schwerer wurde der verschlüsselte Brief (der Cipher). Wenn die Regel kompliziert war, wurde der Brief so groß, dass er kaum noch zu versenden war.

Die neue Erfindung: Der „magische" Stempel

Die Autoren dieses Papiers (Liu, Zhang und Fu) haben einen Weg gefunden, diese verschlüsselten Briefe immer gleich groß zu halten, egal wie kompliziert die Regel ist.

Stellen Sie sich vor, Sie wollen einen Brief an eine Gruppe von Leuten schicken, die eine bestimmte Kombination von Eigenschaften haben.

Das alte Problem: Wenn die Regel 100 Bedingungen hatte, musste der Brief 100 Abschnitte enthalten. Das war wie ein riesiger Wälzer.
Die neue Lösung: Die Autoren nutzen eine Art „magischen Stempel" (basierend auf einer mathematischen Idee namens Lattice oder Gitter, die auch gegen Quantencomputer sicher ist). Mit diesem Stempel können sie die gesamte komplexe Regel in einen einzigen, winzigen „Stempelabdruck" auf den Brief packen.

Die Analogie:
Stellen Sie sich vor, Sie wollen einen Tresor öffnen, der nur mit einem sehr komplizierten Passwort aus 1000 Buchstaben funktioniert.

Alt: Sie müssten den Tresor so bauen, dass er 1000 Schlüssellöcher hat. Der Tresor wäre riesig.
Neu: Die Autoren haben einen Tresor erfunden, der nur ein einziges Schlüsselloch hat. Aber das Schloss im Inneren ist so genial konstruiert, dass es trotzdem prüft, ob alle 1000 Buchstaben des Passworts stimmen. Der Tresor bleibt also immer gleich groß, egal wie lang das Passwort ist.

Was macht das Papier besonders?

Konstante Größe: Der verschlüsselte Brief (der Cipher) ist immer gleich klein. Er wächst nicht mit der Komplexität der Regel. Das ist wie ein E-Mail-Anhang, der immer nur 1 KB groß ist, egal ob Sie eine einfache Regel oder einen ganzen Gesetzestext verschlüsseln.
Sicher gegen die Zukunft: Die Mathematik dahinter basiert auf „Gittern" (Lattices). Das ist wie ein Puzzle, das für normale Computer schwer zu lösen ist, aber für zukünftige Quantencomputer (die alles andere knacken können) fast unmöglich ist. Es ist eine Art „Quanten-Schutzschild".
Effizienz: Die öffentlichen Schlüssel (die Regeln, die jeder sehen darf) sind zwar etwas größer, aber die Autoren zeigen einen Trick: Man kann sie wie ein digitales „Seed" (einen Startwert) behandeln. Statt alles zu speichern, reicht es, einen kleinen Code zu speichern, der den Rest automatisch erzeugt. Das spart enorm viel Speicherplatz.

Ein konkretes Beispiel: Der Rundfunk

Stellen Sie sich vor, Sie sind ein Radiosender mit 1 Million Hörern. Sie wollen nur eine Nachricht an die 10.000 Hörer senden, die ein „Premium-Abo" haben.

Früher: Sie müssten für jeden der 10.000 Hörer einen separaten Schlüssel oder eine separate Nachricht erstellen. Das wäre eine Flut an Daten.
Mit dieser neuen Methode: Sie senden eine einzige Nachricht. Diese Nachricht enthält die Regel „Premium-Abo". Jeder Hörer hat einen Schlüssel. Nur die mit dem Premium-Abo können die Nachricht entschlüsseln. Die Größe der Nachricht hängt nicht davon ab, ob Sie 10 oder 10 Millionen Hörer haben. Sie ist immer gleich klein.

Zusammenfassung in einem Satz

Die Autoren haben einen neuen, quanten-sicheren Weg gefunden, um Daten so zu verschlüsseln, dass die Größe der verschlüsselten Nachricht niemals anwächst, egal wie kompliziert die Zugangsregeln sind – wie ein kleiner Schlüssel, der jede noch so große und komplexe Tür öffnen kann.

Das ist ein riesiger Schritt hin zu effizienteren und sichereren Verschlüsselungssystemen für die Zukunft, besonders in einer Welt, in der immer mehr Daten und immer komplexere Berechtigungen verwaltet werden müssen.

1. Problemstellung und Motivation

Hintergrund:
Attribute-Based Encryption (ABE) ermöglicht eine feingranulare Zugriffskontrolle auf verschlüsselte Daten. Bei Ciphertext-Policy ABE (CP-ABE) wird ein Verschlüsselungsschema mit einer Zugriffsrichtlinie (Policy) verknüpft, und ein Schlüssel ist mit einem Attribut assoziiert. Die Entschlüsselung ist nur möglich, wenn das Attribut die Richtlinie erfüllt.

Das Problem:
Bestehende CP-ABE-Schemata, die auf Gittern (Lattice-based) und dem Learning-With-Errors (LWE)-Problem basieren, leiden oft unter ineffizienten Parametern:

Die Größe des Geheimtextes (Ciphertext) skaliert häufig mit der Komplexität der Zugriffsrichtlinie (z. B. der Größe oder Tiefe des Schaltkreises).
Viele Schemata benötigen nicht-standardisierte oder starke Annahmen (wie „Evasive LWE" oder Tensor-LWE).
Es gibt einen Zielkonflikt zwischen der Unterstützung komplexer Schaltkreise (wie NC1) und der Erhaltung konstanter oder sehr kleiner Geheimtextgrößen.

Ziel:
Die Autoren streben ein CP-ABE-Schema für NC1-Schaltkreise (Schaltkreise mit logarithmischer Tiefe und polynomieller Größe) an, das konstante Geheimtextgrößen ( $O(1)$ ) aufweist, unabhängig von der Schaltkreisgröße oder -tiefe, und dabei auf einer schwächeren, standardmäßigeren Annahme basiert.

2. Methodik und Technische Architektur

Das vorgeschlagene Schema kombiniert mehrere fortgeschrittene kryptographische Techniken:

A. Fundamentale Annahme: Succinct LWE

Die Sicherheit des Schemas basiert auf der $\ell$ -succinct LWE-Annahme (eingeführt von Wee, CRYPTO 2024).

Im Gegensatz zum klassischen LWE, bei dem eine Matrix $A$ und ein Vektor $b = As + e$ gegeben sind, beinhaltet die succinct LWE-Annahme eine zusätzliche Matrix $W$ und einen Trapdoor $T$ .
Die Annahme besagt, dass $(B, s^\top B + e, W, T)$ computationally indistinguishable von $(B, c, W, T)$ ist, wobei $c$ zufällig ist.
Dies ermöglicht es, „verkürzte" (succinct) Beweise oder Verifikationsmechanismen zu nutzen, ohne die Sicherheit zu gefährden.

B. Konstruktion des CP-ABE Schemas

Die Autoren modifizieren das bestehende CP-ABE-Schema von Datta et al. (DKW21), das auf linearen Geheimhaltungs-Schemata (LSSS) basiert.

Matrix Commitment (Wee25):
Um die Geheimtextgröße unabhängig von der Anzahl der Attribute (bzw. der Zeilen der LSSS-Matrix) zu halten, verwenden die Autoren ein Matrix-Commitment-Schema.
- Statt für jede Zeile der Zugriffsrichtlinie separate Komponenten im Geheimtext zu speichern, wird eine einzige Matrix $C$ (Commitment) berechnet, die Informationen über alle relevanten Matrizen $U_i$ kodiert.
- Der Geheimtext besteht nur noch aus drei Komponenten: $c_1$ (bezogen auf $B$ ), $c_2$ (bezogen auf $A+C$ ) und $c_3$ (Nachricht).
Schlüsselgenerierung und Trapdoor-Technik:
- Der Master-Schlüssel enthält einen Trapdoor $td_B$ für die Matrix $B$ .
- Um Schlüssel für nicht-berechtigte Attributmengen zu generieren (was für die Sicherheitsbeweise notwendig ist), nutzen die Autoren eine spezielle Eigenschaft der succinct LWE-Annahme: Mit dem öffentlichen Parameter $T$ kann ein neuer Trapdoor für Matrizen der Form $[I \otimes B | W']$ konstruiert werden, wobei $W'$ statistisch nahe an uniform ist.
- Dies erlaubt es dem Herausforderer (Challenger) im Sicherheitsbeweis, Schlüssel für nicht-zugelassene Mengen zu erzeugen, ohne den ursprünglichen Trapdoor $td_B$ zu verwenden, was die Sicherheit gegen Angreifer sicherstellt.
Entschlüsselung:
- Der Entschlüsselungsalgorithmus nutzt die Rekonstruktionskoeffizienten des LSSS, um die verschlüsselte Nachricht zu rekonstruieren.
- Durch die Nutzung des Commitments und der zugehörigen Öffnungsmatrix ( $Z$ ) kann der Empfänger die notwendigen linearen Kombinationen berechnen, um den Fehlerterm zu eliminieren und die Nachricht zu erhalten.

3. Wichtige Beiträge und Ergebnisse

A. Konstante Geheimtextgröße

Das herausragende Merkmal des Schemas ist die konstante Größe des Geheimtextes ($|ct| = O(1)$), die nur vom Sicherheitsparameter $\lambda$ abhängt.

Sie ist unabhängig von der Schaltkreisgröße $s$ , der Eingabelänge $\ell$ und der Tiefe $d$ .
Dies ist asymptotisch optimal (bis auf polynomielle Faktoren in $\lambda$ ).

B. Parameter und Effizienz

Für einen NC1-Schaltkreis mit Tiefe $d$ und Größe $s$ auf $\ell$ -Bit-Eingaben:

**Öffentlicher Schlüssel ($|pk| $):**$ O(s)$ (skaliert mit der Schaltkreisgröße). Hinweis: Die Autoren argumentieren, dass der größte Teil des öffentlichen Schlüssels uniform ist und durch einen Pseudozufallsgenerator komprimiert werden kann, um die effektive Größe auf $O(1)$ zu reduzieren.
**Geheimtext ($|ct| $):**$ O(1)$.
**Geheimenschlüssel ($|sk| $):**$ O(\ell)$ (skaliert mit der Anzahl der Attribute). Dies ist nicht strikt optimal, aber in Szenarien mit wenigen Attributen pro Benutzer auf $O(1)$ reduzierbar.

C. Sicherheitsbeweis

Das Schema ist selektiv sicher im Standardmodell.
Die Sicherheit basiert auf der poly( $\lambda$ )-succinct LWE-Annahme mit sub-exponentiellem Modul-zu-Rauschen-Verhältnis.
Der Beweis verwendet eine Sequenz von Hybrid-Spielen, die schrittweise die Realwelt in eine Welt überführen, in der die Nachricht informationstheoretisch versteckt ist. Dabei wird die „Noise-Smudging"-Technik und das Leftover-Hash-Lemma mit Trapdoor eingesetzt.

D. Anwendung: Broadcast Encryption

Als direkte Anwendung wird ein Broadcast-Encryption-Schema für $N$ Benutzer abgeleitet:

Die Zugriffsrichtlinie prüft die Mitgliedschaft eines Benutzers in einer Liste.
Parameter:
- $|pk| = \text{poly}(\lambda)$ (nach Komprimierung).
- $|sk| = \text{poly}(\lambda, \log N)$ .
- $|ct| = \text{poly}(\lambda)$ (unabhängig von $\log N$ ).
Dies stellt einen optimalen Broadcast-Encryption-Ansatz unter der succinct LWE-Annahme dar, da die Geheimtextgröße nicht mit der Anzahl der Benutzer skaliert.

4. Bedeutung und Vergleich mit dem Stand der Technik

Vorteil gegenüber Wee25: Im Vergleich zu dem kürzlich vorgestellten Schema von Wee (CRYPTO 2024/2025) unterstützt dieses neue Schema eine etwas engere Klasse von Zugriffsrichtlinien (NC1 statt aller Schaltkreise) und hat einen größeren Geheimenschlüssel. Dafür erreicht es jedoch:
1. Unabhängigkeit der Parameter ($|pk|, |sk|, |ct|$) von der Schaltkreistiefe $d$ .
2. Eine Geheimtextgröße für Broadcast Encryption, die unabhängig von $\log N$ ist (bei Wee25 skaliert sie mit $\log N$ ).
3. Eine effizientere Verschlüsselung, die nur ein einziges Matrix-Commitment durchführt, anstatt eine Kette von Commitments für einen Schaltkreis zu berechnen.
Quantensicherheit: Da das Schema auf LWE-Annahmen basiert, gilt es als widerstandsfähig gegen Quantencomputer-Angriffe, im Gegensatz zu Schemata, die auf bilinearen Gruppen basieren.
Praktische Relevanz: Die konstante Geheimtextgröße ist ein entscheidender Durchbruch für Anwendungen mit begrenzter Bandbreite oder Speicherkapazität, insbesondere bei Broadcast-Systemen mit einer großen Anzahl von Empfängern.

Fazit

Das Paper stellt einen bedeutenden Fortschritt in der post-quanten Kryptographie dar. Es gelingt es, ein CP-ABE-Schema für NC1-Schaltkreise zu konstruieren, das konstante Geheimtextgrößen bietet und auf einer gut untersuchten, schwächeren Annahme (Succinct LWE) basiert. Die Fähigkeit, Broadcast Encryption mit konstanten Kosten pro Nachricht zu realisieren, macht dieses Schema besonders relevant für skalierbare, sichere Kommunikationssysteme.