Details:
Title  Weil sum for birthday attack in multivariate quadratic cryptosystem.  Author(s)  Donald K. Friesen, Tomohiro Harayama  Type  Article in Journal  Abstract  We propose a new cryptanalytic application of a number theoretic tool Weil sum to birthday attack against multivariate quadratic trapdoor function. This new customization of birthday attack is developed by evaluating the explicit Weil sum of the underlying univariate polynomial and the exact number of solutions of the associated bivariate equation. We designed and implemented a new algorithm for computing Weil sum values so that we could explicitly identify some class of weak DembowskiOstrom polynomials and their equivalent forms in multivariate quadratic trapdoor function. Our customized attack can be also regarded as an equation solving algorithm for the system of some special quadratic equations over finite fields, and it is fundamentally different from the Gröbner basis methods. Both theoretical observation and experiment show that the required computational complexity of the attack on these weak polynomial instances can be asymptotically less than the square root complexity of the common birthday attack by factor of as large as 2n/8 in terms of the extension degree n of . We also suggest a few open problems that any MQbased short signature scheme must explicitly take into account for the basic design principles.  Keywords  Weil sum,; birthday attack,; trapdoor oneway function,; multivariate quadratic cryptosystem  ISSN  18622976; 18622984/e 
URL 
http://www.degruyter.com/view/j/jmc.2007.1.issue1/jmc.2007.006/jmc.2007.006.xml 
Language  English  Journal  J. Math. Cryptol.  Volume  1  Number  1  Pages  79104  Publisher  De Gruyter, Berlin  Year  2007  Edition  0  Translation 
No  Refereed 
No 
