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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint. Minor revision.
- Keywords
- Fully Homomorphic EncryptionNTRUFHEWTFHE
- Contact author(s)
- kamil kluczniak @ cispa de
- History
- 2022-01-25: received
- Short URL
- https://ia.cr/2022/089
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/089, author = {Kamil Kluczniak}, title = {NTRU-$\nu$-um: Secure Fully Homomorphic Encryption from NTRU with Small Modulus}, howpublished = {Cryptology ePrint Archive, Paper 2022/089}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/089}}, url = {https://eprint.iacr.org/2022/089} }