O întrebare pentru începători despre NTRUEncrypt: r(x) mic și cea mai apropiată problemă vectorială

În NTRUEncrypt cu parametri la nivelul întregului sistem $(N, p, q)$, să fie cheia publică a lui Bob $h(x).$

Pentru a cripta textul simplu $m(x)$ ai căror coeficienți sunt mici, Alice trebuie să genereze o aleatorie $r(x),$ ai cărui coeficienți trebuie să fie și ei mici și calculează text cifrat $c(x) = r(x) \times h(x) + m(x) \bmod q.$

Se consideră greu de găsit $m(x)$ din $c(x)$ și această dificultate se bazează probabil pe problema celui mai apropiat vector (CVP).

Întrebarea mea este: de ce $r(x)$ trebuie să aibă coeficienți mici în criptare? Se pare că chiar şi când $r(x)$ are coeficienți mari, constatând $m(x)$ din $c(x)$ este încă legat de problema CVP; este adevărat?

Intenția în realizarea coeficienților de $r(x)$ mic nu este acela de a face viața grea atacatorului, ci de a face viața posibilă destinatarului vizat.

Amintește-ți asta $h(X)$ este ales să fie de formă $$h(X)\equiv \frac{g(X)p}{f(X)}\pmod q$$ unde coeficienții de $f(X)$ și $g(X)$ sunt mici și secrete, $p$ este un prim mic relativ la $q$ și $q$ este mare în raport cu toate cantitățile mici.

Acum luați în considerare decriptare care începe cu înmulțirea a $c(X)$ de $f(X)$ a da $$c(X)f(X)\equiv r(X)g(X)p+m(X)f(X)\pmod q$$ dacă coeficienţii de $f$, $g$, $m$ și $r$ sunt toate mici, atunci cu mare probabilitate putem scrie $$c(X)f(X)= r(X)g(X)p+m(X)f(X)$$ peste numerele întregi fără modul de reducere $q$ prin rotunjirea coeficienților spre 0 (adică constrângerea în interval $[-q/2,q/2]$). Pe de altă parte, dacă $r(X)$ are orice mare (în raport cu $q$), aproape sigur că nu putem face acest lucru.

Dacă procesul nostru de rotunjire are succes, atunci putem elimina contribuția $r(X)$ prin reducerea modulo $p$ și apoi recuperați $m(X)$.

Rețineți că procesul de rotunjire nu este garantat a avea succes pe măsură ce gradul crește și astfel NTRUEncrypt are o probabilitate de eșec dependentă de mărimea și gradul coeficientului și pe care trebuie să încercăm să o menținem la un nivel scăzut. Rețineți, de asemenea, că eșecul poate depinde de alegerea $m(X)$ ceea ce poate permite unui atacator să obțină în mod activ informații despre cheia privată (din nou cu o probabilitate pe care încercăm să o păstrăm mică).

ai dreptate ca $r(X)\pmod q$ poate fi recuperat prin rezolvarea unui CVP, indiferent de mărimea coeficienților săi (presupunând că coeficienții de $m(X)$ sunt mici).