Technische Zusammenfassung: RankGuard-Polar

Problemstellung

Die Arbeit adressiert die Herausforderung, eine Teilmenge von Polar-Codewort-Koordinaten sicher über gemeinsame öffentliche Ressourcen (z. B. Broadcast-Links, Cloud-Speicher) zu veröffentlichen, während die informationstheoretische Geheimhaltung der vertraulichen Nachricht gewahrt bleibt. Im Gegensatz zu klassischen Abhör-Szenarien, bei denen ein Lauscher den Ausgang eines verrauschten Kanals beobachtet, geht diese Arbeit von einem „starken Lauscher" aus, der direkten Zugriff auf den Kanaleingang der öffentlichen Ressource hat. Die zentrale operationale Frage lautet: Wie viel Information über die vertrauliche Nachricht wird preisgegeben, wenn bestimmte Codewort-Koordinaten absichtlich auf einem öffentlichen Kanal exponiert werden?

Die Autoren konzentrieren sich auf Polar-Codes endlicher Länge über binären Körpern ($\mathbb{F}_2$), speziell innerhalb eines Rahmens, in dem ein Sender zwischen privaten und öffentlichen Kanälen zeitlich wechselt (Time-Sharing). Das Ziel ist es, zu bestimmen, welche Indizes veröffentlicht werden können, ohne unabhängige lineare Kombinationen der Informationsbits preiszugeben. Dabei wird die inhärente Struktur von Polar-Codes genutzt, bei der „frozen bits" (eingefrorene Bits) als frische geheime Zufälligkeit (Masken) dienen können, die nur dem legitimen Empfänger bekannt sind.

Methodik

Der vorgeschlagene Rahmen, RankGuard-Polar, stützt sich auf eine exakte algebraische Charakterisierung der Informationsleckage, die aus den Rang-Eigenschaften von Teilmatrizen der Polar-Generatormatrix abgeleitet wird.

1. Systemmodell

• Encoder: Der Encoder erzeugt ein Codewort $x = uG_N$, wobei $u = (u_A, u_F)$ aus Informationsbits ($u_A$) und frozen bits ($u_F$) besteht. Entscheidend ist, dass $u_F$ i.i.d. aus einer Gleichverteilung ($\text{Bernoulli}(1/2)$) gezogen wird und als gemeinsamer geheimer Schlüssel zwischen Encoder und Decoder fungiert, dem Angreifer jedoch unbekannt ist.
• Öffentliche Exposition: Eine Teilmenge von Indizes $P \subset [1:N]$ wird veröffentlicht. Der Angreifer beobachtet $x_P = u_A G_{A,P} \oplus u_F G_{F,P}$, wobei $G_{A,P}$ und $G_{F,P}$ Teilmatrizen der Generatormatrix sind, die auf die Zeilen $P$ und die Spalten $A$ bzw. $F$ beschränkt sind.
• Definition der Leckage: Die Leckage wird als gegenseitige Information definiert: $L(P) = I(u_A; x_P)$.

2. Die Leckage-Identität

Die Arbeit etabliert eine fundamentale Identität, die die gegenseitige Information mit Matrixrängen verknüpft:
$$L(P) = \text{rank}(G_P) - \text{rank}(G_{F,P})$$
wobei $G_P$ die Teilmatrix von $G_N$ ist, die auf die Zeilen $P$ und alle Spalten beschränkt ist, und $G_{F,P}$ auf die Zeilen $P$ und die frozen-Spalten $F$ beschränkt ist.

• Interpretation: $L(P)$ repräsentiert die Anzahl der unabhängigen linearen Kombinationen des Informationsvektors $u_A$, die ein Angreifer aus der öffentlichen Beobachtung $x_P$ wiederherstellen kann.
• Leckage-Zertifikat: Wenn $L(P) = 0$, wird keine Information über $u_A$ preisgegeben (die Spalten von $G_{A,P}$ liegen vollständig im Spaltenraum von $G_{F,P}$). Wenn $L(P) = r > 0$, werden bis zu $r$ unabhängige Informationsbits exponiert.

3. Konstruktive Extraktion

Die Arbeit beweist, dass wenn $L(P) = r$, eine explizite lineare Extraktor-Matrix $R$ existiert, sodass:

1. $G_{F,P} R = 0$ (die Wirkung der frozen bits wird eliminiert).
2. $\text{rank}(G_{A,P} R) = r$.
   Die Multiplikation der öffentlichen Beobachtung mit $R$ ergibt $x_P R = u_A (G_{A,P} R)$ und liefert dem Angreifer $r$ unabhängige lineare Gleichungen bezüglich der Nachrichtenbits.

4. Auswahlalgorithmus (ScoreGreedy)

Da die erschöpfende Suche nach der optimalen Menge $P$ der Größe $k$ zur Minimierung der Leckage kombinatorisch teuer ist ($O(\binom{N}{k} \cdot Nk^2)$), schlagen die Autoren einen ScoreGreedy (SG)-Algorithmus vor:

