The SQInstructor: a guide to SQIsign and the Deuring Correspondence with level structures

Dit artikel introduceert SQInstructor, een generalisatie van het SQIsign-handtekeningsschema dat gebruikmaakt van niveaustructuren en een nieuwe expliciete Deuring-correspondentie voor supersinguliere elliptische krommen om een isogenie te vinden die een gekozen niveaustructuur op een andere afbeeldt.

De kern

De SQInstructor: Een Nieuwe Sleutel voor de Digitale Wereld

Stel je voor dat we allemaal in een wereld wonen waar de oude sloten en sleutels (de huidige cryptografie) binnenkort door een superkrachtige "kwantum-hack" opengebroken kunnen worden. Wiskundigen en cryptografen zijn daarom op zoek naar nieuwe, onkraakbare sloten. Een van de meest veelbelovende kandidaten is gebaseerd op isogenieën.

Wat zijn isogenieën? Stel je twee complexe, rijdende treinen voor (dit zijn de wiskundige krommen). Een isogenie is een soort "magische tunnel" die je van de ene trein naar de andere brengt. Het probleem is: als je alleen de starttrein en de eindtrein ziet, is het bijna onmogelijk om de tunnel te reconstructeren. Dit maakt het perfect voor beveiliging.

Het paper introduceert SQInstructor, een nieuwe, slimmere versie van een bestaand systeem (SQIsign). Laten we kijken hoe het werkt, met een paar leuke metaforen.

1. Het Oude Probleem: De "Vernietigende" Sleutel

In het oude systeem (SQIsign) moest de persoon die bewees dat hij de sleutel had (de "prover"), een tunnel bouwen die een specifiek punt op de trein vernietigde (naar nul bracht).

• De analogie: Stel je voor dat je een wachtwoord moet bewijzen door een specifieke bloem in een tuin te plukken en te verpletteren. Als je dat doet, weet de bewaker dat je de tuin kent.
• Het nadeel: Dit was lastig en soms traag om te berekenen. Het was alsof je een heel ingewikkeld recept moest volgen om die ene bloem te vinden en te verpletteren.

2. De Nieuwe Idee: De "Verplaatsende" Sleutel (Level Structures)

De auteurs van dit paper zeggen: "Waarom moeten we een bloem verpletteren? Waarom kunnen we hem niet gewoon verplaatsen naar een andere plek?"

Dit is het kernidee van SQInstructor. Ze gebruiken iets dat ze Level Structures noemen.

• De analogie: Stel je voor dat de trein niet alleen uit rails bestaat, maar ook uit een heel specifiek patroon van bloemen (een "niveau-structuur").
• In plaats van een bloem te verpletteren, zegt de uitdager (de "verifier"): "Ik heb een trein met een patroon van bloemen. Jij moet een tunnel bouwen die precies dat patroon naar een ander, specifiek patroon op mijn trein verplaatst."
• Het is alsof je een puzzel moet oplossen: "Neem dit specifieke patroon van bloemen en schuif het naar die andere plek." Als je het goed doet, bewijs je dat je de route kent, zonder dat je de bloemen hoeft te vernietigen.

3. Waarom is dit beter?

Dit klinkt misschien als een klein verschil, maar het opent de deur tot twee heel verschillende manieren om het probleem op te lossen:

• Manier A: De "Eén-Dimensionale" Route (De oude, vertrouwde weg)
  Je bouwt de tunnel stap voor stap, net als in de oude methoden. Dit is goed voor speciale toepassingen (zoals ringhandtekeningen, waar je anoniem wilt blijven), maar het is wat langzamer. Het is alsof je een tunnel graaft met een kleine schop.

• Manier B: De "Twee-Dimensionale" Route (De snelle, moderne weg)
  Hier gebruiken ze een trucje: in plaats van één tunnel te graven, graven ze twee tunnels tegelijk die in een vierkant patroon werken (een "Kani-diamant").

  • De analogie: In plaats van één smalle tunnel te graven, bouw je een snelweg met twee rijstroken die perfect op elkaar aansluiten. Dit is veel sneller en efficiënter.
  • Het paper laat zien dat je met deze methode net zo snel kunt zijn als de beste bestaande systemen, maar dan met de extra flexibiliteit van het verplaatsen van patronen.

4. De "Deuring Correspondentie": De Vertaalmachine

Het hele systeem rust op een wiskundig wonder genaamd de Deuring Correspondentie.

