Structure of quaternion-type algebras and a post-quantum signature algorithm

Abstract

Algebraic digital signature algorithms with a commutative hidden group, which are based on the computational difficulty of solving large systems of power equa- tions, are promising candidates for post-quantum cryptoschemes, especially in securing applications like the internet of things (IoT) and other information tech- nologies. Associative finite non-commutative algebras are used as an algebraic support of the said algorithms. Among such algebras, finite quaternion-type al- gebras have been identified as strong candidates for providing algebraic support. This paper investigates the decomposition of these algebras into commutative subrings and explores their multiplicative groups, which can serve as poten- tial hidden groups. The analysis reveals the existence of three distinct types of subrings, with derived formulas for the number of subrings and the orders of their multiplicative groups. These findings align with previous studies on four- dimensional algebras defined by sparse basis vector multiplication tables. Using the finite quaternion-type algebras as algebraic support, a novel post-quantum signature algorithm characterized in using two mutually non-commutative hid- den groups has been developed.