Obfuscatie (Deel III): Local Mixing

Het eerste dat opvalt aan local mixing is dat dit een totaal andere manier van cryptografie is. Er zijn geen elliptische curves, geen priemfactorisatie en geen lattices. Sterker nog, het dichtst bij wat "reguliere" cryptografie heeft van wat hier gebeurt, is symmetrische cryptografie: encryptie en het ontwerp van hashfuncties.

Bij symmetrische encryptie en hashfuncties zijn er geen zuivere reducties naar goed gestructureerde wiskundige problemen (zoals: "als je dit kunt kraken, betekent dat dat je zeer grote getallen snel kunt factoriseren"). In plaats daarvan is er een vijftig jaar oude traditie van mensen die proberen functies te creëren die pseudorandom zijn, wiskundigen die deze aanvallen, en ontwerpers die trucjes bedenken om tegen die aanvallen te beschermen, totdat het geheel stabiliseert en we vandaag de dag veilige hashes hebben zoals SHA en BLAKE. Het doel van local mixing is om die traditie over te nemen en de ideeën ervan toe te passen op circuits — om de eigenschappen te bereiken die symmetrische cryptografen hebben geleerd dat hun basisbouwstenen nodig hebben — terwijl de functionaliteit behouden blijft.

Dit is een gewaagde en risicovolle weddenschap; het bevindt zich op een kerkhof van mislukte pogingen tot white-box cryptografie. De hoop van de auteurs van local mixing is dat als we meer inspanning in deze richting steken en slimmer te werk gaan — inclusief het gebruik van AI om de drie decennia die hashfuncties nodig hadden om te stabiliseren in een paar jaar te versnellen, en tegelijkertijd een hogere overhead accepteren — we iets kunnen maken dat werkt.

Hoe werkt local mixing?

Het doel van local mixing is om een circuit $C$ (bestaande uit logische poorten, bijv. XOR, AND, NOT) te nemen en daar een reeks transformaties op toe te passen die de functionaliteit van $C$ behouden, maar progressief elke mogelijkheid wegnemen om de interne logica in te zien.

De obfuscatie-pijplijn

Op hoog niveau is het belangrijkste idee precies wat de naam "local mixing" suggereert: voeg een heleboel "junk gates" toe, hussel alles door elkaar en vervang herhaaldelijk kleine delen van het circuit door verschillende sets poorten die dezelfde functionaliteit hebben.

Dit is echter slechts één stap in de pijplijn. De meeste slimheid zit in de andere stappen: de stappen die het circuit voorbereiden zodat het geschikt is voor mixing, en die geoptimaliseerd zijn om informatielekken in het onderliggende circuit te verwijderen die lastig volledig door mixing aan te pakken zijn.

De stappen zijn als volgt:

1. Toevoegen van omkeerbaarheid (reversibility)
2. Hardening
3. Gadgetisatie
4. Mixing

Toevoegen van omkeerbaarheid

De eerste stap is om het circuit $C$ om te zetten in een omkeerbaar circuit: een circuit dat zowel voorwaarts als achterwaarts kan worden uitgevoerd. De belangrijkste reden hiervoor is dat omkeerbare circuits veel geschikter zijn voor mixing. Een enkele omkeerbare poort kan worden vervangen door een willekeurig groot aantal andere omkeerbare poorten die samen dezelfde functionaliteit hebben als de originele poort. Dit is bij bijvoorbeeld AND- en OR-poorten veel moeilijker.

Een belangrijke reden hiervoor is dat onomkeerbare berekeningen entropie doen instorten: AND voegt 00, 01 en 10 samen tot dezelfde output, en hetzelfde geldt voor OR met 01, 10 en 11. Lange ketens van onomkeerbare poorten vernietigen standaard enorme hoeveelheden informatie, proportioneel aan de lengte van het circuit. Een groot genoeg willekeurig omkeerbaar circuit is plausibel een veilige cryptografische permutatie; een groot genoeg willekeurig onomkeerbaar circuit degradeert tot slechts een paar mogelijke outputs.

