Utilizing Circulant Structure to Optimize the Implementations of Linear Layers

Dit artikel stelt een nieuwe aanpak voor die gebruikmaakt van de circulaire structuur van lineaire lagen in symmetrische cryptografie om transformatiesequenties te construeren, waardoor heuristische algoritmen aanzienlijk efficiëntere XOR-aantallen en schakelcircuitdieptes kunnen bereiken voor blokcijfers zoals Whirlwind en AES in vergelijking met eerdere state-of-the-art resultaten.

De kern

Stel je voor dat je een meesterarchitect bent die probeert een complexe machine te bouwen met een specifieke set Lego-blokken. In de wereld van cryptografie (de wetenschap van geheime codes) worden deze "machines" lineaire lagen genoemd, en ze zijn de werkpaarden die data verwarren om deze veilig te houden.

Jarenlang hebben architecten geprobeerd deze machines te bouwen met zo min mogelijk blokken (om ruimte te besparen) en in de kortst mogelijke tijd (om snelheid te besparen). Het paper dat je hebt aangeleverd introduceert een nieuwe manier om deze machines te ontwerpen door een verborgen patroon in de blauwdrukken op te merken.

Hier is de uiteenzetting van hun ontdekking, eenvoudig uitgelegd:

1. Het Probleem: De "Muur van Complexiteit"

Stel je een cryptografische lineaire laag voor als een enorme muur van schakelaars. Om een bericht te verwarren, moet je deze schakelaars in een zeer specifieke volgorde omzetten.

• Het Doel: Je wilt de schakelaars omzetten met zo min mogelijk bewegingen (om energie/ruimte te besparen) en in zo min mogelijk stappen (om het snel te maken).
• De Oude Manier: Vorige methoden behandelden de muur als een gigantische, chaotische warboel van schakelaars. Ze gebruikten trial-and-error-algoritmen om de beste volgorde te vinden, maar omdat de muur zo groot en rommelig was, misten ze vaak het meest efficiënte pad. Het was alsof je een doolhof probeerde op te lossen door willekeurig tegen muren aan te lopen.

2. De Ontdekking: Het "Roterend Wiel"-patroon

De auteurs merkten op dat veel van deze cryptografische muren eigenlijk niet willekeurig zijn. Ze hebben een Circulaire Structuur.

• De Analogie: Stel je een carrousel voor. Als je een foto maakt van de paarden en de foto vervolgens roteert, ziet het patroon van de paarden er bijna hetzelfde uit, alleen verschoven.
• In wiskundige termen wordt de matrix (de blauwdruk van schakelaars) gebouwd door een enkele rij keer op keer te verschuiven. Het is een herhalend, roterend patroon.
• Het Inzicht: Vorige architecten negeerden dit "carrousel"-patroon en behandelden de muur als een chaotische warboel. De auteurs realiseerden zich dat als je dit patroon erkent, je de muur veel efficiënter kunt ontmantelen.

3. De Oplossing: De "Vouw"-truc

In plaats van te proberen de hele enorme muur in één keer op te lossen, hebben de auteurs een methode ontwikkeld om het probleem op te vouwen.

• De Metafoor: Stel je voor dat je een gigantische, zware deken met een herhalend patroon hebt. In plaats van te proberen het hele ding in één keer te vouwen, besef je dat je, omdat het patroon zich herhaalt, de linkerhelft op de rechterhelft kunt vouwen, en vervolgens de bovenkant op de onderkant.
• Door deze "vouw"-techniek te gebruiken (wiskundige transformatie van de matrix), kunnen ze een enorme, complexe muur omzetten in een veel eenvoudigere, driehoekige vorm.
• Zodra de muur is vereenvoudigd tot deze driehoekige vorm, kunnen standaardtools het werk gemakkelijk afmaken. Het is alsof je een verwarde bal wol omzet in een nette, rechte lijn voordat je probeert een knoop te leggen.

4. De Resultaten: Snellere en Kleinere Machines

De auteurs hebben deze nieuwe "vouw"-methode getest op echte cryptografische machines die worden gebruikt in populaire beveiligingssystemen. De resultaten waren indrukwekkend:

• De "Wervelwind"-machine:

  • Snelheid: Ze hebben de tijd die nodig is om de machine te laten draaien met 39% verkort. Stel je een auto voor die eerder 28 seconden nodig had om een mijl te rijden, en dat nu in 17 seconden doet.
  • Grootte: Ze hebben het aantal benodigde "blokken" (logische poorten) met ongeveer 30% verminderd. Dit betekent dat de machine kleiner is en minder stroom verbruikt.

