Polynomial Equivalence Problems: Algorithmic and Theoretical Aspects

详细信息    查看全文

• 作者：Jean-Charles Faug¨¨re ; Ludovic Perret
• 关键词：Public ; Key Cryptography ; Cryptanalysis ; Isomorphism of Polynomials (IP) ; Gr?bner bases ; F5 algorithm
• 刊名：Lecture Notes in Computer Science
• 出版年：2006
• 出版时间：2006
• 年：2006
• 卷：4004
• 期：1
• 页码：pp.30-47
• 全文大小：569 KB

文摘

The Isomorphism of Polynomials (IP) [28], which is the main concern of this paper, originally corresponds to the problem of recovering the secret key of a C* scheme [26]. Besides, the security of various other schemes (signature, authentication [28], traitor tracing [5], ...) also depends on the practical hardness of IP. Due to its numerous applications, the Isomorphism of Polynomials is thus one of the most fundamental problems in multivariate cryptography. In this paper, we address two complementary aspects of IP, namely its theoretical and practical difficulty. We present an upper bound on the theoretical complexity of “IP-like” problems, i.e. a problem consisting in recovering a particular transformation between two sets of multivariate polynomials. We prove that these problems are not NP-Hard (provided that the polynomial hierarchy does not collapse). Concerning the practical aspect, we present a new algorithm for solving IP. In a nutshell, the idea is to generate a suitable algebraic system of equations whose zeroes correspond to a solution of IP. From a practical point of view, we employed a fast Gr?bner basis algorithm, namely F₅ [17], for solving this system. This approach is efficient in practice and obliges to modify the current security criteria for IP. We have indeed broken several challenges proposed in literature [28, 29, 5]. For instance, we solved a challenge proposed by O. Billet and H. Gilbert at Asiacrypt’03 [5] in less than one second.