CRPSF and NTRU Signatures over cyclotomic fields

Classical NTRUEncrypt is one of the fastest known lattice-based encryption schemes. Its counterpart, NTRUSign, also has many advantages, such as moderate key sizes, high efficiency and potential of resisting attacks from quantum computers. However, like classical NTRUEncrypt, the security of NTRUSign is also heuristic. Whether we can relate the security of NTRUSign to the worst-case lattice problems like NTRUEncrypt is still an open problem. Our main contribution is that we propose a detailed construction of Collision Resistance Preimage Sampleable Functions $($CRPSF$)$ over any cyclotomic field based on NTRU. By using GPV\u27s construction, we can give a provably secure NTRU Signature scheme $($NTRUSign$)$, which is strongly existentially unforgeable under adaptive chosen-message attacks in the $($quantum$)$ random oracle model. The security of CRPSF $($NTRUSign$)$ is reduced to the corresponding ring small integer solution problem $($Ring-SIS$)$. More precisely, the security of our scheme is based on the worst-case approximate shortest independent vectors problem $($SIVP$_\gamma$$)$ over ideal lattices. For any fixed cyclotomic field, we give a probabilistic polynomial time $($PPT$)$ key generation algorithm which shows how to extend the secret key of NTRUEncrypt to the secret key of NTRUSign. This algorithm is important for constructions of many cryptographic primitives based on NTRU, for example, CRPSF, NTRUSign, identity-based encryption and identity-based signature. We also delve back into former construction of NTRUEncrypt, give a much tighter reduction from decision dual-Ring-LWE problem (where the secret is chosen form the codifferent ideal) to decision primal-Ring-LWE problem (where the secret is chosen form the ring of integers) and give a provably secure NTRUEncrypt over any cyclotomic ring. Some useful results about $q$-ary lattices, regularity and uniformity of distribution of the public keys of NTRUEncrypt are also extended to more general algebraic fields