• De "AES"-machine (De Gouden Standaard):

  • AES is de beroemdste encryptiestandaard ter wereld. Het "MixColumn"-gedeelte is een berucht moeilijk raadsel om efficiënt op te lossen.
  • De Prestatie: De auteurs bouwden een geautomatiseerd systeem dat dit raadsel bijna even goed oploste als een menselijk expert die wekenlang handmatig aan het ontwerp had gesleuteld.
  • De Haken en Ogen: Het ontwerp van de menselijke expert gebruikte 105 "blokken". Het geautomatiseerde ontwerp van de auteurs gebruikte 107. Dat zijn slechts 2 extra blokken voor een resultaat dat automatisch werd bereikt, niet met de hand. Ze haalden ook het record voor de snelste snelheid (diepte).

5. Waarom Dit Belangrijk Is

• Voor de Toekomst: Naarmate computers krachtiger worden (inclusief quantumcomputers), moeten deze "machines" sneller en kleiner zijn om veilig te blijven.
• De Kernboodschap: Door simpelweg te erkennen dat de blauwdruk een herhalend, roterend patroon heeft (zoals een carrousel), vonden de auteurs een kortere weg die vorige methoden misten. Ze hebben geen nieuw type blok uitgevonden; ze hebben gewoon een slimmere manier gevonden om ze te stapelen.

Samenvattend: Het paper zegt: "We hebben ontdekt dat veel beveiligingscodes zijn gebouwd op een herhalend patroon. Door dat patroon te gebruiken om het ontwerp eerst te vereenvoudigen, kunnen we de beveiligingssystemen sneller en kleiner bouwen dan ooit tevoren, zelfs beter dan sommige van de beste menselijke experts."

Technische samenvatting

Technische Samenvatting: Benutting van Circulante Structuur voor het Optimaliseren van Implementaties van Lineaire Laag

Probleemstelling
De optimalisatie van lineaire lagen in symmetrische cryptografie is cruciaal voor zowel lichtgewicht-implementaties (beperkt door poortenaantal en oppervlakte) als kwantumeveiligheidsbeoordelingen (beperkt door circuits diepte en DW-kosten). Hoewel er heuristische algoritmen bestaan voor het synthetiseren van CNOT-circuits (kwantum) en XOR-circuits (klassiek) voor algemene inverteerbare matrices, slagen ze er vaak niet in om specifieke algebraïsche structuren die inherent zijn aan cryptografische ontwerpen volledig te benutten. Veel veelgebruikte matrices, zoals die in AES MixColumn en Whirlwind, bezitten een circulante structuur. Bestaande state-of-the-art methoden, zoals die van Shi en Feng [SF24], behandelen deze matrices als algemene $n \times n$ binaire matrices, waardoor kansen om circuits diepte en poortenaantallen te verminderen door gebruik te maken van hun onderliggende circulante eigenschappen, mogelijk worden gemist.

Methodologie
De auteurs stellen een nieuw raamwerk voor dat expliciet gebruikmaakt van de circulante structuur van matrices om de synthese van efficiënte circuits te sturen. De kernmethodologie omvat een recursieve decompositiestrategie die een circulante matrix over een velduitbreiding (bijv. $F_{2^k}$ of $GL(F_2, m)$) transformeert naar een eenvoudigere vorm, specifiek een bovendriehoeksmatrix, voordat standaard heuristische optimalisatie wordt toegepast.

Belangrijke technische componenten zijn:

1. Recursieve Bloktransformatie: Stelling 3 stelt dat een $2^k \times 2^k$ circulante matrix over $F_2[x]$ kan worden getransformeerd naar een blokbovendriehoeksmatrix met behulp van elementaire rij- en kolomoperaties. Het algoritme splitst de matrix recursief in blokken $A$ en $B$ (waarbij $M = \begin{smallmatrix} A & B \\ B & A \end{smallmatrix}$), en past operaties toe om specifieke blokken nul te maken (bijv. transformatie naar $\begin{smallmatrix} A+B & B \\ A+B & \dots \end{smallmatrix}$).
2. Verkenning van Transformatiepaden: De auteurs merken op dat verschillende keuzes van rij- en kolomoperaties tijdens de recursieve stap leiden tot verschillende tussentijdse matrices. Het algoritme (Algoritme 1) verkent meerdere transformatiepaden (tot $4^{2^k-1}$ mogelijkheden voor kleine $k$) om het pad te vinden dat het meest efficiënte volgende circuit oplevert.
3. Vroegtijdig Stoppen en Fallback: Inzichtelijk dat het voordeel van recursie afneemt bij grotere dieptes, introduceren de auteurs een strategie (Algoritme 2) om recursie vroegtijdig te stoppen. Het algoritme itereren door verschillende "blokgroottes", wat effectief de recursiediepte varieert. Als de recursie vroegtijdig wordt gestopt, wordt de resulterende matrix doorgegeven aan een standaard heuristische optimizer (Heu) voor algemene CNOT/XOR-synthese. Dit omvat een "fallback"-strategie waarbij de recursiediepte nul is, wat de matrix effectief behandelt als een algemeen geval.
4. Geautomatiseerde Optimalisatie: In tegenstelling tot eerdere handmatige benaderingen (bijv. Zhang et al. [ZSWS24] voor AES), automatiseert deze methode het proces van het vinden van de "eenvoudigere" matrixvorm en de bijbehorende poortsequenties, waardoor menselijke tussenkomst niet langer nodig is.