• De analogie: Stel je voor dat je een taal spreekt die heel moeilijk is (de taal van de treinen en tunnels). Er is echter een magische vertaalmachine die deze taal omzet in een heel eenvoudige taal (de taal van kwaternionen, een soort wiskundige getallen).
• In de eenvoudige taal zijn de puzzels makkelijk op te lossen. Je lost het probleem op in de "eenvoudige taal", en vertaalt het resultaat terug naar de "trein-taal".
• De auteurs van dit paper hebben deze vertaalmachine verbeterd. Ze hebben laten zien hoe je deze machine kunt gebruiken om niet alleen punten te verplaatsen, maar hele complexe patronen (level structures). Ze hebben zelfs nieuwe regels bedacht om de vertaling te doen, zelfs als de patronen heel groot en ingewikkeld zijn.

5. Wat betekent dit voor ons?

Dit paper is als een bouwhandleiding voor de volgende generatie digitale sloten.

• Het biedt een algemeen raamwerk: Je kunt kiezen welk type "patroon" je wilt gebruiken en welke "bouwmethode" (snel of veilig) je prefereert.
• Het is veilig: De auteurs hebben bewezen dat het net zo veilig is als de huidige top-systemen.
• Het is flexibel: Of je nu een snelle verificatie nodig hebt (voor een app) of een complexe anonieme handtekening (voor privacy), dit systeem kan het aan.

Samenvattend:
SQInstructor is een nieuwe manier om te bewijzen dat je de sleutel hebt, door in plaats van iets te vernietigen, een complex patroon te verplaatsen. Door slimme wiskundige vertalingen en het gebruik van snelle "twee-dimensionale" tunnels, maken ze dit proces zowel veilig als snel. Het is een belangrijke stap op weg naar een toekomst waarin onze digitale wereld veilig is tegen kwantumcomputers.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "The SQInstructor: a guide to SQIsign and the Deuring Correspondence with level structures" in het Nederlands.

Probleemstelling

Isogenie-based cryptografie is een veelbelovende kandidaat voor post-kwantum cryptografie. De huidige staat van de kunst, SQIsign, is de meest compacte signatuurschema die deelneemt aan het NIST-standaardisatieproces. Het schema is gebaseerd op de Deuring-correspondentie, een wiskundige equivalentie tussen supersinguliere elliptische krommen en orden van een quaternionalgebra.

Hoewel SQIsign zeer compacte handtekeningen biedt, heeft het enkele beperkingen:

1. Het ondertekingsproces is complex en traag, afhankelijk van het oplossen van kwadratische vergelijkingen in quaternionalgebra's (via het KLPT-algoritme).
2. Het bewijzen van EUF-CMA-beveiliging (Unforgeability under Chosen Message Attack) is intrinsiek moeilijk vanwege de beperkingen van het KLPT-algoritme.
3. Recentere verbeteringen gebruiken hoger-dimensionale (HD) isogenieën om de snelheid te verhogen, maar dit maakt het schema complexer.

De auteurs stellen dat het concept van level structuren (niveaustucturen), dat vaak impliciet in protocollen zoals SIKE en FESTA voorkomt, niet volledig is benut voor het generaliseren van SQIsign. Een level structuur is een basis van een torsie-subgroep van een elliptische kromme, gedefinieerd tot op een transformatie door een specifieke matrixgroep. Het huidige SQIsign kan worden gezien als een protocol waarbij een isogenie een specifieke level structuur (de kern van een uitdaging) naar nul moet afbeelden. De vraag is of men dit kan generaliseren: in plaats van een structuur te annuleren, kan de respons een isogenie zijn die één level structuur naar een andere afbeeldt?

Methodologie

Het artikel introduceert SQInstructor, een algemeen raamwerk dat de Deuring-correspondentie uitbreidt naar supersinguliere elliptische krommen met level structuren. De methode omvat de volgende stappen:

1. Generalisatie van de Deuring-correspondentie:
   De auteurs definiëren een nieuwe correspondentie tussen supersinguliere krommen met level structuren en specifieke orden (subringen) in de quaternionalgebra $B_{p,\infty}$. Ze tonen aan dat homomorfismen tussen krommen met level structuren corresponderen met linksidele idealen die voldoen aan extra restricties (afhankelijk van de gekozen level structuur, zoals Borel, Cartan of scalair).

2. Het SQInstructor Protocol:
   Dit is een Sigma-protocol voor identificatie dat als volgt werkt:

   • Sleutelgeneratie: De geheime sleutel is een ideaal $I_{sk}$ in een orde $O(E_0)$. De publieke sleutel is een kromme $E_{pk}$ met een level structuur $S_{pk}$.
   • Commitment: De bewijzer kiest een willekeurig ideaal en stuurt de bijbehorende kromme $E_{com}$ naar de verifieerder.
   • Uitdaging: De verifieerder kiest een willekeurige level structuur $S_{com}$ op $E_{com}$.
   • Respons: De bewijzer moet een isogenie $\phi_{rsp}$ construeren die $E_{pk}$ naar $E_{com}$ afbeeldt, zodanig dat de level structuur $S_{pk}$ wordt afgebeeld op $S_{com}$ (in plaats van naar nul).

