Decrypting message as MSB in regev scheme

Question

I was watching this FHE video and it define Regev encryption scheme as fallow :

kyegen:

• sk : choose $t = (1,s)^t \in \mathbb{Z}_q^{n+1}$
• pk = $A \in \mathbb{Z}_q^{m*(n+1)}$ random except $[A * t]_q$ small

Enc: for random $r \in \{0,1\}^m $ output and $\mu \in\{0,1\}$

• $c \leftarrow (\mu,0,...,0).\frac{q}{2} + r.A$

Dec : compute $$\langle c,t\rangle = \mu.\frac{q}{2} + r.A.t = \mu.\frac{q}{2} + \; small \; (mod \; q)$$

• Decrypt $\mu$ as MSB$([\langle c,t \rangle]_q)$

But i can not understand how decryption works? what i think is for example for $q = 8$ if $[\langle c,t \rangle]_q \in [2,6)$ message is 1 and if $[\langle c,t \rangle]_q \in [6,8) \cup [0,2)$ message is 0 (if absolute value of small in $\langle c,t\rangle$ be less thatn $q/4$). I cant understand how the message would be MSB$([\langle c,t \rangle]_q)$ ? for example if we use 3 bits for each number MSb of both 0 and 3 would be 0.

Edit

responding to @kelalaka answer. beside $q$ being odd which is important but not very much what made me confused at first place was this section of Regev's paper. I think what you said is true when "small" bounded like $0<= small < q/2$. for example for $q = 7$ we have something like $$000\\001\\010\\\\011\\---------\\100\\101\\110$$ and what i said when $-q/4<= small < q/4$ and depends on error distribution you choose at first place. but still not sure.

Edit 2 : actually it was kinda a silly question. for future reference if somebody(with low probability) came across this question. Homomorphic Encryption is a good paper from SHai Halevi, the guy in the video. and at secction 2.1 Notations and Basic Definitions you can find definition of $[\;\;]_q$ and much more.

Answer 1

You have some errors on the definition of the Regev's Scheme

• Keygen($1^n$):

  • sk : choose $t = (1,s)^t \in \mathbb{Z}_q^{n}$ where $q$ is an prime between $n^2$ and $2n^2$
  • pk = $B \in \mathbb{Z}_q^{m\times n}$ random except $[B \times t]_q$ "small"

• $Encryption(B,\mu \in \{0,1\}$: For random $r \in \{0,1\}^m $ output and $\mu \in\{0,1\}$ $$c \leftarrow (\mu,0,...,0) \cdot \frac{q}{2} + r \times B$$

• $Decrypt(c,t)$ : Compute

$$\langle c,t\rangle = \mu \cdot \frac{q}{2} + r \times B \times t = \mu \cdot \frac{q}{2} + \text{ "small"} \pmod q$$

• Recover $\mu$ as MSB$([\langle c,t \rangle]_q)$

Details

• the secret key is a $n$ dimensional vector in $\mathbb{Z}_q^{n}$ where the first component is $1$

• The public key is a matrix except that when you multiply with the secret key $t$ you will have a vector in $q$ that hash small values $[B \times t]_q$

• The random $r$ is a bit vector of size $m$, $r \in \{0, 1\}^m$.

• The message It is a bit, yes you encrypt either $\mu \in \{0, 1\}$, and for a vector of size $n$, $(\mu,0,...,0)$

• Encryption :

$$c \leftarrow (\mu,0,...,0) \cdot \frac{q}{2} + r \times B$$

• Decryption :

\begin{align} \langle c,t\rangle &= \langle (\mu,0,...,0) \cdot \frac{q}{2} + r \times B ,t\rangle\\ & = (\mu,0,...,0) \cdot \frac{q}{2} \times t + r \times B \times t \\ & = (\mu \cdot \frac{q}{2},0,...,0) \times t + r \times B \times t \\ & = \mu \cdot \frac{q}{2}+ r \times (B \times t) \end{align}

remember $[B \times t]_q$ was chosen as "small" and $r$ was a bit vector. If you consider the final integer in $\mod q$.

$$\mu \cdot \frac{q}{2} + \text{"small"}$$

The "small" in the beginning is adjusted so that $r \times B \times t$ never exceeds $q/2$.

Now, calling the MSB on the result will provide the $\mu$ since $\mu \cdot q/2$ makes the MSB 0 or 1 depending on the $\mu$.

Correctness

The small term is also called the error $e$ term. The correctness requires that $|e| < \lfloor q/2 \rfloor /2 $

---

Note: I did not go to verify the example, since $q$ is so small to work. The bounds must be carefully controlled.

The below sageMath code is working, however, one needs to tune the "small", that is left!

---

q = 129 # n^2 < 129 < 2n^2
R = IntegerModRing(q)
n = 10 # vector size
m = 10 # random vector size

def randSecretKey(R, size):
    v = vector(R,sample(range(q), size))
    v[0] =1
    return v

def randPublicKey(R,m,n):
    m2 = random_matrix(R,m,n)
    return m2

def randomBitVEctor(R,size):
    v = vector(R,[randint(0, 1) for i in range(size)])
    return v
    
def smallPKSK(R,m,n,sk,q):
    trials = 0
    small = false
    while not small:
        trials += 1
        inrange = true
        pk = randPublicKey(R,m,n)
        c = pk*sk
        for i in c:
            if i > 50:
               inrange = false
        if inrange == true:
            print( "number of =", trials)
            return pk

def encodeMessage(R,bit,m):
    mu = zero_vector(R,m)
    mu[0] = bit
    return mu

def encrypt(R, q, mu, r, B):

    return mu * R(64) + r * B

def decrypt(R, c, t):
    return c*t

sk = randSecretKey(R,n)
print("\nsecret key = ", sk)

pk = smallPKSK(R,m,n,sk,q)
print("\nPublic key\n")
print(pk)

pk*sk

r = randomBitVEctor(R,n)
print( "r = " , r)

mu = encodeMessage(R,1,m)
print("mu = ",mu)

c = encrypt(R, q, mu, r, pk)

print("ciphertext = ",c)

p = decrypt(R, c, sk)

print("plaintext = ",p)
Integer(p).digits(2)