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.

Date: received 21 Feb 2006

Contact author: harayama at tamu edu

Available formats: 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)

Discussion forum: Show discussion | Start new discussion