Cryptanalysis of a System Based on Twisted Dihedral Group Algebras
PDF

Keywords

Group Algebra
Asymmetric key exchange
Twisted Multiplication

How to Cite

Tinani, S. (2024). Cryptanalysis of a System Based on Twisted Dihedral Group Algebras. Mathematical Cryptology, 4(1), 23–35. Retrieved from https://ojs.test.flvc.org/mathcryptology/article/view/132262

Abstract

Several cryptographic protocols constructed based on less-known algorithmic problems, such as those in non-commutative groups, group rings, semigroups, etc., which claim quantum security, have been broken through classical reduction methods within their specific proposed platforms. A rigorous examination of the complexity of these algorithmic problems is therefore an important topic of research. In this paper, we present a cryptanalysis of a public key exchange system based on a decomposition-type problem in the so-called twisted group algebras of the dihedral group D2n over a finite field GF(q). Our method of analysis relies on an algebraic reduction of the original problem to a set of equations over GF(q) involving circulant matrices, and a subsequent solution to these equations. Our attack runs in polynomial time and succeeds with probability at least 90 percent for the parameter values provided by the authors. We also show that the underlying algorithmic problem, while based on a non-commutative structure, may be formulated as a commutative semigroup action problem.

PDF
Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Copyright (c) 2024 Simran Tinani