💻 computer science

Information-Theoretic Distributed Point Functions with Shorter Keys

Dieser Artikel stellt eine neue, perfekt sichere 1-private informationstheoretische verteilte Punktfunktion (ITDPF) über der Gruppe $\mathbb{Z}_p$ vor, die durch die Nutzung einer auf aktuellen Techniken zur privaten Informationsabfrage basierenden Umwandlung von Anteilen asymptotisch kürzere geheime Schlüssel als bestehende Schemata erreicht.

Ursprüngliche Autoren: Hang Deng, Liang Feng Zhang

Veröffentlicht 2026-04-28

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Hang Deng, Liang Feng Zhang

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

Stellen Sie sich vor, Sie besitzen eine geheime Schatzkarte, die genau einen spezifischen Ort auf einem riesigen Gitter (sagen wir einmal eine Stadt mit Millionen von Blöcken) markiert. Sie möchten Kopien dieser Karte an eine Gruppe von Freunden verteilen, damit diese gemeinsam herausfinden können, wo der Schatz liegt. Allerdings gilt eine strikte Regel: Keine kleine Gruppe von Freunden (sagen wir, zwei oder weniger) sollte in der Lage sein, den Ort allein durch den Vergleich ihrer Kopien zu ermitteln. Sie müssen alle ihre Teile kombinieren, um das Rätsel zu lösen.

Dies ist das Kernproblem einer Distributed Point Function (DPF). Es handelt sich um ein kryptografisches Werkzeug, das eine „Punktfunktion" (eine Funktion, die überall null ist, außer an einem speziellen Punkt) in viele „Shares" (Schlüssel) aufteilt.

Der alte Weg vs. der neue Weg

