Optimized Point Addition Circuits for Elliptic Curve Discrete Logarithms

Dit artikel presenteert een gedetailleerde kwantumlogische circuitarchitectuur voor geoptimaliseerde puntoptelling op elliptische curves over priemvelden, waarbij een reductie van 6,5% tot 10% in het aantal Toffoli-poorten wordt bereikt voor secp256k1 vergeleken met de resultaten van Babbush et al. gebaseerd op zero-knowledge-proofs, terwijl er slechts een marginale toename van 1,5% in qubitgebruik optreedt.

De kern

Stel je voor dat je probeert een zeer complex slot te kraken. Decennia lang weten wiskundigen al dat een speciaal soort "super-sleutel" (een kwantumcomputer) dit slot bijna onmiddellijk kan openen, waardoor de beveiliging van het grootste deel van het internet wordt doorbroken. Dit staat bekend als Shor's Algoritme.

Het bouwen van een dergelijke super-sleutel is echter extreem duur en moeilijk. Het vereist een enorme hoeveelheid "magische energie" (kwantumbronnen) om te werken. Het doel van dit paper is om uit te zoeken hoe we een kleinere, efficiëntere versie van die sleutel kunnen bouwen.

Hier is de uitleg van wat de auteur, André Schrottenloher, heeft bereikt, uitgelegd aan de hand van alledaagse analogieën.

1. Het grote probleem: De zware rugzak

Denk aan het uitvoeren van Shor's algoritme als het beklimmen van een berg. Om de top te bereiken (de code kraken), moet je een zware rugzak dragen vol met benodigdheden (kwantumbits, of "qubits").

• Eerdere pogingen: Andere onderzoekers hebben onlangs een zeer efficiënte rugzak gebouwd die lichter was dan ooit tevoren. Echter, zij hielden de blauwdrukken geheim door een "magische truc" (een zero-knowledge proof) te gebruiken om iedereen te overtuigen dat de rugzak licht was, zonder te laten zien hoe deze precies gemaakt was.
• Het doel van dit paper: De auteur wilde een rugzak bouwen die net zo licht is als de geheime versie, maar waarbij de blauwdrukken volledig openbaar zijn, zodat iedereen het werk kan controleren.

2. De kerntaak: Punten toevoegen op een curve

De belangrijkste taak van het algoritme is het uitvoeren van een specifieke wiskundige operatie genaamd "puntoptelling" op een elliptische curve.

• De analogie: Stel je voor dat je over een gigantische, gebogen trampoline loopt. Je moet van de ene plek naar de andere springen op basis van een set regels. Het is moeilijk om deze sprong perfect uit te voeren.
• De bottleneck: Het moeilijkste deel van de sprong is een specifieke beweging genaamd "in-place vermenigvuldiging". Het is alsoal proberen twee getallen met elkaar te vermenigvuldigen terwijl je alleen de ruimte mag gebruiken waar je op dat moment staat, zonder extra ruimte om aantekeningen bij te houden.

3. De oplossing: De "twee-stappen-dans"

Om het "geen schrijfpapier"-probleem op te lossen, gebruikte de auteur een slimme tweestappenstrategie (gebaseerd op een methode genaamd het Extended Euclidean Algorithm):

• Stap 1: De geheugentape (de bewegingen registreren)
  In plaats van de berekening direct uit te voeren en het resultaat te bewaren, legt de computer eerst alleen vast welke bewegingen het zou hebben gemaakt op een lange tape van bits. De computer doet nog niet het zware werk; hij schrijft alleen de instructies op. Deze tape is verrassend kort.
• Stap 2: De reconstructie (het afspelen van de bewegingen)
  Zodra de tape is geschreven, speelt de computer deze in omgekeerde volgorde af. Hij gebruikt de instructies op de tape om de eigenlijke berekening op de getallen uit te voeren.
• Waarom dit helpt: Door het "plannen" te scheiden van het "uitvoeren", bespaart de computer een enorme hoeveelheid ruimte. Het is alsof je een recept op een briefje schrijft voordat je begint met koken, zodat je niet alle ingrediënten tegelijk in je handen hoeft te houden.

4. De afkorting: De "Pseudo-Mersenne" priemgetal

Het paper richt zich op een specifiek type slot genaamd secp256k1 (gebruikt door Bitcoin). Dit slot heeft een speciale vorm.

• De analogie: Stel je voor dat een generiek slot een perfect vierkant is. Maar het Bitcoin-slot is een vierkant met één klein afgeknapt hoekje.
• De optimalisatie: Omdat het hoekje is afgeknapt, is de wiskunde die nodig is om het slot te openen iets eenvoudiger. De auteur heeft speciale tools ontworpen die gebruikmaken van dit "afgeknapte hoekje" om onnodige stappen over te slaan.
  • Voor een generiek slot (elk priemgetal) zijn de tools standaard en iets zwaarder.
  • Voor het Bitcoin-slot (secp256k1) zijn de tools gestroomlijnd en lichter, omdat ze precies weten waar het hoekje mist.

