3
$\begingroup$

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?

| improve this question | |
$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – cygnusv Nov 25 '15 at 8:03
  • $\begingroup$ Yes, sure, you are right, the coefficients are in $\mathbb{Z}_q$, not in $\mathbb{Z}$. I was not very precise. $\endgroup$ – Hilder Vitor Lima Pereira Nov 25 '15 at 12:16
  • $\begingroup$ Anyway, it does not make sense yet, does it? Because multiplying each coefficient by some inverse modular will not discard bits... $\endgroup$ – Hilder Vitor Lima Pereira Nov 25 '15 at 12:18
  • $\begingroup$ You are right. Forget what I said :P $\endgroup$ – cygnusv Nov 25 '15 at 12:20
  • $\begingroup$ 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 :) $\endgroup$ – Hilder Vitor Lima Pereira Nov 25 '15 at 12:26
4
$\begingroup$

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

If you're interested in other examples of where the technique of discarding the lower-order bits is used, see works on the Learning with Rounding problem. (The paragraph in the middle of page 2 gives an equivalent explanation of this notation.)

| improve this answer | |
$\endgroup$
  • $\begingroup$ So, in order to recover the original message $m$ from the new ciphertext $c'$ do we have to decrypt $w^i \cdot c'$ ? $\endgroup$ – Hilder Vitor Lima Pereira Nov 26 '15 at 13:30

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.