Biblio

Symmetry ergodic matrices exponentiation (SEME) problem is to find x, given CxMDx, where C and D are the companion matrices of primitive polynomials and M is an invertible matrix over finite field. This paper proposes a new zero-knowledge identification scheme based on SEME problem. It is perfect zero-knowledge for honest verifiers. The scheme could provide a candidate cryptographic primitive in post quantum cryptography. Due to its simplicity and naturalness, low-memory, low-computation costs, the proposed scheme is suitable for using in computationally limited devices for identification such as smart cards.

The isomorphism of polynomials with two secret (IP2S) problem is one candidate of computational assumptions for post- quantum cryptography. The only identification scheme based on IP2S is introduced in 1996 by Patarin. However, the security of the scheme has not been formally proven and we discover that the originally proposed parameters are no longer secure based on the most recent research. In this paper, we present the first formal security proof of identification scheme based on IP2S against impersonation under passive attack, sequential active attack, and concurrent active attack. We propose new secure parameters and methods to reduce the implementation cost. Using the proposed methods, we are able to cut the storage cost and average communication cost in a drastic way that the scheme is implementable even on the lightweight devices in the current market.