# NTRU homomorphic rerandomization

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?

• 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? – mikeazo Dec 11 '17 at 19:18
• 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. – TomBombadil Dec 12 '17 at 11:18
• Do you have a link to the paper where you got the formulas from or any reference for them? – mikeazo Dec 12 '17 at 13:19

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.

• So is there a workaround? – mikeazo Dec 12 '17 at 15:38
• Thank you for helping me out. I guess there is no way out of this problem? – TomBombadil Dec 12 '17 at 20:03
• 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. – zhenfei zhang Dec 12 '17 at 20:26