NTRU-LPR IND-CPA: A New Ideal Lattices-based Scheme

Soda Diop; Bernard Ousmane Sané; Nafissatou Diarra; Michel Seck

Paper 2018/109

NTRU-LPR IND-CPA: A New Ideal Lattices-based Scheme

Soda Diop, Bernard Ousmane Sané, Nafissatou Diarra, and Michel Seck

Abstract

In this paper, we propose NTRU-LPR IND-CPA, a new secure scheme based on the decisional variant of Bounded Distance Decoding problem over rings (DR-BDD). This scheme is IND-CPA secure and has two KEM variants IND-CCA2 secure in the random oracle model. NTRU-LPR IND-CPA is similar to NTRU LPRime and LPR Cryptosystem. NTRU-LPR IND-CPA does not have a problem of decryption failures. Our polynomial ring can be any ring of the form $\mathbb{Z}[x]/(q,f(x))$, where $f$ is a polynomial of degree $n$ and $q$ is an integer. Relatively to the DR-BDD problem, we propose to use square-free polynomials and such polynomials include $f(x)=x^n-x-1$ (as in NTRU LPRime) and $f(x)=x^n-1$ (as in NTRU). To avoid some weaknesses in Ring-LWE or NTRU-like schemes (Meet-in-the-middle attack, Hybrid attack, Weak keys, etc.), we do not use sparse polynomials or inversion of polynomials. Furthermore, to avoid backdoors, all polynomials in our scheme can be generated by hash functions. We also give a short comparative analysis between our new scheme and some proposals of the NIST Post-Quantum call (November 2017).

Note: Forgotten character

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Keywords: Lattice-based Post-Quantum Cryptography NTRUEncrypt NTRU-Prime NTRU-LPRime NTRU IND-CPA KEM Ring-LWE Titanium Kyber NewHope FrodoKEM NTRU-HRSS-KEM Security proof
Contact author(s): fifiramatou @ gmail com
History: 2018-03-05: last of 4 revisions; 2018-01-30: received; See all versions
Short URL: https://ia.cr/2018/109
License: CC BY

BibTeX

@misc{cryptoeprint:2018/109,
      author = {Soda Diop and Bernard Ousmane Sané and Nafissatou Diarra and Michel Seck},
      title = {NTRU-LPR IND-CPA: A New Ideal Lattices-based Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2018/109},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/109}},
      url = {https://eprint.iacr.org/2018/109}
}