DiTRU: A Resurrection of NTRU over Dihedral Group

Ali Raya; Vikas Kumar; Sugata Gangopadhyay

Paper 2024/805

DiTRU: A Resurrection of NTRU over Dihedral Group

Ali Raya

, Indian Institute of Technology Roorkee

Vikas Kumar

, Indian Institute of Technology Roorkee

Sugata Gangopadhyay, Indian Institute of Technology Roorkee

Abstract

NTRU-like cryptosystems are among the most studied lattice-based post-quantum candidates. While most NTRU proposals have been introduced over a commutative ring of quotient polynomials, other rings can be used. Noncommutative algebra has been endorsed as a direction to build new variants of NTRU a long time ago. The first attempt to construct a noncommutative variant was due to Hoffstein and Silverman motivated by more resistance to lattice attack. The scheme has been built over the group ring of a dihedral group. However, their design differed from standard NTRU and soon was found vulnerable to algebraic attacks. In this work, we revive the group ring NTRU over the dihedral group as an instance of the GR-NTRU framework. Unlike many proposals of noncommutative variants in the literature, our work focuses on putting the scheme into practice. We clear all the aspects that make our scheme implementable by proposing an efficient inversion algorithm over the new setting of the noncommutative ring, describing the decryption failure model, and analyzing the lattice associated with our instantiation. Finally, we discuss the best-known attacks against our scheme and provide an implementation targeting 128-bit, 192-bit, and 256-bit levels of security as proof of its practicality.

Note: This paper is accepted for publication in AfricaCrypt 2024.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. To be published in AfricaCrypt 2024.
Keywords: NTRU noncommutative post quantum lattice-based
Contact author(s): ali_r @ cs iitr ac in
v_kumar @ ma iitr ac in
sugata gangopadhyay @ cs iitr ac in
History: 2024-05-27: approved; 2024-05-24: received; See all versions
Short URL: https://ia.cr/2024/805
License: CC BY

BibTeX

@misc{cryptoeprint:2024/805,
      author = {Ali Raya and Vikas Kumar and Sugata Gangopadhyay},
      title = {{DiTRU}: A Resurrection of {NTRU} over Dihedral Group},
      howpublished = {Cryptology ePrint Archive, Paper 2024/805},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/805}},
      url = {https://eprint.iacr.org/2024/805}
}