💻 computer science

Partial Derandomization for Leakage-Resilient Shamir's Secret Sharing over Composite Order Fields

Diese Arbeit präsentiert eine partielle Derandomisierung von Evaluationsstellen für leckage-resistente Shamir-Geheimnisverarbeitung über Körpern zusammengesetzter Ordnung, indem $n$ unabhängige Zufallspunkte durch Iterationen einer fixen rationalen Funktion ersetzt werden, wodurch der benötigte Zufallsaufwand von $nd \log p$ auf $d \log p$ Bits reduziert wird, während gleichzeitig perfekte Sicherheit gegen Einzelblock-Leckage für spezifische Parameterregime erreicht wird.

Ursprüngliche Autoren: S. Venkitesh

Veröffentlicht 2026-08-03

📖 3 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: S. Venkitesh

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 möchten ein Geheimnis sicher aufbewahren, wie etwa eine Schatzkarte oder ein Passwort, aber Sie müssen es in Stücke zerlegen und jedem Ihrer Freunde ein Stück davon geben. Dies ist die Welt des Secret Sharing (Geheimnis-Teilung). Die klassische Methode, um dies zu tun, erfunden von einem Mathematiker namens Shamir, ist wie ein magisches Puzzle: Wenn genügend Freunde (sagen wir 3 von 5) ihre Teile zusammenbringen, löst sich das Puzzle von selbst und enthüllt den Schatz. Aber wenn weniger Freunde zusammenkommen, sehen die Teile wie zufälliger Buchstabensalat aus und das Geheimnis bleibt sicher.

Das echte Leben ist jedoch chaotisch. Ein hinterlistiger Dieb kann vielleicht kein ganzes Teil des Puzzles stehlen, aber er kann von jedem Teil der Freunde gleichzeitig winzige, winzige Informationen erhaschen. Vielleicht kann er sehen, ob ein bestimmtes Licht auf einem Computerchip an oder aus ist, oder er kann ein winziges elektrisches Summen hören. Dies wird als physische Bit-Leckage bezeichnet. Es ist, als könnte der Dieb nicht den ganzen Schlüssel stehlen, aber er kann die Form der Zähne an jedem einzelnen Schlüssel in einem Schlüsselbund fühlen, einen winzigen Hügel nach dem anderen. Wenn die Puzzleteile unvorsichtig angeordnet sind, können sich diese winzigen Blicke zu dem gesamten Geheimnis summieren.

Lange Zeit war der beste Weg, diesen Dieb zu stoppen, die Puzzleteile vollkommen zufällig auszuwählen. Es ist, als würde man Würfel werfen, um zu entscheiden, wo jedes Teil versteckt wird. Das funktioniert großartig, hat aber ein Problem: Man benötigt einen vertrauenswürdigen „Würfelwerfer“ (eine Quelle perfekter Zufälligkeit) jedes Mal, wenn man das System aufbaut. Wenn der Würfelwerfer manipuliert ist oder der Dieb den Wurf beeinflussen kann, kann das gesamte System zusammenbrechen. Wissenschaftler suchten nach einem Weg, diese Verstecke mithilfe einer einfachen, festen Regel statt durch zufällige Würfel zu wählen, damit das System immer sicher ist, egal wer zusieht.

Dieses Paper befasst sich genau mit diesem Problem. Der Autor nutzt aktuelle Entdeckungen, die zeigten, dass Secret Sharing gegen diese winzigen Blicke entweder perfekt sicher oder völlig kompromittiert ist, und präsentiert einen neuen Weg, die Verstecke zu wählen. Anstatt für jeden einzelnen Freund die Würfel zu werfen, verwendet er ein kluges, sich wiederholendes mathematisches Muster. Er wählt eine Startzahl und generiert dann alle anderen Verstecke, indem er immer wieder eine einfache Formel anwendet, wie eine Kettenreaktion.

