înregistrare Logare
Puncte:3
Leafar avatar Crypto

Cum să decideți dacă un element este o cheie publică în schema de criptare NTRU?

drapel ng
Leafar

În primul rând, folosesc setările de https://en.wikipedia.org/wiki/NTRUencrypt, cu $L_f$ mulţime de polinoame cu $d_f+1$ coeficienți egali cu 1, $d_f$ egal cu $-1$ iar restul $N-2d_f-1$ egal cu 0; și $L_g$ multimea de polinoame cu $d_g$ coeficienți egali cu 1, $d_g$ egal cu $-1$ iar restul $N-2d_g$ egal cu 0. Numerele naturale $d_f$ și $d_g$ sunt doar parametri fix ai schemei.

Să presupunem că cineva primește un polinom $h$ în ring $R_{N,q}=\mathbb{Z}_q[X]/\langle X^N-1 \rangle$.

Întrebare: Este posibil să se determine dacă $h$ este o cheie publică, adică este posibil să se determine dacă $h$ este de forma $pf_q \cdot g \pmod{q}$?

Încercarea mea: ipoteza durității NTRU spune că de la $h$ nu se poate determina $f$ sau $g$, altfel schema ar fi inutilă. Deși nu am putut să-mi răspund la întrebare, am venit cu un test. De cand $g(1)=0$, trebuie sa avem $h(1)=0$. Prin urmare, dacă $h(1) \neq 0$ atunci $h$ nu este o cheie publică. Ce putem testa mai mult?

PS: Nicio dovadă de cunoștințe zero sau lucruri similare de la sursa $h$ sunt date.

304
0 + 0
Puncte:5
Mark avatar Crypto
drapel ng
Mark

Nu puteți în conformitate cu o ipoteză standard cunoscută sub numele de „Prezumția NTRU decizională”. Aceasta este în esență afirmația că cheile publice NTRU sunt pseudoaleatoare. Următorul este definiția 4.4.4 din Un deceniu de criptografie latice.

Problemă de învățare NTRU: Pentru o inversabilă $s\în R_q^*$, și distribuție $\chi$ pe $R$, defini $N_{s, \chi}$ să fie distribuția care iese $e/s\în R_q$ Unde $e\gets\chi$. The Problemă de învățare NTRU este: date eșantioane independente $a_i\în R_q$, unde fiecare probă este distribuită în funcție de oricare

  1. $N_{s,\chi}$, pentru unele alese aleatoriu $s\în R_q^*$ (fixat pentru toate probele) sau
  2. distribuția uniformă, distingeți care este cazul (cu avantaj neneglijabil).

Rețineți că această problemă afirmă în esență că nu puteți face ceea ce cereți, adică afirmă că cheile NTRU nu se pot distinge din punct de vedere computațional de aleatorii.

0 + 0
Leafar avatar
drapel ng
Leafar
Mulțumesc mult! Înțeleg mai multe acum, dar aici, în această definiție, distribuția uniformă este definită peste toți $R_{N,q}$, ceea ce este împotriva testului pe care l-am furnizat. Mai mult, $\chi$ este o distribuție peste $L(d_g,d_g)$. Pot defini punctul 2 ca distribuție uniformă peste $R_{N,q}$, cu excepția tuturor polinoamelor care evaluate la 1 dau 0? Va fi suficientă această definiție / presupunerea durității?
0
Răspunde
Mark avatar
drapel ng
Mark
Probabil că puteți defini doar inelul $R$ pentru a avea polinoame care se evaluează la 0 la 1, de ex. set $R = \mathbb{Z}[x] / (x^n-1)$. Totuși, nu puteți schimba punctul 2 unilateral, deoarece atunci problema distinctivă devine o problemă distinctă diferită.
0
Răspunde
Leafar avatar
drapel ng
Leafar
Nu pot pentru că astfel de polinoame nu sunt niciodată inversabile și acest lucru se va încurca cu $f$, în răspunsul tău $s$, care trebuie să fie inversabil.
0
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.