Technisches Resümee: Schnelle beschränkt unabhängige Funktionen und ihre Duals

Problemstellung

Die Arbeit befasst sich mit der Herausforderung, kryptographische Primitiven zu konstruieren, die die statistischen Eigenschaften von Zufallsfunktionen und Zufallsliniencodes nachahmen, während sie gleichzeitig einen konstanten Rechenaufwand beibehalten. Die Autoren suchen nach „schnellen“ Implementierungen – definiert als durch arithmetische Schaltungen der linearen Größe (Größe $O(n)$ berechenbar) – die Folgendes erfüllen:

1. Beschränkte Unabhängigkeit: Hashfunktionen, die für ein beliebiges konstantes $t$ eine $t$-weise Unabhängigkeit aufweisen.
2. Schnelle Duale Codes: Familien von Linearcodes, bei denen sowohl der Code als auch sein Dual eine schnelle, systematische Kodierung zulassen und Distanzen erreichen, die nahe am Gilbert-Varshamov-Bound (GV-Bound) liegen.
3. Stärkere Random-ähnliche Eigenschaften: Erweiterung über die einfache Distanz hinaus auf Eigenschaften wie Listen-Dekodierbarkeit, um sicherzustellen, dass sich die Codes auch unter lokalen Beschränkungen (lokale Ähnlichkeit) wie Zufallsliniencodes verhalten.

Vorherige Arbeiten, wie [IKOS08] und [DI14], etablierten schnelle paarweise unabhängige Hashfunktionen und schnelle Codes, die den GV-Bound erreichen, hatten jedoch oft Einschränkungen hinsichtlich des Unabhängigkeitsparameters $t$, des zugrunde liegenden Körpers oder der Fähigkeit, den Code und seinen Dual gleichzeitig zu optimieren. Eine kürzlich erschienene Konstruktion von [BR26] verbesserte schnelle Duale Codes, war jedoch auf binäre Körper beschränkt, erforderte eine feste Rate von 1/2, wies eine nicht vernachlässigbare Ausfallwahrscheinlichkeit auf und verfügte über keine systematische Kodierung.

Methodik

Die Autoren bauen auf der „IKOS-Konstruktion“ (Ishai, Kushilevitz, Ostrovsky, Sahai) und der „DI-Konstruktion“ (Druk, Ishai) auf und generalisieren diese für höhere Unabhängigkeitsparameter.

1. Generalisierung von Hashfunktionen

Die Kernkonstruktion für Hashfunktionen folgt einer dreistufigen Pipeline:

1. Äußere Kodierung: Anwendung eines schnellen Linearcodes mit großer Distanz über einen großen (aber konstanten) Alphabet auf den Input.
2. Innere Hashing: Anwendung von konstanten, $t$-weise unabhängigen Hashfunktionen auf jede Koordinate des kodierten Vektors.
3. Extraktion: Anwendung der Transponierten einer Erzeugermatrix eines guten Codes (der als Extraktor fungiert) auf das Ergebnis.

Um $t$-weise Unabhängigkeit zu erreichen, ersetzen die Autoren die konstanten paarweise unabhängigen Hashfunktionen im inneren Schritt durch konstante $t$-weise unabhängige Hashfunktionen. Sie beweisen, dass, wenn der äußere Code eine ausreichend große Distanz besitzt (speziell $> 1 - 1/t^2$), die Unterscheidbarkeit von $t$ Inputs über einen ausreichenden Anteil der Koordinaten erhalten bleibt, was es den inneren Hashfunktionen ermöglicht, unabhängige, uniforme Outputs zu erzeugen, die der abschließende Extraktionsschritt bewahrt.

2. Lineare Uniform Output Familien (LUOF)

Um die Codes zu konstruieren, nutzen die Autoren das Konzept einer Linearen Uniform Output Familie (LUOF). Eine Zufallsmatrix $A$ ist eine LUOF, wenn für jeden nicht-null Vektor $x$ der Output $xA$ gleichverteilt ist.

