💻 computer science

Hardware-Friendly Randomization: Enabling Random-Access and Minimal Wiring in FHE Accelerators with Low Total Cost

Dit paper presenteert een hardware-vriendelijke randomisatie-methode voor FHE-versnellers die de communicatie-overhead vermindert en complexe bedrading elimineert door polynomen $a$ on-the-fly te genereren vanuit een kleine seed, waardoor aanzienlijke energiebesparingen worden behaald zonder de prestaties of flexibiliteit te beïnvloeden.

Oorspronkelijke auteurs: Ilan Rosenfeld, Noam Kleinburd, Hillel Chapman, Dror Reuven

Gepubliceerd 2026-02-24

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Ilan Rosenfeld, Noam Kleinburd, Hillel Chapman, Dror Reuven

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

🏗️ De Grote Uitdaging: Een Telefoongesprek met een Berg Papier

Stel je voor dat je een geheime boodschap wilt sturen naar een supercomputer (de server) die berekeningen voor je moet doen, zonder dat de computer ooit mag weten wat er in die boodschap staat. Dit heet Fully Homomorphic Encryption (FHE).

Om dit veilig te maken, sturen jullie een enorm pakketje mee. Dit pakketje bevat twee grote delen:

Een geheime sleutel (die alleen jij hebt).
Een openbaar deel (een willekeurig getal, genaamd $\mathbf{a}$ ) dat iedereen mag zien.

Het probleem:
Dit openbare deel ( $\mathbf{a}$ ) is gigantisch groot. Het is alsof je elke keer dat je een e-mail stuurt, een hele lading met 100.000 pagina's aan willekeurige krabbels meesturen. Voor de server is het een nachtmerrie: het kost enorm veel tijd om die lading te ontvangen, op te slaan en te verwerken.

De slimme oplossing (tot nu toe):
In plaats van die hele lading te sturen, stuur je alleen een kleine sleutel (een 'zaadje' of seed). De server gebruikt dit zaadje om de lading met krabbels zelf te 'groeien' (reconstrueren). Dit bespaart veel ruimte op de postbus.

Maar... er zit een addertje onder het gras:
De manier waarop de server die lading 'groeit', is erg inefficiënt voor de hardware.

De 'Centrale Keuken' (Wiring): Stel je voor dat er één centrale keuken is waar alle krabbels worden gemaakt, en die moeten dan via lange, dure leidingen naar 10.000 koks (de rekenmodules) worden gebracht. Dit kost enorm veel energie en ruimte in de chip.
De 'Wachtrij' (Serialiteit): De huidige methode werkt als een fabrieksband. Je moet eerst krabbels 1, 2 en 3 maken voordat je krabbels 100 mag maken. Als de server krabbels 100 nodig heeft, moet hij wachten tot de band die eerst heeft afgeleverd.
De 'Gokpartij' (Rejection Sampling): Soms is een getal niet goed genoeg en moet het worden weggegooid en opnieuw gemaakt. Dit maakt het onvoorspelbaar hoe lang het duurt, wat de planning van de server verstoort.

💡 De Oplossing: Een Decentrale 'Tuin'

Het paper van Chain Reaction Ltd. stelt een nieuwe manier voor om dit op te lossen. Ze noemen het "Hardware-Friendly Randomization".

Hier is hoe het werkt, vertaald naar alledaagse beelden:

1. Van Centrale Keuken naar Eigen Tuinen (Distributed PRNG)

In plaats van één grote centrale keuken, geeft de ontwerper elke kok (rekenmodule) zijn eigen kleine tuin met zaadjes.

Hoe het werkt: Iedere kok krijgt een klein stukje van het zaadje en een unieke instructie (bijvoorbeeld: "Maak krabbels voor de rode sectie").
Het voordeel: De kok maakt zijn eigen krabbels direct naast zijn werkplek. Er hoeven geen lange, dure leidingen meer te worden aangelegd om data van A naar B te slepen.
Resultaat: Minder energie, minder warmte en minder ruimte nodig voor de "kabels" in de chip. Het is alsof je in plaats van één grote waterleiding naar elke kraan in het huis, bij elke kraan een eigen kleine pomp zet.

2. Willekeurige Toegang (Random Access)

Vroeger moest je wachten tot de fabrieksband alles had geproduceerd. Nu kun je direct naar de specifieke krabbel springen die je nodig hebt.

