# LWE with secret matrix (Reverse LWE?)

I was wondering if there is a version of LWE with secret matrices and public seed vectors? Would it be as hard as the popular definition of LWE?

• You might want to give a formal definiton of the new problem you are suggesting and for the sake of reference also please give a formal definition of the problem you are referring to. Apr 24, 2018 at 16:46
• If everything other than the matrix is public, then someone is likely able to rederive the matrix with enough plaintext/ciphertext pairs (using linear algebra) Apr 24, 2018 at 17:47
• @poncho Even if the (public) seed vector is different for each new instance, i.e., $\langle s_i, A \rangle$; like there is a different matrix for each LWE instance, i.e., $\langle s, A_i \rangle$? Apr 24, 2018 at 21:09
• And, will the two sides have the same matrix? If that's a shared secret, you've effectively got a symmetric system (and we have better symmetric systems). If only one side has the matrix, how does it work? Apr 24, 2018 at 21:22
• The primary goal is not to define a new cryptosystem but to define a new problem, which is as hard as LWE but has different constraints. The new problem may be useful in many scenarios and novel function constructions but that's not what I am after. Apr 24, 2018 at 21:27

The LWE assumption tells you that $(\mathbf{a},\mathbf{a}\mathbf{s}+e)$ looks random for a hidden random vector $\mathbf{s}$, a random vector $\mathbf{a}$ and small error $e$.
Invoking the LWE assumption k times, you get that $(\mathbf{a},\mathbf{a}\mathbf{s}_1+e_1,\mathbf{a}\mathbf{s}_2+e_2,\ldots,\mathbf{a}\mathbf{s}_k+e_k)$ is indistinguishable from $(\mathbf{a},b_1,b_2,\ldots,b_k)$ where the $b_i$'s are random values.
So $(\mathbf{a},\mathbf{S}\mathbf{a}+\mathbf{e})$ is indistinguishable from $(\mathbf{a},\mathbf{b})$, and if an adversary has advantage $\varepsilon$ in distinguishing those 2 distributions, there is an adversary that has advantage $\frac{1}{k}\varepsilon$ in distinguishing LWE samples from uniform, where $k$ is the dimension of the vector $\mathbf{e}$.