💻 computer science

Quantum Leakage Resilience of Shamir Secret Sharing

Dit artikel stelt vast dat ongewijzigde Shamir-geheime delen over priemvelden veilig blijft tegen kwantumlokale lekkage wanneer de drempelwaarde boven ongeveer 0,73339 ligt, mits lekapparaten beperkte of geen verstrengeling hebben, terwijl wordt aangetoond dat willekeurige verstrengeling tussen apparaten de veiligheid volledig kan breken, zelfs met klassieke lekkage.

Oorspronkelijke auteurs: Rishabh Batra, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa

Gepubliceerd 2026-09-30

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Rishabh Batra, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa

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

In het digitale tijdperk betekent het beschermen van een geheim vaak het opdelen ervan in stukken en die stukken aan verschillende mensen geven. Deze methode, bekend als secret sharing (geheime verdeling), zorgt ervoor dat niemand de volledige sleutel tot een kluis, een wachtwoord of een privécode in handen heeft. In plaats daarvan moeten een specifiek aantal mensen samenkomen om de oorspronkelijke informatie te reconstrueren. Deze benadering is een hoeksteen van de moderne cryptografie, gebruikt voor het beheren van encryptiesleutels en het beveiligen van communicatie. Decennialang hebben onderzoekers bestudeerd hoe ze deze systemen robuust kunnen maken tegen een specifiek type dreiging: een aanvaller die niet de hele stukken kan stelen, maar wel kleine fragmenten ervan kan besluipen. Dit wordt lekkage genoemd. Als een aanvaller zelfs maar één bit aan informatie kan lezen van elk stukje van elke persoon, kan hij mogelijk de hele geheime informatie weer in elkaar puzzelen. De vraag is altijd geweest: hoeveel kan een aanvaller leren voordat het systeem breekt?

Nu de technologie verschuift van klassieke computers naar quantumcomputers, verandert de aard van deze kleine fragmenten. In plaats van alleen bits aan informatie, kan een aanvaller een quantum bit, of qubit, kunnen extraheren, die in een complexe staat van meerdere mogelijkheden tegelijk kan bestaan. Een nieuwe studie door onderzoekers van EPFL en NTT Social Informatics Laboratories onderzoekt of de standaard, breed gebruikte methode van secret sharing kan overleven onder dit nieuwe soort quantum-besluipen. Zij ontdekten dat het systeem veilig blijft, maar alleen als het aantal mensen dat nodig is om het geheim te ontsluiten hoog genoeg is. Specifiek, als de groep meer dan ongeveer drieënzeventig procent van de totale deelnemers nodig heeft om het geheim te reconstrueren, houdt het schema stand, zelfs wanneer een aanvaller probeert een quantum bit uit elk deel van elke deelnemer te extraheren. Deze veiligheid blijft van kracht, zelfs als de aanvaller alle gelekte quantum bits tegelijkertijd meet.

De onderzoekers verkenden ook een complexer scenario waarin de apparaten die de geheime delen bevatten, een speciale quantumverbinding kunnen delen die verstrengeling (entanglement) wordt genoemd, met elkaar, of zelfs met de aanvaller. Verstrengeling is een fenomeen waarbij deeltjes zo met elkaar verbonden raken dat de staat van de een de ander onmiddellijk beïnvloedt, ongeacht de afstand. De studie laat zien dat het systeem deze dreiging nog steeds kan weerstaan, mits het aantal apparaten dat deze verbindingen deelt relatief klein blijft in vergelijking met de totale groepsgrootte. De onderzoekers ontdekten echter ook een harde grens. Als het aantal apparaten dat verstrengeling deelt te groot wordt, wordt het systeem kwetsbaar. Ze demonstreerden een specifieke aanval waarbij een groep apparaten, gebruikmakend van een gedeelde quantumtoestand die bekend staat als een GHZ-toestand, slechts één klassieke bit per stuk kan lekken en toch het geheim kan onthullen. Deze aanval werkt zelfs als de apparaten geen verstrengeling hebben met de aanvaller, wat bewijst dat de grootte van de verstrengelde groep de cruciale factor is.

Het werk steunt op een wiskundige benadering die het proces van secret sharing behandelt als een patroon van golven. Door te analyseren hoe deze golven met elkaar interageren, konden de onderzoekers bewijzen dat zolang de drempel voor reconstructie hoog genoeg is, de informatie die door de quantum bits lekt, te verstrooid is om nuttig te zijn. Ze toonden aan dat voor een groep deelnemers, als het vereiste aantal om te ontsluiten ongeveer drieënzeventig procent van het totaal is, de kans dat een aanvaller het geheim correct raadt zo klein is dat deze effectief nul is. Dit resultaat is significant omdat het van toepassing is op de ongewijzigde versie van het secret sharing-schema die al vandaag de dag in gebruik is, wat betekent dat er geen wijzigingen aan bestaande protocollen nodig zijn om dit niveau van quantumveiligheid te verkrijgen.

