💻 computer science

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

Dit artikel presenteert een gedeeltelijke derandomisering van evaluatieplaatsen voor lekbestendige Shamir-geheime delen over composiete orde velden door $n$ onafhankelijke willekeurige punten te vervangen door iteraties van een vaste rationale functie, waardoor de vereiste willekeur wordt verminderd van $nd \log p$ naar $d \log p$ bits, terwijl perfecte veiligheid tegen enkelblok-lekken wordt bereikt voor specifieke parameterregimes.

Oorspronkelijke auteurs: S. Venkitesh

Gepubliceerd 2026-08-03

📖 3 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: S. Venkitesh

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een geheim veilig wilt houden, zoals een schatkaart of een wachtwoord, maar je moet het in stukken splitsen en elk een stukje geven aan je vrienden. Dit is de wereld van Secret Sharing. De klassieke manier om dit te doen, uitgevonden door een wiskundige genaamd Shamir, is als een magische puzzel: als een bepaald aantal vrienden (bijvoorbeeld 3 van de 5) hun stukjes bij elkaar brengt, lost de puzzel zichzelf op en wordt de schat onthuld. Maar als er minder vrienden zijn, zien de stukjes eruit als willekeurige wartaal en blijft het geheim veilig.

Echter, het echte leven is rommelig. Een sluwe dief kan misschien niet een heel stuk van de puzzel stelen, maar hij kan wel van elk stukje van elke vriend een piepklein beetje informatie opvangen tegelijkertijd. Misschien ziet hij of een specifiek lampje op een computerchip aan of uit staat, of hoort hij een heel zacht elektrisch gezoem. Dit wordt physical bit leakage genoemd. Het is alsof een dief niet de hele sleutel kan stelen, maar de vorm van de tanden van elke sleutel aan een ring kan voelen, één klein bobbeltje tegelijk. Als de puzzelstukken onzorgvuldig zijn gerangschikt, kunnen deze kleine inkijkjes optellen om het hele geheim te onthullen.

Lama lang was de beste manier om deze dief tegen te houden het kiezen van de puzzelstukken volkomen willekeurig. Het is alsof je dobbelstenen gooit om te beslissen waar je elk stukje verstopt. Dit werkt geweldig, maar het heeft een probleem: je hebt een vertrouwde "dobbelsteenwerper" (een bron van perfecte willekeur) nodig elke keer dat je het systeem opzet. Als de dobbelsteenwerper gemanipuleerd is of als de dief de worp kan beïnvloeden, kan het hele systeem instorten. Wetenschappers wilden een manier vinden om deze schuilplaatsen te kiezen met een eenvoudige, vaste regel in plaats van willekeurige dobbelstenen, zodat het systeem altijd veilig is, ongeacht wie er kijkt.

Dit artikel pakt precies dat probleem aan. De auteur, voortbouwend op recente ontdekkingen die lieten zien dat secret sharing ofwel perfect veilig is, ofwel volledig gebroken is tegenover deze kleine inkijkjes, presenteert een nieuwe manier om de schuilplaatsen te kiezen. In plaats van voor elke vriend dobbelstenen te gooien, gebruikt hij een slim, herhalend wiskundig patroon. Hij kiest één startgetal en genereert vervolgens alle andere schuilplaatsen door herhaaldelijk een eenvoudige formule toe te passen, als een kettingreactie.

De auteur bewijst dat deze methode ongelooflijk goed werkt. Hij laat zien dat voor een specifieke reeks groepsgroottes dit gestructureerde patroon het secret sharing-schema perfect veilig maakt. Dit betekent dat de statistische afstand tussen de gelekte informatie en het werkelijke geheim exact nul is; de dief leert absoluut niets, zelfs geen klein voordeel. Hij biedt ook een test om te controleren of het startgetal "goed" (veilig) of "slecht" (onveilig) is, en hij bewijst dat goede startgetallen gemakkelijk te vinden zijn. Hoewel deze methode werkt voor een iets kleiner aantal vrienden dan de methode met de willekeurige dobbelstenen, elimineert het de noodzaak voor een vertrouwde dobbelsteenwerper, wat het systeem praktischer en robuuster tegen manipulatie maakt. Het artikel sluit expliciet het gebruik van een simpeler, meer voor de hand liggend patroon uit (slechts vermenigvuldigen met een getal), en laat zien dat dit faalt om dergelijke veiligheid te bieden omdat het een specifieke wiskundige "twist" mist die hun nieuwe formule wel bevat.

Technisch Overzicht: Partiële Derandomisering voor Lekkeresistentie in Shamir's Secret Sharing over Veldstructuren met Samengestelde Orde

1. Probleemstelling

Het artikel behandelt de constructie van expliciete evaluatieplaatsen voor Shamir's Secret Sharing (SSS) schema's die resistent zijn tegen fysieke bit-lekken (physical-bit leakage) over velden met een samengestelde orde ( $\mathbb{F}_{p^d}$ waar $d \ge 2$ ).

