Cryptology ePrint Archive: Report 2010/504
Practical Cryptanalysis of the Identification Scheme Based on the Isomorphism of Polynomial with One Secret Problem
Charles Bouillaguet and Jean-Charles Faugère and Pierre-Alain Fouque and Ludovic Perret
Abstract: This paper presents a practical cryptanalysis of the Identification
Scheme proposed by Patarin at Crypto 1996. This scheme relies on the
hardness of the Isomorphism of Polynomial with One Secret (IP1S),
and enjoys shorter key than many other schemes based on the hardness
of a combinatorial problem (as opposed to number-theoretic
problems). Patarin proposed concrete parameters that have not been
broken faster than exhaustive search so far. On the theoretical
side, IP1S has been shown to be harder than Graph Isomorphism, which
makes it an interesting target. We present two new deterministic
algorithms to attack the IP1S problem, and we rigorously analyze
their complexity and success probability. We show that they can
solve a (big) constant fraction of all the instances of degree two
in polynomial time. We verified that our algorithms are very
efficient in practice. All the parameters with degree two proposed
by Patarin are now broken in a few seconds. The parameters with
degree three can be broken in less than a CPU-month. The
identification scheme is thus quite badly broken.
Category / Keywords: public-key cryptography / identification protocols, cryptanalysis, multivariate crypto
Date: received 1 Oct 2010
Contact author: charles bouillaguet at ens fr
Available format(s): PDF | BibTeX Citation
Version: 20101002:191236 (All versions of this report)
Short URL: ia.cr/2010/504
[ Cryptology ePrint archive ]