# Decrypting message as MSB in regev scheme

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.

• Article says that Hence we see that 2a decryption error occurs only if the sum of the error terms over all S is greater than q/4. Updated the answer, too. Jan 16 '21 at 22:12
• It also says that, with standard deviation, the probability of $e > q/4$ is negligible. Jan 16 '21 at 22:13

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)

• Note: I did not go to verify the examples, since $q$ is so small to work. The bounds must be carefully controlled. Jan 14 '21 at 7:44