Technische Samenvatting: Exacte Bias van Lineaire TRNG-Correctoren: Spectrale Aanpak

Probleemstelling

Willekeurige getallengeneratoren (TRNG's) halen entropie uit fysieke verschijnselen, maar hun ruwe uitvoer vertoont vaak statistische onvolkomenheden, zoals bias en correlaties, die cryptografische vereisten schenden. Hoewel willekeurigheidsextractoren een theoretisch kader bieden voor het corrigeren van deze onvolkomenheden, geven hardware-implementaties de voorkeur aan eenvoudigere constructies. Lineaire correctoren, gedefinieerd door de operatie $Y = GX$ (waarbij $G$ een binaire matrix is, $X$ de ruwe invoer en $Y$ de gecorrigeerde uitvoer), worden in de praktijk veel gebruikt vanwege hun uitsluitende afhankelijkheid van XOR-poorten.

Bestaande veiligheidsanalyses voor deze lineaire correctoren vertrouwen echter vaak op $\ell_\infty$-grenzen of eenvoudige sommaties van individuele invoer-biases. De auteurs betogen dat deze technieken frequent veiligheidsinschattingen opleveren die te conservatief zijn en ver verwijderd liggen van de ware totale variatie-afstand (de $\ell_1$-norm) tussen de uitvoerverdeling en de uniforme verdeling. Deze kloof leidt tot onnauwkeurige veiligheidsbeoordelingen, wat mogelijk onnodige offers in coderingssnelheid (compressie-efficiëntie) of hardware-complexiteit tot gevolg heeft.

Methodologie

Het artikel hanteert een Fourier-analytische aanpak om de uitvoerverdeling van lineaire correctoren te karakteriseren onder het model van een bevooroordeelde munt, waarbij invoerbits onafhankelijk maar bevooroordeeld zijn.

1. Fourier-ontwikkeling: De auteurs maken gebruik van de Fourier-ontwikkeling van functies op de booleaanse kubus. Door de kansmassafunctie van de uitvoer $Y$ uit te drukken in termen van de Fourier-coëfficiënten, relateren zij de verdeling aan de gewichtenteller van de lineaire code gegenereerd door de matrix $G$.
2. Normkarakterisering:
   • $\ell_\infty$-norm: Zij leiden een exacte formule af voor de maximale kans van elke uitvoer, waarmee de effectiviteit van de corrector als een min-entropiecondensor wordt gekarakteriseerd. Dit wordt uitgedrukt als een functie van de gewichtentellerpolynoom van de code, $W_G(\delta)$.
   • $\ell_2$-norm: Met behulp van de stelling van Plancherel stellen zij een exacte karakterisering vast van de gekwadrateerde $\ell_2$-afstand tot uniformiteit. Dit heeft betrekking op Rényi-entropie en onderscheidbaarheid in encryptiecontexten.
   • $\ell_1$-norm (Totale Variatie): Door te interpoleren tussen de afgeleide $\ell_\infty$- en $\ell_2$-grenzen, construeren de auteurs bijna strakke boven- en ondergrenzen voor de totale variatie-afstand.
3. Codetheoretisch Kader: De analyse veronderstelt dat de invoerbits $X_i$ onafhankelijk zijn met bias $\delta_i = 1 - 2p_i$. De resultaten worden compact uitgedrukt met behulp van de gewichtentellerpolynoom $W_G(x) = \sum A_w x^w$, waarbij $A_w$ het aantal codewoorden met Hamming-gewicht $w$ is.

Belangrijkste Bijdragen

1. Exacte Fourier-analytische Karakterisering

Het artikel biedt de eerste exacte formules voor de $\ell_\infty$- en $\ell_2$-afstanden tot uniformiteit voor lineaire correctoren, direct uitgedrukt via gewichtentellers van codes. Dit breidt eerder werk uit dat vaak leunde op losse grenzen of specifieke aannames over invoerverdelingen.

2. Bijna Strakke $\ell_1$-Grenzen via Interpolatie

De belangrijkste theoretische bijdrage is de afleiding van grenzen voor de totale variatie-afstand ($\ell_1$-norm) die aanzienlijk scherper zijn dan eerdere schattingen. Voor een code met gewichtenteller $W_G$ en invoerbias $\delta$ wordt de totale variatie-afstand begrensd door:
$$\frac{W_G(\delta^2) - 1}{W_G(\delta) - 1} \leq \|P_Y - P_{U_k}\|_1 \leq \sqrt{W_G(\delta^2) - 1}$$
Deze grenzen verbeteren eerdere op $\ell_\infty$ gebaseerde schattingen met een orde van grootte voor praktisch interessante veiligheidsniveaus.

3. Empirische Evaluatie van Trade-offs

De auteurs voerden een grootschalige empirische studie uit over ongeveer 20.000 lineaire codes (waaronder Reed-Muller, BCH en cyclische codes). Zij kwantificeerden de fundamentele trade-offs tussen:

• Compressie-efficiëntie (Coderingssnelheid): De verhouding $k/n$.
• Cryptografische Veiligheid: Het niveau van biasreductie.
• Hardware-complexiteit: Geschat in Poort-equivalenten (GE).

Resultaten

Veiligheidsgrenzen en Strakheid

• Regime met Kleine Bias: Voor kleine invoerbias $\delta \ll 1$ neemt de totale variatie-afstand af als $\Theta(\delta^d)$, waarbij $d$ de minimale afstand van de code is. Dit staat in contrast met eerdere op $\ell_\infty$ gebaseerde grenzen die vaak een afhankelijkheid suggereerden van $\sqrt{\delta}$ of minder gunstige schaling.
• Omvang van Verbetering: Vergelijkingen met Reed-Muller- en BCH-codes tonen aan dat de nieuwe grenzen strikt strakkere veiligheidsbeoordelingen opleveren, vaak met een verbetering van de schattingen met een factor dicht bij een orde van grootte binnen praktische parameterbereiken.
• Strakheid: Voor "goede" codes (die met ongeveer binomiale gewichtsverdelingen), is de kloof tussen de afgeleide onder- en bovengrenzen klein, waardoor $\sqrt{W_G(\delta^2) - 1}$ een betrouwbare proxy wordt voor de exacte totale variatie-afstand.

Trade-offs tussen Snelheid, Veiligheid en Kosten

• Veiligheidskosten: Het bereiken van hoge veiligheid (bijvoorbeeld 80-bit veiligheid) met aanzienlijke invoerbias (bijvoorbeeld 10%) vereist doorgaans het offeren van meer dan 50% van de coderingssnelheid.
• Hardwarekosten: Hogere veiligheidsniveaus correleren over het algemeen met verhoogde hardwarekosten (gemeten in Poort-equivalenten).
• Pareto-grens: De studie benadrukt dat cyclische codes vaak op de Pareto-grens liggen, waardoor zij een gunstige balans bieden tussen implementatiekosten, veiligheid en snelheid.

Betekenis en Beweringen

Het artikel beweert bijna optimale veiligheidsgrenzen te vestigen voor lineaire TRNG-correctoren, en gaat voorbij aan de te conservatieve schattingen die historisch het veld hebben gedomineerd. Door de analyse te verschuiven naar een spectrale (Fourier) invalshoek, tonen de auteurs aan dat de afhankelijkheid van de totale variatie-afstand van de invoerbias evenredig is met de volledige term van de minimale afstand van de code, en niet met de vierkantswortel daarvan.

Dit werk biedt een verenigd codetheoretisch kader dat nauwkeurige veiligheidsbeoordelingen mogelijk maakt. Het kwantificeert de inherente kosten van willekeurigheidsextractie in hardware, en toont aan dat het bereiken van hoge veiligheid met bevooroordeelde invoer substantiële reducties in doorvoer (coderingssnelheid) en toename van hardware-complexiteit vereist. De auteurs merken op dat hun broncode beschikbaar is voor reproduceerbaarheid en suggereren dat toekomstig werk deze resultaten kan uitbreiden naar andere code-families, zoals polaire codes, en specifieke hardware-beperkingen zoals oppervlakte en vermogen kan integreren.