🤖 machine learning

Discovering Lattice Reduction Strategies via Self-Play

Dit artikel introduceert DeltaStar, een deep reinforcement learning-agent die via self-play is getraind en een superieure roosterreductiestrategie ontdekt, die minder operaties vereist dan het klassieke LLL-algoritme en zero-shot generalisatie vertoont naar hogere dimensies en ongeziene moduli.

Oorspronkelijke auteurs: Mohamed Malhou, Kristin Lauter, Ludovic Perret

Gepubliceerd 2026-06-16

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Mohamed Malhou, Kristin Lauter, Ludovic Perret

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 warrige bal wol hebt. Je doel is om de draad te ontwarren en de strengen zo recht en kort mogelijk te rangschikken. In de wereld van de wiskunde en cryptografie wordt deze "draad" een rooster (lattice) genoemd, en de "strengen" zijn vectoren. Het vinden van de kortste, rechtste ordening is cruciaal om digitale geheimen veilig te houden, maar het is ongelooflijk moeilijk om dit met de hand te doen, vooral wanneer de bol wol enorm groot wordt.

Decennialang was het standaardinstrument om deze draad te ontwarren een algoritme genaamd LLL. Zie LLL als een zeer strikte, regelvolgende robot. Het heeft twee eenvoudige bewegingen:

Grootte-reductie (Size Reduction): Het trekt een streng strak tegen de strengen die eraan voorafgingen om speling te verwijderen.
Wisselen (Swapping): Als een streng er uit de toon lijkt te liggen, wisselt het deze met de buurman.

De robot besluit wanneer te wisselen op basis van een rigide, handgeschreven regel (de "Lovász-conditie"). Hoewel deze regel garandeert dat de robot zijn werk binnen een redelijke tijd afkrijgt, levert het niet altijd het perfect ontwarde resultaat op. Het is alsof je een kaart volgt die je naar de stad brengt, maar je eindigt met een paar onnodige omwegen.

De Nieuwe Ontdekking: "Delta-Star"

De auteurs van dit artikel stelden een simpele vraag: Wat als we de robot niet een rigide regelboek gaven, maar hem in plaats daarvan leerden hoe hij het spel van het ontwarren op eigen kracht kan spelen?

Ze bouwden een AI-agent genaamd Delta-Star met behulp van een techniek genaamd Deep Reinforcement Learning. Hier is hoe ze dat deden, met behulp van enkele creatieve analogieën:

1. De Trainingsgrond (De "Kleine Bol Wol")

Ze gooiden de AI niet in een enorme, onmogelijke knoop. In plaats daarvan trainden ze het op kleine, beheersbare 8-dimensionale roosters (denk aan een kleine bol wol met 8 strengen).

Het Spel: De AI speelt een singleplayer-spel waarbij het alleen dezelfde twee bewegingen kan maken als de oude robot (strak trekken of wisselen).
Het Doel: De AI krijgt punten voor het korter en rechter maken van de draad. Het verliest punten als het te veel stappen zet.
De Leraar: De AI leert door miljoenen keren tegen zichzelf te spelen (Self-Play). Het probeert een beweging, ziet of het helpt, en als dat niet zo is, vergeet het die beweging de volgende keer.

2. De "Glazen Bol" Strategie (Adaptive Horizon MCTS)

Het meest vernuftige deel van hun systeem is hoe de AI vooruit denkt.

Standaard Denken: Meestal kijkt een AI één stap vooruit, dan de volgende, dan de volgende. Dit is traag en rekentechnisch duur.
Delta-Stars Denken: De AI heeft een "glazen bol" die de volgende verschillende zetten tegelijkertijd voorspelt.
- Als de glazen bol zegt: "De volgende 10 zetten zijn overduidelijk en automatisch," slaat de AI deze direct over.
- Als de glazen bol zegt: "Ho, de volgende zet is een moeilijke keuze met veel mogelijkheden," dan stopt de AI en denkt diep na over dat specifieke moment.
De Analogie: Stel je voor dat je een auto bestuurt. Op een rechte, lege snelweg hoef je niet over elke centimeter van de weg na te denken; je vaart gewoon door. Maar wanneer je een complexe kruising bereikt, vertraag je en focus je. Delta-Star doet dit automatisch: het bespaart energie op de saaie delen en concentreert zich op de moeilijke beslissingen.