• Schnelle LUOF: Die Autoren generalisieren die Konstruktion von [DI14], um eine schnelle $t$-LUOF zu erstellen. Eine Matrix $A$ ist eine $t$-LUOF, wenn für jede Menge von $t$ linear unabhängigen Inputs $x_1, \dots, x_t$ die Outputs $x_1A, \dots, x_tA$ gleichverteilt und stochastisch unabhängig sind.
• Konstruktion: Dies beinhaltet ähnlich der Hashfunktion-Konstruktion eine äußere Kodierung, eine Schicht aus zufälligen konstanten Matrizen (die als die „innere“ Funktion fungieren) und einen Extraktionsschritt. Die Autoren beweisen, dass, wenn der äußere Code eine ausreichende Distanz besitzt, die inneren Zufallsmatrizen linear unabhängige Inputs auf unabhängige uniforme Outputs abbilden.

3. Konstruktion schneller Dualer Codes

Unter Verwendung einer $t$-LUOF Matrix $A \in \mathbb{F}_q^{k \times r}$ definieren die Autoren einen Code $C$ mit der systematischen Kodierungsabbildung $x \mapsto (x, xA)$.

• Dualität: Der Dualcode $C^\perp$ wird durch die Abbildung $y \mapsto (-yA^\top, y)$ erzeugt.
• Transpositionsprinzip: Unter Berufung auf das Transpositionsprinzip (Lemma 3.4) argumentieren sie, dass, wenn die Berechnung von $xA$ schnell (lineare Größe) ist, auch die Berechnung von $yA^\top$ schnell ist.
• Unabhängigkeit des Duals: Ein entscheidender technischer Beitrag ist der Beweis, dass, wenn $A$ eine $t$-LUOF ist, auch $A^\top$ eine $t$-LUOF ist (Lemma 3.9). Dies stützt sich auf Vaziranis XOR-Lemma und stellt sicher, dass der Dualcode die starken Random-Eigenschaften des Primärcodes erbt.

Zentrale Beiträge und Ergebnisse

1. Schnelle $t$-weise unabhängige Hashfunktionen

• Ergebnis: Für jedes konstante $t$ konstruieren die Autoren eine Familie von $t$-weise unabhängigen Hashfunktionen, die durch Schaltungen der linearen Größe berechenbar sind.
• Optimierung: Für den binären Körper ($q=2$) wird der algebraische Grad auf $\log_2 t$ optimiert. Dies ist nahezu optimal, da geringere Grade keine $t$-weise Unabhängigkeit unterstützen könnten.
• Effizienz: Die Schaltungsgröße ist $O(k+r)$, wobei $k$ die Eingabelänge und $r$ die Ausgabelänge ist. Die versteckte Konstante hängt von $t$ ab (etwa $\Theta(t^7)$), bleibt aber für festes $t$ konstant.

2. Schnelle Codes mit schnellen Dualen (GV-Bound)

• Ergebnis: Die Autoren konstruieren eine Familie von Codes $C$ und deren Duale $C^\perp$ über jedem endlichen Körper $\mathbb{F}_q$ mit beliebiger Rate $R \in (0, 1)$.
• Eigenschaften:
  • Sowohl $C$ als auch $C^\perp$ erlauben eine schnelle, systematische Kodierung (lineare Größe).
  • Beide erreichen Distanzen, die $\varepsilon$-nah am Gilbert-Varshamov-Bound liegen, mit einer Wahrscheinlichkeit von $1 - 2q^{-\varepsilon n}$.
  • Die Konstruktion hat eine vernachlässigbare Ausfallwahrscheinlichkeit (im Gegensatz zu [BR26]).
  • Sie unterstützt eine lineare universelle Schaltung zur Kodierung.

3. Schnelle Listen-dekodierbare Codes mit schnellen Dualen