Der Autor beweist, dass diese Methode unglaublich gut funktioniert. Er zeigt, dass dieses strukturierte Muster für einen bestimmten Bereich von Gruppengrößen das Secret Sharing perfekt sicher macht. Das bedeutet, dass der statistische Abstand zwischen der geleakten Information und dem eigentlichen Geheimnis exakt Null ist; der Dieb erfährt absolut nichts, nicht einmal einen winzigen Vorteil. Er liefert auch einen Test, um zu prüfen, ob die Startzahl „gut“ (sicher) oder „schlecht“ (unsicher) ist, und beweist, dass gute Startzahlen leicht zu finden sind. Während diese Methode für eine etwas kleinere Anzahl von Freunden als die Methode mit den zufälligen Würfeln funktioniert, macht sie den Bedarf an einem vertrauenswürdigen Würfelwerfer überflüssig, was das System praktischer und robuster gegenüber Manipulationen macht. Das Paper schließt die Verwendung eines einfacheren, offensichtlicheren Musters (einfach das Multiplizieren mit einer Zahl) explizit aus und zeigt, dass dies keine Sicherheit bietet, da es den spezifischen mathematischen „Twist“ vermissen lässt, den ihre neue Formel enthält.

Technisches Resümee: Partielle Derandomisierung für die leckage-resistente Shamir-Secret-Sharing-Methode über Körpern mit zusammengesetzter Ordnung

1. Problemstellung

Die Arbeit befasst sich mit der Konstruktion expliziter Evaluationsstellen für Shamir-Secret-Sharing-Verfahren (SSS), die gegen physische Bit-Leckage (physical-bit leakage) über Körpern mit zusammengesetzter Ordnung ( $\mathbb{F}_{p^d}$ mit $d \ge 2$ ) resistent sind.

Im Standard-SSS wird ein Geheimnis unter $n$ Parteien aufgeteilt, sodass eine Gruppe von $k$ Parteien es rekonstruieren kann. Randomisierte Konstruktionen (bei denen die Evaluationsstellen gleichmäßig zufällig gewählt werden) sind bekannt für ihre statistische Sicherheit gegen lokale Leckage, erfordern jedoch vertrauenswürdige öffentliche Zufallszahlen. In der Praxis können Angreifer den Zufallssamen beeinflussen und das Verfahren so steuern, dass es zu vulnerablen Evaluationsstellen führt.

Vorherige Arbeiten haben Folgendes festgestellt:

Über Primkörpern ( $\mathbb{F}_p$ ) führen zufällige Evaluationsstellen mit hoher Wahrscheinlichkeit zu Leckage-Resistenz.
Über Körpern mit zusammengesetzter Ordnung ( $\mathbb{F}_{p^d}$ ) etablierte Nguyen (EUROCRYPT 2025) eine perfekte Dichotomie: Jedes auf linearen Codes basierende Secret-Sharing-Verfahren ist entweder perfekt sicher (statistischer Abstand 0) oder völlig unsicher gegenüber physischer Bit-Leckage.
Für Körper mit zusammengesetzter Ordnung war jedoch bisher keine explizite, deterministische Familie von Evaluationsstellen für $k > 2$ oder allgemeine Block-Leckage-Regime bekannt. Bestehende explizite Konstruktionen für Primkörper stützten sich auf nicht-lineare Bit-Extraktionseigenschaften, die auf die linearen Koordinatenabbildungen von Körpern mit zusammengesetzter Ordnung nicht anwendbar sind.

Die zentrale Herausforderung besteht darin, die Wahl der Evaluationsstellen zu derandomisieren (den Entropiebedarf zur Spezifikation zu reduzieren), während gleichzeitig die perfekte Sicherheit gegen physische Bit-Leckage im Kontext von Körpern mit zusammengesetzter Ordnung aufrechterhalten wird.

2. Methodik und Konstruktion

Der Autor schlägt eine Strategie der partiellen Derandomisierung vor. Anstatt $n$ unabhängige zufällige Evaluationspunkte auszuwählen, konstruiert er die Evaluationsstellen als Iterationen einer einzelnen rationalen Funktion $\Phi$ , die auf einen zufällig gewählten Basispunkt $x_0$ angewendet wird.

Die Konstruktion:

