Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM SIGSAC Conference on Computer and Communications Security (CCS)

NTRU-v-um: Secure Fully Homomorphic Encryption from NTRU with Small Modulus

Kamil Kluczniak

Published Nov 7, 2022• 25 citations
Publisher

Abstract

NTRUEncrypt is one of the first lattice-based encryption schemes. Furthermore, the earliest fully homomorphic encryption (FHE) schemes rely on the NTRU problem. Currently, NTRU is one of the leading candidates in the NIST post-quantum standardization competition. What makes NTRU appealing is the age of the cryptosystem and relatively good performance.

DOI
10.1145/3548606.3560700

Related papers

FINALLY: A Multi-Key FHE Scheme Based on NTRU and LWE

Jeongeun Park, Barry Van Leeuwen, Oliver Zajonc

Multi-key fully homomorphic encryption (MKFHE), a generalization of fully homomorphic encryption (FHE), enables a computation over encrypted data under multiple keys. The first MKFHE schemes were based on the NTRU primitive, however these early NTRU based FHE schemes were found to be insecure due to the problem of over-stretched parameters. Recently, in the case of standard (non-multi key) FHE a secure version, called FINAL, of NTRU has been found. In this work we extend FINAL to an MKFHE scheme, this allows us to benefit from some of the performance advantages provided by NTRU based primitives. Thus, our scheme provides competitive performance against current state-of-the-art multi-key TFHE, in particular reducing the computational complexity from quadratic to linear in the number of keys.

IACR Communications in Cryptology•Oct 7, 2024•11 citations

A Research on the Application Comparison of NTRU in Typical Fully Homomorphic Encryption Scheme

Xu Zhao, Zheng Yuan

Fully homomorphic encryption (FHE) allows arbitrary computations to be performed directly on encrypted data and is a core technology for privacy computing and secure cloud computing. The Number Theory Research Unit (NTRU) has become a research topic in this field by virtue of its lattice-based anti-quantum security, efficient polynomial operation characteristics and natural multi-key homomorphism capability. In this paper, we systematically review the key advances of NTRU-based FHE, covering the directions of the design of FHE, the optimization of bootstrapping techniques, and the application to FHE for multi-key approaches. Furthermore, the innovativeness and practical application challenges of the schemes are analyzed, and the future research trends are envisioned.

International Symposium on AI and Cybersecurity (ISAICS)•Oct 24, 2025•0 citations

Modified multi-key fully homomorphic encryption based on NTRU cryptosystem without key-switching

Xiaoliang Che, Tanping Zhou, Ningbo Li +3 more

The Multi-Key Fully Homomorphic Encryption (MKFHE) based on the NTRU cryptosystem is an important alternative to the post-quantum cryptography due to its simple scheme form, high efficiency, and fewer ciphertexts and keys. In 2012, Lopez-Alt et al. proposed the first NTRU-type MKFHE scheme, the LTV12 scheme, using the key-switching and modulus-reduction techniques, whose security relies on two assumptions: the Ring Learning With Error (RLWE) assumption and the Decisional Small Polynomial Ratio (DSPR) assumption. However, the LTV12 and subsequent NTRU-type schemes are restricted to the family of power-of-2 cyclotomic rings, which may affect the security in the case of subfield attacks. Moreover, the key-switching technique of the LTV12 scheme requires a circular application of evaluation keys, which causes rapid growth of the error and thus affects the circuit depth. In this paper, an NTRU-type MKFHE scheme over prime cyclotomic rings without key-switching is proposed, which has the potential to resist the subfield attack and decrease the error exponentially during the homomorphic evaluating process. First, based on the RLWE and DSPR assumptions over the prime cyclotomic rings, a detailed analysis of the factors affecting the error during the homomorphic evaluations in the LTV12 scheme is provided. Next, a Low Bit Discarded & Dimension Expansion of Ciphertexts (LBD&DEC) technique is proposed, and the inherent homomorphic multiplication decryption structure of the NTRU is proposed, which can eliminate the key-switching operation in the LTV12 scheme. Finally, a leveled NTRU-type MKFHE scheme is developed using the LBD&DEC and modulus-reduction techniques. The analysis shows that the proposed scheme compared to the LTV12 scheme can decrease the magnitude of the error exponentially and minimize the dimension of ciphertexts.

