I am currently implementing NTRU, keeping its homomorphic properties. I want to implement rerandomization like this:

  • Encryption: $e = pr * h + m \pmod q$

  • Rerandomization: $e = e + pr \pmod q$ (using a new random $r$)

  • Decryption is as described in the original NTRU paper.

The first few rerandomizations work just fine, but after some iterations I am not able to decrypt it anymore. What am I missing in my formula?

  • $\begingroup$ Do you ever have problems decrypting after performing a bunch of homomorphic additions? I'm not as familiar with NTRU as I should be, can you add a better description of what everything is? $\endgroup$
    – mikeazo
    Commented Dec 11, 2017 at 19:18
  • $\begingroup$ I had no problems decrypting before i used the rerandomization 6 to 8 times. It seems to depend on the random r after which iteration the error occurs. $\endgroup$ Commented Dec 12, 2017 at 11:18
  • $\begingroup$ Do you have a link to the paper where you got the formulas from or any reference for them? $\endgroup$
    – mikeazo
    Commented Dec 12, 2017 at 13:19

1 Answer 1


The decryption error occurs for the following reason.

In a classical NTRU decryption you compute

$c = e * f \pmod q \pmod p \\ \ \ = p r*h*f + m*f \pmod q \pmod p\\ \ \ = p r*g + m*f \pmod q \pmod p$

By construction $f = 1 \bmod p$. Therefore, if the all the coefficients of $(p r*g + m*f)$ are within the interval of $0$ and $q-1$, (or $-q/2$ and $q/2$, depending on how you define mod operation. Then you will have $c = m \bmod p$. On the other hand if any coefficient is not within the interval, $\bmod q$ will cause a wraparound since in this case:

$p r*g + m*f \pmod q \pmod p \neq p r*g + m*f \pmod p $

The current parameters for NTRU ensures that this wraparound does not happen except for negligible probability, say $2^{-128}$, etc.

Now back to your re-randomization process, suppose

$e_1 = pr_1*h+m$ and $e_2 = e_1+pr_2$

When decrypting $e_2$, you will have

$c = e_2 * f \pmod q \pmod p \\ \ \ = p (r_1 +r_2)*h*f + m*f \pmod q \pmod p \\ \ \ = p (r_1+r_2)*g + m*f \pmod q \pmod p $

As you can see, you have grown the $r$ term and therefore you increase the decryption error probability. You probably will be fine with a few re-randomizations since adding only a few of $r_i$ doesn't increase the $r$ term much. But eventually you will see a decryption error by repeatedly re-randomization.

  • $\begingroup$ So is there a workaround? $\endgroup$
    – mikeazo
    Commented Dec 12, 2017 at 15:38
  • $\begingroup$ Thank you for helping me out. I guess there is no way out of this problem? $\endgroup$ Commented Dec 12, 2017 at 20:03
  • 1
    $\begingroup$ Well, in fact this re-randomization uses the additive homomorphic property of NTRU. This is a somewhat homomorphic encryption scheme as per Gentry's definition. The way to build a fully homomorphic version of the scheme is through bootstrapping. Examples of such a construction with NTRU is can be found from the LTV scheme. That allows you to start from a fresh $r$ once it got accumulated too much. Nonetheless bootstrapping is not very efficient. You are better off with a more tolerate parameter set if you know exactly how many re-randomizations you need. $\endgroup$ Commented Dec 12, 2017 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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