De keuze voor omkeerbare circuits weerspiegelt wijsheid uit de symmetrische cryptografie: zelfs in onomkeerbare toepassingen zoals hashfuncties is de kernbouwsteen een omkeerbare permutatie, waarbij de onomkeerbaarheid voortkomt uit een dunne laag erbovenop, precies om ervoor te zorgen dat de volledige "state space" van het circuit zo lang mogelijk bereikbaar blijft.

Voor een voorbeeld van een twee-bits opteller ziet de omzetting er als volgt uit:

• Het nieuwe circuit is opgebouwd uit vele kopieën van een "r57"-poort, die drie inputs en drie outputs heeft. De kernlogica is: flip draad C, tenzij draad A gelijk is aan 0 en draad B gelijk is aan 1. De outputs op draad A en B blijven gelijk. Elke "standaard" poort met twee inputs en één output kan worden geïmplementeerd met twee r57-poorten.
• Er is een duidelijk gedefinieerde "status" op elk punt in de uitvoering (de waarden op elke draad op een verticaal vlak). Poorten zijn sequentieel van links naar rechts gerangschikt.
• Het circuit heeft een aantal extra "junk"-inputs nodig, waarvan er één 1 moet zijn en de rest 0. Sommige helpen bij de constructie van standaardpoorten via r57-poorten, andere houden tussenresultaten vast.

Door deze stap heb je een object dat hetzelfde doet als $C$, maar in een formaat dat van nature veel vriendelijker is voor mixing.

Hardening

De volgende stap is hardening. Het doel is om een omkeerbaar circuit zo te transformeren dat er, zonder de poorten te manipuleren, geen enkele manier is om het circuit te gebruiken voor iets anders dan het uitvoeren van $C$ op een input om de output te krijgen.

Er zijn twee manieren waarop deze conditie geschonden kan worden:

1. Omzetting naar omkeerbaarheid creëert vaak hulpdraden ("ancillas") die nul moeten zijn. Als deze op niet-nul worden gezet, riskeert men dat het interne gedrag van $C$ op willekeurige manieren lekt.
2. De omkeerbare versie van $C$ kan, nu eenmaal, in reverse worden uitgevoerd. Dit is niet gewenst.

De belangrijkste techniek om dit aan te pakken is de hardened Toffoli-techniek:

• Er worden twee nieuwe sets draden toegevoegd:
• Een extra ancilla-draad, $u{\delta}$, en hulpdraden $u1 \dots uj$. De waarde van $u{\delta}$ kan 0 of 1 zijn; hij komt eruit met dezelfde waarde als hij erin ging.
• Output-draden $y1 \dots yk$, waarnaar de output wordt gekopieerd. Het circuit XOR't $C(\text{inputs})$ in deze positie.

De uitvoering verloopt in vier stappen:

1. Voer $C$ uit.
2. Als $u{\delta} = 0$, zet $y1 \dots y_k \oplus= C(\text{inputs})$.
3. Voer $C$ achterwaarts uit, waarbij alle hulpdraden van $C$ worden schoongeveegd.
4. Als alle hulpdraden die nul moeten zijn ook nul zijn (en alle die één moeten zijn, één zijn), flip dan $u_{\delta}$, anders laat je hem ongewijzigd.
5. Herhaal de bovenstaande vier stappen opnieuw.

Normaal scenario: $u{\delta}$ wordt in het midden geflipt. In een van de twee blokken wordt $C(\text{inputs})$ in de output-draden ge-XOR'd, in de andere gebeurt er niets. De resultaten cancelen elkaar niet uit, maar de status van de draden wordt hersteld. Foutieve hulpdraad: $u{\delta}$ wordt niet geflipt. Hierdoor wordt $C(\text{inputs})$ ofwel nooit ge-XOR'd, ofwel twee keer, waardoor de kopieën elkaar opheffen. Reverse uitvoering: Het volledige circuit uitgevoerd in reverse doet precies hetzelfde als voorwaarts.