Tsinghua Science & Technology•Jun 12, 2020•18 citations

A provably secure variant of NTRU cryptosystem

Danilo Ciaffi

In 1996 Hoffstein, Pipher ad Silverman presented NTRUEncrypt, which is to date the fastest known lattice-based encryption scheme. Its moderate key-sizes, excellent asymptotic performance and conjectured resistance to quantum attacks make it a perfect candidate to succeed where factorization and discrete log fail. Unfortunately, no security proof has been produced for NTRUEncrypt nor for its signature counterpart NTRUSign. In 2013 Stehle and Steinfield proposed to apply some mild modification to the encryption and signature scheme to make them provably secure, under the assumed quantum hardness of standard worst-case lattice problems, restricted to a family of lattices related to some cyclotomic fields. In particular they showed that if the secret key polynomials of the encryption scheme are chosen from discrete Gaussians, then the public key, i.e their ratio, is statistically indistinguishable from uniform. The security will then follow from the hardness of the R-LWE problem.The aim of this thesis is to present Stehle's and Steinfield's work in a slightly more accessi-ble form, providing some more background and details in some points.

•Oct 12, 2018•0 citations

Beyond Quantum Threats: Bridging Fully Homomorphic Encryption Schemes

Mugurel Barcau, George Gugulea, Cristian Lupaşcu +3 more

In the advent of quantum computing, fully homomorphic encryption (FHE), whose security is based on the hardness of lattice problems, gains significant importance due to its quantum-resistant nature. This work provides a comprehensive survey of recent advancements in bridges between FHE schemes, with an emphasis on practical applications.

NATO science for peace and security series. D, Information and communication security•Feb 19, 2024•2 citations

Fully Homomorphic Encryption, Approximate Lattice Problem and LWE

Chunsheng Gu

Abstract: In this paper, we first introduce a new concept of approximate lattice problem (ALP), which is an extension of learning with errors (LWE). Next, we propose two ALP-based public key encryption schemes. Then, we construct two new fully homomorphic encryption scheme (FHE) based on respectively approximate principal ideal lattice problem with related modulus (APIP-RM) and approximate lattice problem with related modulus (ALP-RM). Moreover, we also extend our ALP-RM-based FHE to the ALP problem with unrelated modulus (ALP-UM). Our work is different from previous works in three aspects: (1) We extend the LWE problem to the ALP problem. This ALP problem is similar to the closest vector problem in lattice. We believe that this problem is independent of interest. (2) We construct a new FHE by using a re-randomizing method, which is different from the squashing decryption in previous works. (3) The expansion rate is merely O(k) with k a security parameter in Our FHE, which can be improved to O(logk) by using dimension reduction [BV11], whereas all previous schemes are at least O(k*logk) [BV11, Gen11, LNV11]. Our method can also decrease a factor k of the expansion rate in their schemes.

