Results on the Key Space of Group-Ring NTRU: The Case of the Dihedral Group

NTRU-like schemes are among the most studied lattice-based cryptosystems. Since the first scheme was introduced, many variants of NTRU have been developed in the literature. These variants involve a high degree of freedom in designing the cryptosystem aspects, from sampling the polynomials (representing the private key) to the underlying ring used to build the structure. As a generalization of NTRU, Group-ring NTRU describes how to create different variants of NTRU by employing other groups. While most designs in literature are built over a commutative group-ring, a non-commutative group can also be used. Some groups can result in more efficient implementations or better resistance against some attacks. However, introducing new groups triggers fundamental questions related to the key space, encryption, decryption failures, and correctness of the new scheme. This paper uses the non-commutative dihedral group to explore the key space for a group-ring NTRU. Our work investigates whether elements sampled according to specific properties in the reference NTRU implementations can still be used as a key space in the case of the dihedral group. We show that the key space is suitable for building a non-commutative group-ring NTRU based on the dihedral group. Experimental results are provided for polynomials with different properties and compared to the results of reference implementations of NTRU over well-defined parameter sets.