Een alternatieve benadering uit 2026 is sandwiching. Dit is een vorm van hardened Toffoli geoptimaliseerd voor gevallen waar geen omzetting naar omkeerbaarheid nodig is (zoals bij het obfusceren van een willekeurige permutatie voor publieke-sleutel encryptie). Sandwiching heeft een lagere overhead ($\approx 2\text{x}$ in plaats van $\approx 4\text{x}$) en gebruikt "slice gates" om te voorkomen dat niet-nul inputs op de output-draden de boel verstoren.

Mixing

Mixing is conceptueel eenvoudig: het is het herhaaldelijk transformeren van kleine delen van het circuit. Elke transformatie behoudt de functionaliteit, maar vernietigt of verspreidt zichtbare informatie over de structuur. Na miljoenen rondes is elke poort uit het originele circuit honderden keren gemixt.

Generation mixing

Dit werkt via een enorme tabel met alle kleine circuits die dezelfde functionaliteit hebben:

1. Maak een gigantische tabel van alle kleine circuits met dezelfde functionaliteit.
2. Pak herhaaldelijk sets poorten uit het circuit die aaneengesloten zijn of elkaar niet storen.
3. Kijk in de tabel in welke "klasse" deze set poorten valt en vervang deze door een willekeurig ander klein circuit uit dezelfde klasse.
4. Bepaal de legale posities waarin het nieuwe sub-circuit kan staan zonder de functionaliteit te breken en verplaats het naar een willekeurige positie in dat bereik.
5. Herhaal.

Om dit efficiënt te maken, wordt gebruikgemaakt van canonicalisatie, polynomiale vormen en een "rainbow table" om queries snel te maken. Dit is de krachtigste stap omdat het nonlineariteiten introduceert.

Splitting

Splitting vervangt r57-poorten door een bredere set poorten met één of twee controls.

• Decomposities: Een r57-poort kan worden gesplitst in twee alternatieve sets van twee poorten.
• Distant join: Men kan twee posities A en B op een draad kiezen, daar de poort flippen (tegenovergestelde omstandigheden), en alle leesacties op die draad tussen A en B inverteren.

Dit helpt om informatie over de betekenis van individuele draden (bijv. het verschil tussen "x" en "niet-x") te vernietigen.

The crossing walk

Poorten die niet "botsen" (de één schrijft niet wat de ander leest) kunnen vrij worden herordend. Poorten die wél botsen, kunnen ook worden herordend, mits er een nieuwe poort wordt toegevoegd om de verandering in volgorde van lezen en schrijven te compenseren. Dit creëert "residuen" bij elke poort die wordt gepasseerd.

fcompress

Deze stap vereenvoudigt series poorten die een draad wijzigen voordat deze wordt gelezen. Dit is primair bedoeld om het programma te verkleinen, zodat legitieme gebruikers niet te maken hebben met een onnodig groot object dat een aanvaller sowieso zou proberen te verkleinen.

Gadgetization swaps

Tijdens de gadgetisatiefase worden "role swaps" uitgevoerd waarbij twee draden hun waarden en rollen wisselen. Dit zorgt voor "verticale" beweging van waarden over draden, wat aanvulling biedt op de "horizontale" beweging van de crossing walk.

Samenvatting van mixing-families:

• Splitting: Herschrijft draadwaarden ter plaatse.
• Gadgetization swaps: Verplaatst waarden tussen draden.
• Generation mixing: Vervangt een klein window volledig.
• Crossing walk / fcompress: Verplaatst poorten door de tijd (volgorde).

Gadgetisatie: waarom is het nodig?

Mixing alleen is niet genoeg. Een fundamenteel probleem is dat elke "draad" in $C$ op een bepaald tijdstip nog steeds ergens in het obfusceerde circuit $Obf(C)$ is geïnstantieerd.