De studie verheldert ook de grens tussen veiligheid en gevaar. Hoewel een klein aantal apparaten dat verstrengeling deelt veilig is, bewezen de onderzoekers dat als een grote genoeg groep deze verbindingen deelt, de veiligheid instort. Ze ontdekten dat zelfs met klassieke bits, als genoeg apparaten verstrengeld zijn, zij hun lekken kunnen coördineren om het geheim te onthullen. Dit suggereert dat in een wereld met quantummogelijkheden, de veiligheid van secret sharing niet alleen afhangt van hoeveel informatie er lekt, maar ook van hoe de apparaten die die informatie bevatten met elkaar verbonden zijn. De bevindingen bieden een duidelijke kaart van waar deze systemen veilig zijn en waar ze niet zijn, wat een gids biedt voor het bouwen van veilige systemen in een toekomst waarin quantumcomputers een realiteit zijn.

De onderzoekers stopten niet bij het bewijzen van veiligheid; ze identificeerden ook het precieze punt waarop het faalt. Ze berekenden dat voor een systeem om veilig te blijven tegen een lineair aantal verstrengelde apparaten, de drempelwaarde voldoende hoog moet zijn. Als de drempel te laag is, is het systeem onveilig. Deze balans tussen het aantal deelnemers dat nodig is om te ontsluiten en de hoeveelheid verstrengeling die is toegestaan, is de belangrijkste les. De studie bevestigt dat hoewel quantumlekkage een ernstige zorg is, het beheersbaar is met de juiste parameters. De resultaten bieden een geruststellende conclusie voor degenen die vertrouwen op deze cryptografische instrumenten: de bekende methoden van secret sharing zijn veerkrachtig, mits de regels voor reconstructie hoog genoeg worden ingesteld om de quantumdreigingen buiten de deur te houden.

Technische Samenvatting: Kwantumlekkage-resistentie van Shamir Secret Sharing

Probleemstelling

Het artikel onderzoekt de kwantumlekkage-resistentie van het standaard, ongewijzigde Shamir secret sharing schema over priemvelden $\mathbb{F}_p$ . Hoewel Shamir's schema breed wordt gebruikt in drempelcryptografie en veilige multiparty computing, gaan de veiligheidsgaranties traditioneel ervan uit dat onbevoegde verzamelingen niets leren over het geheim. In de praktica kan er echter partiële informatie (lekkage) worden blootgesteld via zijkanalen.

De auteurs breiden de studie van lokale lekkage-resistentie uit van de klassieke setting (waarbij een tegenstander een korte klassieke output verkrijgt, bijvoorbeeld één bit, van elk aandeel) naar de kwantumsetting. In dit model ontvangt het apparaat van elke partij een klassiek aandeel en geeft een enkele qubit (of een klein aantal qubits) af aan een tegenstander die gezamenlijke metingen kan uitvoeren. De studie onderzoekt verder hoe vooraf gedeelde verstrengeling (pre-shared entanglement) tussen lekkage-apparaten, of tussen apparaten en de tegenstander, de veiligheid beïnvloedt.

Methodologie

Het artikel maakt gebruik van een combinatie van eindveld Fourier-analyse en eigenschappen van Maximum Distance Separable (MDS) codes om het onderscheidend vermogen tussen twee geheime toestanden te begrenzen.

Pauli-Fourier Reductie:
- De lekkage van elk aandeel wordt gemodelleerd als een dichtheidsmatrix $\rho_i(y_i)$ . De auteurs breiden deze uit in de Pauli-basis: $\rho_i(y) = \frac{1}{2}(I + r_{i,X}(y)X + r_{i,Y}(y)Y + r_{i,Z}(y)Z)$ .
- Ze definiëren een "Fourier-budget" $W_i(a)$ gebaseerd op de gekwadrateerde magnitudes van de Fourier-coëfficiënten van de Pauli-coëfficiëntfuncties.
- Met behulp van de Parseval-identiteit en de orthogonaliteit van Pauli-operatoren wordt het onderscheidend voordeel begrensd door een som over de duale Shamir-code $C^\perp_0$ :
  $\text{Adv} \leq \sum_{a \in C^\perp_0 \setminus \{0\}} \prod_{i=1}^n \sqrt{W_i(a_i)}$
- Dit reduceert het kwantumbeveiligingsprobleem tot het beheersen van een gewogen som over de duale code, vergelijkbaar met klassieke lekkagebewijzen, maar complexer door de matrix-waardige aard van de coëfficiënten.
Omgaan met Verstrengeling en Blokken:
- Disjuncte Blokken: Voor apparaten die verstrengeling delen binnen disjuncte blokken (maar niet tussen blokken of met de tegenstander), passen de auteurs een block MDS Brascamp-Lieb ongelijkheid toe. Hiermee kunnen ze de som van producten van sporenormen van Fourier-coëfficiënten voor blokoutputs begrenzen.
- Verstrengeling met Tegenstander: Voor een verzameling apparaten $E$ die willekeurige verstrengeling delen met de tegenstander, gebruiken de auteurs een reductie-argument. Ze tonen aan dat als de tegenstander de klassieke aandelen van $E$ leert, de veiligheid van het resterende systeem reduceert tot een onverstrengeld Shamir-schema met $n-r$ partijen en drempel $t-r$ .
Negatieve Resultaten (Aanvallen):
- Het artikel construeert een specifieke aanval met behulp van een GHZ-toestand die gedeeld wordt door $t$ apparaten. Door faseverschuivingen toe te passen die afhankelijk zijn van hun aandelen en te meten in de Pauli-X basis, kunnen de apparaten tussen geheimen onderscheiden met een hoog voordeel, zelfs als ze slechts één klassieke bit per stuk outputten.

