Paper 2025/795

Efficient Noncommutative KEMs from Twisted Dihedral Group Ring

Ali Raya, Indiain Insititute of Technology, Roorkee
Vikas Kumar, Indiain Insititute of Technology, Roorkee
Sugata Gangopadhyay, Indiain Insititute of Technology, Roorkee
Aditi Kar Gangopadhyay, aditi.gangopadhyay[at]ma.iitr.ac.in
Abstract

NTRU schemes have been extensively studied as post-quantum proposals within the category of lattice-based constructions. Numerous designs have been introduced with security assumptions based on the NTRU hard problem; some focused on security, and others were motivated by faster computations. Recently, some proposals for noncommutative NTRU have appeared in the literature, claiming more resistance to some algebraic attacks. While these proposals provide practical cryptosystems, they fail to perform similarly to the original NTRU over the ring of integers. This work introduces the first construction of noncommutative NTRU that matches the speed of NTRU over the ring of integers. Additionally, we present another construction over the ring of Eisenstein integers, demonstrating that performance can be further enhanced. We comprehensively implement the Key Encapsulation Mechanisms (KEMs) based on our constructions and compare their efficiency and compactness to both commutative and noncommutative NTRU variants in the literature. Our findings indicate that the new designs provide competitive memory and time requirements while utilizing noncommutative algebra. For example, our noncommutative KEM based on the twisted dihedral group ring over the ring of integers achieves encapsulation and decapsulation speeds comparable to NTRU-HPS, with a key generation speed that is 2.5 times faster. Additionally, our construction based on the ring of Eisenstein integers is at least 1.6 times faster for key generation and 1.3 times faster for both encapsulation and decapsulation compared to NTRU-HPS.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
NTRUTwisted group ringsNoncommutativeDihedral group
Contact author(s)
ali_r @ cs iitr ac in
v_kumar @ ma iitr ac in
sugata gangopadhyay @ cs iitr ac in
aditi gangopadhyay @ ma iitr ac in
History
2025-05-05: approved
2025-05-04: received
See all versions
Short URL
https://ia.cr/2025/795
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/795,
      author = {Ali Raya and Vikas Kumar and Sugata Gangopadhyay and Aditi Kar Gangopadhyay},
      title = {Efficient Noncommutative {KEMs} from Twisted Dihedral Group Ring},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/795},
      year = {2025},
      url = {https://eprint.iacr.org/2025/795}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.