FINAL: Faster FHE instantiated with NTRU and LWE

Since the creation of the first FHE scheme by Gentry in 2009, there have been a number of constructions, each of which has been based on slightly different assumptions and all of which eventually come down to a hard lattice problem.

We can categorize these schemes as follows:

Those based on ideal lattices, such as the original proposal by Gentry and the optimization proposed by Smart-Vercauteren. Alas, these schemes have since been shown to be insecure.
The van Dijk-Gentry-Halevi-Vaikuntanathan scheme based on integers, which is no longer seen to be competitive in applications.
Those based on standard Learning-with-Errors (LWE), and its generalization to rings (Ring-LWE), such as the Brakerski-Gentry-Vaikuntanathan (BGV) and Brakerski/Fan-Vercauteren (BFV) schemes. One can also place the Cheon-Kim-Kim-Song (CKKS) for approximate FHE into this category because it is based on Ring-LWE.
The Gentry-Sahai-Waters (GSW) scheme, which led to the FHEW and TFHE systems. These are again based on Ring-LWE but have a different philosophy behind them when compared to BGV, BFV, and CKKS.
The schemes based on the NTRU assumption. Of these, we have a scheme due to Lopez-Alt, Tromer, and Vaikuntanathan, and the YASHE scheme of Bos, Lauter, Loftus, and Naehrig. Alas, these NTRU-based schemes were also shown to be insecure, as they had so-called “over-stretched parameters”.

Despite nearly fifteen years of research, we are therefore left with just the schemes based on LWE and Ring-LWE. This is not a good situation to be in, since this, in some sense, puts all our security eggs into one basket. The other disadvantage is that LWE-style encryption requires each ciphertext to consist of two elements, whereas the main advantage of the NTRU-based schemes is that a ciphertext consists of simply one ring element.

In recent work by researchers based at KU Leuven and Zama, which is published in AsiaCrypt 2022, we revisit the construction based on NTRU. The problem with earlier schemes based on NTRU was that the parameters had to be stretched to allow homomorphic operations, and bootstrapping in particular. The reason for stretching the parameters was because the NTRU schemes followed the philosophy of BGV, BFV, and CKKS in their construction. The stretched parameters resulted, eventually, in the cryptanalysis of NTRU-based schemes by Albrecht et al. (CRYPTO 2016).

Our new work combines the recent work of Ducas and van Woerden (ASIACRYPT 2021), which analyzes precisely how far one can stretch the parameters with NTRU using the philosophy behind the GSW, FHEW, and TFHE constructions. The result is a form of NTRU-based FHE which does not suffer from over-stretched parameters, and which is competitive when compared to schemes such as TFHE. Thus, we are potentially able to regain the advantage of NTRU’s one ring component per ciphertext. Whether the new NTRU-based scheme can be optimized to be truly competitive with the highly-optimized TFHE implementations now available (for example, such as that in the Zama Concrete library) will undoubtedly be the subject of further research.