Итак, через несколько недель мне удалось найти некоторые ответы на свой вопрос.
Это действительно совершенно случайно или я что-то пропустил?
Да, это сделано для того, чтобы уменьшить неоднозначность пространства поиска. Все начинается с мысли, что например:
$
\begin{bматрица}
1\
-1\
0 \
-1\
1\
0 \
\end{bmatrix}
знак равно
\begin{bматрица}
1\
0 \
0 \
-1\
0 \
0 \
\end{bmatrix}
+
\begin{bматрица}
0 \
-1\
0 \
0 \
1\
0 \
\end{bmatrix}
знак равно
\begin{bматрица}
1\
-1\
0 \
0 \
0 \
0 \
\end{bmatrix}
+
\begin{bматрица}
0 \
0 \
0 \
-1\
1\
0 \
\end{bmatrix}
$
Эти 2 комбинации векторов приводят к одному и тому же результату. Но просматривать оба бесполезно, так как их комбинация одинакова.Таким образом, можно уменьшить пространство поиска, игнорируя некоторые избыточные комбинации, и для этого мы устанавливаем некоторые значения в качестве констант в правой части уравнения LWE (т.е. $Как$ и нет $s$) в силу некоторых математических свойств (гомоморфизм проекции вводит А. Мэй).
Почему он такого размера $г$?
$ г = пол (log_q (R)) $ куда $R$ размер пространства представления вектора, который мы ищем. В приведенном выше примере $R\geq2$ потому что мы нашли 2 способа представления вектора.
Таким образом $log_q$ того, что $R$ это количество координат в пространстве $\mathbb{Z}_r^q$ которое мы можем установить на фиксированное значение, чтобы уменьшить пространство поиска. Однако это количество координат должно быть целым числом, поэтому мы берем округление того, что мы получили.
Как мы можем уменьшить пространство поиска $s_1$ используя упомянутое уравнение и его эквивалент для $s_2$?
Один из способов использовать это — применить подход сопоставления и фильтрации:
- Сгенерируйте все возможные половины $s_1$ как описывает А. Мэй
- Объедините их и отфильтруйте, то есть отбросьте полученные $s_1$ если $\pi_r(As_1)\ne t$ или если это не допустимый тернарный вектор с хорошим весом Хэмминга
- Сделайте эквивалент для $s_2$ (обратите внимание на уравнение с $t$ не то же самое, что мы в правой части дерева)
- Объедините эти векторы с хешированием Одлызко и проверьте уравнение LWE.
Конечно, это должно быть адаптировано для больших деревьев.