Belangrijkste Bijdragen

• Nieuw Raamwerk: Dit is het eerste werk dat systematisch gebruikmaakt van de circulante structuur van lineaire lagen om circuits-implementaties te optimaliseren, en de kloof overbrugt tussen algebraïsche matrixeigenschappen en heuristieken voor circuitsynthese.
• Geautomatiseerde Synthese: De auteurs bieden een geautomatiseerd algoritme dat handmatige, casusspecifieke optimalisaties vervangt. Het genereert sequenties van transformatiematrices die downstream heuristieken in staat stellen efficiëntere implementaties te vinden.
• Dubbele Optimalisatie: Het raamwerk is toepasbaar op zowel kwantumcircuits (minimaliseren van CNOT-aantal en diepte) als klassieke circuits (minimaliseren van XOR-aantallen, specifiek g-XOR en s-XOR).

Resultaten
De auteurs evalueerden hun methode op een dataset van lineaire lagen uit blokcijfers (waaronder AES, Whirlwind, Clefia, PRIDE, enz.) en geconstrueerde MDS-matrices.

• Kwantumcircuits Diepte:

  • Whirlwind M0: De voorgestelde methode verlaagde de circuits diepte van 28 (vorige state-of-the-art door [SF24]) naar 17, een verbetering van 39%. Het poortenaantal werd ook verlaagd van 286 naar 200.
  • AES MixColumn: De geautomatiseerde methode bereikte een diepte van 10, wat overeenkomt met het handmatig geoptimaliseerde state-of-the-art resultaat van Zhang et al. [ZSWS24]. Het poortenaantal was 107, wat slechts 2 CNOTs meer is dan het handmatige resultaat (105) en aanzienlijk beter dan de 131 CNOTs bereikt door [SF24].
  • Andere Matrices: Beduidende diepteverminderingen werden waargenomen voor matrices met hoge dichtheid (bijv. Whirlwind, SKOP15 8x8), terwijl verbeteringen marginaal of afwezig waren voor schaarse matrices waar heuristieken al goed presteren.

• Klassiek Circuit (XOR Aantal):

  • Whirlwind M0: De methode bereikte een s-XOR-aantal van 159, wat de vorige beste van 173 (Yuan et al. [YWS+24]) met ongeveer 8% overtrof.
  • Algemene Prestaties: Hoewel de methode over het algemeen een omvangsoverhead veroorzaakt voor veel matrices, slaagde het erin state-of-the-art resultaten te verbeteren voor specifieke hoogdichte matrices zoals Whirlwind M0 en M1.

Betekenis en Claims
Het artikel stelt dat het benutten van de circulante structuur een krachtige, tot nu toe onderbenutte weg is voor het optimaliseren van lineaire lagen. De auteurs stellen dat hun aanpak:

1. Bestaande heuristieken overtreft voor specifieke, dichte matrices waar standaard greedy-strategieën moeite hebben.
2. Handmatige optimalisatie automatiseert, resultaten bereikt die vergelijkbaar zijn met door menselijke experts afgestemde circuits (zoals gezien bij AES MixColumn) zonder dat menselijke tussenkomst vereist is.
3. Een nieuwe basislijn biedt voor kwantumeveiligheidsbeoordelingen, door nauwkeurigere diepteschattingen voor lineaire lagen te bieden, wat cruciaal is voor het berekenen van de DW (Diepte $\times$ Breedte) kosten in post-kwantum beveiligingsevaluaties.

De auteurs concluderen dat hoewel de methode niet universeel superieur is voor alle matrixtypen (met name schaarse), het een significant voordeel biedt voor matrices met circulante structuren en hoge dichtheid, en het potentieel demonstreert van het integreren van algebraïsche eigenschappen in circuitsynthese.