💻 computer science

Rotation-Optimal Noncommutative Prefix Scans in Bit-Reversed Homomorphic Layouts

Dit artikel introduceert een rotatie-optimaal prefix scan-algoritme voor bit-reversed homomorfe encryptie-layouts dat de rotatiecomplexiteit vermindert van $O(m^2)$ naar $O(m)$ door gebruik te maken van een gerepliceerd-geaggregeerd invariant, waardoor de computationele latentie, het geheugengebruik en de opslag van evaluatiesleutels aanzienlijk worden verlaagd en diepere downstream-pipelines mogelijk worden gemaakt.

Oorspronkelijke auteurs: Anis Bkakria, Madicke-Diadji Mbodj, Mawloud Omar, Reda Yaich

Gepubliceerd 2026-07-07

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Anis Bkakria, Madicke-Diadji Mbodj, Mawloud Omar, Reda Yaich

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 gigantische, versleutelde spreadsheet hebt waar elke cel een geheim getal bevat. Je wilt op alle deze getallen tegelijk een specifieke wiskundige truc uitvoeren: voor elke cel moet je de "lopende totaal" weten van alle getallen die eraan voorafgingen. In de wereld van Homomorfe Encryptie (rekenen op geheime gegevens zonder ze ooit te ontsleutelen), wordt dit een "prefix scan" genoemd.

Het probleem is dat de gegevens niet netjes in een rij zijn opgeslagen zoals 1, 2, 3, 4. Vanwege de manier waarop de encryptie werkt, zijn de gegevens gescrorambled in een specifiek patroon genaamd "bit-reversed order". Het is alsof een boek waarbij de pagina's door elkaar zijn gehusseld: pagina 1 wordt gevolgd door pagina 8, dan pagina 4, dan pagina 12, enzovoort.

De Oude Manier: Het "Exacte Buur"-Probleem

Om het lopende totaal te berekenen, moet je meestal vragen aan je buurman wat zijn getal is. In een normale rij is je buurman slechts één stap verwijderd. Maar in dit gescrambelde "bit-reversed" boek, kan je logische buurman zich aan de andere kant van de kamer bevinden.

De oude methode probeerde dit op te lossen door een boodschapper (een "rotatie") te sturen om de exacte specifieke buur op te halen die je nodig had.

De Analogie: Stel je voor dat je in een bibliotheek staat met 8 planken. Je moet praten met de persoon op de plank direct links van jou. Maar omdat de planken gescrambled zijn, betekent "links" verschillende fysieke afstanden voor verschillende mensen.
De Kosten: Om iedereen hun juiste buur te laten krijgen, moest de bibliothecaris boodschappers op veel verschillende routes sturen. Voor een klein boek van 8 pagina's waren er 6 boodschappers nodig. Voor een groter boek groeide dit exponentieel (het groeide als een driehoek: 1+2+3+4...). Dit was traag, duur en vereiste een enorme bibliotheek aan "sleutels" (toestemmingsbriefjes) om boodschappers naar al die verschillende plekken te sturen.

De Nieuwe Manier: De "Copycat"-Strategie

De auteurs van dit paper realiseerden zich dat ze te kieskeurig waren. Ze hadden niet de exacte buur nodig; ze hadden alleen iemand uit de groep van de buur nodig die dezelfde informatie had.

De Analogie: In plaats van te vragen naar de specifieke persoon aan de linkerkant, stel je voor dat iedereen in een "groep" (een blok planken) een identieke kopie van de totaalscore van de groep vasthoudt.
De Magische Beweging: De auteurs ontdekten een manier om de hele bibliotheek slechts één keer per niveau van de berekening te roteren. Deze enkele rotatie verplaatst iedereen naar een plek waar ze naast iemand staan uit de aangrenzende groep. Omdat iedereen in die groep een kopie van de "groepstotaal" vasthoudt, maakt het niet uit welke specifieke persoon je krijgt; de wiskunde werkt perfect uit.
Het Resultaat: In plaats van 6 boodschappers voor 8 pagina's, heb je slechts 1 boodschapper per niveau nodig. Voor het hele boek ga je van een aantal boodschappers dat als een driehoeksgetal groeit (zoals 28) naar simpelweg het aantal niveaus (zoals 7).

