A new cryptanalytic application is proposed for a number theoretic tool Weil sum
to the birthday attack against multivariate quadratic trapdoor function. This new
customization of the 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. I designed and implemented new algorithms for computing
Weil sum values so that I could explicitly identify some class of weak Dembowski-
Ostrom polynomials and the equivalent forms in the multivariate quadratic trapdoor
function. This customized attack, also regarded as an equation solving algorithm for
the system of some special quadratic equations over finite fields, is fundamentally
different from the Grobner basis methods. The theoretical observations and experiments 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 a factor as large as 2^(n/8) in terms of the extension degree n of F2n. I also suggest a few open problems that any MQ-based short signature
scheme must explicitly take into account for the basic design principles.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/5938 |
| Date | 17 September 2007 |
| Creators | Harayama, Tomohiro |
| Contributors | Friesen, Donald K. |
| Publisher | Texas A&M University |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Dissertation, text |
| Format | 450566 bytes, electronic, application/pdf, born digital |
Page generated in 0.0018 seconds