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.

  • 1
    $\begingroup$ 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)? $\endgroup$ Sep 20, 2022 at 11:06
  • $\begingroup$ @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). $\endgroup$
    – Anon
    Sep 20, 2022 at 11:37
  • 1
    $\begingroup$ @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. $\endgroup$
    – Anon
    Sep 20, 2022 at 12:22
  • $\begingroup$ 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$? $\endgroup$
    – kodlu
    Sep 20, 2022 at 12:42
  • 1
    $\begingroup$ @kodlu I have added more details on the equations I mentioned. $\endgroup$
    – Anon
    Sep 20, 2022 at 12:55


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.