• Ergebnis: Durch Nutzung der $t$-LUOF-Eigenschaft erweitern die Autoren die Konstruktion auf Codes, die $t$-lokal ähnlich zu Zufallsliniencodes sind.
• Listen-Dekodierung: Sie beweisen, dass die konstruierten Codes (und deren Duale) für jedes konstante $t$ $(\rho, L)$-listen-dekodierbar bis zur Listen-Dekodierkapazität sind, mit einer Listen-Größe von $L = O(1/\varepsilon)$.
• Neuheit: Dies ist die erste Konstruktion (nach Kenntnis der Autoren), die gleichzeitig schnelle Kodierung, schnelle Dual-Kodierung und optimale Listen-Dekodierbarkeit für sowohl den Code als auch dessen Dual erreicht.

Bedeutung und kryptographische Anwendungen

Die Arbeit zeigt, dass diese Konstruktionen mächtige Bausteine für die Kryptographie darstellen, insbesondere in Szenarien, die hohe Effizienz und starke Sicherheitsgarantien erfordern.

1. Perfekt sichere Multiparty Computation (MPC)

Die Autoren präsentieren die ersten nicht-trivialen Protokolle für perfekt sichere MPC, bei denen die Komplexität der Schaltung linear mit der Anzahl der Parteien skaliert ($O(n)$).

• Kontext: Frühere Protokolle, die algebraische Codes (wie Reed-Solomon) verwendeten, verursachten oft quasi-linearen Overhead.
• Anwendung: Unter Verwendung der schnellen Dualen Codes konstruieren sie ein Oblivious Linear Evaluation (OLE) Protokoll und erweitern dieses auf allgemeine Funktionen konstanter Größe. Das Protokoll erreicht eine Sicherheitsschwelle von $t = (1/2 - \varepsilon)n$ gegen passive Angreifer.

2. Verschlüsselte Matrix-Vektor-Produkte (EMVP)

Im Kontext der komplexitätsbasierten Kryptographie wenden die Autoren ihre schnellen Dualen Codes auf verschlüsselte Matrix-Vektor-Produkte an.

• Verbesserung: Ihre Konstruktion überwindet die Einschränkungen des [BR26]-Ansatzes (der auf $\mathbb{F}_2$ beschränkt war und eine nicht vernachlässigbare Ausfallwahrscheinlichkeit hatte).
• Vorteil: Dies ermöglicht EMVP-Protokolle, bei denen sowohl die Matrix-Kodierung als auch die Query-Kodierung eine asymptotisch optimale Schaltungskomplexität aufweisen.

3. Konservative Substitute für Zufallsliniencodes

Die $t$-LUOF-Konstruktion bietet einen „konservativen“ Ersatz für Zufallsliniencodes in Anwendungen, die auf der Schwierigkeit von verrauschtem Linearsystem-Probleme angewiesen sind (z. B. Learning Parity with Noise - LPN).

• Vorteil: Während frühere Konstruktionen nur auf die minimale Distanz vertrauten (1-lokale Ähnlichkeit), gewährleistet die $t$-LUOF $t$-lokale Ähnlichkeit, was stärkere kombinatorische Eigenschaften wie die Listen-Dekodierbarkeit garantiert. Dies bietet eine robustere Sicherheitsannahme gegen Angriffe, die lokale Strukturen ausnutzen könnten.

4. MPC-freundliches Hashing

Die schnellen $t$-weise unabhängigen Hashfunktionen mit niedrigem algebraischem Grad sind direkt anwendbar auf MPC-Protokolle, bei denen sowohl die Schaltungsgröße als auch der algebraische Grad die Kommunikations- und Round-Komplexität beeinflussen. Die Konstruktion optimiert beide gleichzeitig.

Fazit

Die Arbeit generalisiert erfolgreich bisherige Konstruktionen der linearen Größe, um höhere Unabhängigkeitsparameter und stärkere Random-ähnliche Eigenschaften zu unterstützen. Durch die Einführung schneller $t$-LUOFs und den Beweis ihrer Dualitätseigenschaften bietet die Arbeit einen vereinheitlichten Rahmen zur Konstruktion von Codes und Hashfunktionen, die gleichzeitig schnell, systematisch und statistisch robust sind. Diese Ergebnisse ermöglichen neue kryptographische Protokolle mit optimaler asymptotischer Komplexität, insbesondere in der informationstheoretischen MPC und der verschlüsselten Berechnung.