Patarin proposed the dragon scheme, pointed out the insecurity of the dragon algorithm with one hidden monomial and suggested a candidate dragon signature algorithm with a complicated function. This paper presents an ...Patarin proposed the dragon scheme, pointed out the insecurity of the dragon algorithm with one hidden monomial and suggested a candidate dragon signature algorithm with a complicated function. This paper presents an algebraic method to attack the candidate dragon signature algorithm. The attack borrows the basic idea of the attack due to Kipnis and Shamir, and utilizes the underlying algebraic structure of the candidate dragon signature algorithm over the extension field to derive a way to enable the variable Y be viewed as a fixed value. The attack recovers the private keys efficiently when the parameters are n≤2s and D=[logq^d]≤3.展开更多
基金supported by the National Natural Science Foundation of China (60970119,60803149)the Youth Science and Technology Foundation of Xi’an University of Architecture and Technology (QN0831)the National Basic Research Program of China (2007CB311201)
文摘Patarin proposed the dragon scheme, pointed out the insecurity of the dragon algorithm with one hidden monomial and suggested a candidate dragon signature algorithm with a complicated function. This paper presents an algebraic method to attack the candidate dragon signature algorithm. The attack borrows the basic idea of the attack due to Kipnis and Shamir, and utilizes the underlying algebraic structure of the candidate dragon signature algorithm over the extension field to derive a way to enable the variable Y be viewed as a fixed value. The attack recovers the private keys efficiently when the parameters are n≤2s and D=[logq^d]≤3.
