2005 | OriginalPaper | Chapter
A Fast Cryptanalysis of the Isomorphism of Polynomials with One Secret Problem
Author : Ludovic Perret
Published in: Advances in Cryptology – EUROCRYPT 2005
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
At Eurocrypt’96, Patarin proposed [9] new cryptographic schemes based on the
Isomorphism of Polynomials with one Secret
problem (IP1S) [9]. We study in this paper a restriction of IP1S called
Polynomial Linear Equivalence
problem (PLE) [7]. We show that PLE is in fact not a restriction of IP1S, in the sense that any algorithm solving PLE can be efficiently transformed into an algorithm for solving IP1S. Motivated by the cryptanalysis of schemes based on IP1S, we present a new efficient algorithm for solving PLE. This algorithm is mainly based on a differential property of PLE. The main advantage of this approach is to translate PLE into a simple linear algebra problem. The performances of our algorithm evidence that, with the parameters proposed in [9], schemes based on IP1S are far from achieving the security level required for cryptographic applications.