Der alte Weg (Die schweren Rucksäcke):
Frühere Methoden, dies sicher zu bewerkstelligen (insbesondere mit „informationstheoretischer" Sicherheit, was bedeutet, dass sie selbst gegen Supercomputer mit unendlicher Leistung sicher sind), verlangten von den Freunden, sehr schwere Rucksäcke zu tragen. Diese Rucksäcke enthielten die „Schlüssel", die benötigt wurden, um das Rätsel zu lösen. Je größer die Stadt (die Daten) wurde, desto exponentiell größer wuchsen diese Rucksäcke, was das System langsam und unpraktisch machte.

Der neue Weg (Die leichten Umhängetaschen):
Diese Arbeit stellt eine neue Methode vor, die viel leichtere Umhängetaschen erzeugt. Die Autoren, Hang Deng und Liang Feng Zhang, haben ein System entwickelt, bei dem die Schlüssel signifikant kürzer (kleiner) sind als bei jeder zuvor existierenden perfekt sicheren Methode, insbesondere wenn die Daten riesig werden.

Wie sie es geschafft haben: Das „geheime Rezept"

Die Autoren haben keinen neuen Zaubertrick aus dem Nichts erfunden; sie nutzten einen cleveren Rezept (das LKZ-Framework), das ein Werkzeug zur Geheimhaltung in ein anderes verwandelt.

Die Zutat (PIR): Die geheime Zutat, die sie verwendeten, ist ein hochmodernes Werkzeug namens Private Information Retrieval (PIR). Stellen Sie sich PIR als eine Möglichkeit vor, einem Bibliothekar nach einem bestimmten Buch zu fragen, ohne dass der Bibliothekar weiß, welches Buch Sie angefordert haben. Ein neuer Durchbruch von Ghasemi, Kopparty und Sudan hat diesen „Anfrage"-Prozess unglaublich effizient gemacht.
Die Umwandlung (Der Zaubertrick): Die Autoren fanden heraus, wie sie den „Anfrage"-Mechanismus dieses neuen PIR in den für ihre DPF benötigten „Schlüssel-Aufteilungs"-Mechanismus übersetzen können.
- Analogie: Stellen Sie sich vor, das alte PIR war wie das Anfordern eines Buches bei einem Bibliothekar mittels eines komplexen, 10-seitigen Formulars. Das neue PIR verwendet einen winzigen, 2-Wort-Code. Die Autoren fanden einen Weg, diesen winzigen 2-Wort-Code in die geheimen Schlüssel für die Schatzkarte umzuwandeln, wobei sichergestellt wird, dass die Schlüssel winzig bleiben.

Das Ergebnis: Ein perfekt sicherer, winziger Schlüssel

Die Arbeit behauptet, ein System gebaut zu haben, das:

Perfekt sicher ist: Selbst wenn ein Hacker über unendliche Rechenleistung verfügt, kann er nichts über den geheimen Ort erfahren, wenn er einige Schlüssel stiehlt.
Effizient ist: Die „Schlüssel" (die Daten, die jeder Server hält) sind asymptotisch kürzer. Auf Deutsch: Wenn die Datenmenge wächst, wächst die Größe der Schlüssel viel langsamer als zuvor.
Flexibel ist: Es funktioniert für jede Primzahlgröße (eine bestimmte Art mathematischer Gruppe), was eine breite Palette praktischer Bedürfnisse abdeckt.

Der Haken (Einschränkungen)

Die Autoren sind offen über die Kompromisse:

Die „Ein-Server"-Regel: Derzeit garantiert diese spezifische Konstruktion nur, dass ein Server das Geheimnis nicht erfahren kann, wenn er sich mit anderen zusammenschließt. Wenn Sie Schutz gegen das Zusammenwirken von zwei oder drei Servern wollen, müsste das System in der Größe explodieren (was exponentiell mehr Server erfordert), was derzeit zu ineffizient ist, um nützlich zu sein.
Spezifische Mathematik: Es funktioniert am besten mit bestimmten Arten mathematischer Gruppen (Gruppen mit Primzahlordnung), obwohl die Autoren vorschlagen, dass es in Zukunft auf komplexere Gruppen erweitert werden könnte.

Zusammenfassung

Kurz gesagt ist diese Arbeit wie ein Ingenieur, der einen Weg fand, einen massiven, sperrigen Sicherheitsgewölbe zu einem taschengroßen Safe zu verkleinern, ohne an Stärke zu verlieren. Dies gelang ihnen, indem sie eine hocheffiziente „Schlossknack"-Technik aus einem anderen Bereich (Private Information Retrieval) entliehen und sie anpassten, um Geheimnisse auf Server aufzuteilen. Das Ergebnis ist ein System, das mathematisch unknackbar ist und viel schneller zu verwenden ist als alles, was davor kam.

1. Problemstellung

Das Papier befasst sich mit der Konstruktion von Information-Theoretic Distributed Point Functions (ITDPFs).

Definition: Eine $(t, n)$ -ITDPF ermöglicht es, eine Punktfunktion $f_{\alpha, \beta}(x)$ (die bei Eingabe $\alpha$ den Wert $\beta$ ausgibt und sonst 0) in $n$ geheime Schlüssel aufzuteilen. Jede Teilmenge von $\le t$ Servern erfährt absolut nichts über die Funktion (perfekte Sicherheit), während die Summe der Auswertungen aller $n$ Server den Funktionswert rekonstruiert.
Die Herausforderung: Das primäre Maß für die Effizienz bei DPFs ist die Schlüsselgröße (die maximale Größe der geheimen Schlüssel). Bestehende perfekt sichere ITDPFs für die Ausgabegruppe $G = \mathbb{Z}_p$ $G = Z_{p}$ (wobei $p$ $p$ eine beliebige Primzahl ist) leiden unter suboptimalen Schlüsselgrößen.
- Frühere Arbeiten (z. B. Boyle et al., Li et al.) erzielten Schlüsselgrößen mit Exponenten, die Funktionen wie $\nu_r(N) = (\log N)^{1/r}(\log \log N)^{1-1/r}$ beinhalten.
- Das Ziel ist es, die asymptotische Schlüsselgröße zu reduzieren, während die perfekte Sicherheit erhalten bleibt und eine beliebige Primzahl $p$ unterstützt wird.

2. Methodik

Die Autoren schlagen eine neuartige Konstruktion vor, die auf dem LKZ-Framework (Li, Kopparty und Zhang) basiert und mit modernsten Private Information Retrieval (PIR)-Techniken kombiniert wird.

A. Das LKZ-Framework

Das Framework transformiert ein Secret-Sharing-Schema (SSS) mittels Share Conversion in eine ITDPF.

Share Conversion: Es erfordert die Umwandlung von Anteilen aus einem $(t, n)$ -Schwellenwert-SSS ( $L_1$ ) in Anteile eines additiven SSS ( $L_2$ ), sodass die Summe der umgewandelten Anteile eine spezifische Beziehung zum ursprünglichen Geheimnis offenbart.
Bilineare Darstellung: Die Punktfunktion wird als bilineare Funktion der umgewandelten Anteile dargestellt.
Kernidee: Die Schlüsselgröße der resultierenden ITDPF ist proportional zur Kommunikationskomplexität des zugrunde liegenden PIR-Schemas, das zur Generierung der Share Conversion verwendet wird.

B. Nutzung von GKS-derivativenbasiertem PIR

Die zentrale technische Innovation ist die Nutzung des kürzlich vorgestellten 1-private $n_r$ -server PIR-Schemas von Ghasemi, Kopparty und Sudan (GKS, STOC 2025).

GKS-Mechanismus: Im Gegensatz zu früheren PIR-Schemata, die nur Auswertungen eines Polynoms abfragen, fragt GKS sowohl Auswertungen als auch Hasse-Ableitungen des Polynoms ab.
Mathematische Grundlage:
- Verwendung von $S$ -Matching-Familien und $S$ -Decodierpolynomen über endlichen Körpern.
- Einführung der 0-Interpolationseigenschaft mit Vielfachheit. Durch das Abfragen von Ableitungen kann das Schema den konstanten Term eines dünnbesetzten Polynoms mit weniger Servern oder kleineren Parametern interpolieren.
- Konkret erreicht GKS eine Kommunikationskomplexität von $2^{O(\nu_{r+1}(N))}$ für $n_r$ Server, wobei $n_r$ von der Anzahl der Primfaktoren des Moduls abhängt.

C. Die vorgeschlagenen Konstruktionsschritte

Setup:
- Auswahl eines Moduls $M = m \cdot p$ (Produkt verschiedener Primzahlen).
- Konstruktion einer $S_M$ -Matching-Familie und eines $S_M$ -Decodierpolynoms mit Vielfachheit 2 (ermöglicht durch die Abfrage von Ableitungen).
Share Conversion ($Conv$):
- Der Server hält einen Anteil $c_\ell$ , der von einem Zufallsvektor $w$ und dem Zielindex $\alpha$ abgeleitet ist.
- Gegeben eine Eingabe $x$ , berechnet der Server ein „Kernpolynom" $D_x(Z)$ , das auf einer multiplikativen Linie eingeschränkt ist.
- Unter Verwendung der Kettenregel berechnet der Server die Hasse-Ableitung erster Ordnung von $D_x(Z)$ an spezifischen Punkten $b_\ell$ .
- Der Server gibt einen umgewandelten Anteil aus, der die Auswertung $D_x(b_\ell)$ und den Ableitungsterm umfasst, gewichtet mit Interpolationskoeffizienten $a_{\ell, k}$ .
DPF-Generierung:
- Der Generator erstellt $2n_r$ Schlüssel. Jeder Schlüssel besteht aus einem Paar: einem additiven Anteil des Ausgabewerts und einem Anteil aus dem zugrunde liegenden PIR-basierten SSS.
- Der Auswertungsalgorithmus berechnet das Skalarprodukt der Schlüsselkomponenten, um den additiven Anteil von $f_{\alpha, \beta}(x)$ wiederherzustellen.

3. Hauptbeiträge

Neuartige Share Conversion: Die Autoren leiten eine neue Share-Conversion-Funktion direkt aus dem GKS-derivativenbasierten PIR ab. Dies ist die erste Anwendung von derivativenbasiertem PIR zur Konstruktion von ITDPFs.
Verbesserte Schlüsselgröße: Sie konstruieren eine perfekt sichere $(1, 2n_r)$ $(1, 2 n_{r})$ -ITDPF mit der Ausgabegruppe $\mathbb{Z}_p$ $Z_{p}$ .
- Schlüsselgröße: $O(2^{c_2(r) \cdot \nu_{r+1}(N)} \cdot \log p)$ .
- Verbesserung: Dies ist asymptotisch kleiner als die besten bisherigen perfekt sicheren ITDPFs (z. B. Li et al.'s $2^{O(\nu_r(N))}$ ), was effektiv den Exponenten von $\nu_r(N)$ auf $\nu_{r+1}(N)$ reduziert.
Perfekte Sicherheit: Die Konstruktion behält die perfekte Sicherheit (informationstheoretische Sicherheit gegen rechnerisch unbegrenzte Angreifer) bei, im Gegensatz zu einigen statistischen Alternativen, die Sicherheit gegen Effizienz tauschen.
Allgemeingültigkeit: Das Schema funktioniert für jede Primzahl $p$ als Modul der Ausgabegruppe, eine signifikante Verallgemeinerung gegenüber einigen früheren Konstruktionen.

4. Ergebnisse

Theoretische Schranken: Das Papier beweist, dass das vorgeschlagene Schema die Korrektheits- und Perfektheitsanforderungen des LKZ-Frameworks erfüllt.
Vergleich (Tabelle I):
- Im Vergleich zu Thm. 10 von [10] (Li et al.), das eine Schlüsselgröße von $O(2^{c_1(r) \cdot \nu_r(N)})$ hat, erreicht das neue Schema $O(2^{c_2(r) \cdot \nu_{r+1}(N)})$ . Da $\nu_{r+1}(N) < \nu_r(N)$ , sind die neuen Schlüssel asymptotisch strikt kürzer.
- Im Vergleich zu Thm. 1 von [2] (Boyle et al.) ist das neue Schema nicht schlechter und bietet eine bessere asymptotische Skalierung für große $N$ .
Parameter: Die erforderliche Anzahl an Servern beträgt $2n_r$ , wobei $n_r$ durch die Anzahl der Primfaktoren in der PIR-Konstruktion definiert ist (z. B. $n_1=2, n_2=3, \dots$ ).

5. Bedeutung

Effizienz in MPC und PIR: DPFs sind fundamentale Bausteine für Secure Multi-Party Computation (MPC) und Private Information Retrieval (PIR). Die Reduzierung der Schlüsselgröße führt direkt zu geringerem Kommunikationsaufwand und geringeren Speicheranforderungen in diesen Protokollen.
Brückenschlag zwischen PIR und DPFs: Die Arbeit zeigt eine starke Synergie zwischen jüngsten Fortschritten im PIR (insbesondere derivativenbasierten Ansätzen) und der DPF-Konstruktion auf. Sie legt nahe, dass Verbesserungen der PIR-Kommunikationskomplexität direkt in effizientere DPFs übersetzt werden können.
Zukünftige Richtungen:
- Die aktuelle Konstruktion ist auf 1-private DPFs beschränkt (Sicherheit gegen 1 kolludierenden Server), da das zugrunde liegende GKS-PIR 1-privat ist. Die Erweiterung auf $t$ -private DPFs mit $t > 1$ ohne exponentiellen Anstieg der Serveranzahl bleibt eine offene Herausforderung.
- Die Erweiterung der Ausgabegruppe von Primordnungs- $\mathbb{Z}_p$ auf beliebige abelsche Gruppen wird als zukünftige Arbeit identifiziert.

Zusammenfassend stellt dieses Papier einen Durchbruch in der Effizienz perfekt sicherer ITDPFs dar, indem es die neuesten derivativenbasierten PIR-Techniken nutzt und die kürzesten bekannten geheimen Schlüssel für Ausgabegruppen mit Primordnung erreicht.