Metafoor: Stel je een bibliotheek voor. Vroeger moest je wachten tot de bibliothecaris alle boeken van A tot Z had uitgezocht voordat hij boek #5000 aan je gaf. Nu kun je gewoon naar de plank lopen en direct boek #5000 pakken, omdat elke schap zijn eigen 'zaadje' heeft om die specifieke boeken te genereren.
Resultaat: De server kan berekeningen veel flexibeler plannen zonder te hoeven wachten.

3. Voorspelbare Planning (Deterministisch)

De huidige methode heeft soms "gokmomenten" waarbij getallen worden weggegooid, wat de tijd onvoorspelbaar maakt.

De nieuwe methode: De auteurs hebben een slimme manier bedacht om te garanderen dat de server altijd precies genoeg krabbels krijgt, zonder dat er onnodige gokmomenten zijn.
Resultaat: De server weet precies hoe lang een taak duurt. Geen verrassingen, geen wachttijden.

📉 Waarom is dit belangrijk? (De Kostenbesparing)

De auteurs rekenen dit uit voor een echte chip:

Stroom: Door de lange leidingen (wiring) te verwijderen, besparen ze tientallen Watts aan stroom per chip. Dat is als het uitschakelen van tientallen gloeilampen in een datacenter.
Snelheid: Omdat de data niet hoeft te reizen over de hele chip, gaat alles sneller.
Klantkant: Voor de gebruiker (de klant) is het bijna niets extra's (minder dan 3% meer werk), maar voor de server is het een enorme winst.

🎯 Conclusie in één zin

Dit paper stelt voor om de enorme hoeveelheid willekeurige data die nodig is voor veilige versleutelde berekeningen niet meer centraal te produceren en te vervoeren, maar lokaal en parallel te laten 'groeien' bij elke rekenmodule. Dit bespaart enorm veel stroom, ruimte en tijd, waardoor versleutelde cloud-diensten sneller en goedkoper worden.

Het is alsof je van een systeem overstapt waar één persoon 1000 brieven schrijft en ze allemaal moet uitdelen, naar een systeem waar 1000 mensen elk hun eigen brief schrijven en direct op hun eigen bureau neerleggen.

Titel

Hardware-Vriendelijke Randomisatie: Mogelijkmaking van Random-Access en Minimale Bedrading in FHE-versnellers met Lage Totale Kosten.

1. Het Probleem

