LWE and Lattice-based cryptography: How to recover binary message $M$ from $(u, v)$ values?

I am given a set of $(u, v)$ values, matrix $A$, primary key vector, private key vector, error vector and prime $q$. I wanted to recover the binary value of each $(u, v)$ pairs using LWE decryption.

The formula I used to get that was: $\mbox{result} = v - s u$, where $s$ is the private key. I then compared the result with $q//2$. If result is more than $q//2$, the output is 1. If the result is less than $q//2$. However, I am unable to recover the correct binary values. This is the Python code snippet that I used to get the binary value.

import numpy as np
import json

m = ''

def computeM(u, v, q, s):
    global m
    res=(np.subtract(v, np.dot(s, u))) % q
  
    if (res > q//2):
        m += '1' 
    else:
        m += '0'

# retrieve u and v from JSON 

f = open('CarlDavisJSON.json')
  
data = json.load(f)


# Extract the u and v values from the messages array
u_json = []
v_json = []
s = ""


for message in data['exercise']['messages'][0]['cipher']:
    u_json.append(message['u'])
    v_json.append(message['v'])



s = data['exercise']['alice']['sk']
q = data['exercise']['alice']['q']


# store u and v in numpy array

u_list = np.array(u_json)
v_list = np.array(v_json)


# compute each binary from u and v


for i in range(len(u_list)):
    u = np.array(u_list[i])
    v = np.array(v_list[i])

    # print(v)
    computeM(u, v, q, s)
    

print(m)

I have checked that the correct values are used. What do you think have gone wrong with the method?

Update: I have edited this question with the full codes and the JSON file for this implementation.

These are my JSON file containing prime q, secret key sk and (u, v) ciphertext pairs for decryption.

  {
  "srn": "887766554",
  "name": "Carl Davis",
  "exercise": {
    "alice": {
      "pk": [ 8, 9, 6, 5, 4, 15, 21 ],
      "sk": [ 2, 21, 3, 6, 23 ],
      "e": [ -1, 1, 1, -1, 0, 0, 0 ],
      "q": 29,
      "a":
        [[ 7, 21, 26, 19, 0 ],
        [ 0, 14, 1, 5, 0 ],
        [ 13, 21, 11, 18, 28 ],
        [ 16, 5, 15, 13, 23 ],
        [ 21, 22, 3, 1, 23 ],
        [ 4, 21, 21, 1, 21 ],
        [ 18, 0, 22, 16, 15 ]]
    },
    "messages": [
      { 
        "cipher": [
          { "u": [ 1, 19, 3, 2, 24 ], "v": 16 },
          { "u": [ 3, 20, 22, 26, 15 ], "v": 21 },
          { "u": [ 7, 3, 24, 26, 22 ], "v": 13 },
          { "u": [ 9, 20, 7, 25, 14 ], "v": 5 },
          { "u": [ 28, 11, 26, 22, 16 ], "v": 23 },
          { "u": [ 18, 11, 20, 23, 8 ], "v": 26 },
          { "u": [ 16, 27, 3, 10, 14 ], "v": 18 },
          { "u": [ 15, 4, 16, 9, 17 ], "v": 11 },
          { "u": [ 15, 4, 16, 9, 17 ], "v": 26 },
          { "u": [ 12, 4, 11, 20, 9 ], "v": 18 },
          { "u": [ 9, 27, 2, 0, 14 ], "v": 0 },
          { "u": [ 12, 11, 6, 24, 9 ], "v": 14 },
          { "u": [ 12, 20, 12, 14, 22 ], "v": 27 },
          { "u": [ 3, 20, 22, 26, 15 ], "v": 7 },
          { "u": [ 24, 19, 1, 14, 20 ], "v": 9 },
          { "u": [ 9, 11, 1, 6, 1 ], "v": 6 },
          { "u": [ 9, 20, 7, 25, 14 ], "v": 5 },
          { "u": [ 1, 19, 3, 2, 24 ], "v": 1 },
          { "u": [ 21, 4, 1, 8, 16 ], "v": 9 },
          { "u": [ 0, 27, 12, 12, 7 ], "v": 24 },
          { "u": [ 27, 6, 28, 7, 0 ], "v": 2 },
          { "u": [ 13, 5, 22, 25, 6 ], "v": 6 },
          { "u": [ 9, 11, 1, 6, 1 ], "v": 21 },
          { "u": [ 16, 18, 26, 20, 1 ], "v": 5 },
          { "u": [ 16, 18, 26, 20, 1 ], "v": 20 },
          { "u": [ 28, 11, 26, 22, 16 ], "v": 8 },
          { "u": [ 16, 27, 3, 10, 14 ], "v": 18 },
          { "u": [ 12, 20, 12, 14, 22 ], "v": 27 },
          { "u": [ 12, 4, 11, 20, 9 ], "v": 4 },
          { "u": [ 13, 5, 22, 25, 6 ], "v": 6 },
          { "u": [ 15, 4, 16, 9, 17 ], "v": 26 },
          { "u": [ 11, 10, 15, 22, 14 ], "v": 19 }
        ]
      },
      {
        "text": "node"
      }
    ]
  },
  "solution": {
    "messages": [
      {
        "text": "game",
        "cipher": [
          { "u": [ 1, 19, 3, 2, 24 ], "v": 16 },
          { "u": [ 3, 20, 22, 26, 15 ], "v": 21 },
          { "u": [ 7, 3, 24, 26, 22 ], "v": 13 },
          { "u": [ 9, 20, 7, 25, 14 ], "v": 5 },
          { "u": [ 28, 11, 26, 22, 16 ], "v": 23 },
          { "u": [ 18, 11, 20, 23, 8 ], "v": 26 },
          { "u": [ 16, 27, 3, 10, 14 ], "v": 18 },
          { "u": [ 15, 4, 16, 9, 17 ], "v": 11 },
          { "u": [ 15, 4, 16, 9, 17 ], "v": 26 },
          { "u": [ 12, 4, 11, 20, 9 ], "v": 18 },
          { "u": [ 9, 27, 2, 0, 14 ], "v": 0 },
          { "u": [ 12, 11, 6, 24, 9 ], "v": 14 },
          { "u": [ 12, 20, 12, 14, 22 ], "v": 27 },
          { "u": [ 3, 20, 22, 26, 15 ], "v": 7 },
          { "u": [ 24, 19, 1, 14, 20 ], "v": 9 },
          { "u": [ 9, 11, 1, 6, 1 ], "v": 6 },
          { "u": [ 9, 20, 7, 25, 14 ], "v": 5 },
          { "u": [ 1, 19, 3, 2, 24 ], "v": 1 },
          { "u": [ 21, 4, 1, 8, 16 ], "v": 9 },
          { "u": [ 0, 27, 12, 12, 7 ], "v": 24 },
          { "u": [ 27, 6, 28, 7, 0 ], "v": 2 },
          { "u": [ 13, 5, 22, 25, 6 ], "v": 6 },
          { "u": [ 9, 11, 1, 6, 1 ], "v": 21 },
          { "u": [ 16, 18, 26, 20, 1 ], "v": 5 },
          { "u": [ 16, 18, 26, 20, 1 ], "v": 20 },
          { "u": [ 28, 11, 26, 22, 16 ], "v": 8 },
          { "u": [ 16, 27, 3, 10, 14 ], "v": 18 },
          { "u": [ 12, 20, 12, 14, 22 ], "v": 27 },
          { "u": [ 12, 4, 11, 20, 9 ], "v": 4 },
          { "u": [ 13, 5, 22, 25, 6 ], "v": 6 },
          { "u": [ 15, 4, 16, 9, 17 ], "v": 26 },
          { "u": [ 11, 10, 15, 22, 14 ], "v": 19 }
        ]
      },
      {
        "text": "node",
        "cipher": [
          { "u": [ 7, 3, 24, 26, 22 ], "v": 28 },
          { "u": [ 12, 20, 12, 14, 22 ], "v": 12 },
          { "u": [ 27, 3, 5, 9, 15 ], "v": 22 },
          { "u": [ 17, 28, 23, 12, 9 ], "v": 13 },
          { "u": [ 27, 3, 5, 9, 15 ], "v": 22 },
          { "u": [ 4, 3, 19, 8, 14 ], "v": 20 },
          { "u": [ 25, 18, 16, 8, 8 ], "v": 25 },
          { "u": [ 18, 11, 20, 23, 8 ], "v": 12 },
          { "u": [ 24, 19, 1, 14, 20 ], "v": 9 },
          { "u": [ 10, 19, 22, 19, 2 ], "v": 21 },
          { "u": [ 9, 27, 2, 0, 14 ], "v": 0 },
          { "u": [ 11, 10, 15, 22, 14 ], "v": 5 },
          { "u": [ 9, 11, 1, 6, 1 ], "v": 6 },
          { "u": [ 28, 11, 26, 22, 16 ], "v": 8 },
          { "u": [ 9, 20, 7, 25, 14 ], "v": 19 },
          { "u": [ 28, 11, 26, 22, 16 ], "v": 8 },
          { "u": [ 10, 19, 22, 19, 2 ], "v": 7 },
          { "u": [ 4, 19, 8, 20, 3 ], "v": 23 },
          { "u": [ 12, 20, 12, 14, 22 ], "v": 12 },
          { "u": [ 12, 11, 6, 24, 9 ], "v": 14 },
          { "u": [ 22, 18, 11, 19, 0 ], "v": 18 },
          { "u": [ 26, 12, 12, 6, 3 ], "v": 24 },
          { "u": [ 9, 20, 7, 25, 14 ], "v": 5 },
          { "u": [ 11, 10, 15, 22, 14 ], "v": 5 },
          { "u": [ 16, 27, 3, 10, 14 ], "v": 4 },
          { "u": [ 1, 6, 4, 25, 8 ], "v": 24 },
          { "u": [ 13, 5, 22, 25, 6 ], "v": 6 },
          { "u": [ 14, 28, 18, 23, 1 ], "v": 20 },
          { "u": [ 25, 18, 16, 8, 8 ], "v": 11 },
          { "u": [ 19, 11, 7, 5, 9 ], "v": 17 },
          { "u": [ 12, 4, 11, 20, 9 ], "v": 4 },
          { "u": [ 26, 12, 12, 6, 3 ], "v": 24 }
        ]
      }
    ]
  }
}

The first group of (u, v) ciphertext pairs should encrypt to game which has the binary values of 01100111011000010110110101100101.

Without seeing your full code, it's difficult to debug, although even with code debugging isn't the most interesting. I'll link you to this simple python implementation I put together previously if you want a python reference of things.

Note that while I say your issue is difficult to debug, it is not impossible. You have indicated in the comments

After running through the list of ciphertext (u, v) pairs, my output was 11101111111100010110110111100111. However, my intended output is 01100111011000010110110101100101 which is the binary value for game. Do you think something is potentially wrong with my implementation?

Your issue is almost assuredly an incorrect parameterization of your cryptosystem. At a high level, what you are noticing is explained by the noise $\vec e := b - \langle s, a\rangle$. If $\vec e \in [-q/4, q/4)^n$, you get correct decryption. If this is true except for some coordinates, everything but these coordinates will decrypt correctly. The probabilistic properties of $\vec e$ are such that I strongly suspect that if you replace $q\mapsto 10q$ in your implementation, everything will decrypt correctly (and plausibly $q\mapsto 3q$, or some smaller scalar, should suffice).

Without seeing details of your implementation it is hard to choose the precise scalar factor, but at a high level $\vec e$ tends to be from a distribution such that $\Pr[|\vec e_i| > k\sigma] \leq \exp(-k^2)$, where $\sigma$ is the standard deviation of the underlying distribution (and $k$ is a parameter you choose). Setting $k\sigma = q/4$, one can pretty easily show that all coordinates decrypt correctly with probability at least $1-n\exp(-q^2/16\sigma^2)$. So if you are implicitly in a regime where things mostly work, by moderately increasing $q$ you can quickly get to a regime where things work with very high probability, and you'll be completely correct.

Most probably you are having a problem because your reduction mod q is not centered.

When you compute $w = v - s \cdot u \bmod q$, you obtain $w \equiv e + \lfloor q/2\rfloor \cdot m \pmod q$, where $||e|| < q/4$. This means that $-q/4 < e < q/4$.

As an example, imagine that $m = 0$ and $e=-1$. Then you have $w \equiv -1 \pmod q$, but because your reduction maps the values to $\{0, 1, ..., q-1\}$, you will get $w = q-1 > q/2$, and you will output $m=1$.

One way to solve this is to decrypt using the formula $$w = q/4 + v - s \cdot u \bmod q$$ instead of the one you are using. This will shift the noise $e$ from the open interval $] -q/4, q/4 [$ to the interval $]0 , q/2 [$, that is, you will get $w = e' + \lfloor q/2\rfloor \cdot m \in \{0, 1, ..., q-1\}$ where $0 < e' < q/2$.

Now you clearly have two cases: if $m = 0$, then $0 < w < q/2$, but if $m = 0$, then $q/2 < w < q$. Hence, your decryption will work even without using the centered modular reduction.