# understanding LWE public key algorithm

I'm trying to understand this LWE public key system

say I use matrix A = [[44, 73, 20, 54],[92, 19, 78, 22],[31, 34, 94, 29],[82, 32, 70, 68]]

q = 97

bit = 1

and secret key s: [56, 90, 0, 46]

and secret error vector e:[1, 0, -1, 0]

then B = As+e mod q is [73 17 18 27]

Bob's secret is [1, 0, 1, 1]

Bobby computes u = A*x mod q and get [21, 95,57, 26]

and v = Bx + bit(q/2) mod q and get 69

Alice decrypts:

v-s*u = 69 - 58 = 11

11 is quiet far from q/2 = 48

what am i doing wrong?

The message bit should be just that, a single bit, and $$v$$ should be a single integer modulo $$q$$. I am not sure how you’re getting $$v$$ to be a vector. Note that $$b^t x$$ is an inner product (mod $$q$$), so it is also a single integer mod $$q$$.

• @chrispiekert say I use matrix A = [[44, 73, 20, 54],[92, 19, 78, 22],[31, 34, 94, 29],[82, 32, 70, 68]] q = 97 bit = 1 and secret key s: [56, 90, 0, 46] and secret error vector e:[1, 0, -1, 0] then B = As+e mod q is [73 17 18 27] Bob's secret is [1, 0, 1, 1] Bobby computes u = Ax mod q and get [21, 95,57, 26] and v = Bx + bitq/2 mod q and get 69 Alice decrypts: v-su = 69 - 58 = 11; 11 is quiet far from q/2 = 48 what am i doing wrong? – Deus Ex Feb 16 '20 at 4:38
• What you call $B$ should be the row vector $b^t=s^t A+e^t$. It looks like you may be multiplying on the same side of $A$ for both $b$ and $u$, which will not work. – Chris Peikert Feb 16 '20 at 17:10