International Journal of Cloud Computing and Services Science (IJ-CLOSER)•Sep 24, 2012•4 citations
NTRUEncrypt is one of the first lattice-based encryption schemes. Furthermore, the earliest fully homomorphic encryption (FHE) schemes rely on the NTRU problem. Currently, NTRU is one of the leading candidates in the NIST post-quantum standardization competition. What makes NTRU appealing is the age of the cryptosystem and relatively good performance.
Multi-key fully homomorphic encryption (MKFHE), a generalization of fully homomorphic encryption (FHE), enables a computation over encrypted data under multiple keys. The first MKFHE schemes were based on the NTRU primitive, however these early NTRU based FHE schemes were found to be insecure due to the problem of over-stretched parameters. Recently, in the case of standard (non-multi key) FHE a secure version, called FINAL, of NTRU has been found. In this work we extend FINAL to an MKFHE scheme, this allows us to benefit from some of the performance advantages provided by NTRU based primitives. Thus, our scheme provides competitive performance against current state-of-the-art multi-key TFHE, in particular reducing the computational complexity from quadratic to linear in the number of keys.
Fully homomorphic encryption (FHE) allows arbitrary computations to be performed directly on encrypted data and is a core technology for privacy computing and secure cloud computing. The Number Theory Research Unit (NTRU) has become a research topic in this field by virtue of its lattice-based anti-quantum security, efficient polynomial operation characteristics and natural multi-key homomorphism capability. In this paper, we systematically review the key advances of NTRU-based FHE, covering the directions of the design of FHE, the optimization of bootstrapping techniques, and the application to FHE for multi-key approaches. Furthermore, the innovativeness and practical application challenges of the schemes are analyzed, and the future research trends are envisioned.
The Multi-Key Fully Homomorphic Encryption (MKFHE) based on the NTRU cryptosystem is an important alternative to the post-quantum cryptography due to its simple scheme form, high efficiency, and fewer ciphertexts and keys. In 2012, Lopez-Alt et al. proposed the first NTRU-type MKFHE scheme, the LTV12 scheme, using the key-switching and modulus-reduction techniques, whose security relies on two assumptions: the Ring Learning With Error (RLWE) assumption and the Decisional Small Polynomial Ratio (DSPR) assumption. However, the LTV12 and subsequent NTRU-type schemes are restricted to the family of power-of-2 cyclotomic rings, which may affect the security in the case of subfield attacks. Moreover, the key-switching technique of the LTV12 scheme requires a circular application of evaluation keys, which causes rapid growth of the error and thus affects the circuit depth. In this paper, an NTRU-type MKFHE scheme over prime cyclotomic rings without key-switching is proposed, which has the potential to resist the subfield attack and decrease the error exponentially during the homomorphic evaluating process. First, based on the RLWE and DSPR assumptions over the prime cyclotomic rings, a detailed analysis of the factors affecting the error during the homomorphic evaluations in the LTV12 scheme is provided. Next, a Low Bit Discarded & Dimension Expansion of Ciphertexts (LBD&DEC) technique is proposed, and the inherent homomorphic multiplication decryption structure of the NTRU is proposed, which can eliminate the key-switching operation in the LTV12 scheme. Finally, a leveled NTRU-type MKFHE scheme is developed using the LBD&DEC and modulus-reduction techniques. The analysis shows that the proposed scheme compared to the LTV12 scheme can decrease the magnitude of the error exponentially and minimize the dimension of ciphertexts.
In 1996 Hoffstein, Pipher ad Silverman presented NTRUEncrypt, which is to date the fastest known lattice-based encryption scheme. Its moderate key-sizes, excellent asymptotic performance and conjectured resistance to quantum attacks make it a perfect candidate to succeed where factorization and discrete log fail. Unfortunately, no security proof has been produced for NTRUEncrypt nor for its signature counterpart NTRUSign. In 2013 Stehle and Steinfield proposed to apply some mild modification to the encryption and signature scheme to make them provably secure, under the assumed quantum hardness of standard worst-case lattice problems, restricted to a family of lattices related to some cyclotomic fields. In particular they showed that if the secret key polynomials of the encryption scheme are chosen from discrete Gaussians, then the public key, i.e their ratio, is statistically indistinguishable from uniform. The security will then follow from the hardness of the R-LWE problem.The aim of this thesis is to present Stehle's and Steinfield's work in a slightly more accessi-ble form, providing some more background and details in some points.
Abstract: In this paper, we first introduce a new concept of approximate lattice problem (ALP), which is an extension of learning with errors (LWE). Next, we propose two ALP-based public key encryption schemes. Then, we construct two new fully homomorphic encryption scheme (FHE) based on respectively approximate principal ideal lattice problem with related modulus (APIP-RM) and approximate lattice problem with related modulus (ALP-RM). Moreover, we also extend our ALP-RM-based FHE to the ALP problem with unrelated modulus (ALP-UM). Our work is different from previous works in three aspects: (1) We extend the LWE problem to the ALP problem. This ALP problem is similar to the closest vector problem in lattice. We believe that this problem is independent of interest. (2) We construct a new FHE by using a re-randomizing method, which is different from the squashing decryption in previous works. (3) The expansion rate is merely O(k) with k a security parameter in Our FHE, which can be improved to O(logk) by using dimension reduction [BV11], whereas all previous schemes are at least O(k*logk) [BV11, Gen11, LNV11]. Our method can also decrease a factor k of the expansion rate in their schemes.