A Note on the Equivalence Between Zero-knowledge and Quantum CSS Codes

Diese kurze Notiz zeigt die Äquivalenz zwischen (linearen, perfekten) Zero-Knowledge-Codes und Quanten-CSS-Codes auf und nutzt diese Erkenntnis, um explizite asymptotisch gute Zero-Knowledge-lokal-testbare Codes zu konstruieren.

Das Wesentliche

🕵️‍♂️ Die geheime Verbindung: Wenn Geheimschriften und Quantencomputer sich die Hand reichen

Stellen Sie sich vor, Sie haben zwei völlig unterschiedliche Welten:

1. Die Welt der Spione: Hier geht es darum, Nachrichten so zu verschlüsseln, dass ein Lauscher, der nur ein paar Buchstaben abhört, absolut nichts über den Inhalt der Nachricht erfährt.
2. Die Welt der Quantencomputer: Hier geht es darum, Daten so zu speichern, dass sie selbst dann noch lesbar bleiben, wenn ein Teil des Speichers durch kosmische Strahlung oder Fehler zerstört wurde.

Bis vor kurzem dachten die Wissenschaftler, diese beiden Welten hätten wenig miteinander zu tun. In diesem kurzen, aber wichtigen Papier zeigen die Autoren jedoch etwas Überraschendes: Diese beiden Welten sind eigentlich ein und dasselbe. Sie sind wie zwei verschiedene Seiten derselben Medaille.

1. Die beiden Helden der Geschichte

Held A: Der „Null-Wissen"-Code (Zero-Knowledge Code)
Stellen Sie sich vor, Sie schreiben einen Brief an einen Freund. Sie verwenden einen speziellen Code, bei dem Sie den Brief in viele kleine Teile zerlegen.

• Das Geniale: Wenn ein Spion nur 5 dieser Teile abfängt, sieht er nur zufälliges Gekritzel. Er kann nicht einmal erraten, ob der Brief „Ich liebe dich" oder „Kauf Milch" lautet. Es ist, als würde man ein Puzzle nehmen und nur 5 zufällige Teile zeigen – man sieht kein Bild.
• Der Haken: Wenn man alle Teile hat, kann man den Brief trotzdem lesen.

Held B: Der Quanten-CSS-Code
Quantencomputer sind extrem empfindlich. Ein winziger Fehler kann die ganze Rechnung zerstören. CSS-Codes sind wie ein Sicherheitsnetz.

• Das Geniale: Sie speichern Informationen in einer Art „Schattenwelt". Wenn ein Teil des Codes kaputtgeht, kann das System den Fehler erkennen und korrigieren, ohne die eigentliche Information zu zerstören.
• Die Struktur: Diese Codes bestehen aus zwei sich ergänzenden Teilen (nennen wir sie X und Z), die sich gegenseitig „im Auge behalten".

2. Die große Entdeckung: Der Schlüssel zur Tür

Die Autoren sagen: „Was für den Spion ein Geheimnis ist, ist für den Quantencomputer eine Fehlerkorrektur."

Sie haben einen mathematischen Trick gefunden, der zeigt, wie man einen „Null-Wissen"-Code direkt in einen Quanten-Code verwandelt (und umgekehrt).

• Die Analogie: Stellen Sie sich vor, Sie haben einen Zaun (den Code).
  • Im Spion-Szenario wollen Sie sicherstellen, dass, wenn jemand nur ein kleines Stück des Zauns sieht (z. B. ein paar Latten), er nicht erraten kann, was dahinter passiert.
  • Im Quanten-Szenario wollen Sie sicherstellen, dass, wenn ein Teil des Zauns umfällt (ein Fehler), Sie genau wissen, wo er umgefallen ist, um ihn zu reparieren.

Die Autoren zeigen: Die Regel, die verhindert, dass der Spion etwas sieht, ist exakt dieselbe Regel, die dem Quantencomputer hilft, Fehler zu finden. Wenn der Code so stark ist, dass er keine Informationen preisgibt, ist er automatisch auch stark genug, um Fehler zu korrigieren.

