An alternative approach towards attacks against fully-split PLWE instances

Technische Samenvatting: Een alternatieve benadering van aanvallen op volledig gesplitste PLWE-instanties

Probleemstelling
Het Polynomial Learning With Errors (PLWE) probleem is een hoeksteen van de post-kwantum cryptografie en wordt vaak verkozen boven Ring-LWE vanwege de efficiënte structurele algebraïsche eigenschappen. Deze structuur introduceert echter potentiële kwetsbaarheden. Eerdere werken, met name [5, 6] en gegeneraliseerd in [2], introduceerden "wortel-gebaseerde aanvallen" die gebruikmaken van het bestaan van specifieke polynoomfactoren (bekend als $n$-ideale factoren, $x^n - a$) over eindige velden. Deze aanvallen maken gebruik van evaluatiehomomorfismen en trace-operatoren om PLWE-samples te onderscheiden van uniforme distributies.

Hoewel [2] deze aanvallen heeft gegeneraliseerd naar polynomen die factoriseren over veldextensies, bleef een cruciale open vraag bestaan: zou een aanvaller een gebrek aan kwetsbare factoren in een "veilige" PLWE-instantie kunnen omzeilen door deze via een ring-isomorfisme te mappen naar een "kwetsbare" instantie (één die geschikte $n$-ideale factoren bezit), de aanval daar uit te voeren, en de veiligheid van de oorspronkelijke instantie af te leiden? Dit artikel onderzoekt of een dergelijke migratiestrategie via isomorfismen een betekenevol voordeel biedt tegen volledig gesplitste PLWE-instanties.

Methodologie
De auteurs hanteren een rigoureuze algebraïsche benadering om de haalbaarheid van het overdragen van PLWE-samples tussen verschillende polynoomringen te analyseren. De methodologie verloopt in twee hoofdfasen:

1. Generalisatie van willekeurige factorisatie: Het artikel onderzoekt eerst de uitbreiding van wortel-gebaseerde aanvallen naar polynomen zonder $n$-ideale factoren. Door gebruik te maken van Lemma 1, tonen de auteurs aan dat trace-operatoren gedefinieerd kunnen worden over willekeurige irreducibele factoren. Ze laten echter zien dat het succespercentage van dergelijke aanvallen sterk afhankelijk is van het aantal nul-waarden in de coëfficiënten van de factor, wat voor willekeurige polynomen doorgaans laag is, waardoor de aanval in het algemene geval onpraktisch is.

2. Isomorfisme-analyse in volledig gesplitste settings: De kern van het werk richt zich op de "isomorfisme-benadering". De auteurs beschouwen twee polynomen, $f(x)$ en $g(x)$, beide van graad $N$ en irreducibel over $\mathbb{Z}[x]$, die dezelfde "factorisatiestructuur" delen over $\mathbb{F}_q$ (dat wil zeggen, ze ontleden in irreducibele factoren van dezelfde graden).

   • Constructie: Met behulp van de Chinese Reststelling construeren zij een expliciet isomorfisme $\psi$ tussen de ringen $R_q = \mathbb{F}_q[x]/(f(x))$ en $R'_q = \mathbb{F}_q[x]/(g(x))$. In het volledig gesplitste geval (waar beide polynomen volledig ontleden in lineaire termen), wordt dit isomorfisme gerepresenteerd door het product van Vandermonde-matrices: $\psi = V_g^{-1} \cdot V_f$.
   • Distortie-analyse: De auteurs analyseren het effect van het toepassen van dit isomorfisme op PLWE-samples, gevolgd door een evaluatie in een wortel $\beta$ van $g(x)$. Zij bewijzen dat deze evaluatie wiskundig equivalent is aan de evaluatie van het oorspronkelijke sample in een overeenkomstige wortel $\alpha$ van $f(x)$.
   • Uniciteitbewijs: Een aanzienlijk deel van de methodologie betreft het bewijzen dat elk ring-isomorfisme tussen dergelijke volledig gesplitste polynoomringen deze specifieke vorm moet hebben (de compositie van evaluatiehomomorfismen en het geconstrueerde isomorfisme). Dit wordt vastgesteld via Lemma's 2, 3 en 4, en Stelling 1.

