Autopotency and Conjugacy of Non-Diagonalizable Matrices for Challenge–Response Authentication

We present an algebraic framework for constructing challenge–response authentication protocols based on powers of non-diagonalizable matrices over finite fields. The construction relies on upper triangular Toeplitz matrices with a single Jordan block and on their structured power expansions, which induce nonlinear relations between matrix parameters and exponents through an autopotency phenomenon. The protocol is built from a cyclic family of matrix products derived from secret matrices (Ai)i=1n⊂GLk(Fp): for each index i, a product Pi=AiAi+1…Ai+n−1 is formed (indices modulo n), and its power Pi(x) is published for a secret exponent x. The resulting family of powered products is linked by conjugation via the unknown factors Ai, enabling an interactive authentication mechanism in which the prover demonstrates the knowledge of selected factors by satisfying explicit conjugacy relations. We formalize the underlying algebraic problems in terms of factor recovery and conjugacy identification from powered products, and analyze how the enforced non-diagonalizable structure and Toeplitz constraints lead to coupled multivariate polynomial systems. These systems arise naturally from the algebraic design of the construction and do not admit immediate reductions to classical discrete logarithm settings. The framework illustrates how non-diagonalizable matrix structures and structured conjugacy relations can be used to define concrete authentication primitives in noncommutative algebraic settings, and provides a basis for further cryptanalytic and cryptographic investigation.