3. Warum ist das so wichtig? (Der „Super-Boost")

Warum sollte man sich dafür interessieren? Weil diese Verbindung ein mächtiges Werkzeug ist.

Stellen Sie sich vor, Sie sind ein Architekt, der ein stabiles Haus bauen will (einen guten Code).

• Früher mussten Sie für jedes Problem (Sicherheit oder Fehlerkorrektur) von Grund auf neu erfinden, wie das Haus aussehen soll.
• Jetzt haben Sie einen Baukasten.

Die Autoren nutzen diese Entdeckung, um ein neues, fantastisches Gebäude zu errichten: Perfekte, fehlerresistente Geheimcodes.

Sie haben sich angesehen, wie die besten Quanten-Computer-Forscher kürzlich neue, extrem robuste Quanten-Codes gebaut haben (die wie unzerstörbare Festungen sind). Da diese Codes nun als „Null-Wissen"-Codes verstanden werden können, haben sie diese Bauanleitungen einfach „übersetzt".

Das Ergebnis:
Sie haben nun einen Code, der:

1. Extrem sicher ist: Ein Spion kann nichts herausfinden, selbst wenn er sehr viele Teile sieht.
2. Fehler tolerant ist: Er funktioniert auch, wenn Teile davon beschädigt sind.
3. Schnell geprüft werden kann: Man kann mit wenigen Blicken (wenigen „Queries") sofort sehen, ob der Code noch intakt ist, ohne ihn komplett zu öffnen.

Zusammenfassung in einem Satz

Die Autoren haben entdeckt, dass die Mathematik hinter geheimen Spionage-Codes und fehlertoleranten Quanten-Codes identisch ist. Durch diese Erkenntnis konnten sie die neuesten Durchbrüche aus der Quantenwelt nutzen, um die sichersten und effizientesten Geheimcodes für die klassische Welt zu bauen, die es je gab.

Es ist, als hätten sie herausgefunden, dass die Anleitung für einen Schutzanzug (Quanten) genau dieselbe ist wie für eine Tarnkappe (Spionage) – und nun können sie beides gleichzeitig herstellen!

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papiers „A Note on the Equivalence Between Zero-knowledge and Quantum CSS Codes" auf Deutsch:

Titel: Eine Anmerkung zur Äquivalenz zwischen Zero-Knowledge-Codes und Quanten-CSS-Codes

Autoren: Noga Ron-Zewi und Mor Weiss
Datum: März 2026 (vorläufige Version auf arXiv)

---

1. Problemstellung und Motivation

Das Papier adressiert die Beziehung zwischen zwei scheinbar unterschiedlichen Familien von Fehlerkorrekturcodes:

1. Zero-Knowledge (ZK) Codes: Diese wurden von Decatur, Goldreich und Ron eingeführt. Sie sind lineare Codes, bei denen eine zufällige Kodierung so gestaltet ist, dass das Betrachten einer kleinen Anzahl von Codewortsymbolen (bis zu einem Schwellenwert $t$) keinerlei Informationen über die ursprüngliche Nachricht preisgibt. Diese Codes sind fundamental für kryptographische Konstruktionen wie Multi-Party-Computation (MPC), Secret Sharing und Zero-Knowledge-Interaktive Oracle-Beweise (ZK-IOPs).
2. Quantum CSS Codes: Benannt nach Calderbank, Shor und Steane, sind diese Codes für die Quantenfehlerkorrektur entwickelt worden. Sie bestehen aus einem Paar linearer klassischer Codes $(C_X, C_Z)$, deren Dualcodes orthogonal zueinander sind. Sie spielen eine zentrale Rolle in der Quantenkomplexitätstheorie, insbesondere im Kontext der Quanten-PCP-Vermutung.

Das Kernproblem: Bisher gab es keine explizite Verbindung zwischen diesen beiden Konzepten. Die Autoren stellen die Frage, ob eine strukturelle Äquivalenz besteht, die es erlaubt, Fortschritte in einem Bereich auf den anderen zu übertragen. Insbesondere fehlt es an expliziten Konstruktionen von asymptotisch guten Zero-Knowledge-Local-Testable-Codes (ZK-LTCs), die sowohl eine hohe Rate und Distanz als auch eine effiziente lokale Testbarkeit aufweisen.

---

2. Methodik und Theoretische Grundlagen

Die Autoren definieren zunächst die notwendigen Begriffe präzise:

• ZK-Codes: Ein linearer Code $C$ mit einem Generator $G$ und einem randomisierten Kodierungsmap $Enc$. Der Code ist $t$-ZK, wenn für jede Menge von Indizes $I$ der Größe $t$ und für beliebige Nachrichten $m, m'$ die Verteilungen der eingeschränkten Codewörter $Enc(m)|_I$ und $Enc(m')|_I$ identisch sind.
• CSS-Codes: Ein Paar $(C_X, C_Z)$, wobei $C_X^\perp \subseteq C_Z$ (und äquivalent $C_Z^\perp \subseteq C_X$). Die Distanzen $d_X$ und $d_Z$ werden durch das minimale Gewicht von Vektoren in $C_X \setminus C_Z^\perp$ bzw. $C_Z \setminus C_X^\perp$ definiert.

Der zentrale Ansatz:
Die Autoren konstruieren eine bidirektionale Transformation zwischen ZK-Codes und CSS-Codes. Sie nutzen die Struktur des Generator-Matrix $G$ eines linearen Codes, um die beiden Komponenten eines CSS-Codes zu definieren:

• $C_X$ wird als der Code $C$ selbst gewählt.
• $C_Z$ wird als der Unterraum definiert, der orthogonal zu den letzten $k-k'$ Spalten von $G$ ist (wobei $k'$ die Dimension der Nachricht und $k$ die Dimension des Codes ist).

---

3. Schlüsselbeiträge und Ergebnisse