Wat Ze Eigenlijk Bewezen Hebben

Het paper zegt niet alleen "dit is sneller". Ze hebben drie harde wiskundige feiten bewezen:

Je kunt het niet beter doen: Ze bewezen dat hoe slim je ook bent, je minstens zo veel rotaties moet gebruiken als er niveaus in de berekening zitten. Je kunt de boodschappers niet volledig overslaan.
De "Perfecte" Route: Ze lieten zien dat als je het minimum aantal boodschappers gebruikt, die boodschappers een zeer specifiek, rigide patroon moeten volgen (gerelateerd aan machten van 2). Er is geen ruimte voor variatie; de wiskunde dwingt dit specifieke pad af.
De Afweging: Om op boodschappers te besparen, moet je iets meer lokale wiskundige arbeid verrichten (twee sets getallen bijhouden in plaats van één). Maar in hun tests was het besparen op de boodschappers de moeite waard.

De Praktijktest (Het "Carry"-Probleem)

Ze testten dit op een zeer gebruikelijk wiskundig probleem: het overdragen van getallen (zoals wanneer je 9 + 3 optelt en je krijgt 12, waarbij je de 1 moet "overdragen" naar de volgende kolom).

De Opzet: Ze versleutelden een lijst met cijfers en probeerden de overdrachten te corrigeren zonder de volgorde te ontscramblen.
De Uitkomst:
- Snelheid: Hun nieuwe methode was ongeveer 20% sneller dan de oude "exacte buur"-methode voor middelgrote problemen.
- Geheugen: Het gebruikte 64% minder geheugen omdat ze niet zoveel toestemmingssleutels hoefden op te slaan.
- De Grote Winst: In een langere keten van berekeningen bespaarde hun methode genoeg "encryptiekracht" om een enorme, trage resetprocedure (genaamd "bootstrapping") te vermijden. Dit maakte het hele proces 4,3 keer sneller van begin tot eind.

Samenvatting

Denk aan een estafette.

Oude Methode: Elke loper moest een uniek, lang en kronkelend pad rennen om zijn specifieke teamgenoot te vinden. Het kostte veel energie en tijd.
Nieuwe Methode: Het team realiseerde zich dat als ze gewoon een korte, gestandaardiseerde lus zouden rennen, iedereen naast een teamgenoot zou eindigen die hetzelfde stokje vasthoudt. Het kostte minder stappen, minder energie en het werk werd sneller gedaan, ook al moesten de lopers een paar extra stokjes vasthouden.

Het paper bewijst dat deze shortcut de absoluut snelste manier is om dit specifieke type wiskunde uit te voeren op gescrambelde, versleutelde gegevens.

Technische Samenvatting: Rotatie-optimale niet-commutatieve prefix-scans in bit-omgekeerde homomorfe lay-outs

Probleemstelling

In gepakte homomorfe encryptie (HE), specifiek het CKKS-schema, maken SIMD-operaties parallelle berekeningen op versleutelde vectoren mogelijk. Echter, communicatie tussen slots vereist cyclische rotaties (Galois-automorfismen), wat kostbare operaties zijn die involveert met key switching. De kosten van een rotatie hangen af van de fysieke lay-out van de data.

Het artikel behandelt het probleem van het uitvoeren van geordende prefix-berekeningen (scans) op $n = 2^m$ elementen van een associatief, mogelijk niet-commutatief monoïde, wanneer de data is opgeslagen in een bit-omgekeerde volgorde (bit-reversed order). Deze lay-out is gebruikelijk bij snelle transformaties en packing-conversies.

