Score:3

# Is the scheme in LWE also valid in R-LWE?

One way of interpreting matrices in RLWE is that they are a subset of standard integer matrices that have special structure. For example, rather than using a random matrix $$A\in\mathbb{Z}_q^{n\times n}$$ (as we might in LWE-based constructions), we can replace this a matrix with a matrix where the first column (or row) is random, and the rest have a cyclic rotation structure:

$$\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 a)]$$

Other "special structures" of course exist (say negacyclic rotations).

How far does this analogy stretch? In particular, for any scheme based on LWE, is there a corresponding R-LWE scheme, where one samples the random matrices from this special subset (rather than uniformly randomly)?

For example, in standard Regev-style encryption (that was designed for LWE), can we choose the matrix in the above way to build an R-LWE version of Regev encryption?