Belangrijkste Bijdragen en Resultaten

1. Onverstrengelde Kwantumlekkage

De auteurs bewijzen dat Shamir secret sharing veilig is tegen onverstrengelde lokale één-qubit lekkage, mits de drempel-rate $\tau = t/n$ een specifieke constante $\tau^\star \approx 0.73339$ overschrijdt.

Resultaat: Als $\tau > \tau^\star + \eta$ (voor een vaste $\eta > 0$ ), is het onderscheidend voordeel exponentieel klein ( $2^{-\Omega(n)}$ ).
Techniek: Dit is afgeleid van de block MDS Brascamp-Lieb ongelijkheid met blokgrootte $b=1$ .

2. Disjuncte Verstrengelde Blokken

Veiligheid wordt uitgebreid naar scenario's waarin apparaten zijn verdeeld in disjuncte blokken met een vaste maximale grootte $b$ , waarbij apparaten binnen een blok verstrengeling kunnen delen en gezamenlijke berekeningen kunnen uitvoeren, maar blokken onafhankelijk zijn van elkaar en van de tegenstander.

Resultaat: Veiligheid houdt stand bij voldoende hoge drempel-rates $\tau > \tau^\star(b)$ , waarbij $\tau^\star(b) < 1$ . Naarmate de blokgrootte $b$ toeneemt, nadert de vereiste drempel-rate 1.
Specifieke details: Tabel 1 in het artikel vermeldt voldoende drempels voor gelijke blokgroottes (bijv. voor $b=2$ , $\tau \approx 0.933$ ; voor $b=3$ , $\tau \approx 0.987$ ).

3. Lekkage met Verstrengeling van de Tegenstander

Het artikel analyseert het geval waarbij een lineair aantal apparaten ( $r = \delta n$ ) willekeurige verstrengeling delen met elkaar en met de tegenstander.

Resultaat: Veiligheid houdt stand als de "resterende" rate voldoet aan:
$\frac{\tau - \delta}{1 - \delta} > \tau^\star$
Dit impliceert dat voor een vaste drempel-rate $\tau > \tau^\star$ , veiligheid behouden blijft zelfs als een lineair deel van de apparaten ( $\delta < \frac{\tau - \tau^\star}{1 - \tau^\star}$ ) verstrengeling deelt met de tegenstander.

4. Negatief Resultaat: GHZ-aanval

De auteurs demonstreren dat als $t$ apparaten een GHZ-toestand delen, het schema onveilig wordt, zelfs onder klassieke single-bit lekkage.

Mechanisme: $t$ apparaten delen een GHZ-toestand. Elk past een fase toe op basis van hun aandeel en meet in de X-basis. Het product van de uitkomsten onthult het geheim met een voordeel van $\cos^2(\pi/(2p)) \approx 1 - O(p^{-2})$ .
Implicatie: Deze aanval vereist geen verstrengeling met de tegenstander, alleen onder de $t$ lekkage-apparaten zelf. Het stelt vast dat het maximale aantal apparaten dat willekeurige verstrengeling kan delen terwijl de veiligheid behouden blijft, lineair is in $n$ (tot constante factoren), maar de optimale fractie blijft een open vraag.

Betekenis en Claims

Het artikel claimt de studie te initiëren van de kwantumlekkage-resistentie voor het breed gebruikte, ongewijzigde Shamir secret sharing schema.

Robuustheid van Standaard Schema's: De resultaten laten zien dat het standaard Shamir-schema sterke veiligheidsgaranties behoudt tegen kwantumlekkage zonder dat nieuwe deelalgoritmen of protocolwijzigingen nodig zijn, mits de drempel-rate voldoende hoog is (boven $\approx 0.733$ ).
Rol van Verstrengeling: Het werk benadrukt een cruciaal onderscheid: terwijl onverstrengelde kwantumlekkage beheersbaar is met hoge drempels, kan de aanwezigheid van willekeurige verstrengeling tussen lekkage-apparaten (specifiek een GHZ-toestand onder $t$ apparaten) de veiligheid breken, zelfs bij klassieke outputs.
Optimaliteit: De auteurs zijn bescheiden over de optimaliteit van hun grenzen. Ze merken op dat de voldoende drempel $\tau^\star \approx 0.733$ hoger is dan de bekende klassieke grens ( $\approx 0.668$ ) en stellen de vraag of dit gat gedicht kan worden. Ook het exacte optimale deel van verstrengelde apparaten dat compatibel is met veiligheid, wordt als een open probleem gelaten.

Het artikel concludeert dat kwantumlekkage-resistentie fundamenteel afhangt van zowel de omvang van de gelekte outputs als de verstrengelingsstructuur die beschikbaar is voor de lekkage-apparaten.