Attacks on Sparse LWE and Sparse LPN with new Sample-Time tradeoffs

Probleemstelling

Het artikel richt zich op de cryptografische hardheid van varianten van de Learning With Errors (LWE) en Learning Parity with Noise (LPN) problemen, specifiek wanneer de steekproefvectoren sparse (spaarzaam) zijn.

• Sparse LWE/LPN: In plaats van dat de steekproefvectoren $a \in \mathbb{Z}_q^n$ willekeurig zijn, hebben ze slechts $k$ niet-nul elementen, waarbij $k \ll n$.
• Context: Deze varianten worden gebruikt om cryptografische primitieven te versnellen (kleinere sleutels, snellere berekeningen). Echter, de hardheid van deze varianten, vooral voor grotere moduli $q$ (niet alleen $q=2$), is minder goed onderzocht dan de standaardversies.
• Doel: Het analyseren van de complexiteit (sample- en tijdcomplexiteit) om te bepalen of een gegeven instance "geplant" is (met een geheime oplossing en ruis) of "willekeurig". Dit is het beslissingsprobleem (decisional problem).

Methodologie: De Kikuchi-methode voor $q > 2$

De auteurs generaliseren de Kikuchi-methode, die eerder succesvol was toegepast op $k$-XOR ($q=2$) door Wein et al. en Gupta et al., naar het geval van hogere moduli $q$.

1. Transformatie naar Productvergelijkingen:

   • Lineaire vergelijkingen over $\mathbb{Z}_q$ worden herschreven als productvergelijkingen over de groep van $q$-de eenheidswortels $\Omega_q = \{e^{2\pi i s/q} : s \in \mathbb{Z}_q\}$.
   • Een $k$-spaarzame vergelijking wordt getransformeerd naar een reeks $2$-spaarzame vergelijkingen in een verhoogde dimensie.
   • De ruimte wordt uitgebreid van subsets van $[n]$ naar subsets van index-coëfficiënt paren: $\binom{[n]}{l} \times [q]^l$, waarbij $l \geq k/2$ een parameter is die de trade-off tussen samples en tijd bepaalt.

2. Constructie van de Kikuchi-graf:

   • Er wordt een gerichte graf $K_l(I)$ geconstrueerd. De knopen zijn de elementen van de verhoogde ruimte.
   • Voor elke constraint (vergelijking) in de instance worden randen toegevoegd tussen knopen die een specifieke relatie (een veralgemeende symmetrische verschil) delen.
   • Om de spectrale analyse mogelijk te maken, wordt de graf symmetrisch gemaakt door voor elke rand $T \xrightarrow{b} T'$ ook de rand $T' \xrightarrow{b^*} T$ toe te voegen, waardoor de burenmatrix Hermitisch wordt.

3. Twee Aanvalsmethoden:
   De auteurs gebruiken deze graf voor twee verschillende aanvalstechnieken:

   • Spectrale Methode: Bereken de spectrale norm (de grootste eigenwaarde) van de burenmatrix van de Kikuchi-graf.
   • q-ary Cover Methode (Gesloten Wandelingen): Zoek naar niet-triviale gesloten wandelingen in de graf. Deze corresponderen met "q-ary covers" (multisets van constraints die lineair afhankelijk zijn modulo $q$).

Kernbijdragen en Resultaten

De paper levert algoritmen die nieuwe trade-offs bieden tussen het aantal benodigde steekproeven ($m$) en de tijdcomplexiteit, afhankelijk van de parameter $l$.

1. Spectrale Methode (Theorema 5.20 & 5.21)

• Principe: In een willekeurige instance is de verwachte spectrale norm laag (rond 0), terwijl in een geplaagde instance de norm significant hoger is (gerelateerd aan de ruisvariatie $\rho$).
• Resultaat:
  • Voor Sparse LWE: Een algoritme dat werkt voor elke ruisverdeling (zolang deze geconcentreerd rond 0 is). Tijdcomplexiteit: $\tilde{O}(\binom{n}{l} q^l)$.
  • Voor Sparse LPN: Werkt voor de specifieke LPN-ruisverdeling.
