Refining Identification Scheme Based on Isomorphism of Polynomials with Two Secrets: A New Theoretical and Practical Analysis

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.