Als een aanvaller $C$ en $Obf(C)$ heeft, kunnen ze correlaties zoeken tussen draden. Zelfs als $C$ geheim is, is vaak een groot deel ervan publiek, behalve een ingebedde geheime sleutel. Een aanvaller kan een "oracle" gebruiken om poorten in $C$ te mappen naar $Obf(C)$ en zo het circuit stap voor stap bloot te leggen.

Gadgetisatie lost dit op door te garanderen dat geen enkele draad in $C$ expliciet wordt geïnstantieerd in $Obf(C)$.

Hoe werkt gadgetisatie?

Elke poort in het circuit wordt vervangen door een "gadgetized gate".

Lineaire gadgetisatie

In het simpelste ontwerp wordt elke draad $wi$ gerepresenteerd door twee draden, $si$ en $ri$, zodanig dat $wi = si \oplus ri$. Door ideeën uit multi-party computation en secure hardware (het d-probing model) te gebruiken, kan het gedrag van de poort worden gereproduceerd zonder dat $wa, wb$ of $w_c$ ooit expliciet verschijnen op één enkele draad.

Lineaire algebra-aanvallen

Ondanks bovenstaande blijft er een lineaire (affiene) relatie bestaan. Een aanvaller kan via Gauss-eliminatie ($\mathcal{O}(N^3)$) of Strassen ($\mathcal{O}(N^{2.8})$) systemen van lineaire vergelijkingen oplossen om de relatie tussen $C$ en $G$ (het gadgetized circuit) te vinden.

Niet-lineaire gadgetisatie

Om dit te voorkomen, worden draden niet-lineair opgeslagen. In plaats van $wi = si \oplus ri$, gebruikt men een "carrier" draad $ci$ en "band products" $B_{ij}$ (producten van pseudorandom gegenereerde waarden).

Een techniek genaamd Gray folding wordt gebruikt om operaties uit te voeren zonder de onderliggende waarden expliciet te vormen. Dit proces is complex:

• nonlinear291: Gebruikt 291 poorten per onderliggende poort. Dit is immuun voor exacte lineaire aanvallen op rijen van $G$.
• behemoth1415: Een monsterconstructie waarbij poorten in een secret-share gadget zijn vervangen door nonlinear291-gadgets.
• behemoth80000: Een extreme variant waarbij elke poort in een nonlinear291 weer is vervangen door een nonlinear291. Dit resulteert in een blow-up van $\approx 80.000$ poorten per originele poort. Hoewel dit enorm lijkt, is het nog steeds minder dan de overhead van fully homomorphic encryption (FHE).

Complementaire rollen van gadgetisatie en mixing

• Gadgetisatie zorgt voor nonlineariteit en minimale correlatie-gewichten per poort, maar is afhankelijk van mixing om te voorkomen dat een aanvaller simpelweg patronen herkent in de gadgets.
• Mixing vernietigt structurele lekkage zeer effectief, maar is minder robuust tegen algebraïsche lekkage.

Beveiligingseigenschappen en aanvallen

Het doel is het ontbreken van detecteerbare relaties tussen executies van het obfusceerde circuit en het originele circuit.

Relatie	Aanvaller/Methode	Complexiteit
Exacte lineaire matches	Gauss-eliminatie / Matrix inversie	$\mathcal{O}(	Obf(C)	)^{\approx 2.8}$
Exacte graad-k matches	Tensor power van $Obf(C)$ + Matrix inversie	$\mathcal{O}(	Obf(C)	)^{\approx 2.8}$
Correlaties weight-k lineair	Sparse Learning Parity with Noise (LPN)	$\mathcal{O}(	Obf(C)	)^{\approx 0.7k}$
Correlaties weight-k non-lineair	Exhaustive search / Junta learning	$\mathcal{O}(	Obf(C)	)^{\approx 0.7k}$

Random bit flip aanvallen

Een aanvaller kan proberen willekeurig bits te flippen tijdens de uitvoering om bijvoorbeeld een controle-bit ("was de STARK correct?") te omzeilen en zo een geheime sleutel te extraheren.

Oplossingen:

