Paper 2022/089

NTRU-$\nu$-um: Secure Fully Homomorphic Encryption from NTRU with Small Modulus

Kamil Kluczniak

Abstract

NTRUEncrypt is one of the first lattice-based encryption schemes. Furthermore, one of the first fully homomorphic encryption (FHE) schemes were built on the NTRU problem. What makes NTRU appealing when designing cryptosystems is the age of the problem and relatively good performance results when compared to ring learning with errors. Unfortunately, current fully homomorphic schemes based on NTRU became extremely impractical duo to efficient sublattice attacks. Roughly speaking, these types of (leveled) homomorphic encryption schemes, to support a reasonable depth of the circuit we want to evaluate, require publishing RLWE or NTRU encryptions with a very large modulus. Unfortunately, recovering the sublattice and breaking the NTRU problem for such large moduli turns out to be easy, and to compensate, one would need to choose an impractically large dimension. We call NTRU instances with a too large modulus ``overstretched''. Due to the sublattice attacks, any serious work on practical NTRU-based fully homomorphic encryption essentially stopped. In this paper, we reactivate research on practical FHE that can be based on NTRU. To do so, we design an efficient bootstrapping scheme in which the noise growth is small enough to keep the modulus to dimension ratio relatively small, thus avoiding the negative consequences of ``overstretching'' the modulus. Our bootstrapping algorithm is an accumulation-type bootstrapping scheme analogous to FHEW/TFHE. Finally, we show that we can use the bootstrapping procedure to compute any function over $\mathbb{Z}_p$. Consequently, we obtain one of the fastest FHE schemes to compute arithmetic circuits over finite fields.