**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.

**Date: **received 21 Feb 2006

**Contact author: **harayama at tamu edu

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Note: **This is a resubmission of the previous submission xxxx/129. Please use this paper instead of the previous paper. I slightly modified
the abstract. I am sorry for this incovenience.
Sincerely,
Tomohiro Harayama

**Version: **20060224:224112 (All versions of this report)

**Short URL: **ia.cr/2006/075

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]