3. De Magische Truc: Zero-Shot Generalization

Dit is het meest verrassende resultaat. De AI werd alleen getraind op kleine 8-strengs bollen wol. Het heeft tijdens de training nooit een grotere bol gezien.

De Test: De onderzoekers gaven de AI een enorme 32-strengs bol wol (een dimensie die het nog nooit had gezien).
Het Resultaat: De AI raakte niet in de war. Het wist de enorme bol direct beter te ontwarren dan de oude LLL-robot ooit zou kunnen.
De Metafoor: Het is alsof je een kind leert om schoenen te strikken met een paar kleine baby-schoentjes, en je geeft het kind vervolgens een paar volwassen laarzen. Het kind heeft geen nieuwe les nodig; het past simpelweg dezelfde logica toe en doet een beter werk dan de volwassene die al jarenlang schoenen strikt.

Waarom Is Dit Belangrijk?

Het artikel beweert dat Delta-Star een "schoner" ontward rooster produceert dan het klassieke LLL-algoritme.

Betere Kwaliteit: De uiteindelijke ordening van de draad is korter en efficiënter.
Minder Stappen: Het kost minder "trekken en wisselen" om daar te komen.
Geen Herprogrammering: Het werkt op formaten die het nog nooit heeft gezien.

Het Nadeel

Het artikel is zeer duidelijk over één beperking: Snelheid.
Hoewel Delta-Star een beter resultaat vindt met minder wiskundige stappen, is de AI zelf momenteel trager in uitvoering dan de oude robot. Dit komt omdat de AI een complex neuraal netwerk (een gigantisch digitaal brein) moet draaien om elke enkele zet te beslissen. De oude robot is een simpele rekenmachine; de AI is een supercomputer.

De auteurs zeggen niet dat deze AI vandaag de dag de oude robot in je telefoon moet vervangen. In plaats daarvan zeggen ze: "We hebben een betere manier gevonden om de draad te ontwarren. Nu moeten we uitzoeken hoe we de regels die deze AI heeft ontdekt, kunnen opschrijven zodat we een eenvoudige, snelle robot kunnen bouwen die hetzelfde doet."

Kortom, ze hebben een superintelligente AI gebruikt om een betere strategie te ontdekken voor een wiskundig probleem, en die strategie werkt zelfs op problemen waar de AI nooit expliciet voor is getraind.

Technische Samenvatting: Ontdekken van Strategieën voor Roosterreductie via Self-Play

Probleemstelling

Roosterreductie (lattice reduction) is een fundamenteel probleem in de computationele wiskunde en cryptografie, dat de veiligheid van post-kwantum cryptografische schema's onderbouwt. Het Lenstra-Lenstra-Lovász (LLL) algoritme is de standaard methode in polynomiale tijd voor roosterbasisreductie. Hoewel LLL een specifieke looptijd en een grens aan vectorenlengtes garandeert, zijn de resultaten in de praktijk vaak suboptimaal, vooral naarmate de dimensie van het rooster toeneemt. Het algoritme vertrouwt op een handmatig ontworpen heuristiek, de Lovász-conditie, om te beslissen wanneer basisvectoren moeten worden verwisseld. Deze conditie zorgt voor een monotone afname van een potentiaalfunctie, maar is niet noodzakelijkerwijs optimaal voor het bereiken van de sterkst mogelijke reductie.

