Enhanced matrix power function for cryptographic primitive construction (Q2415047)

Summary: A new enhanced matrix power function (MPF) is presented for the construction of cryptographic primitives. According to the definition in previously published papers, an MPF is an action of two matrices powering some base matrix on the left and right. The MPF inversion equations, corresponding to the MPF problem, are derived and have some structural similarity with classical multivariate quadratic (MQ) problem equations. Unlike the MQ problem, the MPF problem seems to be more complicated, since its equations are not defined over the field, but are represented as left-right action of two matrices defined over the infinite near-semiring on the matrix defined over the certain infinite, additive, noncommuting semigroup. The main results are the following: (1) the proposition of infinite, nonsymmetric, and noncommuting algebraic structures for the construction of the enhanced MPF, satisfying associativity conditions, which are necessary for cryptographic applications; (2) the proof that MPF inversion is polynomially equivalent to the solution of a certain kind of generalized multivariate quadratic (MQ) problem which can be reckoned as hard; (3) the estimation of the effectiveness of direct MPF value computation; and (4) the presentation of preliminary security analysis, the determination of the security parameter, and specification of its secure value. These results allow us to make a conjecture that enhanced MPF can be a \textit{candidate} one-way function (OWF), since the effective (polynomial-time) inversion algorithm for it is not yet known. An example of the application of the proposed MPF for the Key Agreement Protocol (KAP) is presented. Since the direct MPF value is computed effectively, the proposed MPF is suitable for the realization of cryptographic protocols in devices with restricted computation resources.