A method of Weil sum in multivariate quadratic cryptosystem

Simple item page
dc.contributorFriesen, Donald K.
dc.creatorHarayama, Tomohiro
dc.date.accessioned2007-09-17T19:38:47Z
dc.date.accessioned2017-04-07T19:53:32Z
dc.date.available2007-09-17T19:38:47Z
dc.date.available2017-04-07T19:53:32Z
dc.date.created2003-05
dc.date.issued2007-09-17
dc.description.abstractA 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.
dc.identifier.urihttp://hdl.handle.net/1969.1/5938
dc.language.isoen_US
dc.publisherTexas A&M University
dc.subjectWeil sum
dc.subjectbirthday attack
dc.subjectMQ trapdoor
dc.subjectmultivariate quadratic cryptosystem
dc.titleA method of Weil sum in multivariate quadratic cryptosystem
dc.typeBook
dc.typeThesis

Files

Collections

Texas A&M University at College Station