Один из способов интерпретации матриц в RLWE состоит в том, что они являются подмножеством стандартных целочисленных матриц, которые имеют особая структура.
Например, вместо использования случайной матрицы $A\in\mathbb{Z}_q^{n\times n}$ (как мы могли бы в конструкциях на основе LWE), мы можем заменить эту матрицу матрицей, в которой первый столбец (или строка) является случайным, а остальные имеют структуру циклического вращения:
$$\begin{pmatrix}
a_1 & a_n & \dots & a_2\
a_2 & a_1 & \dots & a_3\
\vdots & &\ddots & \
a_n & a_{n-1} & \dots & a_1
\end{pmatrix} = [\vec a, \mathsf{rot}(\vec a),\mathsf{rot}^2(\vec a),\dots, \mathsf{rot}^{n-1}( \vec а)]$$
Разумеется, существуют и другие «специальные структуры» (скажем, негациклический вращения).
Насколько далеко простирается эта аналогия? В частности, для любой схемы, основанной на LWE, существует ли соответствующая схема R-LWE, в которой выбираются случайные матрицы из этого специального подмножества (а не равномерно случайным образом)?
Например, в стандартном шифровании в стиле Regev (которое было разработано для LWE) можем ли мы выбрать матрицу указанным выше способом для построения версии R-LWE шифрования Regev?
