1

in LWE instance $b=A^t s +e$, can we find an orthogonal basis of coefficient matrix A in polynomial time, let it be B.Multiply B to get $Bb=Be$ as term with s will vanish. Then solve for $e$. After getting $e$, subtract from $b$ and get the equation without error. Solve for $s$.

My doubt is, "Is finding orthogonal complement matrix difficult?" otherwise LWE may be broken?

kodlu
  • 22,423
  • 2
  • 27
  • 57
Matrixee
  • 11
  • 3
  • I got some answer .Here the matrix A is full rank ,so its null space matrix is zero matrix.So LWE will be hard – Matrixee Dec 23 '19 at 07:00
  • 1
    Welcome to crypto.stackexchange - If you have found the answer to your question, you are encouraged to post it as an answer properly down below. Comments are supposed to be used for making suggestions or asking for clarifications and are specifically not supposed to contain the answer to the question. – Ella Rose Dec 23 '19 at 16:18

0 Answers0