Technische Samenvatting: Complexiteit van het oplossen van stelsels vergelijkingen van dezelfde graad

Probleemstelling

De veiligheid van talrijke cryptografische schema's, met name in de multivariate cryptografie en post-quantum settings, rust op de computationele hardheid van het oplossen van stelsels van multivariate polynoomvergelijkingen over eindige velden. De complexiteit van het oplossen van dergelijke stelsels via Gröbner-basis-methoden wordt primair bepaald door de graad van regulariteit ($d_{reg}$) en de oplossingsgraad (solving degree). Hoewel de graad van regulariteit een bovengrens biedt voor de complexiteit van Gröbner-basis-berekeningen, is het vaak moeilijk om deze te berekenen of te schatten voor stelsels van cryptografische omvang.

In de praktijk wordt vaak vertrouwd op de heuristische aanname dat stelsels semiregulier (of cryptografisch semiregulier) zijn, wat expliciete formules oplevert voor de graad van regulariteit. Deze aanname is echter niet altijd geldig; er bestaan parameterkeuzes en velden waar geen semireguliere sequentie bestaat. Daarom is er behoefte aan bewezen, niet-heuristische bovengrenzen voor de graad van regulariteit en de oplossingsgraad die van toepassing zijn op stelsels waar de graad van regulariteit eindig is, zonder te vertrouwen op de semiregulariteitsaanname.

Methodologie

De auteurs benaderen het probleem met behulp van instrumenten uit de commutatieve algebra, waarbij zij zich specifiek richten op stelsels waarbij het ideaal gegenereerd door de hoogste-graad delen van de polynomen een reguliere sequentie bevat van $n$ polynomen in een gegeven graad $D$.

1. Kader: Het artikel beschouwt een stelsel $F = \{f_1, \dots, f_m\}$ van $m$ polynomen in $n$ variabelen over een veld $F$. De analyse gaat ervan uit dat de hoogste-graad delen $f_1^{top}, \dots, f_m^{top}$ lineair onafhankelijk zijn en dat het stelsel regulier is in graad $D$ (wat betekent dat het ideaal gegenereerd door de hoogste-graad delen een reguliere sequentie bevat van $n$ polynomen van graad $D$).
2. Reductie naar LPP-idealen: Om de Castelnuovo-Mumford-regulariteit te begrenzen (die gelijk is aan de graad van regulariteit wanneer deze eindig is), maken de auteurs gebruik van de Eisenbud-Green-Harris (EGH) Vermoeden. Dit vermoeden stelt dat, onder alle homogene idealen die een reguliere sequentie van specifieke graden bevatten, het Lex-Plus-Powers (LPP) ideaal de maximale regulariteit heeft.
3. Combinatorische Analyse: De auteurs construeren specifieke LPP-idealen geassocieerd met de gegeven parameters ($n, m, D$). Door de structuur van deze idealen onder de lexicografische ordening te analyseren, bepalen zij de regulariteit van het LPP-ideaal, wat dient als een bovengrens voor de regulariteit van het oorspronkelijke stelsel (onder de voorwaarde van het EGH-vermoeden).
4. Veldvergelijkingen: De methodologie wordt uitgebreid naar stelsels die zijn aangevuld met veldvergelijkingen ($x_i^q - x_i$), wat cruciaal is voor stelsels over eindige velden $\mathbb{F}_q$, met name wanneer de graad van de vergelijkingen $D$ groter dan of gelijk is aan de veldgrootte $q$.

Belangrijkste Bijdragen en Resultaten

1. Bovengrenzen voor stelsels die regulier zijn in graad $D$ (Zonder veldvergelijkingen)

Theorem 23 biedt een scherpe bovengrens voor de graad van regulariteit van een stelsel van $m$ vergelijkingen van graad $D$ in $n$ variabelen, uitgaande van het feit dat het stelsel regulier is in graad $D$.

