Cryptology ePrint Archive: Report 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}$.

Category / Keywords: public-key cryptography / NTRU, Ideal lattice, Canonical embedding, Algebraic fields, CRPSF, Ring-LWE, Ring-SIS

Date: received 12 May 2018

Contact author: wyang1114 at mail sdu edu cn

Available format(s): PDF | BibTeX Citation

Version: 20180516:014957 (All versions of this report)

Short URL: ia.cr/2018/445

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]