5. De resultaten: Een iets lichtere rugzak

De auteur heeft de volledige "blauwdruk" voor deze nieuwe rugzak gebouwd en getest.

• Ruimte (Qubits): De nieuwe rugzak is ongeveer 1,5% zwaarder dan de geheime versie van de andere onderzoekers. Het is een kleine concessie.
• Energie (Gates): Echter, de nieuwe rugzak is 6,5% tot 10% efficiënter qua energie (Toffoli gates) die nodig is om het te draaien.
• Betrouwbaarheid: De auteur heeft bewezen dat deze rugzak net zo betrouwbaar werkt als de geheime versie. Als je hem op willekeurige inputs probeert te gebruiken, slaagt hij bijna altijd, net als de geheime versie.

Samenvatting

In eenvoudige bewoordingen zegt dit paper: "We hebben ontdekt hoe we de kwantumcomputer kunnen bouwen die nodig is om moderne encryptie te kraken. We hebben niet alleen gegokt; we hebben de exacte instructies opgeschreven. Onze versie is iets groter in omvang, maar verbruikt minder energie om te draaien dan de vorige 'geheime' versie, en we hebben bewezen dat het werkt voor zowel generieke sloten als het specifieke slot dat door Bitcoin wordt gebruikt."

De auteur benadrukt dat dit een logisch ontwerp is (het theoretische blauwdruk). Dit betekent niet dat we dit vandaag de dag al kunnen bouwen, maar het vertelt ons precies hoeveel "magische energie" we nodig zullen hebben wanneer kwantumcomputers krachtig genoeg zijn om dit te proberen.

Technische samenvatting

Probleemstelling
Het artikel behandelt de schatting van de middelen voor het Shor-algoritme voor het berekenen van elliptische kromme discrete logaritmen (ECDL), een primaire bedreiging voor de huidige publieke-sleutelcryptografie. Hoewel recente werken door Babbush et al. (arXiv 2026) significante reducties in gate- en qubit-aantallen voor de curve secp256k1 hebben aangetoond, vertrouwden zij op een zero-knowledge bewijs om hun resultaten te valideren zonder de onderliggende logische kwantumcircuits te onthullen. Dit gebrek aan transparantie belemmert reproduceerbaarheid en onafhankelijke verificatie. Het artikel beoogt een volledig gedetailleerde, reproduceerbare logische kwantumcircuitarchitectuur te bieden die een vergelijkbare efficiëntie bereikt als Babbush et al., terwijl de ontwerpprincipes en implementatiedetails expliciet worden onthuld.

Methodologie
De auteurs hanteren een top-down benadering, beginnend bij de hoog-niveau structuur van het Shor-algoritme en verfijnend naar de rekenkundige componenten. De kern van de optimalisatie ligt in de implementatie van windowed point addition op elliptische krommen over priemvelden.

1. Hoog-niveau Structuur: Het algoritme maakt gebruik van een semiclassieke Fourier-transformatie met qubit-recycling om de puntvermenigvuldiging $|u, v\rangle|0\rangle \to |u, v\rangle|[u]P + [v]Q\rangle$ te reduceren tot een sequentie van windowed puntoptellingen. Punten worden gerepresenteerd in affiene coördinaten.
2. Modulaire In-Place Vermenigvuldiging: De meest kostbare operatie in puntoptelling is in-place modulaire vermenigvuldiging $|x, y\rangle \to |x, yx \pmod q|$. De auteurs passen een techniek uit [14] aan die het Uitgebreide Euclidische Algoritme (EEA) ontkoppelt in twee afzonderlijke fasen:
   • Euclidisch Algoritme (Forward): In plaats van Bézout-coëfficiënten direct te berekenen, verwerkt deze fase de inputs $(q, x)$ en produceert een "garbage" bit-vector die de sequentie van operaties (swaps, aftrekkingen, delingen door 2) codeert. Dit vermindert de ruimtecomplexiteit.
   • Bézout Reconstructie (Backward): Deze fase neemt de garbage bit-vector en past de geregistreerde operaties toe op een paar $(y, 0)$ om $|y, yx^{-1} \pmod q\rangle$ te berekenen. Door dit in omgekeerde volgorde of met specifieke inputs uit te voeren, bereiken de auteurs simultane in-place vermenigvuldiging en inversie.