In standaard SSS wordt een geheim gedeeld onder $n$ partijen, waarbij elke $k$ partijen het kunnen reconstrueren. Terwijl gerandomiseerde constructies (waarbij evaluatieplaatsen uniform willekeurig worden gekozen) bekend staan als statistisch veilig tegen lokale lekkage, vereisen zij vertrouwde publieke willekeur. In de praktijk kunnen tegenstanders de willekeurige zaadwaarde (random seed) beïnvloeden, waardoor het schema naar kwetsbare evaluatieplaatsen wordt gestuurd.

Vorig werk heeft vastgesteld dat:

Over priemvelden ( $\mathbb{F}_p$ ) willekeurige evaluatieplaatsen met hoge waarschijnlijkheid lekkeresistentie opleveren.
Over velden met een samengestelde orde ( $\mathbb{F}_{p^d}$ ), Nguyen (EUROCRYPT 2025) een perfecte dichotomie vaststelde: elk lineair code-gebaseerd geheim deelingsschema is ofwel perfect veilig (statistische afstand 0) ofwel volledig onveilig tegen fysieke bit-lekken.
Echter, voor velden met een samengestelde orde was er voor $k > 2$ of algemene block-lekregimes geen expliciete, deterministische familie van evaluatieplaatsen bekend. Bestaande expliciete constructies voor priemvelden vertrouwden op niet-lineaire bit-extractie-eigenschappen die niet van toepassing zijn op de lineaire coördinaat-afbeeldingen van samengestelde velden.

De kernuitdaging is om de keuze van evaluatieplaatsen te derandomiseren (het verminderen van de entropie die nodig is om ze te specificeren) terwijl de perfecte veiligheid tegen fysieke bit-lekken in de context van samengestelde velden behouden blijft.

2. Methodologie en Constructie

De auteur stelt een partiële derandomiseringsstrategie voor. In plaats van $n$ onafhankelijke willekeurige evaluatiepunten te selecteren, construeert de auteur de evaluatieplaatsen als de iteraties van een enkele rationale functie $\Phi$ toegepast op een willekeurig gekozen basispunt $x_0$ .

De Constructie:

Veldopzet: Laat $\mathbb{F} = \mathbb{F}_{p^d}$ zijn met een primitief element $\alpha$ .
Stap-operator: Definieer de Möbius-transformatie $\Phi(x) = \frac{\alpha x}{x + 1}$ .
Evaluatieplaatsen: De $n$ evaluatieplaatsen worden gedefinieerd als $x_j = \Phi^j(x_0)$ voor $j = 0, \dots, n-1$ , waarbij $x_0 \in \mathbb{F}^*$ een willekeurig gekozen basispunt is.
Entropiereductie: Het specificeren van het schema vereist slechts $d \log p$ bits (om $x_0$ te kiezen), een significante reductie ten opzichte van de $nd \log p$ bits die nodig zijn voor $n$ onafhankelijke willekeurige punten.

Cruciaal Structureel Inzicht:
De veiligheidsanalyse berust op de distincte polen van de iteraties $\Phi^j$ .

$\Phi^0(x) = x$ heeft een pool bij $\infty$ .
Voor $j \ge 1$ heeft $\Phi^j(x)$ een distinctie pool bij een ander eindig punt in $\mathbb{F}^*$ .
Deze "pool-distinctheid" is cruciaal. De auteur contrasteert dit met de kandidaat $\Psi(x) = \alpha x$ (zuivere dilatatie), waarbij alle iteraties dezelfde pool delen bij $\infty$ , waardoor de veiligheidsargumentatie instort.

3. Technische Benadering

Het bewijs verloopt in drie fasen, gebruikmakend van de perfecte dichotomie vastgesteld door Nguyen (2025):