Belangrijkste Bijdragen

• Formeel Bewijs van Isomorfisme-invariantie: Het artikel levert een formeel bewijs dat voor volledig gesplitste PLWE-instanties elk poging om samples naar een kwetsbare setting te migreren via een ring-isomorfisme geen nieuwe kwetsbaarheden oplevert. De ruis (error) die door het isomorfisme wordt geïntroduceerd, vervormt de samples zodanig dat de resulterende onderscheidbaarheidscondities identiek zijn aan die van de oorspronkelijke instantie.
• Karakterisering van Ring-isomorfismen: De auteurs karakteriseren de volledige verzameling isomorfismen tussen volledig gesplitste polynoomringen, waarbij zij aantonen dat deze uniek bepaald worden door de mapping van de wortels. Dit bewijst dat er geen "verborgen" isomorfisme bestaat dat de ruis-vervorming zou kunnen omzeilen.
• Uitbreiding naar Willekeurige Factorisatie: Het werk verheldert dat, hoewel wortel-gebaseerde aanvallen theoretisch toegepast kunnen worden op polynomen zonder $n$-ideale factoren, het gebrek aan structurele beperkingen (specifiek het aantal nul-coëfficiënten) hun succespercentage ernstig beperkt, wat de deur naar een praktische dreiging effectief sluit.

Resultaten

• Ruis-vervorming: De toepassing van een isomorfisme $\psi$ gevolgd door een evaluatie in een wortel $\beta$ van $g(x)$ resulteert in de uitdrukking $b(\beta) = \sum a_j \alpha^j$, waarbij $\alpha$ de overeenkomstige wortel is van $f(x)$. Dit demonstreert dat de aanval op de getransformeerde setting wiskundig identiek is aan de aanval op de oorspronkelijke setting.
• Falen van de Migratiestrategie: De analyse bevestigt dat als een wortel-gebaseerde aanval faalt op de oorspronkelijke PLWE-instantie (door hoge ruis of gebrek aan onderscheidbaarheid), deze ook zal falen op elke isomorfe instantie. Het isomorfisme "reinigt" de ruis niet, maar behoudt de onderliggende moeilijkheid van het probleem.
• Specifieke Wortel-analyse: Het artikel analyseert specifieke gevallen waar de evaluatie-wortel $\beta$ gelijk is aan $0$, $1$, of een willekeurige wortel. In alle gevallen reduceert de resulterende evaluatie tot de evaluatie van de oorspronkelijke polynoom in een overeenkomstige wortel, wat bevestigt dat er geen voordeel wordt behaald.

Betekenis
Het artikel concludeert dat de intuïtie met betrekking tot de veiligheid van volledig gesplitste PLWE-instanties correct is: als wortel-gebaseerde aanvallen niet succesvol zijn tegen een initiële PLWE-instantie, zullen ze ook niet succesvol zijn als de samples naar een potentieel zwakkere PLWE-setting worden overgedragen via ring-isomorfismen.

Dit resultaat biedt een bron van vertrouwen voor de veiligheid van volledig gesplitste PLWE-instanties, die vanwege hun efficiëntie (bijv. door Number Theoretic Transforms) veel voorkomen in cryptografische constructies. Het werk sluit de "isomorfisme-migratie" effectief uit als een levensvatbare vector voor het genereren van nieuwe aanvallen tegen deze specifieke instanties. De auteurs merken op dat hoewel deze analyse specifiek is voor volledig gesplitste polynomen, het de overgrote meerderheid van de cryptografisch relevante PLWE-instanties beslaat. Het artikel claimt niet de veiligheid van niet-volledig gesplitste instanties of andere aanvalvectoren (zoals de Stickelberger-ideaal aanvallen vermeld in de introductie) op te lossen, maar verstevigt het begrip van wortel-gebaseerde aanvallen binnen het volledig gesplitste domein.