Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields

Titel: Cryptanalyse van de Legendre Pseudorandom Function over Uitbreidingsvelden

Auteur: Daksh Pandey (Indian Institute of Technology, Roorkee)

1. Probleemstelling

De Legendre Pseudorandom Function (PRF) is een efficiënt cryptografisch primitief dat veel wordt gebruikt in Multi-Party Computation (MPC) en Zero-Knowledge Proof (ZKP) protocollen vanwege zijn lage multiplicatieve complexiteit. Traditioneel wordt deze PRF geïmplementeerd over priemvelden ($\mathbb{F}_p$). Om de doorvoer in specifieke protocollen te optimaliseren, is er echter een verschuiving naar instantiaties over uitbreidingsvelden ($\mathbb{F}_{p^r}$).

Hoewel de veiligheid over $\mathbb{F}_p$ goed onderzocht is, ontbreekt er tot nu toe een grondige analyse van de veiligheid van de Legendre PRF over $\mathbb{F}_{p^r}$, specifiek voor de single-degree variant (waarbij de sleutel een enkel polynoom is). Dit paper onderzoekt of de overgang naar uitbreidingsvelden daadwerkelijk de bekende kwetsbaarheden (zoals sliding-window collision attacks) neutraliseert of juist nieuwe, fundamentele zwaktes introduceert.

2. Methodologie

De auteur analyseert de structuur van de PRF onder twee verschillende dreigingsmodellen:

A. Passief Dreigingsmodel (Sequential Additive Queries)

• Context: De server genereert een keystream door de PRF toe te passen op een sequentieel oplopende integer teller $n$, die wordt gecodeerd als een polynoom $X_n$ in $\mathbb{F}_{p^r}$ via basis-$p$ expansie.
• Observatie: In $\mathbb{F}_p$ is het verschil tussen opeenvolgende inputs constant ($\Delta = 1$). In $\mathbb{F}_{p^r}$ echter, veroorzaakt de polynomiale optelling (coëfficiëntsgewijs modulo $p$) geen "dragen" (carry-over) naar hogere graden zoals bij integer-optelling. Dit leidt tot een asynchrone "no-carry fracture": het verschil $\Delta_n = X_{n+1} \oplus X_n$ is niet constant, maar varieert afhankelijk van de $p$-adische waardering van $n$.
• Analyse: Hoewel deze fractuur klassieke collision attacks verstoort, is de reeks van verschillen deterministisch en periodiek. De auteur introduceert een nieuwe techniek genaamd "Differential Signature" bucketing. Hierbij worden gebroken sequentiewindows gegroepeerd op basis van hun structurele vorm (het patroon van de verschillen).

B. Actief Dreigingsmodel (Chosen-Query)

• Context: Een aanvaller kan zelf inputs kiezen. In plaats van een additieve reeks, kiest de aanvaller een geometrische reeks gegenereerd door een primitief element $g(x)$ van de multiplicatieve groep $\mathbb{F}_{p^r}^*$.
• Analyse: De Legendre-symboolfunctie is volledig multiplicatief. Door de input als $g^i$ te kiezen, kan de evaluatie $L(g^i + K)$ algebraïsch worden ontbonden (gefactoreerd) in een constante afhankelijk van de sleutel en een universele, sleutel-onafhankelijke referentiereeks. Dit omzeilt de additieve beperkingen volledig en herstelt de homomorfisme-eigenschappen die nodig zijn voor efficiënte aanvalstechnieken.

3. Belangrijkste Bijdragen en Resultaten

Resultaat 1: Passieve Sleutelherwinning

Ondanks de "no-carry fracture" is de single-degree Legendre PRF kwetsbaar voor passieve aanvallen.

• Methode: Door de keystream te analyseren en windows te clusteren op basis van hun "Differential Signature", kan een aanvaller de gebroken sequenties herstructureren.
• Complexiteit: De sleutel $K$ kan passief worden herwonnen met een complexiteit van $O(U \cdot p^r / M)$, waarbij $U$ de unicity distance is en $M$ het aantal geobserveerde bits. Dit betekent dat de fractuur de veiligheid niet garandeert, maar slechts de complexiteit licht verhoogt ten opzichte van een directe aanval.

Resultaat 2: Actieve Sleutelherwinning (Geometrische Aanval)

In een actief model is de single-degree PRF fundamenteel onveilig.

• Methode: Door de PRF te bevragen met een geometrische reeks ($g^i$), wordt de sleutel $K$ gereduceerd tot een discrete logaritme-probleem (een verschuiving $j$ in de exponent).
• Complexiteit: De aanvaller kan de geheime sleutel volledig omzeilen en herwinnen in $O(p^r / M)$ operaties. Dit is een lineaire complexiteit ten opzichte van de veldgrootte, wat betekent dat de PRF effectief is "gebroken" in dit model.

Resultaat 3: Noodzaak van Hogere Gradaties

Het paper concludeert dat de single-degree variant ($d=1$) onveilig is over uitbreidingsvelden.

• Oplossing: De auteur toont aan dat het gebruik van hogere graad varianten ($d \geq 2$), waarbij de sleutel bestaat uit meerdere polynoomcoëfficiënten (bijv. $K(x) = x^2 + K_1x + K_0$), de algebraïsche factorisatie onmogelijk maakt.
• Veiligheidsmarge: Voor $d \geq 2$ wordt de $O(p^r/M)$ aanval geneutraliseerd. Hoewel geoptimaliseerde zoektochten (zoals Meet-in-the-Middle) mogelijk blijven, is een graad van $d \geq 3$ of $4$ noodzakelijk om een exponentiële veiligheidsmarge te behouden tegen structurele reductie.

4. Significatie en Conclusie

Dit paper levert de eerste uitgebreide cryptanalyse van de Legendre PRF over uitbreidingsvelden en weerlegt de veronderstelling dat de "no-carry" eigenschap van polynoomoptelling voldoende bescherming biedt tegen collision attacks.

• Fundamentele Inzichten: De studie toont aan dat deterministische periodiciteit in polynoom-encoding kwetsbaarheden creëert die passief uitgebuit kunnen worden, en dat multiplicatieve homomorfieën in uitbreidingsvelden actief kunnen worden gebruikt om de sleutelstructuur te onthullen.
• Praktische Implicatie: Voor implementaties in MPC en ZKP-systemen die uitbreidingsvelden gebruiken, is de standaard single-degree Legendre PRF niet veilig.
• Aanbeveling: Toekomstige implementaties moeten verplicht gebruikmaken van hogere graad varianten ($d \geq 2$, bij voorkeur $d \geq 3$) om algebraïsche reducties te voorkomen en een robuuste cryptografische veiligheid te garanderen.

De broncode voor de beschreven aanvallen is open source beschikbaar gesteld, wat verdere verificatie en onderzoek door de gemeenschap mogelijk maakt.