A Zero-Knowledge Identification Scheme Based on Matrix Power Problem

This paper shows that in some case the matrix power function f(x)=CxDx is injective, where C and D are the the companion matrices of primitive polynomials. And a new zero-knowledge identification scheme based on the matrix power problem is proposed. It is perfect zero-knowledge for honest verifiers. Due to its simplicity, low-memory and low-computation costs, the proposed scheme is suitable for using in computationally limited devices for identification such as smart cards.