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

Lecture notes in computer science

Provably Secure NTRUEncrypt over Any Cyclotomic Field

Yang Wang, Mingqiang Wang

Published Jan 1, 2019• 8 citations
Publisher
DOI
10.1007/978-3-030-10970-7_18

Related papers

Provably Secure NTRU Instances over Prime Cyclotomic Rings

Yang Yu, Guangwu Xu, Xiaoyun Wang

Lecture notes in computer science•Jan 1, 2017•30 citations

Making NTRUEncrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices.

Damien Stehlé, Ron Steinfeld

•Jan 1, 2013•45 citations

Provably Secure NTRUEncrypt over More General Cyclotomic Rings.

Yang Yu, Guangwu Xu, Xiao-Yun Wang

NTRUEncrypt is a fast and standardized lattice-based public key encryption scheme, but it lacks a proof of security.Stehlé and Steinfeld (EUROCRYPT 2011) first gave a variant of NTRUEncrypt, denoted by pNE, over power-of-2 cyclotomic rings.The pNE scheme is provably secure assuming the hardness of worst-case problems over ideal lattices.Recently, Yu, Xu and Wang (PKC 2017) proposed a pNE variant over prime cyclotomic rings, but it requires the parameters to be of rather larger sizes.In this paper, working with canonical embedding, we modify the key generation algorithm of pNE scheme to make it applicable to general cyclotomic rings.Through an improved analysis, we provide tighter parameters of pNE over prime power cyclotomic rings.To be more specific, even for the general case, our parameters are as good as that obtained by Stehlé and Steinfeld for the case of power-of-2; compared to that of Yu, Xu and Wang (PKC 2017), the sizes of our parameters get significantly reduced.Thus our result not only applies to a larger class of rings but also enjoys greater efficiency.In proving our results, we have developed some technical tools which may be of general interest.Some remarks on further extension of the work (e.g., for more general polynomial rings) have also been made.

•Jan 1, 2017•4 citations

Lattice-Based Cryptography and NTRU

Duncan A. Buell

Undergraduate topics in computer science•Jan 1, 2021•2 citations

Provably Secure Identity-Based Encryption and Signature over Cyclotomic Fields

Yang Wang, Mingqiang Wang, Jingdan Zou +2 more

Identity-based cryptography is a type of public key cryptography with simple key management procedures. To our knowledge, till now, the existing identity-based cryptography based on NTRU is all over power-of-2 cyclotomic rings. Whether there is provably secure identity-based cryptography over more general fields is still open. In this paper, with the help of the results of collision resistance preimage sampleable functions (CRPSF) over cyclotomic fields, we give concrete constructions of provably secure identity-based encryption schemes (IBE) and identity-based signature schemes (IBS) based on NTRU over any cyclotomic field. Our IBE schemes are provably secure under adaptive chosen-plaintext and adaptive chosen-identity attacks, meanwhile, our IBS schemes are existentially unforgeable against adaptively chosen message and adaptively chosen identity attacks for any probabilistic polynomial time (PPT) adversary in the random oracle model. The securities of both schemes are based on the worst-case approximate shortest independent vectors problem (SIVPγ) over corresponding ideal lattices. The secret key size of our IBE (IBS) scheme is short—only one (two) ring element(s). The ciphertext (signature) is also short—only two (three) ring elements. Meanwhile, as the case of NTRUEncrypt, our IBE scheme could encrypt n bits in each encryption process. These properties may make our schemes have more advantages for some IoT applications over postquantum world in theory.

Wireless Communications and Mobile Computing•Oct 17, 2019•4 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
NTRUEncrypt is a fast and standardized lattice-based public key encryption scheme, but it lacks a proof of security.Stehlé and Steinfeld (EUROCRYPT 2011) first gave a variant of NTRUEncrypt, denoted by pNE, over power-of-2 cyclotomic rings.The pNE scheme is provably secure assuming the hardness of worst-case problems over ideal lattices.Recently, Yu, Xu and Wang (PKC 2017) proposed a pNE variant over prime cyclotomic rings, but it requires the parameters to be of rather larger sizes.In this paper, working with canonical embedding, we modify the key generation algorithm of pNE scheme to make it applicable to general cyclotomic rings.Through an improved analysis, we provide tighter parameters of pNE over prime power cyclotomic rings.To be more specific, even for the general case, our parameters are as good as that obtained by Stehlé and Steinfeld for the case of power-of-2; compared to that of Yu, Xu and Wang (PKC 2017), the sizes of our parameters get significantly reduced.Thus our result not only applies to a larger class of rings but also enjoys greater efficiency.In proving our results, we have developed some technical tools which may be of general interest.Some remarks on further extension of the work (e.g., for more general polynomial rings) have also been made.
Identity-based cryptography is a type of public key cryptography with simple key management procedures. To our knowledge, till now, the existing identity-based cryptography based on NTRU is all over power-of-2 cyclotomic rings. Whether there is provably secure identity-based cryptography over more general fields is still open. In this paper, with the help of the results of collision resistance preimage sampleable functions (CRPSF) over cyclotomic fields, we give concrete constructions of provably secure identity-based encryption schemes (IBE) and identity-based signature schemes (IBS) based on NTRU over any cyclotomic field. Our IBE schemes are provably secure under adaptive chosen-plaintext and adaptive chosen-identity attacks, meanwhile, our IBS schemes are existentially unforgeable against adaptively chosen message and adaptively chosen identity attacks for any probabilistic polynomial time (PPT) adversary in the random oracle model. The securities of both schemes are based on the worst-case approximate shortest independent vectors problem (SIVPγ) over corresponding ideal lattices. The secret key size of our IBE (IBS) scheme is short—only one (two) ring element(s). The ciphertext (signature) is also short—only two (three) ring elements. Meanwhile, as the case of NTRUEncrypt, our IBE scheme could encrypt n bits in each encryption process. These properties may make our schemes have more advantages for some IoT applications over postquantum world in theory.
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.