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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – SEJPM
    Apr 24 '18 at 16:46
  • $\begingroup$ 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) $\endgroup$
    – poncho
    Apr 24 '18 at 17:47
  • $\begingroup$ @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$? $\endgroup$ Apr 24 '18 at 21:09
  • $\begingroup$ 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? $\endgroup$
    – poncho
    Apr 24 '18 at 21:22
  • $\begingroup$ 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. $\endgroup$ Apr 24 '18 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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.