Feld-Setup: Sei $\mathbb{F} = \mathbb{F}_{p^d}$ mit einem primitiven Element $\alpha$ .
Schritt-Operator: Definiere die Möbius-Transformation $\Phi(x) = \frac{\alpha x}{x + 1}$ .
Evaluationsstellen: Die $n$ Evaluationsstellen sind definiert als $x_j = \Phi^j(x_0)$ für $j = 0, \dots, n-1$ , wobei $x_0 \in \mathbb{F}^*$ ein zufällig gewählter Basispunkt ist.
Entropie-Reduktion: Die Spezifikation des Verfahrens erfordert nur noch $d \log p$ Bits (um $x_0$ zu wählen), was eine signifikante Reduktion gegenüber den $nd \log p$ Bits darstellt, die für $n$ unabhängige Zufallspunkte erforderlich wären.

Zentraler struktureller Einblick:
Die Sicherheitsanalyse stützt sich auf die distinkten Pole der Iterationen $\Phi^j$ .

$\Phi^0(x) = x$ hat einen Pol bei $\infty$ .
Für $j \ge 1$ hat $\Phi^j(x)$ einen distinkten endlichen Pol in $\mathbb{F}^*$ .
Diese „Pol-Distinktheit“ ist entscheidend. Der Autor kontrastiert dies mit dem Kandidaten $\Psi(x) = \alpha x$ (reine Dilatation), bei dem alle Iterationen denselben Pol bei $\infty$ teilen, was die Sicherheitsargumentation zum Kollabieren brächte.

3. Technischer Ansatz

Der Beweis erfolgt in drei Phasen unter Nutzung der durch Nguyen (2025) etablierten perfekten Dichotomie:

Die perfekte Dichotomie (Phase 1):
Die Arbeit nutzt die Tatsache, dass die Koordinatenextraktion in $\mathbb{F}_{p^d}$ $\mathbb{F}_p$ -linear ist. Folglich ist die Leckage-Abbildung linear. Dies impliziert, dass der statistische Abstand zwischen Leckage-Verteilungen verschiedener Geheimnisse entweder 0 oder 1 ist. Perfekte Sicherheit wird erreicht, wenn und nur wenn die Leckage-Abbildung surjektiv ist. Diese Bedingung ist äquivalent dazu, dass eine Testmatrix $\Theta_{\vec{i}}$ (abgeleitet aus den Evaluationsstellen und dem Leckage-Muster) vollen Spaltenrang über $\mathbb{F}_p$ besitzt.
Partielle Bruchentfaltung-Nichtdegeneriertheit (Phase 2):
Um den vollen Rang der Testmatrix zu beweisen, muss der Autor zeigen, dass keine nicht-triviale Linearkombination der Potenzen der Evaluationsstellen verschwindet. Er definiert eine rationale Funktion $G_\ell(x) = \sum c_j \eta(i_j) (\Phi^j(x))^\ell$ .
Unter Verwendung der partiellen Bruchentfaltung nutzt er die distinkten Pole von $\Phi^j$ aus. Da die Pole distinkt sind, wird der Residue von $G_\ell$ an einem spezifischen Pol durch einen einzelnen Term in der Summe bestimmt. Wäre $G_\ell$ identisch Null, müssten alle Koeffizienten verschwinden. Dieses „Nichtdegeneriertheits“-Argument begrenzt die Anzahl der „schlechten“ Basispunkte $x_0$ , die die Rangbedingung verletzen.
Multi-Block-Erweiterung (Phase 3):
Das Argument wird auf Multi-Block-Leckage erweitert (bei der mehrere Koordinaten pro Anteil geleakt werden). Der Autor behandelt die Feldkoeffizienten, die aus Linearkombinationen innerhalb der Anteile resultieren, und zeigt, dass das Argument der partiellen Bruchentfaltung gültig bleibt, sofern das Leckage-Muster „zulässig“ ist (distinkte Blockpositionen pro Anteil).

4. Hauptergebnisse

