# Regev PKE not CPA secure for specific $A$?

I encountered notes stating that, for certain fixed $$A$$, such as $$A \in M_{n\log(q)\times n}$$ as follows:

$$\begin{bmatrix} 1 & 0 & 0 &\dots\\ 2 & 0 & 0 &\dots\\ 4 & 0 & 0 &\dots\\ &\dots\\ 2^{\log(q)-1} & 0 & 0 &\dots \\ 0 & 1 & 0 &\dots\\ 0 & 2 & 0 &\dots\\ 0 & 4 & 0 &\dots\\ &\dots\\ 0 & 2^{\log(q)-1} & 0 &\dots\\ &\dots\\ \end{bmatrix}$$

(where for simplicity of representation, it is assumed that $$q$$ is a power of $$2$$), the Regev encryption scheme is not CPA secure.

I've been trying to prove this, but I seem to be missing something crucial. Specifically, I thought that, perhaps knowing $$A$$, one wold be able to solve for $$s$$ using unit vectors for the encryption instead of random ones, but that didn't yield anything. I couldn't come up with other forms of encryption that would inform of the CPA challenger's choice.

Specifically, I thought of creating encryptions of $$0$$ using unit vectors $$u_i$$ as such: $$(u_i^TA, u_i^Tb)$$ (where $$b=As+e$$). With this, for $$u_1$$, for example, we get: $$(u_1, s_1+e_1)$$, so we know the value of $$s_1+e_1$$ as a result of the encryption. This doesn't seem to facilitate solving for $$s_i, e_i$$ though.

What am I missing?

Note: I have also added the FHE tag because this matrix reminds me of the FHE scheme to reduce the error size.

• Hint: you can indeed solve for $s$ (and the error $e$). Do you see how to recover, say, the least-significant bit of $s_1$ (i.e., whether it is odd or even)? Sep 20, 2022 at 11:06
• @ChrisPeikert Still unsuccessful... :/ I just get equations of the form $s_1 +e_1=c_1$, $2s_1 +e_2=c_2$ etc. ($c_i$ is the second element in the encryption tuple) when I use unit vectors instead of random ones. So this yields a system of equations that has one-too-many variables in order to solve (so far we have 2 equations with three variables).
– Anon
Sep 20, 2022 at 11:37
• @ChrisPeikert Perhaps looking for $s$ in binary form somehow? If $s$ is binary, then knowing that $e$ is roughly $0$ means that a result of $c_1<\frac{q}{4}$ (e.g.) yields that $s_1$ is $0$ and vice versa.
– Anon
Sep 20, 2022 at 12:22
• What is the relevant equation you are trying to solve? If this is to be useful to others, you should state it in the question . Is it something like $As+e=y$ given $y$? Sep 20, 2022 at 12:42
• @kodlu I have added more details on the equations I mentioned.
– Anon
Sep 20, 2022 at 12:55