A. Die Äquivalenz (Theorem 3.1 & Korollar 3.2)

Die Hauptleistung des Papiers ist der Beweis, dass (lineare, perfekte) Zero-Knowledge-Codes und Quanten-CSS-Codes äquivalent sind.

• Transformation ZK $\to$ CSS:
  Gegeben ein ZK-Code mit Generator $G$, definiert man $C_X = C$ und $C_Z$ basierend auf der Orthogonalität zu den „Rausch"-Spalten von $G$.

  • Die Eigenschaft, dass $Enc$ von $e$ Fehlern decodierbar ist, entspricht genau der Bedingung $d_X > 2e$.
  • Die Eigenschaft, dass $Enc$ $t$-Zero-Knowledge ist, entspricht genau der Bedingung $d_Z > t$.
  • Die Orthogonalität der Dualcodes $C_X^\perp$ und $C_Z^\perp$ ist automatisch erfüllt.

• Transformation CSS $\to$ ZK:
  Gegeben ein CSS-Code $(C_X, C_Z)$, kann man einen Generator $G$ für $C_X$ konstruieren, dessen letzte Spalten eine Basis für $C_Z^\perp$ bilden. Die daraus resultierende randomisierte Kodierung ist ein ZK-Code mit den entsprechenden Parametern.

Dies zeigt, dass die „Zero-Knowledge"-Eigenschaft (Unkenntnis bei kleinen Abtastungen) mathematisch äquivalent zur Distanz des dualen Codes im CSS-Rahmen ist.

B. Anwendung: Explizite asymptotisch gute ZK-LTCs (Abschnitt 4)

Die Autoren nutzen diese Äquivalenz, um ein konkretes, lang gesuchtes Ergebnis zu erzielen:

• Ausgangspunkt: Es gibt kürzlich entwickelte explizite Konstruktionen von asymptotisch guten Quanten-LTCs (Local-Testable Codes) mit konstanter Rate und Distanz $\Omega(n)$, die mit nur $poly(\log n)$ Abfragen testbar sind (basierend auf Arbeiten von [DLV24, KP25, WLH25]).
• Transfer: Durch Anwendung der Äquivalenz (Korollar 3.2) auf diese Quanten-LTCs erhalten die Autoren explizite asymptotisch gute Zero-Knowledge-LTCs.
• Ergebnis (Korollar 4.3): Es existiert eine explizite unendliche Familie linearer Codes $C_n$, die:
  1. Asymptotisch gut sind (konstante Rate, Distanz $\Omega(n)$).
  2. Mit $poly(\log n)$ Abfragen lokal testbar sind.
  3. Einen Zero-Knowledge-Schwellenwert von $\Omega(n)$ haben (d.h., man kann einen linearen Bruchteil des Codeworts betrachten, ohne Informationen zu erhalten).
  4. Decodierbar von $\Omega(n)$ Fehlern sind.

Dies ist laut den Autoren das erste Beispiel einer expliziten Familie von asymptotisch guten ZK-LTCs, bei der der ZK-Schwellenwert größer ist als die Abfragekomplexität des Testers.

---

4. Signifikanz und Implikationen

1. Brückenschlag zwischen Disziplinen: Das Papier etabliert eine tiefe theoretische Verbindung zwischen klassischer Kryptographie (Zero-Knowledge) und Quanteninformationstheorie (CSS-Codes). Es zeigt, dass Fortschritte in der Quantenfehlerkorrektur direkt in kryptographische Primitive übersetzt werden können.
2. Lösung eines offenen Problems: Die Konstruktion expliziter, asymptotisch guter ZK-LTCs mit hohen Parametern war ein offenes Problem. Bisherige Ansätze waren oft probabilistisch oder hatten suboptimale Parameter. Die Nutzung von Quanten-LTCs umgeht diese Hürden.
3. Anwendungen in der Kryptographie: Da ZK-LTCs das Herzstück von Zero-Knowledge-PCPs und ZK-IOPs bilden, ermöglicht diese Arbeit effizientere und sicherere kryptographische Protokolle mit informationstheoretischen Garantien.
4. Methodischer Fortschritt: Die Arbeit demonstriert, wie die „Dualität" in CSS-Codes genutzt werden kann, um die Zero-Knowledge-Eigenschaft (die typischerweise als Eigenschaft der Kodierungsmatrix betrachtet wird) als geometrische Eigenschaft (Distanz) zu analysieren und zu konstruieren.

Fazit:
Noga Ron-Zewi und Mor Weiss zeigen, dass Zero-Knowledge-Codes und Quanten-CSS-Codes zwei Seiten derselben Medaille sind. Durch die Ausnutzung dieser Äquivalenz gelingt es ihnen, die jüngsten Durchbrüche in der Quanten-LTC-Theorie zu nutzen, um erstmals explizite, hochleistungsfähige Zero-Knowledge-Codes zu konstruieren, die für die moderne Kryptographie und Komplexitätstheorie von großer Bedeutung sind.