Paper 2025/795
Efficient Noncommutative KEMs from Twisted Dihedral Group Ring
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
-
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} }