Provably Secure NTRUEncrypt over Any Cyclotomic Field

Yang Yu, Guangwu Xu, Xiaoyun Wang

Damien Stehlé, Ron Steinfeld

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.

Duncan A. Buell

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.

Reza Ebrahimi Atani, Shahabaddin Ebrahimi Atani, Amir Hassani Karbasi

Jarvis and Nevins presented ETRU in 2013 which has applausive performance with moderate key-sizes and conjectured resistance to quantum computers. ETRU, as an efficient NTRUEncrypt-like cryptosystem, is over the ring of Eisenstein integers that is faster with smaller keys for the same or better level of security than does NTRUEncrypt which is a desirable alternative to public-key cryptosystems based on factorisation and discrete logarithm problem. However, because of its construction, doubts have regularly arisen on its security. In this paper, we propose how to modify ETRU to make it provably secure, under our modified assumption of quantum hardness of standard worst-case lattice problems, restricted to extended ideal lattices related to some extensions of cyclotomic fields structures. We describe the structure of all generated polynomial rings of quotient over direct product of Dedekind domains Z and Z[ζ3], where ζ3 is complex cube root of unity. We give a detailed description to show that if the private key polynomials of the ETRU are selected from direct product of some Dedekind domains using discrete Gaussians, then the public key, which is their ratio, is statistically indistinguishable from uniform over its range. The security then proves for our main system from the already proven hardness of the R-SIS and R-LWE problems by their extensions.