Constrângeri asupra q pentru rețele q-ary?

După cum menționează Hilder, prin tehnica „commutării modulului” alegerea particulară a $q$ nu contează prea mult pentru securitatea LWE. Prin urmare, forma particulară a $q$ este mai ales pentru a permite îmbunătățiri ale eficienței. Sunt persoana greșită să le enumerez exhaustiv pe toate, dar se poate indica cu ușurință câteva citind propunerile NIST PQC KEM.

De exemplu:

1. Alegerea $q = 2^k$ pentru unii $k$ permite înlocuirea reducerilor modulare prin $q$ cu deplasări de biți, o operațiune mai ieftină. Acesta este o parte din motivul pentru care Sabre alege $q = 2^{13}$.

2. Alegerea $q$ să fie „NTT Friendly”. NTT este un anumit analog al FFT „mod $q$" (mai degrabă decât peste $\mathbb{C}$) care poate permite accelerații mari în înmulțirile polinomiale (aproximativ de la $O(n^2)$ complexitate naiva la $O(n\log n)$). Mărimea accelerației este direct legată de existența unui analog adecvat $i\in\mathbb{C}$. Cel mai bun caz (să zicem când lucrezi $\mathbb{Z}_q[x]/(x^n+1)$ pentru $n = 2^k$) se întâmplă atunci când aveți un „primitiv 2n$a rădăcină a unității”, ceea ce se întâmplă când $q\equiv 1\bmod 2n$ (Cred). Rețineți că acest lucru nu este compatibil cu optimizarea anterioară. KEM Kyber face această alegere (aproape, există mici diferențe tehnice).

3. Alegerea $q$ să fie un produs de coprime mici (cu mărimea cuvântului), astfel încât se poate face apel la teorema restului chinezesc și să păstreze toate dimensiunile aritmetice ale cuvântului. Nu știu de un KEM care să facă acest lucru, dar acest lucru este popular în literatura de specialitate FHE (și adesea poartă numele de „Residue Number System” sau aritmetică RNS).

Deci există argumente pentru alegere $q \equiv 0 \bmod 2^k$, $q\equiv 1\bmod 2\times 2^k$, și $q$ un produs de coprime mici. Toate acestea pot părea a fi optimizări care se exclud reciproc, dar cineva poate fi oarecum inteligent și poate folosi mai multe optimizări simultan. De exemplu, există acest lucru asupra modului aritmetic de încorporare $2^k$ (adică „reducere modulară prietenoasă”) într-un inel prietenos NTT, permițându-ne să folosească ambele optimizări 1 și 2.