Paper 2018/445

CRPSF and NTRU Signatures over cyclotomic fields

Yang Wang and Mingqiang Wang

Abstract

We propose a detailed construction of Collision Resistance Preimage Sampleable Functions $($CRPSF$)$ over any cyclotomic field based on NTRU, hence give a provably secure NTRU Signature scheme $($NTRUSign$)$, which is strongly existentially unforgeable under adaptive chosen-message attacks in the random oracle module. The security of CRPSF $($NTRUSign$)$ is reduced to the corresponding small integer solution problem over rings $($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 conversion 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 and enrich the choices of the module $q$. Some useful results about $q$-ary lattices, regularity and uniformity of distribution of the public key of NTRUEncrypt are also generalized to more general algebraic field $K$, as long as $K$ is Galois over $\mathbb{Q}$.