De kernuitdaging is dat een standaard "getransporteerde voorganger"-scan, die de afstand naar logische voorgangers recursief verdubbelt, een hoge routingskosten veroorzaakt in een bit-omgekeerde lay-out. Omdat bit-reversal de logische indices permuteert, vervalt een enkele logische verschuiving door $2^t$ in meerdere verschillende cyclische verplaatsingsklassen. Bijgevolg vereist een directe implementatie $R_{direct} = \sum_{t=0}^{m-1} (m-t) = \frac{m(m+1)}{2}$ rotaties. De auteurs onderzoeken of deze driehoekige kosten een inherente eigenschap is van prefix-berekening in bit-omgekeerde lay-outs of een artefact van de specifieke routingtopologie.

Methodologie en Constructie

Het artikel introduceert een gerepliceerd-geaggregeerd invariant om het aantal rotaties van kwadratisch naar lineair te verminderen.

Semantische Replicatie: In plaats van elke slot naar zijn exacte logische voorganger te routeren, behoudt de constructie een staat waarin elke slot binnen een uitgelijnde logische blok het volledige aggregaat van dat blok opslaat.
Sibling-Block Uitwisseling: Op elk niveau $d$ $d$ van de scan (het combineren van blokken van grootte $2^d$ $2^{d}$ ), roteert het algoritme de geaggregeerde staat met een specifieke offset $s_d = 2^{m-d-1}$ $s_{d} = 2^{m - d - 1}$ .
- Onder bit-reversal bezetten de twee kinderen van een ouderblok fysieke cosets die precies gescheiden zijn door $s_d$ .
- Een rotatie door $s_d$ brengt een slot naar sommige positie in het sibling-blok. Omdat het aggregaat van de sibling over alle slots is gerepliceerd, levert elke positie in het sibling-blok de correcte semantische waarde.
- Dit maakt een enkele gerichte cyclische rotatie mogelijk om geldige aggregaten voor beide kind-oriëntaties simultaan te leveren, waarbij de correctheid voor niet-commutatieve monoïden wordt gewaarborgd via publieke maskers die de operand-volgorde selecteren.
Exclusive Scan Formulering: De auteurs implementeren een exclusive scan (waarbij de prefix vóór het huidige element wordt uitgevoerd). Dit voorkomt dat er een finale logische-voorganger verschuiving nodig is om de binnenkomende carry voor digit-correctie op te halen, een vereiste die anders de lay-out-gevoelige routing opnieuw zou introduceren.
Lower Bound Bewijzen: Het artikel stelt vast dat $m$ rotaties een globale ondergrens zijn voor elk circuit dat een output berekent die afhankelijk is van alle $2^m$ inputs in dit model. Het bewijs berust op een subset-sum argument: als $R$ rotaties worden gebruikt, kunnen maximaal $2^R$ verschillende input-verplaatsingen een vaste output bereiken. Om alle $2^m$ inputs te dekken, is $R \ge m$ noodzakelijk. Verder bewijst het artikel dat het bereiken van deze grens vereist dat de rotatie-offsets een volledige 2-adische basis vormen (één offset voor elke valentie $0, \dots, m-1$ ).

Belangrijkste Bijdragen

