# Truncating ciphertexts on ring-LWE schemes

On the section 5.4 of the paper Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme, the authors explain how to discard some bits of the ciphertexts to get smaller ciphertexts and smaller evaluation keys.

The function Discard simply takes a ciphertext $c$ and an integer $i$ (number of words to be discarded) and returns

$\lfloor w^{-i}c \rfloor$

where $w$ is the number of bits of each word.

But, since $c$ is a polynomial with integer coefficients (coefficients in $\mathbb{Z}_q$), I don't understand how this function is discarding bits. To me, it seems like it is only zeroing all the coefficients whose absolute values are smaller than $w^i$.

I also checked the reference from where this technique of truncating ciphertext was extracted, named the paper Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP, but its explanation does not make sense to me as well.

So, do you know how this technique works? Could you give more details or show me what point I am interpreting wrong?

• AFAIK, coefficients of $c$ are in $\mathbb Z_q$, therefore $\lfloor w^{-i}c \rfloor$ is actually $\lfloor ((w^i)^{-1} \bmod q) \cdot c \rfloor$. – cygnusv Nov 25 '15 at 8:03
• Yes, sure, you are right, the coefficients are in $\mathbb{Z}_q$, not in $\mathbb{Z}$. I was not very precise. – Hilder Vitor Lima Pereira Nov 25 '15 at 12:16
• Anyway, it does not make sense yet, does it? Because multiplying each coefficient by some inverse modular will not discard bits... – Hilder Vitor Lima Pereira Nov 25 '15 at 12:18
• You are right. Forget what I said :P – cygnusv Nov 25 '15 at 12:20
• By the way I don't think this multiplication is done as you said, because if it was the case, all the results would be in $\mathbb{Z}_q$ and it would be pointless to take the floor... But thanks, @cygnusv :) – Hilder Vitor Lima Pereira Nov 25 '15 at 12:26

The expression $c' = \lfloor w^{-i} c \rfloor$ is a slight abuse of notation. What it technically means is to interpret each coefficient of $c$ as real number, divide by $w^i$, round the result to the nearest integer, and then interpret it as an element of $\mathbb{Z}_q$ again.
This is equivalent to expressing each $\mathbb{Z}_q$ coefficient of the ciphertext as a bitstring, and then discarding the $i$ least significant $w$-words of each bitstring. It also explains why $w^i c'$ is equal to c with the $i$ least significant $w$-words of $c$ being set to $0$, as the authors say in the next sentence of Section 5.4.
By the way, $w$ does not represent the number of bits in each word. Instead, $w$ describes the size of each word, and so the number of bits in each word is actually $log_2(w)$.
• So, in order to recover the original message $m$ from the new ciphertext $c'$ do we have to decrypt $w^i \cdot c'$ ? – Hilder Vitor Lima Pereira Nov 26 '15 at 13:30