Secret sharing with additive access structures from correlated random variables

Technische Samenvatting: Secret Sharing met Additieve Accessstructuren vanuit Gecorreleerde Random Variabelen

Probleemstelling
Het artikel behandelt het probleem van secret sharing in een dynamische omgeving waarin de verzameling geautoriseerde deelnemers (de accessstructuur) in de loop van de tijd evolueert. Traditionele secret sharing-modellen gaan doorgaans uit van een vaste accessstructuur; als de structuur verandert, moeten de shares opnieuw worden verdeeld, wat leidt tot inefficiëntie. Hoewel het "Evolving Access Structure" (EAS)-model toestaat dat de structuur monotoon groeit, gaat dit model ervan uit dat deelnemers sequentieel toetreden en shares ontvangen via privékanalen.

Dit werk introduceert het Additive Access Structure (AAS)-model, dat op twee fundamentele punten verschilt van EAS:

1. Simultane Initialisatie: Alle deelnemers zijn vanaf het begin aanwezig.
2. Gecorreleerde Bron van Randomness: Shares worden gelijktijdig gegenereerd vanuit een gecorreleerde bron van randomness (bijv. kanaalversterkingsmetingen in draadloze netwerken) in plaats van te worden verdeeld via privékanalen.
3. Publieke Communicatie: De dealer communiceert met deelnemers via een publiek, ruisloos, geauthenticeerd kanaal. De dealer leert over veranderingen aan de accessstructuur (nieuwe geautoriseerde groepen) pas op het moment dat deze zich voordoen, en moet de secret sharing-strategie iteratief aanpassen.

Het doel is om een secret sharing-strategie te bepalen die ervoor zorgt dat geautoriseerde groepen een geheim met een hoge betrouwbaarheid kunnen herstellen, terwijl ongeautoriseerde groepen een verwaarloosbare hoeveelheid informatie verkrijgen, terwijl tegelijkertijd de secret rate (de grootte van het gedeelde geheim genormaliseerd door het aantal bronobservaties) wordt gemaximaliseerd.

Methodologie
De auteurs stellen een secret sharing-strategie voor die gebaseerd is op random binning, aangepast voor een dynamische setting. De kern van de methodologie omvat:

• Gekwantiseerde Random Binning: De dealer observeert een sequentie $Y^n$ van een gecorreleerde bron $(Y, X_L)$. Voor elk tijdstip $t$ maken de dealer en de deelnemers gebruik van vooraf bepaalde random binning-functies ($g_i$ en $h_j$) die bronsequenties naar indices mappen.
• Iteratieve Encodering: Op elk tijdstip $t$ bepaalt de dealer het aantal binning indices ($k_t$) dat in het publieke bericht wordt opgenomen en het aantal indices ($\sigma_t$) dat als geheim wordt aangemerkt. Deze aantallen worden gekozen op basis van de huidige geautoriseerde verzameling $A_t$ en de ongeautoriseerde verzameling $U_t$.
• A Priori Strategie Specificatie: Een nieuw aspect van het bewijs is de introductie van een gekwantiseerd aantal binnings. Dit maakt de constructie van een enkele secret sharing-strategie mogelijk die volledig a priori is gespecificeerd. Cruciaal is dat deze strategie niet afhankelijk is van kennis over hoe de AAS in toekomstige tijdstappen zal evolueren; de dealer hoeft alleen de huidige accessstructuur te kennen om het bericht en het geheim voor dat specifieke tijdstip te bepalen.
• Decoding: Geautoriseerde deelnemers gebruiken hun lokale observaties ($X^n_A$), de geaccumuleerde publieke berichten en de binning-functies om de unieke bronsequentie te identificeren die consistent is met de typiciteitseisen en de ontvangen bin indices.

Belangrijkste Bijdragen en Resultaten
Het artikel stelt de volgende theoretische resultaten vast:

1. Bereikbaarheid van Fixed-Structure Rates: De auteurs bewijzen dat er een strategie bestaat voor het AAS-model waarbij de bereikbare secret rate op elk tijdstip $t$ onafhankelijk is van de accessstructuren op alle andere tijdstippen. Specifiek komt de bereikbare rate $R_t$ overeen met de best bekende bereikbare rate voor een vast model met een vaste structuur:
   $$R_t = \min_{U \in U_t} H(Y | X_U) - \max_{A \in A_t} H(Y | X_A)$$
   Dit resultaat impliceert dat de dynamische aard van de accessstructuur de secret rate niet inherent verslechtert ten opzichte van een statisch scenario.

2. Capaciteit voor Threshold Access Structures: Het artikel bewijst dat wanneer de accessstructuur op een gegeven tijdstip een Threshold Access Structure vormt (waarbij elke groep van omvang $\ge f_1(t)$ geautoriseerd is en elke groep van omvang $\le f_2(t)$ ongeautoriseerd is), de voorgestelde strategie de capaciteit bereikt. Voor een specifiek geval waarbij de dealer onafhankelijke private keys met deelnemers deelt, wordt de capaciteit als volgt weergegeven:
   $$R_t = H(X)(f_1(t) - f_2(t))$$

3. Omniscience vs. Causality: Een belangrijke bevinding is dat voor het drempelwaarde (threshold) AAS-geval, een dealer die alwetend (omniscient) is (de volledige toekomstige sequentie van accessstructuren kent) geen voordeel behaalt ten opzichte van een causale dealer (die alleen de huidige structuur kent) wat betreft de bereikbare secret rates.

Betekenis en Claims
Het artikel beweert secret sharing-modellen die steunen op gecorreleerde randomness te generaliseren van vaste naar dynamische additieve accessstructuren. De primaire betekenis ligt in het aantonen dat dynamische aanpasbaarheid niet ten koste gaat van de efficiëntie van de secret rate. De auteurs laten zien dat men dezelfde prestatiegrenzen kan bereiken als de beste statische strategieën zonder voorafgaande kennis te vereisen over de evolutie van het systeem.

Het werk benadrukt dat het "verrassende" resultaat de onafhankelijkheid is van de bereikbare rate op tijdstip $t$ van de geschiedenis of de toekomst van de accessstructuur. Hoewel het artikel een niet-constructief existentiebewijs biedt voor het algemene AAS-geval (door gebruik te maken van de probabilistische methode om de existentie van geschikte binning-functies aan te tonen), merkt het expliciet op dat het leveren van een constructief bereikbaarheidsbewijs voor het algemene AAS een openstaand probleem blijft, wat het onderscheidt van bestaande constructieve bewijzen voor vaste structuren.

Het artikel concludeert dat voor drempelwaarde-gebaseerde dynamische structuren de capaciteit volledig is gekarakteriseerd, en dat het gebrek aan vooruitziendheid met betrekking tot toekomstige veranderingen in de accessstructuur de prestaties van het systeem niet benadeelt.