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


  • 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.


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.

  • $\begingroup$ 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. $\endgroup$
    – kelalaka
    Jan 16 at 22:12
  • $\begingroup$ It also says that, with standard deviation, the probability of $e > q/4$ is negligible. $\endgroup$
    – kelalaka
    Jan 16 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)$


  • 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$.


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")


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)
  • $\begingroup$ Note: I did not go to verify the examples, since $q$ is so small to work. The bounds must be carefully controlled. $\endgroup$
    – kelalaka
    Jan 14 at 7:44
  • $\begingroup$ first of all thanks for answer. Please read my edit and add your opinion to your answer before i accept your answer. $\endgroup$
    – alfred
    Jan 16 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.