## Cryptology ePrint Archive: Report 2006/075

ON THE WEIL SUM EVALUATION OF CENTRAL POLYNOMIAL IN MULTIVARIATE QUADRATIC CRYPTOSYSTEM

TOMOHIRO HARAYAMA

Abstract: A parity checking-styled Weil sum algorithm is presented for a general class of the univariate polynomials which fully characterize a system of $n$ polynomials in $n$ variables over $F_{2}$. The previously known proof methods of explicit Weil sum evaluation of Dembowski-Ostrom polynomials are extended to general case. The algorithm computes the absolute values of the Weil sums of the generic central polynomials in MQ problem.

Category / Keywords: public-key cryptography / MQ problem, MQ trapdoor function, multivariate quadratic cryptosystem, Dembwoski-Ostrom polynomial, central polynomial, character and Weil sum.