De kernuitdaging die in dit werk wordt aangepakt, is of een datagestuurde aanpak een sequentiële beleidsstrategie (sequencing policy) kan ontdekken voor de primitieve operaties van LLL (grootte-reductie en aangrenzende wissels) die een strikt superieure reductiekwaliteit oplevert vergeleken met het klassieke algoritme, zonder de actieruimte uit te breiden naar complexere orakels (zoals exacte Shortest Vector Problem solvers).

Methodologie: Delta-Star

De auteurs formuleren roosterreductie als een single-player Markov Beslissingsproces (MDP) en maken gebruik van een Deep Reinforcement Learning (RL) framework, aangevuld met Monte Carlo Tree Search (MCTS).

1. MDP Formulering

Toestandsruimte (State Space): De toestand bevat de huidige basis-matrix $B$ , de Gram-Schmidt orthogonalisatie (GSO) vectoren en coëfficiënten, de cursorpositie $k$ (die aangeeft welke rij momenteel wordt verwerkt), en de resterende stappen.
Actieruimte (Action Space): De agent is beperkt tot de exacte primitieve acties van het LLL-algoritme om een eerlijke vergelijking te garanderen:
- MOVEUP/MOVEDOWN: Aanpassen van de cursorpositie.
- SWAP: Het verwisselen van aangrenzende basisrijen $b_k$ en $b_{k-1}$ .
- SIZEREDUCE: Het aftrekken van gehele veelvouden van voorgaande rijen om aan de grootte-reductieconditie te voldoen ( $|\mu_{j,k}| \le 1/2$ ).
Beloningsfunctie (Reward Function): Een genormaliseerde beloning wordt gedefinieerd op basis van de relatieve reductie in de log-metriek van kwaliteitsmaten (Orthogonaliteitsdefect $\delta$ en LLL-potentiaal $\Phi$ ). Een hybride beloning interpoleert tussen deze twee doelstellingen.

2. Adaptive-Horizon MCTS

De auteurs introduceren een nieuw mechanisme genaamd Adaptive-Horizon MCTS om de zoekefficiëntie te verbeteren:

Multi-Step Voorspelling: Het neurale netwerk voorspelt tegelijkertijd een beleid (policy) en waarde (value) voor een horizon van $H$ toekomstige stappen.
Entropy-Gated Expansion: In plaats van de boom één knoop tegelijk uit te breiden, doorloopt het algoritme het "greedy" pad dat door het netwerk wordt voorspeld. Bij elke stap $k$ $k$ berekent het de Shannon-entropie $H[p(k)]$ $H [p (k)]$ van het voorspelde beleid.
- Als de entropie laag is (hoge mate van zekerheid), doorloopt het algoritme de stap automatisch zonder te vertakken, waardoor de kosten voor inferentie worden geamortiseerd.
- Als de entropie de drempelwaarde $\tau$ overschrijdt (wat duidt op een echt beslismoment), stopt de expansie en vertakt de boom op dat punt.
Dit mechanisme stelt de zoektocht in staat om deterministische sequenties over te slaan en de computationele middelen te concentreren op onzekere beslismomenten.

3. Neuraal Netwerk Architectuur

Backbone: Een diep Residual Network (ResNet) met een lookback-venster om de temporele historie te vangen.
Observatie-tensor: Codeert de basis, GSO, coëfficiënten, resterende tijd en cursorpositie in een 5-kanaals tensor.
Heads: Het netwerk geeft een policy-head (kansen voor $H$ stappen) en een value-head (verwachte rendementen voor $H$ stappen) uit.
Training: Het model wordt getraind via AlphaZero-achtige self-play, waarbij de cross-entropie tussen de voorspelde policy en de MCTS-bezoekfrequenties wordt geminimaliseerd, en de Mean Squared Error tussen de voorspelde waarden en de episode-opbrengsten.

4. Training Setup

De agent, genaamd Delta-Star, wordt uitsluitend getraind op kleine $q$ -ary roosters met een basisdimensie $n=8$ en modulus $q=251$ . De training maakt gebruik van een gedistribueerde pipeline met self-play workers, inference servers en een centrale learner.

