înregistrare Logare
Puncte:1
avatar Crypto

De ce să folosiți convoluții negaciclice pentru înmulțirea polinomială în loc de convoluții regulate?

drapel pm
warforgad

La înmulțirea polinoamelor din $\mathbb{Z}_q[X] / (X^n-1) $, NTT discret este utilizat deoarece: $$ f \cdot g = \mathsf{NTT}_n^{-1}\left( \mathsf{NTT}_n\left(f\right) * \mathsf{NTT}_n\left(g\right) \right ) $$ Cu toate acestea, în aproape toate schemele am văzut negaciclic se folosește convoluția – inelul este $\mathbb{Z}_q[X] / (X^n+1) $ și un truc este folosit pentru a calcula $\mathsf{NTT}_{2n}^{-1}\left( \mathsf{NTT}_{2n}\left(f\right) * \mathsf{NTT}_{2n}\left(g\right) ) \dreapta) $ folosind $\mathsf{NTT}_n$ deoarece trebuie să înmulțim polinoamele în $\mathbb{Z}_q[X] / (X^{2n}-1) $.
Întrebarea mea este - de ce să te deranjezi $\mathbb{Z}_q[X] / (X^n+1) $ și nu pur și simplu folosiți $\mathbb{Z}_q[X] / (X^n-1) $, aplicând astfel $\mathsf{NTT}_n$ într-un mod simplu, fără complicații suplimentare?

41
0 + 0
lwe
Puncte:1
Hilder Vitor Lima Pereira avatar Crypto
drapel us
Hilder Vitor Lima Pereira

Problema dificilă de bază folosită pentru a construi primitivele criptografice ne cere să folosim acel inel de polinoame modulo $X^n + 1$.

De exemplu, dacă securitatea schemei dvs. se bazează pe RLWE, atunci trebuie să rămâneți cu inelele care fac RLWE sigur, ceea ce înseamnă că nu puteți utiliza $X^n - 1$, după cum s-a discutat în acest raspuns.

Aveți aceeași situație pentru Problemă Ring-SIS.

În general, trebuie să fii atent când instanțiază orice problemă cu $X^n - 1$ ca modul, deoarece se pot evalua polinoamele pe $1$ pentru a lucra peste numere întregi în loc de polinoame. Acest lucru este discutat, de exemplu, în secțiunea „Evaluare polinomială” a această hârtie.

0 + 0
Puncte:1
kodlu avatar Crypto
drapel sa
kodlu

Dumneavoastră declarați (ți-am corectat notația, clasele de reziduuri sunt luate cu a $/$ nu $\backslash)$ primul este setminus, care nu este același:

Cu toate acestea, în aproape toate schemele am văzut negaciclic se folosește convoluția – inelul este $\mathbb{Z}_q[X] / (X^n+1) $ și un truc este folosit pentru a calcula $\mathsf{NTT}_{2n}^{-1}\left( \mathsf{NTT}_{2n}\left(f\right) * \mathsf{NTT}_{2n}\left(g\right) ) \dreapta) $ folosind $\mathsf{NTT}_n$ deoarece trebuie să înmulțim polinoamele în $\mathbb{Z}_q[X] / (X^{2n}-1) $.

si pune intrebarea:

de ce sa te deranjezi $\mathbb{Z}_q[X] / (X^n+1) $ și nu pur și simplu folosiți $\mathbb{Z}_q[X] \setminus (X^n-1) $?

Dacă avem factorizarea polinomială $x^{2n}-1=(x^n-1)(x^n+1)$ apoi calcule modulo $x^{2n}-1$ poate fi accelerat prin convoluția (prin NTT) în raport cu fiecare dintre factori și apoi combinând. Asa de

  1. Avem o factorizare care duce la o transformare rapidă, așa că luăm această cale. Cazul extrem este FFT complex când putem factoriza până la capăt în factori liniari $x^n-1=\prod_{i=1}^n (\omega^i-1)$ cu $\omega$ un primitiv $n^{th}$ rădăcină a unității.
  2. Factorizarea este unică, nu o puteți folosi $(x^n+1)$ numai de când $(x^n+1)^2=(x^{2n}+2 x^n+1)$ și $q$ în general, nu este caracteristic 2. Dacă ai vrut să spui de fapt, folosește $x^{2n}-1$ direct, nu ai avea nicio accelerare.
0 + 0
drapel pm
warforgad
Îmi pare rău, sunt rău cu notația coeficientului. Cred că ai înțeles greșit întrebarea mea (sau am înțeles greșit răspunsul tău). Nu întreb cum să înmulțesc polinoamele de gradul $(2n-1)$ folosind NTT-uri de ordinul $n$ și nu întreb de ce este imposibil să înmulțim polinoame din $\mathbb{Z}_q[X]/(X) ^n+1)$ cu NTT-uri. Mă întreb de ce folosiți polinoamele modolu $X^n+1$ în primul rând (care au nevoie de trucul cu $(X^{2n}-1)$), și nu folosiți polinoamele modolu $X^n-1$
1
Răspunde
kodlu avatar
drapel sa
kodlu
dacă lungimea ta este $N=2n,$ adică chiar, aceasta ESTE factorizarea pe care trebuie să o folosești pentru a începe, adică $x^{2n}-1=(x^n-1)(x^n+1)$ deoarece orice $2n^{th}$ rădăcină a unității în orice câmp sau inel este fie ordin $2n$ (cele care sunt -1 când sunt ridicate la putere $n$) fie au ordin împărțind $n$.
0
Răspunde
kodlu avatar
drapel sa
kodlu
începi cu $N$ ca un dat.
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.