De Perfecte Dichotomie (Fase 1):
Het artikel maakt gebruik van het feit dat coördinaat-extractie in $\mathbb{F}_{p^d}$ $\mathbb{F}_p$ -lineair is. Bijgevolg is de lekfunctie lineair. Dit impliceert dat de statistische afstand tussen lek-distributies voor verschillende geheimen ofwel 0 ofwel 1 is. Perfecte veiligheid wordt bereikt indien en slechts indien de lekfunctie surjectief is. Deze conditie is equivalent aan een testmatrix $\Theta_{\vec{i}}$ (afgeleid van de evaluatieplaatsen en het lekpatroon) die volledige kolomrang heeft over $\mathbb{F}_p$ .
Partiële Breuk Niet-degeneratie (Fase 2):
Om de testmatrix een volledige rang te geven, moet de auteur aantonen dat geen enkele niet-triviale lineaire combinatie van de macht van de evaluatieplaatsen verdwijnt. Zij definiëren een rationale functie $G_\ell(x) = \sum c_j \eta(i_j) (\Phi^j(x))^\ell$ .
Met behulp van partiële breukontbinding maken zij gebruik van de distincte polen van $\Phi^j$ . Omdat de polen distinct zijn, wordt de residu van $G_\ell$ bij een specifieke pool bepaald door een enkele term in de som. Als $G_\ell$ identiek nul zou zijn, zouden alle coëfficiënten moeten verdwijnen. Dit "niet-degeneratie"-argument begrenst het aantal "slechte" basispunten $x_0$ die ervoor zorgen dat de rangconditie faalt.
Multi-block Extensie (Fase 3):
Het argument wordt uitgebreid naar multi-block lekkage (waarbij meerdere coördinaten per share gelekt worden). De auteur behandelt de veldcoëfficiënten die voortvloeien uit lineaire combinaties binnen de shares, en toont aan dat het partiële breuk-argument geldig blijft, mits het lekpatroon "toelaatbaar" (admissible) is (distincte block-posities per share).

4. Belangrijkste Resultaten

Stelling 1.1 (Perfecte Veiligheid tegen Single-Block Lekkage):
Voor parameters $n = O(d / \log_p d)$ en elke drempelwaarde $k \ge 2$ , bestaat er een verzameling "slechte" basispunten $Bad \subset \mathbb{F}^*$ met grootte $|Bad| \le n + n(dp)^n$ . Voor elke $x_0 \notin Bad$ is het schema dat de evaluatieplaatsen $x_j = \Phi^j(x_0)$ gebruikt perfect veilig (statistische afstand exact 0) tegen elk single-block lekpatroon.

Dit impliceert perfecte veiligheid tegen enkele fysieke bit-lekken per share voor elke priem $p$ .
Een goed $x_0$ is gegarandeerd aanwezig wanneer $d > n(1 + \log_p d) + \log_p(2n)$ .

Stelling 1.2 (Multi-Block Lekkage):
Voor een vast toelaatbaar lekpatroon met $M$ totaal gelekte blokken is de grootte van de slechte verzameling begrensd door $n + n \cdot p^M$ . Een goed $x_0$ bestaat indien $M < d - \log_p(2n)$ .

Voor universele veiligheid tegen alle patronen met $\le M$ blokken, is de grens $|Bad| \le n + n(dpe)^M$ , waarbij existentie gegarandeerd is wanneer $d > M(\frac{5}{2} + \log_p d) + \log_p(2n)$ .

Classificator:
Het artikel biedt een expliciete classificator (Algoritme 1) die, gegeven een kandidaat $x_0$ , de volledige-rang-conditie voor alle lekpatronen verifieert. Dit dient als een solide test om de veiligheid van de gestructureerde constructie te certificeren.

5. Betekenis en Vergelijking

Het artikel claimt de volgende bijdragen en onderscheidend vermogen:

Perfecte Veiligheid vs. Statistische Veiligheid: In tegenstelling tot eerdere gerandomiseerde constructies over samengestelde velden die statistische veiligheid boden ( $\epsilon = 2^{-\Omega(d)}$ ), bereikt deze constructie perfecte veiligheid (statistische afstand 0) voor een beperkt parameterregime.
Derandomisering: Het vermindert de willekeur die nodig is om het schema te specificeren van $nd \log p$ bits naar $d \log p$ bits door de evaluatieplaatsen te beperken tot een één-parameter familie (de baan van $\Phi$ ).
Expliciete Constructie: Het biedt de eerste expliciete familie van evaluatieplaatsen voor $k > 2$ over samengestelde velden die resistent is tegen fysieke bit-lekken, waarmee het voorbij gaat aan het "random places"-paradigma.
Beperkingen en Trade-offs:
- Het aantal partijen $n$ is beperkt tot $O(d / \log_p d)$ , terwijl gerandomiseerde constructies $O(dk / \log_p d)$ ondersteunen. De auteur vermoedt dat dit factor- $k$ verlies inherent is aan één-parameter constructies.
- De universaliteit voor multi-block lekkage wordt momenteel beperkt door een bottleneck in de enumeratie van patronen, wat resulteert in exponentiële grenzen voor de slechte verzameling in $M$ .
- De constructie rust op de specifieke algebraïsche structuur van de Möbius-transformatie $\Phi(x) = \alpha x / (x+1)$ ; de alternatieve dilatatie $\alpha x$ faalt in het bieden van veiligheid.

Het werk claimt niet het probleem van derandomisering voor alle parameterregimes op te lossen, maar identificeert dit als een open probleem, evenals de polynomiale grootte van de slechte-verzameling voor multi-block universaliteit. De primaire bijdrage is een rigoureuze, partiële derandomisering die perfecte veiligheid bereikt in een specifiek, praktisch relevant regime door gebruik te maken van de distincte polen van rationale iteraties.