• Voordeel: Geen aannames nodig over de primaliteit van $q$ of een ondergrens voor $q$. Werkt voor willekeurige ruisverdelingen.
• Nadeel: Vereist dat de linkerhandkanten van de vergelijkingen uniform willekeurig zijn.

2. q-ary Cover Methode (Theorema 6.15 & 6.20)

• Principe: Zoek naar gesloten wandelingen in de Kikuchi-graf die corresponderen met een $q$-ary cover $c$ (waarbij $\sum c_i \cdot \text{coëfficiënten} \equiv 0 \pmod q$).
  • Voor Sparse LWE (beperkte ruis): Bereken $c^T \beta$. In een geplaagde instance is dit klein (beperkt door de ruisgrootte), in een willekeurige instance is het uniform verdeeld over $\mathbb{Z}_q$.
  • Voor Sparse LPN: Gebruik een anti-concentratie resultaat voor polynomen van de ruisvariabelen. Omdat de ruis uniform is over niet-nul elementen, gedraagt het product zich anders dan in de willekeurige case.
• Resultaat:
  • Biedt een kwalijk kwadratische snelheidswinst ten opzichte van de spectrale methode voor dezelfde sample-complexiteit (vooral wanneer $l \gg k$).
  • Werkt zelfs als de linkerhandkanten niet uniform willekeurig zijn (worst-case links).
• Beperkingen: Vereist dat $q$ een priemgetal is. Voor LWE is een ondergrens nodig op $q$ ten opzichte van de ruisbreedte ($q \gg r(l \log n)^{3/2}$).

Significantie en Implicaties

1. Verfijning van Hardheidsvermoedens:
   De auteurs testen het vermoeden van Jain, Lin en Saha (JLS24) dat Sparse LWE met $k = \Omega(\log n)$ en polynoomiale samples net zo hard is als standaard LWE.

   • Hun resultaten tonen aan dat als $k = O(\log n / \log \log n)$ of als men iets meer dan polynoomiale samples toestaat, het probleem in sub-exponentiële tijd (bijv. $2^{\delta n}$) opgelost kan worden.
   • Dit suggereert dat de hardheid van Sparse LWE afhangt van de precieze keuze van $k$ en $m$, en dat de JLS24-conjectuur "tight" is, maar dat er een kleine ruimte is voor aanval.

2. Nieuwe Trade-offs:
   De paper introduceert een parameter $l$ die het mogelijk maakt om te schakelen tussen sample-complexiteit en tijdcomplexiteit.

   • Meer samples $\rightarrow$ Lagere tijd.
   • Minder samples $\rightarrow$ Hogere tijd.
     Dit biedt cryptografen meer inzicht in de veiligheidsmarges bij het kiezen van parameters voor cryptosystemen die op sparse LWE/LPN zijn gebaseerd.

3. Quantum Speedup:
   De spectrale methode heeft een bekende quantum-versnelling (via het schatten van eigenwaarden), wat een extra kwadratische tot kwartieke snelheidswinst kan opleveren. De auteurs noteren dat dit ook voor hun generalisatie naar $q > 2$ geldt.

Conclusie

Dit werk breidt de Kikuchi-methode uit naar hogere moduli en biedt twee krachtige aanvalstechnieken voor sparse LWE en LPN. Ze tonen aan dat de hardheid van deze problemen gevoeliger is voor parameters dan eerder gedacht, en leveren concrete algoritmen die nieuwe grenzen stellen aan de benodigde samples en rekentijd. De resultaten zijn relevant voor het ontwerpen van efficiënte cryptosystemen (zoals FHE) die op deze varianten vertrouwen, en waarschuwen voor de noodzaak van zorgvuldige parameterkeuze om kwetsbaar te zijn voor deze nieuwe aanvalsmethoden.