1. Mixing layer: Zorg dat elke draad regelmatig als ancilla dient voor veel andere gadgets. Een flip veroorzaakt dan een lawine van pseudorandom flips in de rest van de uitvoering.
2. Gadgetization layer: Zorg dat de meeste representaties "junk" zijn en slechts een paar representaties 0 of 1 betekenen. Het zou meerdere bit-flips moeten kosten om van een 0-representatie naar een 1-representatie te gaan.

Naar (soort van) bewijsbare Indistinguishability Obfuscation (iO)

De auteurs richten zich momenteel op het obfusceren van willekeurige circuits. Dit heeft twee belangrijke toepassingen:

1. Publieke-Sleutel Encryptie

Door een omkeerbaar willekeurig circuit $R$ te genereren en $Obf(R)$ te publiceren, kan iedereen encryptie uitvoeren via $Obf(R)(m, r)$. De eigenaar van $R$ kan dit ontsleutelen via $R^{-1}$.

• Voordelen: Potentieel quantum-resistent, zeer kleine ciphertexts (48 bytes), zeer snelle ontsleuteling.
• Nadeel: Publieke sleutels zijn vele megabytes groot.

2. Constructie van iO

Er is een methode gevonden om iO van willekeurige circuits te construeren uit de obfuscatie van random circuits. Dit gebeurt door elke poort $g$ in een circuit te vervangen door een complexe constructie $\Gamma$ bestaande uit obfuscaties van random circuits $R$ en hun inverse.

Deze bewijsvoering rust op twee aannames:

1. RIO (Random Input and Output obfuscation) voor random circuits.
2. Split Circuit Pseudorandomness conjecture: de aanname dat men het verschil niet kan zien tussen $Obf(C1 | R) | Obf(R^{-1} | C2)$ en $Obf(C1 | C2)$.

De cryptografische traditie van local mixing

De epistemologie van local mixing is vreemd vergeleken met traditionele cryptografie. Waar de meeste cryptografie rust op wiskundige bewijzen en reducties naar harde problemen, is local mixing veel heuristischer. Het lijkt meer op de traditie van symmetrische cryptografie (hashes en encryptie) en secure hardware design.

Symmetrische cryptografie gebruikt concepten als:

• Confusion and diffusion.
• Substitution-permutation networks.
• Reversibele stappen met onomkeerbaarheid aan het eind.
• Lineaire en differentiële cryptanalyse om zwakheden te vinden.

De filosofie is dat hashes "intentionele chaos" zijn. Het is makkelijker te geloven dat iets dat ontworpen is om geen structuur te hebben, ook geen structuur behoudt, dan te geloven dat een complex wiskundig object geen onvoorziene structuren bevat.

Vergelijking van cryptografische bouwstenen

Object	Waar de plaintext verborgen is	Hoe er op wordt gerekend
Elliptic Curves	Discrete log wrt standardized point $G$	Lineaire homomorfie van curve-optelling
RSA	$k$-de wortel modulo $N = pq$	Homomorfie op vermenigvuldiging
Lattices	Benaderde lineaire vergelijkingen	Ring-eigenschappen (tot foutmarge)
Local Mixing	Lage-graad polynomiale functies van $G$	Een "pad" bewandelen dat expliciete instantiatie van waarden vermijdt

Conclusie

Local mixing is een serieuze poging om een nieuwe basis-cryptografische primitieve uit te vinden. Hoewel het nog in een vroeg stadium is en onbewezen, biedt het een route naar obfuscatie die potentieel veel efficiënter is dan lattice-gebaseerde methoden en zelfs kan concurreren met FHE-protocollen.

De grootste uitdaging is de tijd die nodig is voor cryptanalyse. Waar dit normaal decennia duurt, hopen de auteurs dat AI-versneld onderzoek dit proces kan inkorten tot enkele jaren. Obfuscatie is de "laatste grens" van de cryptografie: zodra dit werkt, kunnen vrijwel alle andere primitieven eruit worden gebouwd.