3. Rekenkundige Optimalisatie:
   • Ruimte versus Gate Trade-offs: De auteurs schakelen strategisch tussen de CDKM-adder (lage ruimte) en de Gidney-adder (lage gate-aantal, hogere ruimte) afhankelijk van de beschikbaarheid van ancilla-qubits tijdens verschillende stadia van het algoritme.
   • Benaderende Rekenkunde: Om de gate-aantallen te verminderen, introduceren de auteurs benaderende rekenkundige circuits. Vergelijkingen worden uitgevoerd met behulp van alleen de meest significante bits (MSB's) in plaats van volledige breedte-vergelijkingen. Dit introduceert een faalkans, die wordt beheerd door constanten te optimaliseren om succes op willekeurige inputs met een hoge waarschijnlijkheid te garanderen (specifiek, faalkans $\le 2^{-13.3}$).
   • Instantie-specifieke Optimalisatie: Voor de secp256k1-curve, die een pseudo-Mersenne priemgetal gebruikt ($q = 2^{256} - 4294968273$), worden de modulaire reductiecircuits verder vereenvoudigd. De auteurs maken gebruik van het kleine verschil $f$ in de vorm $2^u - f$ om dure modulaire aftrekkingen te vervangen door eenvoudige bit-manipulaties en optellingen van $f$.

Belangrijkste Bijdragen

• Reproduceerbare Circuitarchitectuur: Het artikel beschrijft het eerste volledig gespecificeerde logische kwantumcircuit voor ECDL op secp256k1 dat de efficiëntieclaims van het opaak werk van Babbush et al. evenaart. De code is geïmplementeerd en beschikbaar via de Qarton library.
• Geoptimaliseerde Resource Counts: De auteurs presenteren twee varianten van het circuit:
  • Ruimte-geoptimaliseerd: Gebruikt ongeveer $4.36n + O(\sqrt{n})$ qubits.
  • Gate-geoptimaliseerd: Gebruikt ongeveer $4.36n + O(\sqrt{n})$ qubits maar reduceert het aantal Toffoli-gates.
• Generieke Variant: Een versie van het circuit wordt geleverd die geldig is voor elk priemveld, niet alleen voor secp256k1, hoewel dit een iets hogere gate-kosten met zich meebrengt door het gebrek aan pseudo-Mersenne optimalisaties.
• Gedetailleerde Kostenanalyse: Het artikel biedt een granulair overzicht van de Toffoli gate-kosten, waarbij onderscheid wordt gemaakt tussen de GCD-constructie, Bézout-reconstructie en modulaire rekenkundige componenten.

Resultaten
De auteurs rapporteren de volgende resource-schattingen voor de curve secp256k1 (waarbij $n=256$):

• Qubit Aantal:
  • Ruimte-geoptimaliseerde variant: 1.192 qubits (vergeleken met 1.175 in Babbush et al.).
  • Gate-geoptimaliseerde variant: 1.446 qubits (vergeleken met 1.425 in Babbush et al.).
  • Dit vertegenwoordigt een lichte toename van ongeveer 1,5% in het aantal qubits.
• Gate Aantal (Toffolis):
  • Ruimte-geoptimaliseerde variant: $2^{21.19}$ (ongeveer $2,3 \times 10^6$).
  • Gate-geoptimaliseerde variant: $2^{20.83}$ (ongeveer $1,8 \times 10^6$).
  • Dit vertegenwoordigt een reductie van 6,5% tot 10% in het aantal Toffoli-gates vergeleken met Babbush et al.
• Volledige Algoritme Kosten: Voor het volledige Shor-algoritme op secp256k1 vereist de gate-geoptimaliseerde variant ongeveer $2^{25.78}$ Toffoli gates en 1.462 qubits. Dit is een significante verbetering ten opzichte van het eerdere werk van Litinski (arXiv 2023), dat ongeveer $2^{27.57}$ Toffoli gates en tweemaal zoveel qubits vereiste.

Betekenis
Het artikel claimt zijn betekenis primair in de sfeer van reproduceerbaarheid en transparantie. Door de expliciete logische circuitarchitectuur te verstrekken, stellen de auteurs de cryptografische gemeenschap in staat om de resource-schattingen voor het breken van elliptische curve-cryptografie te verifiëren, die voorheen verborgen waren achter een zero-knowledge bewijs. Het werk demonstreert dat een vergelijkbare of licht verbeterde efficiëntie kan worden bereikt door expliciete ontwerpkeuzes, specifiek de scheiding van de EEA in een opnamefase en een reconstructiefase, gecombineerd met benaderende rekenkunde. De auteurs merken op dat hun circuits niet exact zijn en vertrouwen op een hoge waarschijnlijkheid van succes op willekeurige inputs, een eigenschap die gedeeld wordt met het werk dat zij repliceren. De resultaten bevestigen dat de kosten voor het breken van secp256k1 lager zijn dan eerder geschat door sommige logische circuitmodellen, wat de urgentie van de migratie naar post-kwantum cryptografie versterkt.