Theorem 1.1 (Perfekte Sicherheit gegen Single-Block-Leckage):
Für die Parameter $n = O(d / \log_p d)$ und jedes Schwellenwert $k \ge 2$ existiert eine Menge „schlechter“ Basispunkte $Bad \subset \mathbb{F}^*$ mit der Größe $|Bad| \le n + n(dp)^n$ . Für jedes $x_0 \notin Bad$ ist das Verfahren unter Verwendung der Evaluationsstellen $x_j = \Phi^j(x_0)$ perfekt sicher (statistischer Abstand exakt 0) gegen jedes Single-Block-Leckage-Muster.

Dies impliziert perfekte Sicherheit gegen jede Single-Bit-Leckage pro Anteil für jede Primzahl $p$ .
Ein gutes $x_0$ ist garantiert vorhanden, wenn $d > n(1 + \log_p d) + \log_p(2n)$ .

Theorem 1.2 (Multi-Block-Leckage):
Für ein festes zulässiges Leckage-Muster mit $M$ insgesamt geleakten Blöcken ist die Größe der Menge der schlechten Punkte durch $|Bad| \le n + n \cdot p^M$ beschränkt. Ein gutes $x_0$ existiert, wenn $M < d - \log_p(2n)$ .

Für universelle Sicherheit gegen alle Muster mit $\le M$ Blöcken gilt: $|Bad| \le n + n(dpe)^M$ , wobei die Existenz garantiert ist, wenn $d > M(\frac{5}{2} + \log_p d) + \log_p(2n)$ .

Klassifizierer:
Die Arbeit stellt einen expliziten Klassifizierer bereit (Algorithmus 1), der gegeben einen Kandidaten $x_0$ die Vollrang-Bedingung für alle Leckage-Muster verifiziert. Dies dient als fundierter Test, um die Sicherheit der strukturierten Konstruktion zu zertifizieren.

5. Bedeutung und Vergleich

Die Arbeit beansprucht folgende Beiträge und Unterscheidungen:

Perfekte Sicherheit vs. Statistische Sicherheit: Im Gegensatz zu bisherigen randomisierten Konstruktionen über Körpern mit zusammengesetzter Ordnung, die statistische Sicherheit ( $\epsilon = 2^{-\Omega(d)}$ ) boten, erreicht diese Konstruktion perfekte Sicherheit (statistischer Abstand 0) für ein eingeschränktes Parameterregime.
Derandomisierung: Sie reduziert die erforderliche Zufälligkeit zur Spezifikation des Verfahrens von $nd \log p$ Bits auf $d \log p$ Bits, indem sie die Evaluationsstellen auf eine Ein-Parameter-Familie (die Orbit von $\Phi$ ) einschränkt.
Explizite Konstruktion: Sie liefert die erste explizite Familie von Evaluationsstellen für $k > 2$ über Körpern mit zusammengesetzter Ordnung, die gegen physische Bit-Leckage resistent ist, und bewegt sich damit über das Paradigma der „zufälligen Stellen“ hinaus.
Limitierungen und Trade-offs:
- Die Anzahl der Parteien $n$ ist auf $O(d / \log_p d)$ begrenzt, während randomisierte Konstruktionen $O(dk / \log_p d)$ unterstützen. Der Autor vermutet, dass dieser Faktor- $k$ -Verlust inhärent für Ein-Parameter-Konstruktionen ist.
- Die universelle Multi-Block-Sicherheit ist derzeit durch einen Engpass in der Muster-Enumeration begrenzt, was zu exponentiellen Bad-Set-Grenzen in $M$ führt.
- Die Konstruktion beruht auf der spezifischen algebraischen Struktur der Möbius-Transformation $\Phi(x) = \alpha x / (x+1)$ ; die alternative Dilatation $\alpha x$ bietet keine Sicherheit.

Die Arbeit behauptet nicht, das Derandomisierungsproblem für alle Parameterregime gelöst zu haben, und identifiziert die polynomielle Größe der Bad-Set-Grenzen für die Multi-Block-Universalität als offene Probleme. Der primäre Beitrag ist eine rigorose, partielle Derandomisierung, die perfekte Sicherheit in einem spezifischen, praktisch relevanten Regime durch die Ausnutzung der distinkten Pole rationaler Iterationen erreicht.