Cryptology ePrint Archive: Report 2007/137

Multivariates Polynomials for Hashing

Jintai Ding and Bo-yin Yang

Abstract: We propose the idea of building a secure hash using quadratic or higher degree multivariate polynomials over a finite field as the compression function, whose security relies on simple hard questions. We analyze some security properties and potential feasibility, where the compression functions are randomly chosen high-degree polynomials. Next, we propose to improve on the efficiency of the system by using some specially designed polynomials using composition of maps and certain sparsity property, where the security of the system would then relies on stronger assumptions.

Category / Keywords: foundations /

Date: received 17 Apr 2007

Contact author: ding at math uc edu

Available format(s): PDF | BibTeX Citation

Version: 20070418:124147 (All versions of this report)

Short URL: ia.cr/2007/137

Discussion forum: Show discussion | Start new discussion