Multivariates polynomials for hashing

Jintai Ding; Bo Yin Yang

doi:10.1007/978-3-540-79499-8_28

Multivariates polynomials for hashing

Jintai Ding^*, Bo Yin Yang

^*Corresponding author for this work

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

14 Citations (Scopus)

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. We analyze some security properties and potential feasibility, where the compression functions are randomly chosen high-degree polynomials, and show that under some plausible assumptions, high-degree polynomials as compression functions has good properties. Next, we propose to improve on the efficiency of the system by using some specially designed polynomials generated by a small number of random parameters, where the security of the system would then relies on stronger assumptions, and we give empirical evidence for the validity of using such polynomials.

Original language	English
Title of host publication	Information Security and Cryptology - Third SKLOIS Conference, Inscrypt 2007, Revised Selected Papers
Pages	358-371
Number of pages	14
DOIs	https://doi.org/10.1007/978-3-540-79499-8_28
Publication status	Published - 2008
Externally published	Yes
Event	3rd SKLOIS Conference on Information Security and Cryptology, Inscrypt 2007 - Xining, China Duration: 31 Aug 2007 → 5 Sept 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4990 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	3rd SKLOIS Conference on Information Security and Cryptology, Inscrypt 2007
Country/Territory	China
City	Xining
Period	31/08/07 → 5/09/07

Keywords

Hash function
Multivariate polynomials
Sparse

Access to Document

10.1007/978-3-540-79499-8_28

Cite this

Ding, J., & Yang, B. Y. (2008). Multivariates polynomials for hashing. In Information Security and Cryptology - Third SKLOIS Conference, Inscrypt 2007, Revised Selected Papers (pp. 358-371). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4990 LNCS). https://doi.org/10.1007/978-3-540-79499-8_28

@inproceedings{546b6fe600e84e93ac7bedf388605a4d,

title = "Multivariates polynomials for hashing",

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. We analyze some security properties and potential feasibility, where the compression functions are randomly chosen high-degree polynomials, and show that under some plausible assumptions, high-degree polynomials as compression functions has good properties. Next, we propose to improve on the efficiency of the system by using some specially designed polynomials generated by a small number of random parameters, where the security of the system would then relies on stronger assumptions, and we give empirical evidence for the validity of using such polynomials.",

keywords = "Hash function, Multivariate polynomials, Sparse",

author = "Jintai Ding and Yang, {Bo Yin}",

year = "2008",

doi = "10.1007/978-3-540-79499-8_28",

language = "English",

isbn = "3540794980",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "358--371",

booktitle = "Information Security and Cryptology - Third SKLOIS Conference, Inscrypt 2007, Revised Selected Papers",

note = "3rd SKLOIS Conference on Information Security and Cryptology, Inscrypt 2007 ; Conference date: 31-08-2007 Through 05-09-2007",

}

Ding, J & Yang, BY 2008, Multivariates polynomials for hashing. in Information Security and Cryptology - Third SKLOIS Conference, Inscrypt 2007, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4990 LNCS, pp. 358-371, 3rd SKLOIS Conference on Information Security and Cryptology, Inscrypt 2007, Xining, China, 31/08/07. https://doi.org/10.1007/978-3-540-79499-8_28

Multivariates polynomials for hashing. / Ding, Jintai; Yang, Bo Yin.
Information Security and Cryptology - Third SKLOIS Conference, Inscrypt 2007, Revised Selected Papers. 2008. p. 358-371 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4990 LNCS).

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

TY - GEN

T1 - Multivariates polynomials for hashing

AU - Ding, Jintai

AU - Yang, Bo Yin

PY - 2008

Y1 - 2008

N2 - We propose the idea of building a secure hash using quadratic or higher degree multivariate polynomials over a finite field as the compression function. We analyze some security properties and potential feasibility, where the compression functions are randomly chosen high-degree polynomials, and show that under some plausible assumptions, high-degree polynomials as compression functions has good properties. Next, we propose to improve on the efficiency of the system by using some specially designed polynomials generated by a small number of random parameters, where the security of the system would then relies on stronger assumptions, and we give empirical evidence for the validity of using such polynomials.

AB - We propose the idea of building a secure hash using quadratic or higher degree multivariate polynomials over a finite field as the compression function. We analyze some security properties and potential feasibility, where the compression functions are randomly chosen high-degree polynomials, and show that under some plausible assumptions, high-degree polynomials as compression functions has good properties. Next, we propose to improve on the efficiency of the system by using some specially designed polynomials generated by a small number of random parameters, where the security of the system would then relies on stronger assumptions, and we give empirical evidence for the validity of using such polynomials.

KW - Hash function

KW - Multivariate polynomials

KW - Sparse

UR - http://www.scopus.com/inward/record.url?scp=54249150553&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-79499-8_28

DO - 10.1007/978-3-540-79499-8_28

M3 - Conference Proceeding

AN - SCOPUS:54249150553

SN - 3540794980

SN - 9783540794981

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 358

EP - 371

BT - Information Security and Cryptology - Third SKLOIS Conference, Inscrypt 2007, Revised Selected Papers

T2 - 3rd SKLOIS Conference on Information Security and Cryptology, Inscrypt 2007

Y2 - 31 August 2007 through 5 September 2007

ER -

Multivariates polynomials for hashing

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this