• De grens hangt af van het aantal vergelijkingen ($m$), variabelen ($n$) en graad ($D$).
• De formule omvat het identificeren van unieke gehele getallen $k$ en $t$ zodanig dat $m-n$ binnen een specifiek interval valt dat wordt gedefinieerd door combinatorische sommen ($\sigma_{k,t}$).
• De resulterende grens is: $d_{reg}(F) \le (D - t) + (n - k)(D - 1)$.
• Deze grens is scherp voor alle waarden van $m, n, D$ en wordt behaald door stelsels waarbij de hoogste-graad delen een specifiek LPP-ideaal vormen.

Corollary 27 vertaalt dit naar een bovengrens op de oplossingsgraad voor mutant-algoritmen:
$$\text{solv. deg}_m(F) \le D - t + 1 + (n - k)(D - 1)$$

2. Bovengrenzen voor stelsels met veldvergelijkingen

Het artikel behandelt het geval waarbij veldvergelijkingen aan het stelsel worden toegevoegd, wat essentieel is wanneer $D \ge q$.

• Proposition 31: Voor zeer overgedetermineerde stelsels (waarbij $m$ de dimensie van de ruimte van polynomen modulo de veldvergelijkingen overschrijdt), is de graad van regulariteit exact $D$.
• Theorem 33: Voor stelsels waarbij $q \le D \le n(q-1)$ en de hoogste-graad delen lineair onafhankelijk zijn modulo de veldvergelijkingen, bieden de auteurs een bovengrens voor de graad van regulariteit.
  • De grens wordt afgeleid door de positie van het $m$-de monoom in de lexicografische ordening van graad $D$ monomen modulo $(x_1^q, \dots, x_n^q)$ te analyseren.
  • De grens wordt uitgedrukt in termen van $B = q - t + (n - k)(q - 1)$, waarbij $k$ en $t$ worden bepaald door het interval dat $m$ bevat.
  • Afhankelijk van specifieke condities betreffende $m, D,$ en $t$, is de grens ofwel $B$ of $B-1$.

Corollary 34 specialiseert deze resultaten voor binaire stelsels ($q=2$), wat vereenvoudigde formules oplevert voor de graad van regulariteit en de oplossingsgraad voor stelsels van graad $D$ over $\mathbb{F}_2$.

3. Toepassing op Specifieke Schema's

De auteurs passen hun grenzen toe op concrete cryptografische schema's:

• Cubic Simple Matrix: Zij leiden een bewezen grens af van $d_{reg} \le 2n - 1$, wat de eerste bewezen grens is voor dit stelsel, in contrast met eerdere heuristische schattingen.
• Unbalanced Oil and Vinegar (UOV): De grenzen worden toegepast op UOV-stelsels over $\mathbb{F}_2$, waarbij wordt aangetoond hoe de graad van regulariteit zich gedraagt wanneer veldvergelijkingen worden meegenomen.

Betekenis en Claims

Het artikel claimt met name significant te zijn door het leveren van bewezen, niet-heuristische grenzen voor de complexiteit van het oplossen van polynoomstelsels.

• Betrouwbaarheid: In tegen tegenstelling tot schattingen gebaseerd op de semiregulariteitsaanname (die kunnen falen voor bepaalde parameters), zijn deze grenzen van toepassing op elk stelsel waar de graad van regulariteit eindig is en het stelsel regulier is in een gegeven graad.
• Generaliteit: De resultaten zijn van toepassing op stelsels over willekeurige velden en dekken zowel de gevallen met als zonder veldvergelijkingen.
• Scherpte: De grenzen worden als "scherp" beschreven, wat betekent dat ze worden behaald door specifieke stelsels (LPP-idealen), wat een realistische inschatting van het slechtste scenario biedt voor veiligheidsanalyse.
• Beperkingen: De auteurs erkennen expliciet dat hun grenzen over het algemeen minder nauw (d.w.z. hoger) zijn dan die verkregen onder de semiregulariteitsheuristiek. Zij stellen echter dat deze afruil noodzakelijk is om onbewezen aannames te vermijden, met name in scenario's waar geen semireguliere sequenties bestaan.

Het werk stelt geen nieuwe algoritmen of experimentele implementaties voor, maar vestigt de theoretische limieten op de complexiteit van bestaande Gröbner-basis-methoden (zowel standaard als mutant) voor een brede klasse van polynoomstelsels die relevant zijn voor de cryptografie.