Optimale Scan-constructie: Een inclusieve en exclusieve scan-algoritme dat $R = m$ rotaties en $D = m$ monoïde-diepte bereikt voor bit-omgekeerde lay-outs. Dit vermindert het aantal rotaties van de directe topologie's $O(m^2)$ naar $O(m)$ .
Rigiditeit van Optimaliteit: Een karakterisering van alle optimale circuits. Als een circuit exact $m$ rotaties gebruikt, moeten de offsets een volledige 2-adische basis vormen. Dit bewijst dat het rotatieprofiel rigide is, zelfs als de circuittopologie varieert.
Rotation-Key Frontier: Een analyse van de afruil tussen het aantal direct gekende offsets ( $K$ $K$ ) en het aantal online rotatie-oproepen ( $R$ $R$ ).
- Het artikel leidt een product-ondergrens af: $\prod (c_j + 1) \ge 2^m$ , waarbij $c_j$ het aantal keren is dat key $j$ wordt gebruikt.
- Wanneer $K$ deelbaar is door $m$ , wordt de exacte frontier bewezen als $R^* = K \cdot (2^{m/K} - 1)$ .
Radix-CKKS Instantiatie: Toepassing van de exclusive scan op exacte carry en borrow propagatie in radix-gebaseerde CKKS. Dit maakt integer-vergelijking en modulaire rekenkunde mogelijk zonder de natuurlijke volgorde te herstellen of een finale verschuiving uit te voeren.
Batching Efficiëntie: Demonstratie dat de besparingen in rotaties standhouden voor volledig bezette digit-major interleavings, waarbij $g$ onafhankelijke integers in een enkel ciphertext zijn gepakt zonder het aantal rotaties te vermenigvuldigen.

Resultaten en Evaluatie

De auteurs hebben het algoritme geïmplementeerd in Lattigo (Go) en vergeleken met twee baselines:

Direct Bit-Reversed Predecessor: De naïeve $O(m^2)$ rotatie-aanpak.
Normalize–Scan–Restore: Een baseline die data converteert naar natuurlijke volgorde, scant, en weer converteert.

Belangrijkste bevindingen bij $m=7$ (128 slots):

Rotaties: Verminderd van 28 (direct) naar 7 (gerepliceerd).
Evaluatie Keys: Opslag verminderd met 70,0% (908,6 MB $\to$ 272,6 MB).
Geheugen: Piekuitvoering van de heap verminderd met 63,9% (2,30 GB $\to$ 830,5 MB).
Latentie: De gerepliceerde scan verbeterde de geïsoleerde scan-latentie met 19,9% ten opzichte van de directe voorganger-methode.
End-to-End Pipeline: In een downstream pipeline met een diepte van 5 vermeed de gerepliceerde scan een volledige bootstrapping-operatie die vereist was door de normalize-restore baseline. Dit leverde een gemiddelde snelheidswinst van 4,31 $\times$ op (95% BI [3,69, 4,92]).

Het artikel merkt op dat hoewel "normalize–scan–restore" een lagere geïsoleerde latentie heeft voor kleine $m$ vanwege minder monoïde-composities, de gerepliceerde scan sneller wordt bij $m \ge 5$ en superieure resource-efficiëntie biedt (keys, geheugen, modulus-levels).

Betekenis en Claims

Het artikel claimt dat het behouden van een bit-omgekeerde SIMD-representatie geen onvermijdbare rotatie-overhead oplegt voor geordende prefix-berekeningen. De betekenis ligt in:

Doorbreken van de Kwadratische Barrière: Het bewijzen dat de $O(m^2)$ kosten van directe routing in bit-omgekeerde lay-outs niet inherent zijn, maar kunnen worden teruggebracht naar de theoretische ondergrens van $O(m)$ via semantische replicatie.
Resource Afruil: Vaststellen dat de reductie in routingkosten (rotaties) en key-opslag ten koste gaat van de toegenomen gepakte monoïde-arbeid ( $2m-1$ composities versus $m$ ) en een tweede live state-vector. Het artikel beargumenteert dat deze afruil gunstig is voor diepe pipelines waar modulus-levels en bootstrapping knelpunten zijn.
Exactheid: Het bieden van exacte ondergrenzen en frontier-karakteriseringen voor rotatie-key management, wat verder gaat dan heuristische optimalisaties naar bewijsbare limieten voor specifieke afhankelijkheidspatronen.

Het werk wordt gepresenteerd als een specifieke optimalisatie voor de bit-omgekeerde lay-out beperking, onderscheidend van algemene prefix-netwerktheorie, en wordt gevalideerd door rigoureuze combinatorische bewijzen en empirische evaluatie in een standaard CKKS-implementatie.