• Bewertung: Jede Zeile $i$ wird basierend auf $s_i = f_i - a_i$ bewertet, wobei $f_i$ die Anzahl der von Null verschiedenen Einträge in den frozen-Spalten und $a_i$ die Anzahl der von Null verschiedenen Einträge in den Informations-Spalten für diese Zeile ist.
• Auswahl: Der Algorithmus wählt die Top-$k$ Zeilen mit den höchsten Bewertungen aus.
• Theoretische Schranke: Satz 3 liefert eine deterministische obere Schranke, die zeigt, dass die Summe der $a_i$ für die ausgewählte Menge die Leckage begrenzt. Dies rechtfertigt das Ersatzziel, die Berührungspunkte mit Informations-Spalten zu minimieren und gleichzeitig die Berührungspunkte mit frozen-Spalten zu maximieren.

Hauptbeiträge

1. Exaktes Leckage-Zertifikat: Die Herleitung der Rang-Differenz-Identität $L(P) = \text{rank}(G_P) - \text{rank}(G_{F,P})$, die ein exaktes, nicht-asymptotisches Maß für die Informationsleckage für jede veröffentlichte Indexmenge in Polar-Codes endlicher Länge liefert.
2. Konstruktive Extraktoren: Der Beweis der Existenz einer Matrix $R$, die die linearen Kombinationen der Nachrichtenbits, die durch eine bestimmte öffentliche Menge $P$ geleakt werden, explizit konstruiert.
3. Effiziente Zertifizierungsverfahren: Die Entwicklung effizienter Algorithmen zur Berechnung der Leckage und zur Zertifizierung der Sicherheit für jede Indexmenge, die über die asymptotische Analyse der Geheimhaltungsrate hinausgeht und Garantien für endliche Blocklängen bietet.
4. Praktischer Auswahlalgorithmus: Die Einführung des ScoreGreedy-Algorithmus, eines schnellen ($O(N^2)$) Heuristikverfahrens zur Auswahl öffentlicher Indizes, das die Leckage minimiert und durch eine theoretische obere Schranke validiert wird.

Ergebnisse und Beispiele

Die Arbeit validiert den Rahmen durch theoretische Beweise und illustrative Beispiele (z. B. Polar-Codes mit $N=4$):

• Szenario 1: Das Veröffentlichen einer Koordinate, die direkt ein Informationsbit trägt (z. B. $x_4 = u_4$), führt zu $L(P)=1$ und gibt das Bit vollständig preis.
• Szenario 2: Das Veröffentlichen einer Koordinate, die eine lineare Kombination aus Informations- und frozen bits ist (z. B. $x_1 = u_4 \oplus u_3 \oplus u_2 \oplus u_1$), führt zu $L(P)=0$, wenn die frozen bits die Information effektiv maskieren und keine unabhängigen linearen Kombinationen preisgegeben werden.
• Gemischte Mengen: Der Rahmen quantifiziert korrekt eine partielle Leckage (z. B. $L(P)=2$), wenn eine Menge von Koordinaten lineare Beziehungen zwischen Informationsbits exponiert, obwohl einige davon maskiert sind.

Bedeutung und Behauptungen

Die Autoren positionieren RankGuard-Polar als eine operationale Audit- und Kontrollebene für Systeme, die öffentliche Ressourcen nutzen.

• Fokus auf endliche Länge: Im Gegensatz zur klassischen Abhör-Literatur, die oft auf asymptotische Geheimhaltungsraten für Blocklängen $N \to \infty$ angewiesen ist, liefert diese Arbeit exakte Garantien für endliche $N$.
• Starkes Angreifermodell: Der Rahmen ist für einen starken Lauscher konzipiert, der den Kanaleingang beobachtet, ein Szenario, das sich von Standard-Abhör-Modellen unterscheidet, bei denen der Angreifer einen verrauschten Kanalausgang beobachtet.
• Praktischer Nutzen: Die Methode ersetzt keine asymptotischen Abhör-Konstruktionen, bietet jedoch einen Mechanismus, um Leckage in realen Systemen zu zertifizieren und zu kontrollieren, in denen eine gemischte Nutzung öffentlicher/privater Kanäle für Durchsatzsteigerung oder Kostensenkung notwendig ist.
• Algebraische Transparenz: Durch die Reduktion von Geheimhaltung auf lineare Algebra (Matrixränge) bietet der Rahmen eine transparente und berechenbare Möglichkeit, Sicherheitseigenschaften zu verifizieren, ohne sich auf komplexe kryptografische Annahmen oder geheime Generatormatrizen zu verlassen.

Die Arbeit schließt, dass RankGuard-Polar die sichere Nutzung öffentlicher Kanäle ermöglicht, indem es eine rigorose, konstruktive Methode bereitstellt, um genau zu bestimmen, welche Codewort-Koordinaten exponiert werden können und wie viel Information kompromittiert wird.