Belangrijkste Resultaten

1. Superieure Reductiekwaliteit

Delta-Star bereikt een aanzienlijk betere root Hermite factor ( $\delta_0$ ) en orthogonaliteitsdefect dan het klassieke LLL-algoritme over diverse dimensies.

Bij de trainingsdimensie ( $n=8$ ) convergeert Delta-Star naar een iets lagere $\delta_0$ ( $\approx 1.00657$ ) vergeleken met LLL ($1.00660$).
Cruciaal is dat het prestatieverschil groter wordt naarmate de dimensie toeneemt. Bij $n=32$ bereikt Delta-Star $\delta_0 = 1.0149$ , waarmee het LLL ($1.0171$) verslaat en de kwaliteit van BKZ- $\beta$ ($1.0125$) benadert, ondanks dat het nooit is getraind op dimensies groter dan 8.

2. Zero-Shot Generalisatie

Het model vertoont robuuste zero-shot generalisatie:

Dimensie: Het generaliseert naar ongeziene dimensies tot $n=32$ .
Modulus: Het generaliseert naar ongeziene moduli $q$ in de reeks van $\sim 20$ tot $5000$.
Dit wordt bereikt door het gebruik van $q$ -genormaliseerde observatie-tensoren en adaptieve pooling in de netwerkarchitectuur.

3. Algoritmische Efficiëntie

Delta-Star vereist minder primitieve rij-operaties dan LLL om een vergelijkbare of betere reductiekwaliteit te bereiken.

Bij $n=8$ gebruikt het slechts 55% van de rij-operaties die LLL nodig heeft.
Bij hogere dimensies ( $n=26, 32$ ) behoudt het gedurende het hele reductieproces een strikt beter traject, waarbij het sneller convergeert en naar een betere eindtoestand leidt.
De auteurs merken op dat hoewel de inferentie van het neurale netwerk trager is in werkelijke wandkloktijd dan een klassieke implementatie, de vermindering in het aantal elementaire operaties wijst op een efficiëntere onderliggende strategie.

Betekenis en Claims

Het artikel beweert aan te tonen dat deep reinforcement learning in staat is om strikt superieure, generaliseerbare reductiestrategieën te ontdekken door te interageren met de primitieve actieruimte van LLL.

Voorbij Handmatige Heuristieken: Het werk laat zien dat de rigide Lovász-conditie niet optimaal is en dat een geleerd beleid de toestandsruimte effectiever kan navigeren.
Schaalbaarheid: De aanpak daagt de opvatting uit dat roosterreductiestrategieën opnieuw moeten worden ontworpen voor verschillende dimensies, door aan te tonen dat een model getraind op kleine instanties kan schalen naar aanzienlijk grotere, ongeziene dimensies.
Algoritme-ontdekking: De auteurs positioneren dit werk binnen het paradigma van AI-gestuurde algoritme-ontdekking (vergelijkbaar met AlphaTensor en AlphaDev), en suggereren dat fundamentele, op heuristieken gebaseerde algoritmen kunnen worden geoptimaliseerd door optimale beslissingspaden te ontdekken via RL.
Toekomstige Richtingen: Het paper concludeert dat de geleerde beleidsgewichten een deterministisch, efficiënt algoritme coderen. Een primaire toekomstige doelstelling is om dit klassieke algoritme uit het neurale netwerk te extraheren en te formaliseren. Daarnaast zou de methodologie uitgebreid kunnen worden om blokgebaseerde algoritmen zoals BKZ te verbeteren.

De auteurs blijven bescheiden over de huidige implementatie, erkennen dat het neurale netwerk trager is per operatie dan klassieke code, en benadrukken dat de waarde van het werk ligt in het karakteriseren van de structuur van een efficiëntere reductiestrategie in plaats van de directe runtime-prestaties.