3. Implementatievarianten:
   Het raamwerk wordt geïnstancieerd op twee manieren:

   • 1-dimensionale isogenieën: Gebruikmakend van het KLPT-algoritme (of varianten daarvan) om idealen met een "gladde" (smooth) norm te vinden. Dit vereist het oplossen van beperkte normvergelijkingen in de quaternionalgebra.
   • 2-dimensionale (HD) isogenieën: Gebruikmakend van moderne technieken (zoals in het recente SQIsign) om hogere snelheid te bereiken zonder KLPT, maar met een complexere representatie van de isogenie.

Belangrijkste Bijdragen

1. Expliciete Deuring-correspondentie met Level Structuren:
   De auteurs geven een expliciete constructie van de correspondentie voor supersinguliere krommen met level structuren, zelfs voor grote, niet-gladde niveaus. Ze definiëren de orden $O(E, S)$ voor verschillende types level structuren (Borel, gesplitste Cartan, scalair) en analyseren hun covolume en eigenschappen.

2. Het SQInstructor Framework:
   Een volledig nieuw identificatieprotocol dat de uitdaging en respons generaliseert tot het afbeelden van level structuren. Dit biedt flexibiliteit in het kiezen van het type level structuur en de implementatietechniek (1D of HD).

3. Algoritmen voor Beperkte Normvergelijkingen:
   Voor de 1-dimensionale variant hebben de auteurs nieuwe algoritmen ontwikkeld om beperkte normvergelijkingen op te lossen. Ze passen het bestaande KLPT-algoritme aan (via ScalarSigningKLPT en BorelSigningKLPT) om idealen te vinden die voldoen aan de level structuur-restricties. Ze presenteren een proof-of-concept implementatie hiervoor.

4. Hogere Dimensionale Instantiatie en Beveiliging:
   Ze analyseren een moderne instantiatie met 2-dimensionale isogenieën. Ze bewijzen de EUF-CMA-beveiliging onder aannames die vergelijkbaar zijn met die van SQIsign, maar nu binnen het nieuwe raamwerk. Ze gebruiken orakels (isogeny oracles) voor het bewijs van Zero-Knowledge.

5. Implementatie en Benchmarking:
   De auteurs hebben een implementatie gemaakt door de referentie-implementatie van SQIsign te fork-en. Ze vergelijken de prestaties van SQInstructor met SQIsign.

Resultaten

• Prestaties: De benchmarkresultaten (Tabel 3 in het artikel) tonen aan dat SQInstructor vergelijkbare prestaties levert als SQIsign. Er is een lichte toename in de grootte van de handtekening en de verificatietijd, wat wordt toegeschreven aan de langere (2,2)-isogenie-ketens die nodig zijn voor de level structuur-transformatie.
  • Voorbeeld (NIST I): SQInstructor heeft een signatuur van 174 bytes (vs 148 bij SQIsign) en verificatie van 6.0 Mcycles (vs 4.3).
• Sleutelgroottes: De publieke sleutels en handtekeningen blijven compact, vergelijkbaar met de huidige SQIsign-standaarden.
• Veiligheid: Het protocol is bewezen 2-special sound voor de relatie $R_{\Gamma}$-OneEnd, wat equivalent is aan het probleem van het vinden van een endomorfismenring. De kennisfout (knowledge error) wordt bepaald door de index van de level structuur-groep in $GL_2(\mathbb{Z}/N)$.

Betekenis en Impact

Deze paper is significant voor de post-kwantum cryptografie om de volgende redenen:

1. Generalisatie en Flexibiliteit: SQInstructor biedt een unificerend raamwerk dat laat zien dat SQIsign slechts een specifiek geval is van een breder concept (het afbeelden van level structuren). Dit opent de deur voor nieuwe varianten en optimalisaties.
2. Geavanceerde Primitieven: De 1-dimensionale variant van SQInstructor is cruciaal voor het implementeren van geavanceerde cryptografische primitieven zoals ring signatures en chameleon hashes, waarvoor de huidige HD-varianten van SQIsign minder geschikt zijn.
3. Beveiligingsbewijzen: Door de Deuring-correspondentie expliciet te generaliseren, kunnen de auteurs de beveiliging van het protocol steviger onderbouwen en nieuwe aannames over de output-distributie van algoritmen formuleren.
4. Praktische Toepasbaarheid: De implementatie toont aan dat het toevoegen van level structuren geen drastische prestatieverlies veroorzaakt. Het schema is dus direct inzetbaar als een alternatief of uitbreiding op bestaande NIST-candidaten.

Kortom, SQInstructor verrijkt het landschap van isogenie-based cryptografie door een elegante wiskundige generalisatie te bieden die zowel theoretisch inzicht als praktische implementatie-opties biedt voor toekomstige post-kwantum standaarden.