1

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?

Novice Geek
  • 13
  • 3
  • 1
    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. – SEJPM Apr 24 '18 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) – poncho Apr 24 '18 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$? – Novice Geek Apr 24 '18 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? – poncho Apr 24 '18 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. – Novice Geek Apr 24 '18 at 21:27
  • So, I was wondering if anyone has defined/proved such a variant of LWE? – Novice Geek Apr 24 '18 at 21:35

1 Answers1

4

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}$.

Florian Bourse
  • 986
  • 5
  • 16