Așa că după câteva săptămâni am reușit să găsesc câteva răspunsuri la întrebarea mea.
Este într-adevăr complet aleatoriu sau am omis ceva?
Da, este aici pentru a reduce ambiguitatea spațiului de căutare. Totul pleacă de la ideea că de exemplu:
$
\begin{bmatrix}
1 \
-1 \
0 \
-1 \
1 \
0 \
\end{bmatrix}
=
\begin{bmatrix}
1 \
0 \
0 \
-1 \
0 \
0 \
\end{bmatrix}
+
\begin{bmatrix}
0 \
-1 \
0 \
0 \
1 \
0 \
\end{bmatrix}
=
\begin{bmatrix}
1 \
-1 \
0 \
0 \
0 \
0 \
\end{bmatrix}
+
\begin{bmatrix}
0 \
0 \
0 \
-1 \
1 \
0 \
\end{bmatrix}
$
Aceste 2 combinații de vectori conduc la același rezultat. Dar navigarea pe ambele este inutilă, deoarece combinația lor este aceeași.Astfel, este posibil să reducem spațiul de căutare ignorând unele combinații redundante și pentru a face asta setăm unele valori ca constante în partea dreaptă a ecuației LWE (de ex. $Ca$ si nu $s$) din cauza unor proprietăţi matematice (omomorfismul proiecţiei A. mai introduce).
De ce este de dimensiune $r$?
$r=floor(log_q(R))$ Unde $R$ este dimensiunea spațiului de reprezentare al vectorului pe care îl căutăm. În exemplul de mai sus, $R\geq2$ deoarece am găsit 2 moduri de a reprezenta vectorul.
Astfel, cel $log_q$ de care $R$ este numărul de coordonate din spațiu $\mathbb{Z}_r^q$ pe care o putem seta la o valoare fixă pentru a reduce spațiul de căutare. Cu toate acestea, acest număr de coordonate trebuie să fie un întreg, așa că luăm rotunjirea etajului a ceea ce am obținut.
Cum putem reduce spațiul de căutare de $s_1$ folosind ecuația menționată și echivalentul acesteia pentru $s_2$?
O modalitate de a-l exploata este să aplici abordarea potrivire și filtrare:
- Generați toate jumătățile posibile ale $s_1$ după cum descrie A. May
- Combinați-le și filtrați, adică respingeți cele obținute $s_1$ dacă $\pi_r(As_1) \ne t$ sau dacă nu este un vector ternar valid cu greutatea Hamming bună
- Faceți echivalentul pentru $s_2$ (rețineți ecuația cu $t$ nu este același lucru cu care suntem în partea dreaptă a copacului)
- Combinați acești vectori cu hashingul Odlyzko și verificați ecuația LWE
Desigur, acesta trebuie adaptat pentru copacii mai mari.