Volledige Homomorfische Versleuteling (FHE) staat bekend om zijn rekenintensieve aard, waarbij hardware-versnellers (ASIC's) essentieel zijn voor praktische toepassing. Een cruciaal onderdeel van RLWE-gebaseerde FHE-schema's (zoals CKKS, BFV, BGV) is het gebruik van uniform verdeelde polynomen $\mathbf{a}$ in de publieke sleutels en ciphertexts.

De huidige uitdagingen zijn:

Communicatie- en geheugenoverhead: Het verzenden van grote polynomen (vaak megabytes tot gigabytes) van client naar server is inefficiënt. Hoewel een "seeded" aanpak (waarbij de server $\mathbf{a}$ genereert uit een kleine seed) de communicatie halveert, introduceert dit hardware-uitdagingen.
Hardware-architectuur beperkingen: Traditionele ASIC-ontwerpen gebruiken vaak een centrale PRNG-eenheid (Pseudo-Random Number Generator) die de data naar alle parallelle rekenresources stuurt. Dit vereist enorme interne bedrading (wiring) over grote afstanden op de chip, wat leidt tot:
- Hoge energieverbruik (tot tientallen Watts).
- Beperkingen in metaallagen (dichte bedrading is fysiek moeilijk).
- Hoge latency door lange signalen.
Schedulingsproblemen: Gebruikelijke hash-functies (XOF) werken serieel. Om het $k$ -de element te genereren, moeten alle voorgaande $0$ tot $k-1$ eerst worden gegenereerd. Dit beperkt de flexibiliteit van de hardware om willekeurig toegang te krijgen tot specifieke delen (limbs) van een polynoom, wat nodig is voor efficiënte scheduling.
Niet-deterministische latentie: Rejection sampling (nodig voor uniforme verdeling) kan variëren in het aantal benodigde hash-uitvoerbits, wat complexe flow-control en stalling in de hardware vereist.

2. Methodologie

De auteurs stellen een nieuwe architectuur en algoritmen voor die de PRNG-functie gedistribueerd implementeren in plaats van centraal.

Gedistribueerde PRNG: In plaats van één centrale generator, wordt de taak opgesplitst in segmenten. Een polynoom van dimensie $N$ wordt verdeeld in $n_{seg}$ segmenten. Elke segment wordt gegenereerd door een lokaal PRNG-motor die fysiek naast de bijbehorende rekenresources (bijv. modulaire multipliers) is geplaatst.
Domein-separatie: Om te voorkomen dat verschillende segmenten of RNS-limbs (Residue Number System) dezelfde output genereren, wordt de input voor de hash-functie verrijkt met:
- De gemeenschappelijke seed.
- De modulus $q$ (voor specifieke RNS-limbs).
- Een segment-ID ( $id_{seg}$ ).
- Formule: input = seed || q || id_seg.
Random Access: Door de domein-separatie kan de hardware direct een specifiek segment genereren zonder de voorgaande segmenten te hoeven berekenen. Dit elimineert de seriële afhankelijkheid van traditionele XOF-functies.
Deterministische Schedulering: De auteurs beperken het ondersteunde setje van priemmoduli ( $S(q)$ ) tot die welke een lage kans op afwijzing (rejection probability) garanderen bij rejection sampling. Hierdoor kan de client vooraf controleren of een seed succesvol zal zijn, waardoor de server altijd gegarandeerd succesvolle generatie heeft zonder wachttijden of "bubbles" in de pipeline.
Algoritmen:
- Algorithm 1: Genereert een multi-residue polynoom (MRP) door segmenten onafhankelijk te genereren en te permuteren.
- Algorithm 2: De kern van de segmentgeneratie via hashing en rejection sampling binnen een vaste bit-breedte.

3. Belangrijkste Bijdragen

Eliminatie van zware bedrading: Door lokale PRNG-eenheden te plaatsen naast de rekenresources, wordt de behoefte aan lange, energie-intensieve metalen lagen voor data-distributie verwijderd.
Random Access tot RNS-limbs: De architectuur maakt directe toegang mogelijk tot specifieke RNS-limbs (modulo's) zonder eerst de volledige polynoom te genereren of op te slaan. Dit is cruciaal voor operaties zoals Key-Switching waarbij alleen specifieke limbs nodig zijn.
Deterministische Latentie: Door het beperken van de moduli-set en het verplaatsen van de validatie naar de client, wordt de server-versneller vrijgesteld van complexe flow-control voor rejection sampling.
Lage Client-overhead: De extra berekeningen aan de client-kant (voor het vinden van een geldige seed) zijn minimaal (< 3% extra tijd tijdens sleutelgeneratie).

4. Resultaten en Evaluatie

De auteurs presenteren een concreet voorbeeld met de volgende parameters:

Hardware: Een ASIC met 16.384 parallelle multipliers (32-bit), werkend op 1 GHz.
Vergelijking:
- Centrale aanpak: Vereist gemiddeld 7,5 mm bedrading per bit. Bij een bandbreedte van 65,5 Tbps resulteert dit in een vermogensverbruik van ~19,7 Watt alleen voor de bedrading.
- Gedistribueerde aanpak: Elimineert dit vermogensverbruik voor de bedrading. De lokale bedrading is kort en kan fijnere metalen lagen gebruiken.
Statistieken: Met een hash-uitvoer van 1344 bits (SHAKE128/KangarooTwelve) en een segmentgrootte ($len$) van 32, kan een set van geschikte moduli worden gevonden waarbij de kans op mislukte generatie (MRP rejection) lager is dan 3%.
Zekerheid: De seed-lengte van 288 bits (met een unieke 32-bit component per polynoom) biedt voldoende cryptografische veiligheid, zelfs na het filteren van slechte seeds.

5. Betekenis en Conclusie

Dit paper biedt een praktische oplossing voor een van de grootste engineering-hindernissen in de schaalbaarheid van FHE-hardware.

Energie-efficiëntie: Het bespaart tientallen Watts per chip in high-throughput configuraties, wat essentieel is voor datacenters.
Schaalbaarheid: Het maakt het mogelijk om FHE-versnellers te schalen naar hogere parallelle capaciteiten zonder dat de bedrading en het vermogensverbruik prohibitief worden.
Ecosysteem: Door de scheiding van verantwoordelijkheden (client valideert seeds, server genereert deterministisch) wordt de integratie met bestaande FHE-compiler en bibliotheken (zoals OpenFHE) vergemakkelijkt.

De voorgestelde methode stelt de industrie in staat om grootschalige, versleutelde toepassingen uit te voeren met een aanzienlijk lagere hardware- en energiekost, wat een belangrijke stap is naar de bredere adoptie van Fully Homomorphic Encryption.