SNOVAS

SNOVA

SNOVA is een algoritme voor digitale handtekeningen dat is geselecteerd voor de derde ronde van het NIST-project voor post-quantumcryptografie. De huidige versie dateert van augustus 2026.

Over SNOVA

SNOVA is een variant van de Unbalanced Oil and Vinegar (UOV)-handtekeningenfamilie en is ontworpen om over niet-commutatieve ringen te werken teneinde een hogere efficiëntie en een kleinere omvang van de publieke sleutel te bereiken. Traditionele UOV-schema's hebben te kampen hebben met zeer grote publieke sleutels. Dit wordt door SNOVA effectief opgelost.

Naar aanleiding van de cryptanalyse tijdens rondes 1 en 2 is het SNOVA-schema voor de ronde 3 inzending opnieuw geformuleerd om tot een flexibeler raamwerk te komen. Recent onderzoek laat zien dat SNOVA kan worden gekarakteriseerd als het toepassen van een whipping-transformatie, vergelijkbaar met die van MAYO, op een gestructureerde publieke UOV-sleutel die gebruikmaakt van de F_q[S]-structuur. Omdat de ring F_q[S] isomorf is met het uitbreidingslichaam F_(q^l), is dit ontwerp te vergelijken met de techniek van polynoommatrices die in QR-UOV wordt toegepast.

De herformulering voor ronde 3 breidt de handtekening uit naar rechthoekige matrices. Dit levert een schema op dat door zeven parameters wordt gedefinieerd: (v, o, q, l, r, m_1, m_2). Hierdoor kan de whipping-dimensie r een onafhankelijke parameter zijn die losstaat van l, en kan het aantal vergelijkingen m_2 onafhankelijk van het aantal matrices van de publieke sleutel m_1 worden gekozen. Deze herformulering biedt veiligheidsvoordelen en veel meer flexibiliteit bij de parameterkeuze, maar is wel volledig compatibel met de ronde 2 versie.

Voordelen

  • Als multivariaat handtekeningschema behoudt SNOVA de kenmerkende korte handtekeningen, maar vermindert het wel het nadeel van de grote publieke sleutel die traditionele multivariate schema's kennen. SNOVA biedt op alle veiligheidsniveaus kleinere publieke sleutels en kleinere handtekeningen dan Falcon.
  • Bescheiden hardware eisen en snelle verificatie. Het ondertekenen en het verifiëren zijn geïmplementeerd met eenvoudige bewerkingen op matrices over eindige lichamen. Deze bewerkingen kunnen op moderne processors efficiënt worden geïmplementeerd met AVX2 en GFNI-instructies.
  • Grote flexibiliteit in de parameters en een ruime veiligheidsmarge. De ronde 3 versie van SNOVA ondersteunt rechthoekige handtekeningen. Het resulterende raamwerk wordt beschreven door zeven parameters: (v,o,q,l,r,m_1,m_2). Deze parameters bieden aanzienlijke flexibiliteit om de omvang van de publieke sleutel, de omvang van de handtekening, de rekenprestaties en de weerstand tegen bekende aanvallen tegen elkaar af te wegen. Ook maken ze het mogelijk om conservatieve parametersets te kiezen met veiligheidsmarges die de minimumeisen van de beoogde NIST-veiligheidsniveaus ruimschoots overtreffen.
  • Hoewel SNOVA conceptueel is opgebouwd met niet-commutatieve matrixringen, bestaan de concrete bewerking voornamelijk uit standaard lineaire algebra over eindige lichamen. Onze SageMath-versie reproduceert de officiële SNOVA-KAT-bestanden in minder dan 600 regels broncode. SNOVA kan worden gezien als een constructie van het UOV-type, aangevuld met een niet-commutatieve matrixstructuur. Daardoor blijft het schema conceptueel toegankelijk en leent het zich voor gedetailleerde analyse op algebraïsch niveau en op implementatieniveau.

Prestaties

De volgende tabel toont de prestaties van de voorgestelde SNOVA-instanties. De omvang is uitgedrukt in bytes en de prestaties in klokcycli, gemeten op een modern desktopsysteem met ondersteuning voor AVX2 en GFNI (Intel Core Ultra 7 265K).

SL I

VariantpksksigKeyGenSignVerify
SNOVA_I_K37696528159,618584,188166,666
SNOVA_I_K_AES3769652887,169512,00494,164
SNOVA_I_B65696388170,468557,746141,919
SNOVA_I_B_AES65696388102,661489,98374,376
SNOVA_I_S101696272204,195397,921149,024
SNOVA_I_S_AES101696272132,758325,41878,305

SL III

VariantpksksigKeyGenSignVerify
SNOVA_III_K91296688416,4901,240,034349,462
SNOVA_III_K_AES91296688243,3111,061,262175,688
SNOVA_III_B141696532484,6261,226,638335,912
SNOVA_III_B_AES141696532303,6221,045,116156,118
SNOVA_III_S203296456562,0691,333,170356,953
SNOVA_III_S_AES203296456372,1651,141,612167,684

SL V

VariantpksksigKeyGenSignVerify
SNOVA_V_K121696896811,6802,573,021684,735
SNOVA_V_K_AES121696896548,9982,301,728424,527
SNOVA_V_B189196691955,4442,470,611679,221
SNOVA_V_B_AES189196691682,8232,192,284409,444
SNOVA_V_S2716965911,101,9532,619,986749,582
SNOVA_V_S_AES271696591823,1542,341,503465,939

Referenties

Team

Indiener

  • Lih-Chung Wang

Teamleden (in alfabetische volgorde)

  • Chun-Yen Chou
  • Jintai Ding
  • Hao Guo
  • Yen-Liang Kuan
  • Jan Adriaan Leegwater
  • Ming-Siou Li
  • Peigen Li
  • Bo-Shu Tseng
  • Po-En Tseng
  • Chia-Chun Wang

Contact